Math 1090 N Homework 3 Math 1090 N Homework 3

  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)


    (p q)(q r)(r q)       (p r)

    (3.36), (3.65)

    (r q)    ((p q)(q r) (p r))


    (r q) 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  q s) .
    You may use the hint for Problem (4.5) in the text.
    Answer: By (3.65),
    ((p q) (r s)    (p  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


    p (p q) r (r s)


    pq r s


    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.


    true q

    Assumptions, Metatheorem, (3.39)

    (p q) (r p) r     q

    (3.36), (3.66)

    (p q) rp     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.