Math 1090 N Homework 3 Math 1090 N Homework 3
SOLUTIONS

1. Prove in the proof style of the text, Transitivity, (3.82)(c),
 |- (p Þ q)  Ù  (q º r)    Þ    (p Þ r).
You may use any lower numbered theorem in your proof.
 (pÞ q)Ù(q º r)   Þ    (pÞ r)
 =

 (3.80)

 (pÞ q)Ù(q Þ r)Ù(r Þ q)   Þ    (pÞ r)
 =

 (3.36), (3.65)

 (rÞ q)  Þ  ((pÞ q)Ù(q Þ r) Þ(p Þ r))
 =

 (3.82)(a)

 (rÞ q) Þ true
 =

 (3.72)

 true

2. Prove the Derived Inference Rule,
 |- P Þ Q,    |- Q    º    R
 |- P Þ R
.
You may make use of the Derived Inference Rule,
 |- P
 |- true    º   P
and the three basic Inference Rules only.
Answer: Since |- Q    º   R, by Leibniz with r fresh, E being P Þ r, we have
 |- P Þ Q    º   P Þ R .
By (3.2),
 |- P Þ R    º   P Þ Q    º   P Þ Q    º   P Þ R .
By Equanimity,
 |- P Þ R    º   P Þ Q .
Since |- P Þ Q,
 |- P Þ R  .
3. Use the method of Section 4.1 to prove
 |- (pÞ q) Ù(r Þ s)    Þ    (p Ùr Þ q Ùs) .
You may use the hint for Problem (4.5) in the text.
 ((pÞ q) Ù(r Þ s)  Þ  (p Ùr Þ q Ùs))      º     ((pÞ q) Ù(r Þ s)Ù(p Ùr)   Þ  q Ùs) .
We will prove
 (pÞ q) Ù(r Þ s)Ù(p Ùr)   Þ  q Ùs .

 (pÞ q)Ù(r Þ s)Ùp Ùr
 =

 (3.36)

 p Ù(pÞ q) Ùr Ù(r Þ s)
 =

 (3.66)

 pÙq Ùr Ùs
 Þ

 (3.76)(b)

 q Ùs
4. Apply the Deduction Theorem (i.e., use the method of assuming the antecedent) to prove
 |- (p Þ q)    Þ    ((rÞ p) Þ  (rÞ q)) .

Assume pÞ q.
We need to prove (rÞ p) Þ  (rÞ q).
Now assume (rÞ p).
We need to prove (rÞ q).
Now assume r.
We need to prove q.
 q
 =

 (3.73)

 true Þ q
 =

 Assumptions, Metatheorem, (3.39)

 (pÞ q) Ù(r Þ p) Ùr   Þ  q
 =

 (3.36), (3.66)

 (pÞ q) ÙrÙp   Þ  q
 =

 (3.36), (3.66)

 p Ùq Ùr   Þ  q
 =

 (3.37), (3.36)

 qÙ(p Ùr) Þ q

File translated from TEX by TTH, version 2.60.
On 28 Oct 2000, 19:01.