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 tables.
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 major ones.
 | 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 truth table. |
| 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. |