Propositional Logic

Proof Construction:  Problem Set # 1

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

 

Problem # 1

1. C
2. C ~D
3. ~D C
4. D C
D C
1 add
2 com
3 mi

Problem # 2
1. E (F G)
2. (E F) G
3. (F E) G
4. F (E G)
F (E G)
1 exp
2 com
3 exp

Problem # 3
1. H (I J)
2. ~H (I J)
3. (~H I) (~H J)
4. ~H I
5. H I
H I
1 mi
2 dist
3 simp
4 mi

Problem # 4
1. N O
2. ~N O
3. (~N O) ~P
4. ~N (O ~P)
5. ~N (~P O)
6. (~N ~P) O
7. ~(N P) O
8. (N P) O
(N P) O
1 mi
2 add
3 ass
4 com
5 ass
6 DeM
7 mi

Problem # 5
1. (Q R) S
2. ~(Q R) S
3. (~Q ~R) S
4. S (~Q ~R)
5. (S ~Q) (S ~R)
6. S ~Q
7. ~Q S
8. Q S
Q S
1 mi
2 DeM
3 com
4 dist
5 simp
6 com
7 mi

Problem # 6
1. T ~(U V)
2. T ~(~U V)
3. T (U ~V)
4. ~T (U ~V)
5. (~T U) (~T ~V)
6. ~T U
7. T U
T U
1 mi
2 DeM
3 mi
4 dist
5 simp
6 mi

