Propositional Logic

Proof Construction:  Problem Set # 2

Answer Key:  Remember, there are other ways to construct proofs for these problems.  I just give one way here.

Problem # 1

 1. (S · U) → P 2. (U → P) → W 3. S 4. S → (U → P) 5. U → P 6. W ∴ W 1 exp 3,4 MP 2,5 MP

Problem # 2

 1. A ▼ (B · C) 2. (A ▼ B) → D 3. (A ▼ B) · (A ▼ C) 4. A ▼ B 5. D 6. D ▼ C 7. C ▼ D ∴ C ▼ D 1 dist 3 simp 2,4 MP 5 add 6 com

Problem # 3

 1. G → (B → C) 2. G · ~C 3. G 4. ~C 5. B → C 6. ~B ∴ ~B 2 com, simp 2 simp 1,3 MP 4,5 MT

Problem # 4

 1. P → S 2. ~P ▼ S 3. (~P ▼ S) ▼ ~H 4. ~P ▼ (S ▼ ~H) 5. ~P ▼ (~H ▼ S) 6. P → (~H ▼ S) 7. P → (H → S) ∴ P → (H → S) 1 MI 2 add 3 assn 4 com 5 MI 6 MI

Problem # 5

 1. (F → R) · (L → U) 2. (U · R) → C 3. ~C 4. ~(U · R) 5. ~U ▼ ~R 6. ~R ▼ ~U 7. ~F ▼ ~L ∴ ~F ▼ ~L 2, 3 MT 4 DeM 5 com 1, 6 DD

Problem # 6

 1. (~A ▼ B) · (A → C) 2. B → (C → E) 3. ~A ▼ B 4. A → B 5. A → (C → E) 6. (A · C) → E 7. (C · A) → E 8. C → (A → E) 9. A → C 10. A → (A → E) 11. (A · A) → E 12. A → E ∴ A → E 1 simp 3 MI 4, 2 HS 5 exp 6 com 7 exp 1 com, simp 9, 8 HS 10 exp 11 Red

Problem # 7

 1. A → (B · C) 2. (B ▼ C) → I 3. ~A ▼ (B · C) 4. (~A ▼ B) · (~A ▼ C) 5. ~A ▼ B 6. A → B 7. ~I → ~(B ▼ C) 8. I ▼ ~(B ▼ C) 9. I ▼ (~B · ~C) 10. (I ▼ ~B) · (I ▼ ~C) 11. I ▼ ~B 12. ~B ▼ I 13. B → I 14. A → I ∴ A → I 1 MI 3 dist 4 simp 5 MI 2 contra 7 MI 8 DeM 9 dist 10 simp 11 com 12 MI 6, 13 HS

Problem # 8

 1. [(E · S) → P] · [(E · ~S) → ~P] 2. (E · S) → P 3. (E · ~S) → ~P 4. E → (S → P) 5. E → (~S → ~P) 6. ~E ▼ (S → P) 7. ~E ▼ (~S → ~P) 8. [~E ▼ (S → P)] · [~E ▼ (~S → ~P)] 9. ~E ▼ [(S → P) · (~S → ~P)] 10. ~E ▼ [(S → P) · (P → S)] 11. ~E ▼ (S « P) 12. E → (S « P) 13. E → [(S · P) ▼ (~S · ~P)] ∴ E → [(S · P) ▼ (~S · ~P)] 1 simp 1 com, simp 2 exp 3 exp 4 MI 5 MI 6,7 conj 8 dist 9 contra 10 ME 11 MI 12 ME

Problem # 9

 1. A → (B ▼ C) 2. B → C 3. ~A ▼ (B ▼ C) 4. ~A ▼ (C ▼ B) 5. (~A ▼ C) ▼ B 6. ~(~A ▼ C) ▼ B 7. ~(~A ▼ C) ▼ C 8. (~A ▼ C) ▼ C 9. ~A ▼ (C ▼ C) 10. ~A ▼ C 11. A → C ∴ A → C 1 MI 3 com 4 assn 5 MI 6,2 HS 7 MI 8 assn 9 Red 10 MI

Problem # 10

 1. (A ▼ B) → (C · E) 2. ~(A ▼ B) ▼ (C · E) 3. [~(A ▼ B) ▼ C] · [~(A ▼ B) ▼ E] 4. ~(A ▼ B) ▼ C 5. (~A · ~B) ▼ C 6. C ▼ (~A · ~B) 7. (C ▼ ~A) · (C ▼ ~B) 8. C ▼ ~A 9. ~C → ~A 10. A → C ∴ A → C 1 MI 2 dist 3 simp 4 DeM 5 com 6 dist 7 simp 8 MI 9 contra

