Are we done yet?

Exercise 2.3.3.1

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?

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!

Exercise 2.3.3.2

Using a truth table, show the validity of conjunctive Redundancy: φ ∧ (¬φ ∨ ψ) ≡ φ ∧ ψ 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.