Given a predicate calculus sentence, along with the number of times that each predicate literal and its negative appear in the search space, rearrange the sentence such that it's logically equivalent, but more likely faster to evaluate for truth.
p OR q
If 'p' occurs 2% of the time, and 'q' occurs 90% of the time, it'd be quicker to test "q OR p" over 1,000 cases, instead of using the original. (we're assuming the cost here is looking up the literal values, not doing the AND/OR)
So, I guess it's not too hard....
In a series of disjunctions, move the highest probability disjunct to the beginning.
In a series of conjunctions, move the lowest probability conjunct to the beginning.
For clauses more complex than a literal or negative literal, I could fake the probability ... for a conjunction, just multiple the probabilities. In a closed search space, that's nowhere close to the truth, but it'd make a good heuristic. After all, it doesn't matter what weightings we use, really, as long as all transformations keep the logical equivalence of the original sentence.
I'm probably describing this entirely wrong. I want to go dig into storage and get out some of my intro CS books so I could at least describe things using the right terminology.