Problem # 11

 1. (P ▼ W) → (R · A) 2. (R → J) · ~J 3. R → J 4. ~J 5. ~R 6. ~R ▼ ~A 7. ~(R · A) 8. ~(P ▼ W) 9. ~P · ~W 10. ~P ∴ ~P 2 simp 2 simp 3,4 MT 5 add 6 DeM 1,7 MT 8 DeM 9 simp

Problem  # 12

 1. P → (C → N) 2. (N · R) → E 3. T → (R · ~E) 4. (P · C) → N 5. N → (R → E) 6. ~(R · ~E) → ~T 7. (~R ▼ E) → ~T 8. (R → E) → ~T 9. N → ~T 10. (P · C) → ~T 11. P → (C → ~T) ∴ P → (C → ~T) 1 exp 2 exp 3 contra 6 DeM 7 MI 5,8 HS 4,9 HS 10 exp

Problem # 13

 1. T ▼ (I · O) 2. T → O 3. (T ▼ I) · (T ▼ O) 4. T ▼ O 5. O ▼ T 6. ~T ▼ O 7. ~O → T 8. T → O 9. ~O → O 10. O ▼ O 11. O ∴ O 1 dist 3 simp 4 com 2 MI 5 MI 6 MI 7,8 HS 9 MI 10 Red

Problem # 14

 1. R ▼ N 2. R → G 3. G → ~S 4. (N → B) · (B ▼ →~S) 5. S ▼ C 6. N → B 7. B → ~S 8. N → ~S 9. R → ~S 10. (R → ~S) · (N → ~S) 11. ~S ▼ ~S 12. ~S 13. C ∴ C 4 simp 4 com, simp 6,7 HS 2,3 HS 9,8 conj 1,10 CD 11 Red 5,12 DS

Problem # 15

 1. P → S 2. S → ~(B · D) 3. (~B → T) · ~T 4. D 5. ~B → T 6. ~T 7. B 8. B · D 9. ~S 10. ~P ∴ ~P 3 simp 3 simp 5,6 MT 7,4 conj 8,2 MT 9,1 MT

Problem # 16

 1. (S → E) · (H → L) 2. (E ▼ L) → C 3. ~C 4. ~(E ▼ L) 5. ~E · ~L 6. ~E 7. ~L 8. S → E 9. H → L 10. ~S 11. ~H 12. ~S · ~H 13. ~(S ▼ H) ∴ ~(S ▼ H) 2,3 MT 4 DeM 5 simp 5 simp 1 simp 1 simp 6,8 MT 7,9 MT 10,11 conj 12 DeM

Problem # 17

 1. (T → E) · (A → L) 2. (T → E) 3. ~T ▼ E 4. (~T ▼ E) ▼ ~A 5. ~T ▼ (E ▼ ~A) 6. ~T ▼ (~A ▼ E) 7. A → L 8. ~A ▼ L 9. (~A ▼ L) ▼ ~T 10. ~T ▼ (~A ▼ L) 11. [~T ▼ (~A ▼ E)] · [~T ▼ (~A ▼ L)] 12. ~T ▼ [(~A ▼ E) · (~A ▼ L)] 13. ~T ▼ [~A ▼ (E · L)] 14. ~T ▼ [A → (E · L)] 15. T → [A → (E · L)] 16. (T · A) → (E · L) ∴ (T · A) → (E · L) 1 simp 2 MI 3 add 4 assn 5 com 1 simp 7 MI 8 add 9 com 6,10 conj 11 dist 12 dist 13 MI 14 MI 15 exp

Problem # 18

 1. E → S 2. E → (S → N) 3. S → (N → F) 4. (E · S) → N 5. (S · E) → N 6. S → (E → N) 7. E → (E → N) 8. (E · E) → N 9. E → N 10. (S · N) → F 11. (N · S) → F 12. N → (S → F) 13. E → (S → F) 14. (E · S) → F 15. (S · E) → F 16. S → (E → F) 17. E → (E → F) 18. (E · E) → F 19. E → F ∴ E → F 2 exp 4 com 5 exp 1,6 HS 7 exp 8 Red 3 exp 10 com 11 exp 9,12 HS 13 exp 14 com 15 exp 1,16 HS 17 exp 19 Red

