Math 314 Fall 2011 Homework IDr. HolmesSeptember 4, 2011This assignment is due at class time on Wednesday, September 14th.In connection with problems 1-3, I will shortly put up more notes abouttruth table issues and the neither/nor excursion.It is important to remember that in the proofs in problems 4,5,6 (proofs bynatural deduction) you are not allowed to use rules involving substitutionsof equivalent expressions. You may not use deMorgan’s laws, replace animplication explicitly with its contrapositive, replace A → B with ¬A ∨ B,replace A ∨ B with ¬A → B or indeed make any move of this kind. Youneed to use the exact strategies listed in the notes. This does not mean thatsubstitutions of equivalent expressions are not a legitimate logical move; theyare fine. But there is a particular style I am encouraging here.1. Notice that the operators ∧ and ∨ are associative, in the sense that(A ∧ B) ∧ C is logically equivalent to A ∧ (B ∧ C) and (A ∨ B) ∨ C islogically equivalent to A ∨ (B ∨ C) .Prove using a truth table that P → (Q → R) is not logically equivalentto (P → Q) → R. State a specific assignment of truth values for P, Q, Runder which these two statements have different truth values.Prove using a truth table that P ↔ (Q ↔ R) is logically equivalent to(P ↔ Q) ↔ R.Since ↔ is associative, we can write P ↔ Q ↔ R without parentheses.Briefly state under what conditions this statement is true (they mightbe surprising, but you can read them off the truth table).Extra credit: Give a brief explanation of the conditions under whichP1↔ P2↔ . . . ↔ Pnis true for different values of n. The meaning isnot “all the Pi’s are equivalent”.12. Write an expression for something for which a truth table is given.Then do the same thing for the biconditional.Write an expression using just ¬, ∨, ∧ and letters for the operationrepresented by this truth table:P Q R ???T T T FT T F TT F T FT F F FF T T TF T F FF F T TF F F FWrite an expression using just ¬, ∨, ∧ and letters equivalent to P ↔ Q.3. Give expressions for P → Q and P ↔ Q using the neither/nor operator| and letters only.Define P ↓ Q as ¬(P ∧ Q). This operator is also called NAND. Giveexpressions for ¬P , P ∧ Q and P ∨ Q in terms of the ↓ operator andletters only. This shows that any operation defined by a truth tablecan be expressed in terms of just ↓ as well as just |.4. Prove ¬(A ∨ B) ↔ (¬A ∧ ¬ B) (the deMorgan law not proved in thenotes), using natural deduction.5. Prove ((A ∧ B) → C) ↔ ((A → C) ∨ (B → C)), using natural deduc-tion.6. Prove the theorem (A ∨ B) ↔ (¬A → B) using natural deduction.First, do this using the full set of rules we have available. This shouldbe straightforward.Second, do it using any rule you like for implication or negation, butonly using the positive rules (proof by cases and weakening) for dis-junction. This can be done but is much trickier. It shows that thepositive rules for disjunction actually are enough for all proofs (thoughthe others are much more