Provide direct derivations using just the equivalence and inference
rules we we have worked with so far.
1. P -> (Q & R), ~P -> S, ~S |- P
& Q
1. P
-> (Q & R)
2.
~P -> S
3.
~S
\show P & Q
4.
P v S
2, Impl
5.
P
3,4, DS
6.
~P v (Q & R) 1,
Impl
7.
Q &
R
5,6, DS
8.
Q
7, Simp
9.
P &
Q
5,8, Conj
2. ~(P v ~Q), P v S, ~T |- Q v T
1. ~(P
v ~Q)
2.
P v S
3.
~T
\show
Q v T
4.
~P &
Q
1, DM
5.
Q
4, Simp
6.
Q v
T
5,
Add
note that "~T" turns out to be an irrelevant premise that plays no role
in the proof
3.
(P v Q) -> (R v S), P
& ~R |- S
1. (P v Q) -> (R v S)
2. P &
~R
\ show S
3. ~(P v Q) v (R v S) 1, Impl
4.
P
2, Simp
5. P v
Q
4, Add
6. R v
S
3,5, DS
7.
~R
2, Simp
8.
S
6,7, DS
4.
(P & Q) -> (R
& S), P, Q |- S
1. (P & Q) -> (R & S)
2. P
3.
Q
\show S
4. P &
Q
2,3, Conj
5. ~(P & Q) v (R
& S) 1, Impl
6. R & S
4,5, DS
7. S
6, Simp
5. P
-> Q, Q -> R, S -> T, P v S, ~T |- R
1. P -> Q
2.
Q -> R
3.
S -> T
4.
P v S
5.
~T
\show R
6.
~S v
T
3, Impl
7.
~S
5,6, DS
8.
P
4,7, DS
9.
~P v
Q
1, Impl
10.
Q
8,9, DS
11.
~Q v
R
2, Impl
12.
R
10,11, DS
