Assignment 5 Solutions

Exercise 6.2.4

• (f) Premise (\forall x)(\exists y) Gyx
Conclusion ¬(\exists y) (\forall z) Gyz

• (h) Premise (\forall x)[ Ex \biconditional ¬Ox ]
Premise Et
Conclusion ¬Ot

• (l) Premise (\forall x)[ Sxy -> Lxy ]
Conclusion (\forall x)(\forall y) [ ( Lxy & [Sxz & Syw] ) -> Lzw ]

Exercise 6.2.6

• (f) (\forall x)(\forall y)[ ¬Ixa & ¬Iya ->( (\forall z) Pxyz -> ¬Iza) ]

• (h) (\forall x)(\forall y)(\forall z)[ ( Lxy & Laz ) - >
(\forall w) (\forall u)( [ Pxzw &Pyzu]-> Lwu) ]

Exercise 6.2.11 (h)

(\forall x)[ Ox -> (\exists y)(0y & Dxy) ]

Exercise 6.2.12

• (j) (\exists x)[Pqx & Prx]

• (l) (\forall x) ¬ Pxx

Exercise 6.2.13 (b)

Prs & (\forall x)[Pxs -> Ixr]
or (\forall x)[ Pxs \biconditional Ixr ]

Exercise 6.3.6

This is an example of a recursive definition (in the spirit of Math 2320 and Math 1090). The basic idea is that the wffs are defined by an inductive or recursive process, which we can lay out in the form of a parsing tree. With this 'tree' we can define other properties, such as the free variables Free(\alpha) 'up' the parsing tree from the leaves to the root formula.
                             (Fxay v (¬Gxa -> (\forall z)Hzwb))
/      \
Fxay     (¬Gxa -> (\forall z)Hzwb)
/       \
¬Gxa   (\forall z)Hzwb
|                |
Gxa            Hzwb

The question gives instructions for defining the set Free(\alpha) up the tree from the bottom:

By 1.         Free(Gxa) = {x}  and   Free(Hzwb)={z,w}
Then:
by 2                  Free(¬Gxa) = {x} by 1.
by 4                    Free((\forall z)Hzwb) = {z,w} - {z} = {w}
Then
by  1        Free(Fxay) = {x,y}
by 3       Free((¬Gxa -> (\forall z)Hzwb)) = {x} U {w} = {x,w}
Finally by 3: Free((Fxay v (¬Gxa -> (\forall z)Hzwb))) = {x,y} U {x,w} = {x,y,w}

I have shown the steps of distinct lines. However, if I was 'solving' such a problem, I would just write out the Free set beside the formulae in the parsing tree, starting at the bottom.

Exercise 6.3.7

This is a second recursive definition in the same spirit as the previous exercise. Here is the parsing tree:

Gabc -> ¬(Fa&Hm)
/     \
Gabc        ¬(Fa&Hm)
|
(Fa&Hm)
/        \
Fa         Hm
We can now define SubWffs recursively up from the leaves of this tree:
By 1                   SubWffs(Fa) = {Fa}         SubWffs(Hm) = {Hm}
By 3     SubWffs(Fa&Hm) = {Fa&Hm} U {Fa} U {Hm} = {Fa&Hm,Fa,Hm}
By 2    SubWffs(¬(Fa&Hm)) = {¬(Fa&Hm),Fa&Hm,Fa,Hm}
By  1              SubWffs(Gabc) = {Gabc}
By 3 SubWffs(Gabc -> ¬(Fa&Hm)) =
{Gabc -> ¬(Fa&Hm), Gabc, ¬(Fa&Hm), Fa&Hm, Fa, Hm}

Again, if I were actually solving this, I would just write out the parsing tree and then work back up writing the SubWffs beside each node.

Therefore the Size is 6.


Exercise 6.3.8

• (f) [Ga -> (\exists x)Fxc]

• (h) [ Kaa v Fbac]

• (j) [(\exists x) Sx \biconditional (\exists y) Kay]

Exercise 6.3.9 (f)

(\forall y)[ (\exists x)Kxy -> Fy].

Exercise 6.3.10

• (b) (\exists y) Fabc, (\exists y) Faby.

• (d) (\exists y) (\exists x) Lxc, (\exists y) (\exists x) Lxy.