Problem # 7
1. W (X ~Y)
2. ~W (X ~Y)
3. (~W X) (~W ~Y)
4. ~W ~Y
5. (~W ~Y) X
6. ~(W Y) X
7. (W Y) X
8. (W (Y X)
W (Y X)
1 mi
2 dist
3 com, simp
4 add
5 DeM
6 mi
7 exp

Problem # 8
1. E F
2. E G
3. ~E F
4. ~E G
5. (~E F) (~E G)
6. ~E (F G)
7. E (F G)

E (F G)
1 mi
2 mi
3,4 conj
5 dist
6 mi

Problem # 9
1. H (I J)
2. ~I
3. ~H (I J)
4. ~H (J I)
5. (~H J) I
6. ~H J
7. H J

H J
1 mi
3 com
4 ass
2,5 DS
6 mi

Problem # 10
1. (K L) ~(M N)
2. (~M ~N) (O P)
3. (O P) (Q R)
4. (K L) (~M ~N)
5. (K L) (O P)
6. (K L) (Q R)
7. (L K) (R Q)


(L K) (R Q)
1 DeM
4,2 HS
5,3 HS
6 com, com

Problem # 11
1. S T
2. S T
3. ~T ~S
4. ~S T
5. ~T T
6. T T
7. T

T
1 trans
2 mi
3,4 HS
5 mi
6 taut

Problem # 12
1. A (B C)
2. C (D E)
3. ~C (D E)
4. (~C D) (~C E)
5. ~C D
6. C D
7. (A B) C
8. (A B) D
9. A (B D)

A (B D)
2 mi
3 dist
4 simp
5 mi
1 exp
7,6 HS
8 exp

Problem # 13
1. E F
2. G F
3. ~E F
4. ~G F
5. (~E F) (~G F)
6. (F ~E) (F ~G)
7. F (~E ~G)
8. (~E ~G) F
9. ~(E G) F
10. (E G) F

(E G) F
1 mi
2 mi
3,4 conj
5 com, com
6 dist
7 com
8 DeM
9 mi

Problem # 14
1. [(H I) J] [~K (I ~J)]
2. (H I) J
3. ~K (I ~J)
4. H (I J)
5. ~(I ~J) K
6. (~I J) K
7. (I J) K
8. H K
H K
1 simp
1 simp
2 exp
3 trans
5 DeM
6 mi
4,7 HS

Problem # 15
1. [L (M N)] (M N)
2. L [(M N) (M N)]
3. L [~(M N) (M N)]
4. L [[~(M N) M] [~(M N) N]]
5. L [[(~M ~N) M] [(~M ~N) N]
6. L [(M ~M) (M N) (N ~M) (N ~N)]
7. ~L [(M ~M) (M N) (N ~M) (N ~N)]
8. [~L (M ~M)] [~L (M N)] [~L (N ~M)] [~L (N ~N)]
9. ~L (N ~M)
10. ~L (~M v N)
11. ~L (M N)
12. L (M N)
L (M N)
1 exp
2 mi
3 dist
4 DeM, DeM
5 dist, dist
6 mi
7 dist
8 simp
9 con
10 mi
11 mi
There must be an easier way!

Problem # 16
1. S (T U)
2. (T U) V
3. ~S (T U)
4. (~S T) (~S U)
5. ~S T
6. S T
7. ~(T U) V
8. (~T ~U) V
9. V (~T ~U)
10. (V ~T) (V ~U)
11. V ~T
12. ~T V
13. T V
14. S V


S V
3 dist
4 simp
5 mi
2 mi
7 DeM
8 com
9 dist
10 simp
11 com
12 mi
6,13 HS

Problem # 17
1. ~W [(X Y) (Z Y)]
2. W (X Z)
3. W
4. X Z
5. (X Y) (Z Y)
6. Y Y
7. Y

Y
2 simp
2 simp
1,3 DS
4,5 CD
6 taut

Problem # 18
1. (A B) (C D)
2. ~A (E ~E)
3. ~C
4. ~(A B) (C D)
5. [~(A B) C] [~(A B) D]
6. ~(A B) C
7. ~(A B)
8. ~A ~B
9. ~A
10. E ~E
11. ~E ~E
12. ~E


~E
1 mi
4 dist
5 simp
3,6 DS
7 DeM
8 simp
2,9 MP
10 mi
11 taut

Problem # 19
1. (F G) (H I)
2. F H
3. (F ~I) (H ~G)
4. G I
5. ~I ~G
6. ~G ~I
7. G ~I
8. I G
9. ~I G
10. (G ~I) (~I G)
11. G ~I


G ~I
1,2 CD
2,3 CD
5 com
6 mi
4 com
8 mi
7,9 conj
10 me

Problem # 20
1. Q (R S)
2. (Q T) (T S)
3. (Q R) (Q S)
4. Q S
5. Q T
6. T S
7. Q S
8. ~Q S
9. ~S Q
10. ~S S
11. S S
12. S

S
1 dist
3 simp
2 simp
2 com, simp
5,6 HS
4 mi
8 trans
9,7 HS
10 mi
11 taut

Problem # 21
1. (U V) (W X)
2. (U V)
3. ~U V
4. (~U V) X
5. ~U (V X)
6. (V X) ~U
7. W X
8. ~W X
9. (~W X) V
10. ~W (X V)
11. ~W (V X)
12. (V X) ~W
13. [(V X) ~U] [(V X) ~W]
14. (V X) (~U ~W)
15. (~U ~W) (V X)
16. ~(U W) (V X)
17. (U W) (V X)
(U W) (V X)
1 simp
2 mi
3 add
4 ass
5 com
1 simp
7 mi
8 add
9 ass
10 com
11 com
6,12 conj
13 dist
14 com
15 DeM
16 mi
This is a very short proof with CP.

 

Problem # 22

1. (Y Z) (A B)
2. (Y Z)
3. ~Y Z
4. (~Y Z) ~A
5. ~Y (Z ~A)
6. ~Y (~A Z)
7. A B
8. ~A B
9. (~A B) ~Y
10. ~Y (~A B)
11. [~Y (~A Z)] [~Y (~A B)]
12. ~Y [(~A Z) (~A B)]
13. ~Y [~A (Z B)]
14. ~Y [A (Z B)]
15. Y [A (Z B)]
16. (Y A) (Z B)
(Y A) (Z B)
1 simp
2 mi
3 add
4 ass
5 com
1 simp
7 mi
8 add
9 com
6,10 conj
11 dist
12 dist
13 mi
14 mi
15 exp
This is another very short proof with CP.

Problem # 23
1. (C D) (E F)
2. G (C E)
3. ~G (C E)
4. (~G C) E
5. (C ~G) E
6. C (~G E)
7. ~C (~G E)
8. C D
9. ~D ~C
10. ~D (~G E)
11. D (~G E)
12. D (E ~G)
13. (D E) ~G
14. (E D) ~G
15. E (D ~G)
16. ~E (D ~G)
17. E F
18. ~F ~E
19. ~F (D ~G)
20. F (D ~G)
21. (D ~G) F
22. (~G D) F
23. ~G (D F)
24. G (D F)

G (D F)
2 mi
3 ass
4 com
5 ass
6 mi
1 simp
8 trans
9,7 HS
10 mi
11 com
12 ass
13 com
14 ass
15 mi
1 simp
17 trans
18,16 HS
19 mi
20 com
21 com
22 ass
23 mi

Problem # 24
1. (H I) (J K)
2. H J
3. (H ~K) (J ~I)
4. (I ~K) L
5. K (I M)
6. I K
7. ~K ~I
8. ~I K
9. K ~I
10. ~I ~I
11. I ~I
12. (~K I) L
13. ~K (I L)
14. I ~K
15. I (I L)
16. (I I) L
17. I L
18. ~I (I M)
19. I (I M)
20. (I I) M
21. I M
22. ~I M
23. (I L) (~I M)
24. L M




L M
1,2 CD
2,3 CD
6 mi
7 mi
8,9 HS
10 mi
4 com
12 exp
9 trans
14,13 HS
15 exp
16 taut
8,5 HS
18 mi
19 ass
20 taut
21 mi
17,22 conj
23,11 CD