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) .
 (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 ) .
 (+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.