In doing these proofs, I generally make use of Neg->, MTT, BP, BT and DM. Of course, there are lots other ways to do the proofs.
#2 ~P v Q, ~Q v R, ~R |- ~P
1 (1) ~P v Q A
2 (2) ~Q v R A
3 (3) ~R
A
2,3 (4) ~Q
2,3 vE
1,2,3 (5) ~P 1,4 vE
#4 (Q -> P) -> R, ~Q v S, ~S |- ~R -> T
1 (1) (Q -> P) -> R
A
2 (2) ~Q v S
A
3 (3) ~S
A
4 (4) ~R
A [for ->I]
5 (5) ~T
A [for RAA]
2,3 (6) ~Q
2,3 vE
1,4 (7) ~(Q -> P)
1,4 MTT
1,4 (8) Q & ~P
7 Neg->
1,4 (9) Q
8 &E
1,2,3,4 (10) T
6,9 RAA (5)
1,2,3 (11) ~R -> T
10 ->I (4)
Note: Since T does not appear in the premises,
we cannot get it directly. So the strategy used here is to assume
~T and aim for a contradiction.
#5 P & (Q ->R), Q v ~P, R v S -> T |- T v U
1 (1) P & (Q ->R)
A
2 (2) Q v ~P
A
3 (3) R v S -> T
A
1 (4) P
1 &E
1,2 (5) Q
2,4 vE
1 (6) Q -> R
1 &E
1,2 (7) R
5,6 ->E
1,2 (8) R v S
7 vI
1,2,3 (9) T
3,8 ->E
1,2,3 (10) T v U
9 vI
Notice that in this case there is no need
to go indirect!
#6 P <-> ~Q, R v ~Q, R <-> S |- S v P
1
(1) P <-> ~Q A
2
(2) R v ~Q A
3
(3) R <-> S A
4
(4) ~(S v P) A [for RAA]
4
(5) ~S & ~P 4 DM
4
(6) ~P
5 &E
1,4 (7) Q
1,6 BT
1,2,4 (8) R
2,7 vE
1,2,3,4 (9) S
3,8 BP
4 (10)
~S 5
&E
1,2,3 (11) S v P
9,10 RAA (4)
#9 ~R <-> ~Q, P v ~Q, P <-> S |- S v ~R
1 (1) ~R <-> ~Q
A
2 (2) P v ~Q
A
3 (3) P <-> S
A
4 (4) ~(S v ~R)
A [for RAA]
4 (5) ~S & R
4 DM
4 (6) ~S
5 &E
3,4 (7) ~P
3,6 BT
2,3,4 (8) ~Q
2,7 vE
4 (9) R
5 &E
1,4 (10) Q
1,9 BT
1,2,3 (11) S v ~R
8,10 RAA (4)
#11 Valid - will be discussed in class on Tuesday, 3/12
#14 P & Q, Q -> (P -> R), R -> (~S -> ~T v ~W), ~S & T |- ~W
1 (1)
P & Q
A
2 (2)
Q -> (P -> R) A
3 (3)
R -> (~S -> ~T v ~W) A
4 (4)
~S & T
A
1 (5)
Q
1 &E
1,2 (6) P -> R
2,5 ->E
1 (7)
P
1 &E
1,2 (8) R
6,7 ->E
1,2,3 (9) ~S -> ~T v ~W
3,8 ->E
4 (10)
~S
4 &E
1,2,3,4 (11) ~T v ~W
9, 10 ->E
4 (12)
T
4 &E
1,2,3,4 (13) ~W
11,12 vE
#15 P v Q -> R v S, ~(T v R) -> S, (T -> P) & (R -> Q), ~S |- R
1
(1) P v Q -> R v S A
2
(2) ~(T v R) -> S A
3
(3) (T -> P) & (R -> Q) A
4
(4) ~S
A
2,4 (5)
T v R
2,4 MTT
6
(6) ~R
A [for RAA]
2,4,6 (7) T
5,6 vE
3
(8) T -> P
3 &E
2,3,4,6 (9) P
7,8 ->E
2,3,4,6 (10) P v Q
9 vI
1,2,3,4,6 (11) R v S
1,10 ->E
1,2,3,4,6 (12) S
6,11 vE
1,2,3,4 (13) R
6,12 RAA (6)
[I've skipped 16 - 20 for now]
#21. P <-> Q, R v ~P, T & Q -> ~R |- ~S & T -> ~(P
v Q)
| 1 | (1) P <-> Q | A |
| 2 | (2) R v ~P | A |
| 3 | (3) T & Q -> ~R | A |
| 4 | (4) ~S & T | A [for ->I] |
| 5 | (5) P v Q | A [for RAA] |
| 6 | (6) ~P | A [for RAA] |
| 1,6 | (7) ~Q | 1,6 BT |
| 5,6 | (8) Q | 5,6 vE |
| 1,5 | (9) P | 7,8 RAA (6) |
| 1,2,5 | (10) R | 2,9 vE |
| 4 | (11) T | 4 &E |
| 1,5 | (12) Q | 1,9 BP |
| 1,4,5 | (13) T & Q | 11,12 &I |
| 1,3,4,5 | (14) ~R | 3,13 ->E |
| 1,2,3,4 | (15) ~(P v Q) | 10,14 RAA (5) |
| 1,2,3 | (16) ~S & T -> ~(P v Q) | 15 ->I (3) |
#22. P & Q -> (R <-> S), ~P -> ~T, ~(~R v S) |-
Q -> ~T
| 1 | (1) P & Q -> (R <-> S) | A |
| 2 | (2) ~P -> ~T | A |
| 3 | (3) ~(~R v S) | A |
| 4 | (4) Q | A [for ->I] |
| 5 | (5) T | A [for RAA] |
| 2,5 | (6) P | 2,5 MTT |
| 2,4,5 | (7) P & Q | 4,6 &I |
| 1,2,4,5 | (8) R <-> S | 1,7 ->E |
| 3 | (9) R & ~S | 3 DM |
| 3 | (10) R | 9 &E |
| 3 | (11) ~S | 9 &E |
| 1,2,3,4,5 | (12) S | 8,10 BP |
| 1,2,3,4 | (13) ~T | 11,12 RAA (5) |
| 1,2,3 | (14) Q -> ~T | 13 ->I (4) |
#23. P & Q -> R, P & ~R <-> Q v ~S, T &
(~Q & ~R -> P),
(T -> S) v (T ->
R) |- S & R
I hate this one. A lot. Any suggestions for shorter
proofs are welcome.
| 1 | (1) P & Q -> R | A |
| 2 | (2) P & ~R <-> Q v ~S | A |
| 3 | (3) T & (~Q & ~R -> P) | A |
| 4 | (4) (T -> S) v (T -> R) | A |
| 5 | (5) ~S | A [for RAA; 1st conjunct] |
| 5 | (6) Q v ~S | 5 vI |
| 2,5 | (7) P & ~R | 2,6 BP |
| 2,5 | (8) ~R | 7 &E |
| 3 | (9) T | 3 &E |
| 2,3,5 | (10) T & ~R | 8,9 &I |
| 2,3,5 | (11) ~(T -> R) | 10 Neg-> |
| 2,3,4,5 | (12) T -> S | 4, 11 vE |
| 2,3,4,5 | (13) S | 9,12 ->E |
| 2,3,4 | (14) S | 5,13 RAA (5) |
| 15 | (15) ~R | A [for RAA, 2nd conjunct] |
| 16 | (16) P | A [for RAA] |
| 15,16 | (17) P & ~R | 15, 16 &I |
| 2,15,16 | (18) Q v ~S | 2,17 BP |
| 2,3,4,15,16 | (19) Q | 14,18 vE |
| 2,3,4,15,16 | (20) P & Q | 16,18 &I |
| 1,2,3,4,15,16 | (21) R | 1,20 ->E |
| 1,2,3,4,15 | (22) ~P | 15,21 RAA (16) |
| 3 | (23) ~Q & ~R -> P | 3 &E |
| 1,2,3,4,15 | (24) ~(~Q & ~R) | 22,23 MTT |
| 1,2,3,4,15 | (25) Q v R | 24 DM |
| 1,2,3,4,15 | (26) Q | 15,25 vE |
| 1,2,3,4,15 | (27) Q v ~S | 26 vI |
| 1,2,3,4,15 | (28) P & ~R | 2,27 BP |
| 1,2,3,4,15 | (29) P | 28 &E |
| 1,2,3,4 | (30) R | 22,29 RAA (15) |
| 1,2,3,4 | (31) S & R | 14,30 &I |
#24. R v (P -> S), T & ~W, (~T v W) -> ~R, (S -> Q) & ~Q |- ~P
Invalidating assignment:
P:T, Q:F, R:T, S:F, T:T, W:F
#25. R v (P v S), T & ~W, ~(~T v W) -> ~R, (S -> Q) &
~Q |- P
| 1 | (1) R v (P v S) | A |
| 2 | (2) T & ~W | A |
| 3 | (3) ~(~T v W) -> ~R | A |
| 4 | (4) (S -> Q) & ~Q | A |
| 4 | (5) S -> Q | 4 &E |
| 4 | (6) ~Q | 4 &E |
| 4 | (7) ~S | 5,6 MTT |
| 2 | (8) ~(~T v W) | 2 DM |
| 2,3 | (9) ~R | 3,8 ->E |
| 1,2,3 | (10) P v S | 1,9 vE |
| 1,2,3,4 | (11) P | 7,10 vE |