University of Waterloo
PMATH 330
1. (a) Let F = P→(¬Q ∧ R), G = (Q→P)↔R and H = Q↔¬R. The following is a derivation of the valid argument F, G |= H. Provide justification on each line. Solution: We indicate which rule is used on each line by writing V for a Basic Validity Rule and TE for a Basic Truth-Equivalence. 1. {¬P, Q→P, R, Q} |= Q Premise (V1) 2. {¬P,
...[Show More]
1. (a) Let F = P→(¬Q ∧ R), G = (Q→P)↔R and H = Q↔¬R. The following is a derivation of the valid argument F, G |= H. Provide justification on each line. Solution: We indicate which rule is used on each line by writing V for a Basic Validity Rule and TE for a Basic Truth-Equivalence. 1. {¬P, Q→P, R, Q} |= Q Premise (V1) 2. {¬P, Q→P, R, Q} |= Q→P Premise (V1) 3. {¬P, Q→P, R, Q} |= P Modus Ponens (V23) on lines 1,2 4. {¬P, Q→P, R, Q} |= ¬P Premise (V1) 5. {¬P, Q→P, R, Q} |= ¬R Contradiction (V5) on 3,4 6. {¬P, Q→P, R} |= Q→¬R Deduction (V21) on 5 7. {¬P, Q→P, R} |= R Premise (V1) 8. {¬P, Q→P, R} |= ¬¬R Truth-Equivalence (V35) using Double Negation (TE2) on 7 9. {¬P, Q→P, R} |= ¬R→Q Implication (V19) on 8 10. {¬P, Q→P, R} |= H If and Only If (V28) on 6,9 11. {¬P, ¬(Q→P), ¬R} |= ¬(Q→P) Premise (V1) 12. {¬P, ¬(Q→P), ¬R} |= Q ∧ ¬P Truth-Equivalence (V35) using Implication (TE28) on 11 13. {¬P, ¬(Q→P), ¬R} |= Q Conjunction (V9) on 12 14. {¬P, ¬(Q→P), ¬R} |= ¬R Premise (V1) 15. {¬P, ¬(Q→P), ¬R} |= H If and Only If (V26) on 13,14 16. {¬P, G} |= H If and Only If (V33) on 10,15 17. {¬Q ∧ R, G} |= ¬Q ∧ R Premise (V1) 18. {¬Q ∧ R, G} |= ¬Q Conjunction (V9) on 17 19. {¬Q ∧ R, G} |= R Conjunction (V10) on 17 20. {¬Q ∧ R, G} |= ¬¬R Truth-Equivalence (V35) using Double-Negation (TE2) on 20 21. {¬Q ∧ R, G} |= H If and Only If (V27) on 18,20 22. {F, G} |= H Implication (V25) on 16,21 (b) The following is a restricted derivation of the formula G from the premise set {¬F ∧ F}. Provide justification on each line. Solution: 1. ¬F ∧ F Premise 2. (¬F ∧ F)→¬(¬F→¬F) Axiom 4 3. ¬(¬F→¬F) Modus Ponens on lines 1,2 4. ¬F→((¬F→¬F)→¬F) Axiom 1 5. ¬F→(¬F→¬F) Axiom 1 6. ¬F→((¬F→¬F)→¬F) → (¬F→(¬F→ ¬F))→(¬F→¬F) Axiom 3 7. (¬F→(¬F→¬F))→(¬F→¬F) Modus Ponens on 4, 6 8. ¬F→¬F Modus Ponens on 5,7 9. ¬(¬F→¬F)→(¬G→¬(¬F→¬F)) Axiom 1 10. (¬G→¬(¬F→¬F))→((¬F→¬F)→G) Axiom 2 11. ¬G→¬(¬F→¬F) Modus Ponens on 3,9 12. (¬F→¬F)→G Modus Ponens on 10,11 13. G Modus Ponens on 8,12 2. Make a derivation, with justification on each line, for each of the following valid arguments. (a) P ∨ Q , P↔R , Q→(R ∨ P) |= P ∧ (Q→R) Solution: Here is one possible derivation 1. {P ∨ Q , P↔R , Q→(R ∨ P), ¬P} |= P ∨ Q Premise (V1) 2. {P ∨ Q , P↔R , Q→(R ∨ P), ¬P} |= ¬P Premise (V1) 3. {P ∨ Q , P↔R , Q→(R ∨ P), ¬P} |= Q Disjunction (V16) on 1,2 4. {P ∨ Q , P↔R , Q→(R ∨ P), ¬P} |= Q→(R ∨ P) Premise (V1) 5. {P ∨ Q , P↔R , Q→(R ∨ P), ¬P} |= R ∨ P Modus Ponens (V23) on 3,4 6. {P ∨ Q , P↔R , Q→(R ∨ P), ¬P} |= R Disjunction (V17) on 2,5 7. {P ∨ Q , P↔R , Q→(R ∨ P), ¬P} |= P↔R Premise (V1) 8. {P ∨ Q , P↔R , Q→(R ∨ P), ¬P} |= P If and Only If (V30) on 6,7 9. {P ∨ Q , P↔R , Q→(R ∨ P)} |= P Contradiction (V5) on 2,8 10. {P ∨ Q , P↔R , Q→(R ∨ P)} |= P↔R Premise (V1) 11. {P ∨ Q , P↔R , Q→(R ∨ P)} |= R If and Only If (V29) on 9,10 12. {P ∨ Q , P↔R , Q→(R ∨ P)} |= Q→R Implica
[Show Less]