SOLUTIONS

- 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 - 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*. - Give an example (i.e., choose a universe of discourse and
examples for P, Q and y) which shows that

is not a theorem.(Py Þ Qy) Þ (($x|:Px)Þ ($x|:Qx))

**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 ¹ 0 Ù x ¹ 1'', and y to be 1. - Fill in REASONS in the following proof that
|- (+j | 0 £ j £ n-1 : (j+1) ^{2}) = (+k | 1 £ k £ n : k^{2}) .**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:k ^{2}))=

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

(+j,k | (0 £ j £ n-1) Ù(k = j+1):k ^{2})=

Arithmetic, Leibniz (8.12)

(+j,k | (0 £ j £ n-1) Ù(j = k-1):k ^{2})=

(3.84)(a), Leibniz (8.12)

(+j,k | (0 £ k-1 £ n-1) Ù(j = k-1):k ^{2})=

Arithmetic, Leibniz (8.12)

(+j,k | (1 £ k £ n) Ù(j = k-1):k ^{2})=

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

(+k,j | (1 £ k £ n) Ù(j = k-1):k ^{2})=

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

(+k | 1 £ k £ n:(+j | j = k-1:k ^{2}))=

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

(+k | 1 £ k £ n:k ^{2}))

File translated from T

On 11 Nov 2000, 10:01.