Math 1090 A Homework 4 Math 1090 A Homework 4
SOLUTIONS

  1. Prove using the methods of the text that
    |- (a = 2) (a = 3)     (2 = 3) .
    Answer:
    (a = 2) (a = 3)
    =

    (3.84)(a)

    (a = 2) (2 = 3)

    (3.76)(b)

    2 = 3
  2. You are given that {0,1} is the universe of discourse, Px is the predicate ``x = 0'', and Qx is the predicate ``x = 1''. Establish whether each of the following is true.
    ("x|:Px Qx)
    ((" x|:Px) ("x|:Qx))
    ((" x|:Px) ("x|:Qx))
    ("x|:Px Qx)
    ("x|:Px Qx)
    ((" x|:Px) ("x|:Qx))

    Answer: ("x)(Px Qx) is f since P0 Q0 is f. Then ("x)(Px Qx) (("x)Px ("x)Qx) is t.
    ("x)Px is f, ("x)Qx is f so ("x)Px ("x)Qx) is t. But ("x)(Px Qx) is f, so (("x)Px ("x)Qx) ("x)(Px Qx) is f.
    If ("x)(Px Qx) (("x)Px("x)Qx) were t we would have both ("x)(Px Qx) (("x)Px ("x)Qx) and (("x)Px ("x)Qx) ("x)(Px Qx) t. But this is not the case, so ("x)(Px Qx) (("x)Px ("x)Qx) is f.

  3. Give an example (i.e., choose a universe of discourse and examples for P, Q and y) which shows that
    (Py Qy) (($x|:Px) ($x|:Qx))
    is not a theorem.
    Answer: The form of the expression indicates that for an interpretation where it is not satisfied, Py Qy is t, ($x|:Px) is t, and ($x|:Qx) is f. Once we find such an interpretation, by soundness it would follow that the expression is not a theorem.
    Take {0,1} to be the universe of discourse, Px to be ``x = 0'' , Qx to be ``x  x 1'', and y to be 1.

  4. Fill in REASONS in the following proof that
    |- (+j | 0 j n-1 : (j+1)2 ) = (+k | 1 k n : k2 ) .
    Answer:
    (+j | 0 j n-1 : (j+1)2 )
    =

    (8.14), k d.n.o.f. in j+1.

    (+j | 0 j n-1 : (+k | k = j+1:k2 ))
    =

    (8.20), k d.n.o.f. in 0 j n-1.

    (+j,k | (0 j n-1) (k = j+1):k2 )
    =

    Arithmetic, Leibniz (8.12)

    (+j,k | (0 j n-1) (j = k-1):k2 )
    =

    (3.84)(a), Leibniz (8.12)

    (+j,k | (0 k-1 n-1) (j = k-1):k2 )
    =

    Arithmetic, Leibniz (8.12)

    (+j,k | (1 k n) (j = k-1):k2 )
    =

    Axiom, (*x,y | P:Q ) = (*y,x | P:Q )

    (+k,j | (1 k n) (j = k-1):k2 )
    =

    (8.20), j d.n.o.f. in 1 k n.

    (+k | 1 k n:(+j | j = k-1:k2 ))
    =

    (8.14) j d.n.o.f. in k+1.

    (+k | 1 k n:k2 ))


File translated from TEX by TTH, version 2.60.
On 11 Nov 2000, 10:01.