Problem # 19

 1. A → (B ▼ C) 2. E → (C ▼ P) 3. ~C 4. ~E ▼ (C ▼ P) 5. (C ▼ P) ▼ ~E 6. C ▼ (P ▼ ~E) 7. P ▼ ~E 8. ~E ▼ P 9. (~E ▼ P) ▼ B 10. ~E ▼ (P ▼ B) 11. ~E ▼ (B ▼ P) 12. (B ▼ P) ▼ ~E 13. ~A ▼ (B ▼ C) 14. (~A ▼ B) ▼ C 15. ~A ▼ B 16. (~A ▼ B) ▼ P 17. ~A ▼ (B ▼ P) 18. (B ▼ P) ▼ ~A 19. [(B ▼ P) ▼ ~E] · [(B ▼ P) ▼ ~A] 20. (B ▼ P) ▼ (~E · ~A) 21. (B ▼ P) ▼ ~(E ▼ A) 22. (B ▼ P) ▼ ~(A ▼ E) 23. ~(B ▼ P) → ~(A ▼ E) ∴ ~(B ▼ P) → ~(A ▼ E) 2 MI 4 com 5 assn 3,6 DS 7 com 8 add 9 assn 10 com 11 com 1 MI 3 assn 3,14 DS 15 add 16 assn 17 com 12,18 conj 19 dist 20 DeM 21 com 22 MI

Problem # 20

 1. (A ▼ B) ▼ [(C ▼ E) → (~P · V)] 2. (~P ▼ ~N) → U 3. ~(P · N) → U 4. (P · N) ▼ U 5. U ▼ (P · N) 6. (U ▼ P) · (U ▼ N) 7. U ▼ P 8. ~U → P 9. [(A ▼ B) · (C ▼ E)] → (~P · V) 10. ~[(A ▼ B) · (C ▼ E)] ▼ (~P · V) 11. [~(A ▼ B) ▼ ~(C ▼ E)] ▼ (~P · V) 12. [(~A · ~B) ▼ (~C · ~E)] ▼ (~P · V) 13. [(~A · ~B) ▼ (~C · ~E)] ▼ ~P] · [(~A · ~B) ▼ (~C · ~E)] ▼ V] 14. [(~A · ~B) ▼ (~C · ~E)] ▼ ~P 15. (~A · ~B) ▼ [(~C · ~E) ▼ ~P] 16. (~A · ~B) ▼ [~P ▼ (~C · ~E)] 17. [(~A · ~B) ▼ ~P] ▼ (~C · ~E) 18. [(~A · ~B) ▼ ~P] ▼ ~C] · [(~A · ~B) ▼ ~P] ▼ ~E] 19. [(~A · ~B) ▼ ~P] ▼ ~C 20. [~P ▼ (~A · ~B)] ▼ ~C 21. ~P ▼ [(~A · ~B) ▼ ~C] 22. P → [(~A · ~B) ▼ ~C] 23. ~U → [(~A · ~B) ▼ ~C] 24. U ▼ [(~A · ~B) ▼ ~C] 25. U ▼ [~C ▼ (~A · ~B)] 26. U ▼ [(~C ▼ ~A) · (~C ▼ ~B)] 27. [U ▼ (~C ▼ ~A)] · [U ▼ (~C ▼ ~B)] 28. U ▼ (~C ▼ ~A) 29. U ▼ (~A ▼ ~C) 30. ~U → (~A ▼ ~C) 31. ~U → ~(A · C) 32. (A · C) → U 33. A → (C → U) /∴ A → (C → U) 2 DeM 3 MI 4 com 5 dist 6 simp 7 MI 1 exp 9 MI 10 DeM 11 DeM, DeM 12 dist 13 simp 14 assn 15 com 16 assn 17 dist 18 simp 19 com 20 assn 21 MI 7,22 HS 23 MI 24 com 25 dist 26 dist 27 simp 28 com 29 MI 30 DeM 31 contra 32 exp

Problem # 21

 1. (S ▼ ~S) → A 2. ~(S ▼ ~S) ▼ A 3. (~S · S) ▼ A 4. A ▼ (~S · S) 5. (A ▼ ~S) · (A ▼ S) 6. A ▼ ~S 7. A ▼ S 8. ~S ▼ A 9. S → A 10. ~A → S 11. ~A → A 12. A ▼ A 13. A ∴ A 1 MI 2 DeM 3 com 4 dist 5 simp 5 simp 6 com 8 MI 7 MI 10,9 HS 11 MI 12 Red