Math 1090 A Homework 2 Math 1090 A Homework 2
Solutions

  1. Rewrite the following to include ``invisible'' parentheses and test the resulting expression for validity.
    pr    q         r    (p q)  .
    Answer:
    ((pr)    q)         (r    (p q))  .
    p q r ((pr)q)     (r(p q))
    tttttttttt
    ttfftttftt
    tfttffttff
    tffftftftf
    fttftttttt
    ftfftttftt
    fftftftttt
    fffftftftt

    This is a valid formula.

  2. Find one state in which the following is satisfied and one state in which it is not satisfied.
    (p q    q r)        (p r).
    Answer: The formula is not satisfied when p is t, q is f, r is f. It is satisfied in all other states.
  3. Fill in the complete details (in the proof style of the ``model proof'') of the proof of (3.42),
    |-  p  p          false  ,
    where the proof steps are given below.
    Answer:
     p
    =


    (3.35) where P is p and Q is p
    gives |- (p  p)         (p     p     pp) .


    p     p     pp
    =




    (3.28) where P is p and Metatheorem gives |- pp true
    and Leibniz with E being p p r
    gives |- (p     p     pp) (p     p      true) .




    p     p      true
    =


    (3.2) where P is p p and Q is true
    gives |-(p     p      true)         (true     p     p) .


    true     p     p
    =


    (3.2) where P is p and Q is p and Leibniz with E being true r
    gives |-(true     p     p)         (true     p     p) .


    true     p     p
    =


    (3.15) where P is p and Leibniz with E being true r
    gives |- (true     p     p)         (true     false) .


    true     false
    =


    (3.3) where Q is false
    gives |- (true     false)         (false) .


    false

    Transitivity applied 5 times gives |-  pp         false.

  4. Using the proof style of the text, prove (3.30):
    |-  p  false         p  .
    You may assume any result with lower number.
    Answer:
    pfalse
    =

    (3.15), (3.2)

    p(p p)
    =

    (3.27)

    pp      pp
    =

    (3.28), Metatheorem

    true pp
    =

    (3.26)

    true p
    =

    (3.3)

    p


File translated from TEX by TTH, version 2.60.
On 25 Sep 2000, 18:14.