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.
    Answer:
    (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  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
    =

    (3.36)

    p (p q) r (r s)
    =

    (3.66)

    pq 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)) .

    Answer:
    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) 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.