m12076 Propositional Logic: soundness and completeness 1.10 2004/07/01 12:41:02 GMT-5 2009/03/09 14:32:50.182 GMT-5 Ian Barland Ian Barland ibarland@radford.edu John Greiner John Greiner greiner@cs.rice.edu Phokion Kolaitis Phokion Kolaitis kolaitis@cse.ucsc.edu Moshe Vardi Moshe Vardi vardi@cs.rice.edu Matthias Felleisen Matthias Felleisen matthias@ccs.neu.edu Ian Barland Ian Barland ibarland@radford.edu John Greiner John Greiner greiner@cs.rice.edu Ian Barland Ian Barland ibarland@radford.edu John Greiner John Greiner greiner@cs.rice.edu Phokion Kolaitis Phokion Kolaitis kolaitis@cse.ucsc.edu Moshe Vardi Moshe Vardi vardi@cs.rice.edu Matthias Felleisen Matthias Felleisen matthias@ccs.neu.edu Mathematics and Statistics The soundness and completeness of a system. en

We have shown procedures, using both truth tables and equivalences, for solving two different logic problems: Equivalence: Show whether or not two WFFs φ and ψ are equivalent (the same under any truth assignment); Tautology: Show whether or not a given WFF φ is a tautology (true under all truth assignments). Which of these two logic problems seems harder than the other? That is, suppose you have a friend who can solve any Equivalence problem efficiently. But you want to open a business which will solve any Tautology problem efficiently. Can you open your business and, by subcontracting out specific Equivalence problems to your friend, really solve any Tautology problem brought to you? This question is sometimes phrased as Does Tautology reduce to Equivalence? Or, does it work the other way: does Equivalence reduce to Tautology? We can indeed reduce the question of Tautology to the question of Equivalence: if somebody asks you whether φ is true, you can just turn around and ask your friend whether the following two formulas are equivalent: φ, and true. Your friend's answer for this variant question will be your answer to your customer's question about φ. Thus, the Tautology problem isn't particularly harder than the Equivalence problem. But also, Equivalence can be reduced to Tautology: if somebody asks you whether φ is equivalent to ψ, you can construct a new formula φ ψ ψ φ . This formula is true exactly when φ and ψ are equivalent. So, you ask your friend whether this bigger formula is a tautology, and you then have your answer to whether the two original formulas were equivalent. Thus, the Equivalence problem isn't particularly harder than the Tautology problem! Given these two facts (that each problem reduces to the other), we realize that really they are essentially the same problem, in disguise. But we have a more fundamental question to ask, about the method of using Boolean algebra (propositional equivalences) to prove something: Where does the initial list of allowable equivalences come from, and how do we know they're valid? The answer is easy — each equivalence can be verified by a truth table! Using a truth table, show the validity of conjunctive Redundancy: φ φ ψ φ ψ Compare the last two columns in the following: a b a b a a b a b This is called soundness of Boolean algebra: If, using our propositional equivalence rules, we derive that φ and ψ are equivalent, then truly they are equivalent. (Whew!) By the way, there is one subtle point: our truth table tells us that a b and b a are equivalent. But then suddenly we generalize this to saying that for any formulas φ and ψ, φ ψ and ψ φ are also equivalent. What lets us justify that step? It's because any given formula will be either true or false, so we can reduce the entire formula to a single true/false proposition. Is Boolean algebra enough? Does our list of allowable propositional equivalences include everything you'll need? That is, could I have asked as a homework problem to show some two formulas equivalent (using Boolean algebra), and even though they really are equivalent, there aren't enough rules to on our list to let you finish the homework? Hmm, good question! The property we desire here is called the completeness of Boolean algebra: any equivalence which is true can be proved. It turns out that, given any two formulas which really are equivalent, Boolean algebra is indeed sufficiently powerful to show that. Put both formulas into CNF (or, DNF); if the truth tables are equal then the CNF formulas will be equal. (Well, there are a few details to take care of: you have to order the clauses alphabetically, eliminate any duplicate clauses, and include all variables in each clause. This might be tedious, but not difficult.) Thus, Boolean algebra is complete, since (we state without proof) this procedure can always be carried out. The concepts of soundness and completeness can be generalized to any system. soundness If the system (claims to) prove something is true, it really is true. completeness If something really is true, the system is capable of proving it.