Math 470 Spring ’05

HW #7 Solutions

Section 2.4

8. Assume that j(xi) is valid. Then it is satisfied by any interpretation A. So whatever elements of A are chosen as the values of xi, the formula holds,. Let L’ be the extension of L to include new constants ci. Let A’ be any interpretation of L’. Whatever values are chosen for the ci, the formula j holds for those values. Thus j(ci) is true in A”. Therefore j(ci) is valid.

Conversely, assume that j(ci) is valid. Then for any A’ an interpretation of L’, j(ci) is true. Restrict L’ to L by removing the ci. In the resulting A. j(xi) is true.

Thus j(xi) is true in every interpretatuon of L, so it is valid.

Section 2.6

12. a) F "x$yØ"zj(x,y,z) <-> "x$y$zØ j(x,y,z)

/ \

T "x$yØ"zj(x,y,z)) F "x$yØ"zj(x,y,z)

F "x$y$zØ j(x,y,z) T "x$y$zØ j(x,y,z)

F $y$z Øj(c,y,z) F $yØ"zj(d,y,z)

T $yØ"z j(c, y, z) T $y$z Øj(d, y, z)

T Ø"z j(c,e, z) T $z Øj(d,g,z)

T Øj(c,e,f) T Øj(d,g,h)

F $y$z Øj(c,y,z) F j(d,g,h)

F $z Øj(c, e, z) F $yØ"zj(d,y,z)

F Øj(c,e,f) F Ø"z j(d,g,z)

X T "z j(d,g,z)

T j(d,g,h)

X

b) Since z is a free variable of y, the formula is not a sentence. It can be made one (without changing its validity) by prefixing it with a universal quantifier applied to a new variable and then applying rule 7b to that variable, so that y becomes yc.

We can now ignore the free occurrence of z.

(Or treat the formula as if it didn’t have a free occurrence of z.)

F "z($x"y ("zj v y) <-> $x"y"w (j(z/w) v y) )

/ \

T $x"y ("zj v y) F $x"y ("zj v y)

F $x"y"w (j(z/w) v y) T $x"y"w (j(z/w) v y)

T "y ("z j(c,y,z) v y(c,y)) T "y"w j(f,y,w) v y(f,y)

F "y"w (j(c,y, w) v y(c,y) F $x"y ("zj v y)

F "w (j(c,d, w) v y(c,d) F "y( "z j(f,y,z) v y(f,y)

F (j(c,d,e) v y(c,d) F ("z j(f,g,z) v y(f,g))

T "y ("z j(c,y,z) v y(c,y)) F"z j(f,g,z)

T "z j(c, d, z) v y(c,d) Fy(f,g)

T j(c,d,e) v y(c,d) F j(f,g,h)

X T "y"w j(f,y,w) v y(f,y)

T j(f,g,h) v y(f,g)

/ \

T j(f,g,h) Ty(f,g)

X X

c) d) similar

Section 2.9

1. Suppose that j and y are equivalent.

Prove that "xj and "xy are equivalent. If "xj is true in a structure A, then j is true in A for any element a of A replacing free occurrences of x, Since y is equivalent to j, y is also true for any element of A. Then "xy is true in A.

Prove that $xj and $x y are equivalent. If $xj is true in a structure A, then j is true in A for some element a of A replacing free occurrences of x, Since y is equivalent to j, y is also true for a. Then $xy is true in A.

Thus the equivalence of j and y is preserved for Qxj and Qx y. Repeating this n times proves the claim.

2. A formula with free variables is valid iff the corresponding formula with the free variables replaced by new constants is.

So we can replace any free variables in 1a to 4b’ by new constants without changing their validity.

3. By exercises 1 and 2, we can assume that 1a to 4b contain neither free variables and that the leading strings of quantifiers are empty. Thus 1a becomes

Ø"yj <-> $yØj

Tableau: F Ø"yj <-> $yØj

/ \

T Ø"yj F Ø"yj

F $yØj T $y Øj

F "y j T Øj(c)

F j(d) F j(c)

F Øj(d) T "y j

T j(d) T j(c)

X X

Semantic argument:

Assume that Ø"y j is true in a structure A. Then "yj is false in A. Then for some element a of A, j is false when a replaces free occurrences of y. Then Øj is true for a. So $y Øj is true in A.

Conversely, assume that $y Øj is true in A. Then for some element a of A, Øj is true for a. So j is false for A. Then "y j is false in A. Then Ø"y j is true in A.

Hence they are equivalent.

Similar tableau and semantic proofs can be carried out for the other claims.

4. Assume that "x j(x, f(x) ) is true in A. Let a be any element of A. Then j(a, f(a)) is true. So $y j(a, y) is true. As this holds for any element of A, "x$y j(x,y) is true in A. Thus the implication "x j(x, f(x) ) -> "x$y j(x,y) is valid.

Now let A = N, j(x,y) be x < y and f be the identity function f(x) = x.

Then "x$y j(x,y) is true in A but "x j(x, f(x) is not. So "x$y j(x,y) -> "x j(x, f(x) is false in A.

5. a) First pull out the "y and $y, changing the second y to v. Either can go first, we’ll put the $ in front.

$v"y( ( $xP(x,y) -> Q(y,z) ) ^ ("xR(x,v) v Q(x, v)).

Next, dealing with the x’s in each conjunct, changing the second to u, gives:

$v"y ( "x( P(x,y ) -> Q (y,z) ) ^ "u( R(u,v ) v Q (x, v)) (Note that the final x is not in the scope of the quantifier.)

The u and the first x can now be pulled out, but must change to a new variable as there is a free x.

$v"y "w "u (P(w,y) -> Q(y, z) ^ (R(u,v) v Q (x, v))

Skolemizing gives "y "w "u ( (P (w,y) -> Q(y, z) ) ^ ( R(u, c) v Q (x, c))

b) First translate to ($xR(x,y) -> "y P(x,y) ) ^ ("y P(x,y) -> $xR(x,y))

The y in R is free as is the x in P, so all of the bound variables must be changed.

($u R(u,y) -> "vP(x,v) ) ^ ("wP(x,w) -> $z R(z,y))

"u"v( R(u,y) -> P(x, v) ) ^ $w $z (P(x, w) -> R( z,y))

Finally

$w $z "u "v (R(u,y) -> P(x,v)) ^ P(x,w) -> R(z, v))

Skolemizing gives "u"v (R(u,y) -> P(x, v)) ^ (P(x,c) -> (d, v))

c) Rewrite the 3^rd conjunct as "x"y ØP(x,y). Then replace 2^nd xy by uv and 3^rd by wz.

$u"x$y "v "w"z (Q(x,y) v P(u,v) ^ ØP(w,z))

Skolemizing gives: "x "v "w "z (Q(x, f(x)) v P(c, v)) ^ Ø P(w, z))

d) Rewrite the 1^st conjunct as ("x$y P(x,y) ^ Ø$x$yR(x,y)) and then as "x$y P(x,y) ^ "x"y ØR(x,y).

Rewrite the second as "x"yØQ(x,y).

Then pull the quantifiers forward, changing the second xy to uv and the third to wz;

"x$y "u"v "w"z (P(x,y) ^ ØR(u,v) ^ ØQ(w,z))

Skolemizing gives: "x "u"v"w"z (P(x,f(x)) ^ ØR(u,v) ^ ØQ(w,z)).