80-211 Spring 2003

 

Answer key

 

Note: These are the answers to some of the questions in the book and some answers to problems not in the book, most of these were not problems you had to do for homework, but are similar.

 

 

Problems from pages 27-28:

 

 

1-a P |- Q (P & Q)

1 (1) P A

2 (2) Q A

1,2 (3) P & Q 1,2 &-I

1 (4) Q (P & Q) 2,3 CP

 

 

1-f (P R) & (Q R) |- (P v Q) R

 

1 (1) (P R) & (Q R) A

2 (2) P v Q A

3 (3) P A

1 (4) P R 1, &-E

1,3 (5) R 3,4 MPP

6 (6) Q A

1 (7) Q R 1, &-E

1, 6 (8) R 6,7 MPP

1,2 (9) R 2, 3, 5, 6, 8 v-E

1 (10) (P v Q) R 2, 9 CP

 

1-g P Q, R S |- (P & R) (Q & S)

 

1 (1) P Q A

2 (2) R S A

3 (3) P & R A

3 (4) P 3, &-E

1, 3 (5) Q 1, 4 MPP

3 (6) R 3, &-E

2, 3 (7) S 2, 6 MPP

1, 2, 3 (8) Q & S 5, 7 &-I

1, 2 (9) (P & R) (Q & S) 3, 8 &-I

 

 

 

 

 

 

 

 

 

1-i P (Q & R) |- (P Q) & (P R)

1 (1) P (Q & R) A

2 (2) P A

1, 2 (3) Q & R 1,2 MPP

1, 2 (4) Q 3, &-E

1 (5) P Q 2, 4 CP

1, 2 (6) R 3, &-E

1 (7) P R 2, 6 CP

1 (8) (P Q) & (P R) 5, 7 &-I

 

Problems on page 33:

 

1-c P Q |- ~ P ~Q

 

1 (1) P Q A

1 (2) (P Q) & (Q P) 1, def

1 (3) P Q 2, &-E

1 (4) Q P 2, &-E

5 (5) ~Q A

1, 5 (6) ~P 3, 5 MTT

1 (7) ~Q ~P 5,6 CP

8 (8) ~P A

1, 8 (9) ~Q 4, 8 MTT

1 (10) ~P ~Q 8, 9 CP

1 (11) (~P ~Q) & (~Q ~P) 7, 10 &-I

1 (12) ~P ~Q 11, def

 

1-e (P v Q) P |- Q P

 

1 (1) (P v Q) P A

1 (2) ((P v Q) P) & (P (P v Q)) 1, def

3 (3) Q A

3 (4) P v Q 3, v-I

1 (5) (P v Q) P 2, &-E

1, 3 (6) P 4,5 MPP

1 (7) Q P 3, 6 CP

 

 

 

 

Problems on page 41:

 

1-c P & (Q v R) -||- (P & Q) v (P & R)

 

Part a: P & (Q v R) |- (P & Q) v (P & R)

 

1 (1) P & (Q v R) A

1 (2) P 1, &-E

1 (3) Q v R 1, &-E

4 (4) Q A

1, 4 (5) P & Q 2, 4 &-I

1, 4 (6) (P & Q) v (P & R) 5, v-I

7 (7) R A

1, 7 (8) P & R 2, 7 &-I

1, 7 (9) (P & Q) v (P & R) 8, v-I

1 (10) (P & Q) v (P & R) 3, 4, 6, 7, 9 v-E

 

Part b: (P & Q) v (P & R) |- P & (Q v R)

 

1 (1) (P & Q) v (P & R) A

2 (2) P & Q A

2 (3) P 2, &-E

2 (4) Q 2, &-E

2 (5) Q v R 4, v-I

2 (6) P & (Q v R) 3, 5 &-I

7 (7) P & R A

7 (8) P 7, &-E

7 (9) R 7, &-E

7 (10) Q v R 9, v-I

7 (11) P & (Q v R) 8, 10 &-I

1 (12) P & (Q v R) 1, 2, 6, 7, 11, v-E

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1-f ~ (P v Q) -||- ~P & ~Q

 

Part a: ~ (P v Q) |- ~P & ~Q

 

1 (1) ~ (P v Q) A

2 (2) P A

2 (3) P v Q 2, v-I

1, 2 (4) ~ (P v Q) & (P v Q) 1, 3 &-I

1 (5) ~P 2, 4 RAA

6 (6) Q A

6 (7) P v Q 6, v-I

1, 6 (8) ~ (P v Q) & (P v Q) 1, 7 &-I

1 (9) ~Q 6, 8 RAA

1 (10) ~P & ~Q 5, 9 &-I

 

Part b: ~P & ~Q |- ~ (P v Q)

 

1 (1) ~P & ~Q A

2 (2) P v Q A

3 (3) P A

1 (4) ~P 1, &-E

1, 3 (5) P & ~P 3, 4 &-I

3 (6) ~ (~P & ~Q) 1, 5 RAA

7 (7) Q A

1 (8) ~Q 1, &-E

1, 7 (9) Q & ~Q 7, 8 &-I

7 (10) ~ (~P & ~Q) 1, 9 RAA

1, 2 (11) ~ (~P & ~Q) 2, 3, 6, 7, 10, v-E

1, 2 (12) ~ (~P & ~Q) & (~P & ~Q) 1, 11 &-I

1 (13) ~ (P v Q)

 

Note: The following 4 proofs use derived rules.

 

|- (PQ) v (QP)

 

(1) P v ~P TI 44

2 (2) P A

2 (3) QP 2 SI 50

2 (4) (PQ) v (QP) 3, v-I

5 (5) ~P A

5 (6) PQ 5 SI 51

5 (7) (PQ) v (QP) 6, v-I

(8) (PQ) v (QP) 1, 2, 4, 5, 7 v-E

 

 

 

 

 

~(P v Q) v ~(~P v ~Q) |- PQ

 

1 (1) ~(P v Q) v ~(~P v ~Q) A

2 (2) ~(P v Q) A

2 (3) ~P & ~ Q 2 SI DeMorgan

2 (4) ~P 3, &-E

2 (5) ~Q 3, &-E

2 (6) PQ 4 SI 51

2 (7) QP 5 SI(S) 51

2 (8) (PQ) & (QP) 6, 7 &-I

9 (9) ~(~P v ~Q) A

9 (10) P & Q 9 SI DeMorgan (prob 1-h)

9 (11) P 10 &-E

9 (12) Q 10 &-E

9 (13) QP 11 SI-50

9 (14) PQ 12 SI(S)-50

9 (15) (PQ) & (QP) 13, 14 &-I

1 (16) (PQ) & (QP) 1, 2, 8, 9, 15 v-E

1 (17) PQ 16 Def

 

 

P v Q, (QR) & (~P v S), (Q & R)T |- T v S

 

1 (1) P v Q A

2 (2) (QR) & (~P v S) A

3 (3) (Q & R)T A

4 (4) P A

2 (5) ~P v S 2, &-E

4 (6) ~~P 4, DN

2, 4 (7) S 5, 6 MTP (aka disjunctive syllogism)

2, 4 (8) T v S 7, v-I

9 (9) Q A

2 (10) QR 2, &-E

2, 9 (11) R 9, 10 MPP

2, 9 (12) Q & R 9, 11 &-I

2, 3, 9 (13) T 3, 12 MPP

2, 3, 9 (14) T v S 13, v-I

1, 2, 3 (15) T v S 1, 4, 8, 9, 14 v-E