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