• (f) (\exists y) [ (\exists x)Kxc -> Fc], (\exists y) [ (\exists x)Kxy -> Fc],
(\exists y) [ (\exists x)Kxc -> Fy], (\exists y) [ (\exists x)Kxy -> Fy].

Exercise 6.4.3

• (b) (\exists x)[ Fxa \biconditional Fax] is T:
Faa is T and Faa is T. Therefore the biconditional Faa \biconditional Faa is T.
This gives us (\exists x)[ Fxa \biconditional Fax] is T

• (d) (\forall x)(\exists y)Fxy is F:
Consider b/x. By the definition of the truth value assignment, Fba, Fbb, Fbc, .... are all F. Therefore (\exists y)Fby is F.
One failure is enough to make (\forall x)(\exists y)Fxy to be F

• (f) (\forall x)(\exists y)Fyx is T
For any instantiation d/x, Fad is T.
Therefore (\exists y)Fyd is T for all choices of d
Therefore (\forall x)(\exists y)Fyx is T

Exercise 6.4.11 (f)

The argument is invalid.
To demonstrate this we need to offer a 'model' in which the Premise of the argument is true and the Conclusion is false.
The whole point of logic is to preserve any 'Truth' of the Premises into 'Truth' for the Conclusion!

One way to communicate the 'model' is to list the truth value assignment for the critical ground atomic sentences (for a restricted finite set of constants that appear in the formulae).

We choose a model with the universal domain labeled U = { a, b }.
We assign the following tva:
Fa is T, Fb is F, Ga is F, Gb is T.
With this choice Fa v Ga is T and Fb v Gb is T. However (\forall x)Fx is F, since Fb is F; and (\forall x)Gx is F, since Ga is F.
We conclude that (\forall x)Fx v (\forall x)Gx is F. Note: To figure out the counterexample, you actually first see what it takes to make
(\forall x)Fx v (\forall x)Gx False.
From our current work on PD+, we know that this is the same as making: ¬[(\forall x)Fx v (\forall x)Gx] T, or equivalently.
(\exists) x ¬ Fx & (\exists) x ¬ Gx True.
This suggests Fb is F and Ga is F for some a, b.
The next step is to make (\forall x)[ Fx v Gx] T.
This requires Fa v Ga is T, and since Ga is F, we must have Fa T. This also requires Fb v Gb is T, and since Fb is F, we must have Gb T.

Exercise 6.4.11 (i)

This argument is invalid. We offer a 'model' in which the Premise of the argument is true and the Conclusion is false.

We choose a model with the universal domain labeled U = { a, b }.
We assign the following tva:
Fa is T, Fb is T, Ga is T, Gb is F.
With this assignment: (\exists x)Gx is T (because of the one instantiation Gb);
Therefore Fa -> (\exists x)Gx is also T.
However, (\forall x)[Fa ->Gx] is False because of the one instantiation: [Fa ->Gb] which is F (with Fa T and Gb F).

Note: To figure out the counterexample, you actually first see what it takes to make
(\forall x)[Fa ->Gx] F: Fa T and Gb F for some b.
Then look for a way to make Fa -> (\exists x)Gx T - which now requires
(\exists x)Gx T or Gc T for some instantiation.
I chose to use a for this instantiation just to keep things small!

Exercise 6.4.12 (d)

True
A quantified formula looks like (\forall x)[ \alpha] and all parts of \alpha are in the scope of x. If \alpha has a second quantifier then the scope of this second quantifier lies inside this larger scope!

Many people thought this was false - but they were really answering (c)
The 'counterexamples' such as (\forall x)Fx v (\forall x)Gx do not have overlapping scopes but this is not a quantified formula.

Exercise 6.4.12 (l)

False
This is not a sentence since the x in Bxy is Free (not inside the scope of any quantifier with x as the variable).

Exercise 6.4.12 (n)

False
The universal generalization would be (\forall x)[Fx -> Gc].
This is different in appearance from (\forall x)Fx -> Gc.
That difference in appearance is enough to demonstrate the sentence is false, since 'universal generalization' is a syntactic operation - pure appearance!

By the way, if you think about it, in terms of models or chapter 8, the universal generalization is also different in meaning from the formula they gave. That fact is nice to know, but not relevant to this question!