Solving Logic Problems
I've identified about half a dozen techniques used in Logic
Problem Solver program to build truth tables from facts and rules and thus
solve the problem. Truth tables are built for each combination of
variables taken in pairs with the first encountered variable values represented
as rows and the second variable values as columns. Each row-column intersection,
a cell, initially contains a "U" (for Unknown. The
processing described here tries to replace each 'U" with a "T"
(True) or "F" (False).
Before starting the search, user supplied Order and Separation
rules are used to generate additional Facts and If Rules.
For example: "John is older than Mary" generates facts
"John is not youngest" and "Mary is not oldest"
Other user supplied facts are next used to fill in truth
Finally, a processing loop runs until a complete pass through the
loop produces no changes. Within the loop, several techniques are used to
fill in truth table cells. We'll use sample statements to illustrate the
- Positive Identity: If John has red hair and the 14 year-old
has red hair, then John is 14 years old.
- Negative Identity: If John has red hair and the 14 year-old
does not have red hair, then John is not 14 years old.
- Uniqueness: If John has red hair then no one else has red hair
and John does not have any other hair color.
- Only Choice: There is probably a more formal name for this, but if
John's hair must be red, brown or blonde, and it is not red or brown, then
"John must have blonde hair".
- Modus Ponens: Given a "If" rule "If John has
red hair then Mary is the youngest " and the fact "John has red
hair", we can conclude that "Mary is the youngest" and place a
"T" in the appropiate cell in a truth table.
- Modus Tollens: Given a "If" rule "If John
has red hair then Mary is the youngest " and the fact "Mary is
not the youngest", we can conclude that "John does not have red
hair" and put and "F" in the corresponding cell in a
- Reductio Ad Absurdum: This is the method of
contradiction. If we assume that an unknown fact is true and that causes
a contradiction, the assumption
must be incorrect. Contradictions are recognized when we try to replace a "T" with an "F"
or an "F" with a 'T" in a truth table cell while processing all
of the conclusions that would follow from our assumption. Similarly we can assume that an unknown fact is
false and play the same game. As currently implemented, this technique
is only used if there are only 2 unresolved truth values in a column or row
and applying Reductio A. produces a contradiction in only one one of them, then the
other must be the case.
Back to Logic Problem Solver