Logic Text Chapter 10 Solutions

Chapter 10: Trees for Predicate Logic

Basic

Question {10.1}

1. A tautology. Here is my tree for it:

2. A tautology.

3. Not a tautology.

This branch stays open. We have resolved every single-use formula, and the reusable formula (∀ x)(Fx ∨ Gx) has had every name substituted into it. So, we read off the open branch the following interpretation.

D = {a,b}

And this indeed makes our original formula false. We have everything in the domain either F or G, yet it’s not the case that everything is F and it’s not the case that everything is G.

4. Is a tautology.

You need to keep an eye on the brackets in the original formula. On the left of the conditional, the (∃ x) binds the whole (Fx ⊃ p). On the right, the (∀ x) binds just the Fx, and (∀ x)Fx is the antecedent of the whole conditional (∀ x)Fx ⊃ p.

The question in the text book contains an error. The question should have been to test the formula (∃ x)(Fx ⊃ p) ≡ ((∀ x)Fx ⊃ p). This is also a tautology. The tree is:

This one was quite difficult. You need to keep an eye on the brackets in the original formula. On the left of the biconditional, the (∃ x) binds the whole (Fx ⊃ p). On the right, the (∀ x) binds just the Fx, and (∀ x)Fx is the antecedent of the whole conditional (∀ x)Fx ⊃ p.

Then on the right branch we needed to substitute into the negated existential twice to get it to close.

We could have done it after processing (∀ x)Fx ⊃ p, and this would have resulted in a tree with fewer substitutions. The right branch would have been:

There’s something tricky going on here. The name `a’ gets introduced in the right branch with the ~(∀ x)Fx. Then we substitute the name into the negated existential at the top of the tree here. The result, ~(Fa ⊃ p), gets placed in both branches below it. In one, `a’ is already there, and in the other, `a’ is new. This is permissible, according to our rules.

5. Is a tautology.

6. Is a tautology.

7. Is a tautology. The `p’ here is just a basic proposition.

8. Is a tautology.

9. Is a tautology.

10. Is a tautology.

Question {10.2}

The arguments 1, 4 and 5 are valid. The rest are not.

1. Valid:

2. Invalid.

We’ve substituted every name into each universal quantifier, and the only formulae left to process have the form Lcd ⊃ .., where c and d are each replaced by either a and b. Note that there is nothing in this branch which compels us to take any formula of the form Lcd as true. The only results we have are that Mab is true and Mba false. Each of the conditionals Lcd ⊃ … will be true if the antecedent is false. Therefore we can construct the following interpretation:

D = {a,b}

The values for Maa and Mbb are arbitrary. Any will do. This makes the premises true and the conclusion false, as you can see.

3. Invalid.

This tree is like the first infinite tree example we’ve seen. The premise (∀ x)(∃ y)Lxy on its own will generate the infinite branch. We will therefore use the names a1, a2, a3 … to keep track of the pattern.

You can see the pattern.

If we take each name to name one object only, we get the following domain D = {a1, a2, a3, a4, a5, a6, a7, a8 …}

And L works like this. L relates object number n to object (2 x n), and it doesn't relate object n to object (2 x n) + 1. So, a4 gets related to a8, and not to a9. a5 gets related to a10 and not to a11. And so on.

This will obviously make (∀ x)(∃ y)Lxy true (object n is related to object (2 x n). And (∃ x)(∀ y)Lxy is false. There is no object which is related to everything. Object n is not related to object (2 x n) + 1. Here’s the table, for those who like thinking in pictures:

Now: Let’s see what we know about these objects, to see whether we can make a smaller interpretation.

a2 can’t be the same as a3, and a4 can’t be the same as a5, and a6 can’t be the same as a7, because of the 1s and 0s in each row. However, that is all that we can’t do. a1 can be the same as anything, as there’s nothing in the a1 column, and the a1 row doesn’t clash with any row.

Now: a2 can be the same as a4, which can be the same as a6, etc… Similarly, a3 can be the same as a5, which can be the same as a7, etc… So, let the odd-numbered names all name one object, and the even-numbered names name another.

Compressing the table, you get:

As b is named by a1, a3, a5, etc… b can’t be related to itself (as a1 isn’t related to a3), but b is related to c, as a1 is to a2. Similarly, c isn’t related to b (a2 isn’t related to a5) but c is related to itself (a2 is related to a4).

This makes the premise true: (∀ x)(∃ y)Lxy — Everything is related to something (everything is related to c). However, there isn’t something related to everything (nothing is related to b).

4. Is valid.

The tree is very much longer if you don’t do the substitutions I did here (or ones very much like them). To do this, you need to think about how the reasoning goes. Down to the line I marked (*), it is completely automatic, using the edict “do particular rules before general ones”. Then you must make the first substitution into a universal quantifier. I picked the formula (∀ x)(∀ y)(Lxy ⊃ Lyx) because I saw that I could substitute a for x and b for y to get Lab ⊃ Lba. I knew I had Lab, and this would give me new and interesting information: Lba. Then our facts are Lab, Lba and ~ Laa. This then is inconsistent with the other premise: (∀ x)(∀ y)(∀ z)((Lxy & Lyz) ⊃ Lxz) when you substitute a, b and a for x, y, and z, respectively. So, they were the substitutions I made, and that closed the tree.

If you just did any substitutions you liked, in any order, the tree would still close (if you applied the rules correctly.) It would just have been much longer.

5. Is valid too.

Notice that the premise (∀ x)(∀ y)(∀ z)((Lxy & Lyz) ⊃ Lxz) is completely irrelevant to the proof. We got the tree to close without it. I didn’t substitute a into (∀ y)(Lby ∨ Lyb) in this proof as it would just have given us Lba ∨ Lab, and we already had Lab ∨ Lba on an earlier line. Similarly, I didn’t branch the disjunctions until I knew I could use them to close one disjunct. That way the tree remained reasonably manageable.

Question {10.3}

Arguments 1, 6, 7, 8, 9 and 10 are valid, in the way that I formalised them in the solutions to {8.4}. The rest are not. I will present trees for the valid ones and just small interpretations for those which are not.

1. Lb, Rb, therefore Lb & Rb. That’s obviously valid.

2. (∃ x)Lx, (∃ x)Rx, therefore (∃ x)(Lx & Rx) . Invalid.

D = {a, b}

3. (∀ x)(Sx ⊃ (∃ y)(Ly & Oxy)) therefore (∃ y)(Ly & (∀ x)(Sx ⊃ Oxy))

Invalid.

D = {a, b, c, d}

a and b are solids, c and d are liquids, a dissolves in c, and b in d. So each solid dissolves in some liquid. However, there’s no liquid such that each solid dissolves in it.

4. (∀ x)(Ex ⊃ (Sx ∨ Ax)), Ea therefore Sa & Aa

Invalid.

D = {a}

Ian is a secretary but not and administrator. He’s eligible for the clean desk prize.

5. (∀ x)Mx, therefore (~(∃ x)Mx ∨ ((∃ x)(Mx & Tx) & (∀ x)(Tx ⊃ Mx))) & ~(~(∃ x)Mx & ((∃ x)(Mx & Tx) & (∀ x)(Tx ⊃ Mx)))

D = {a}

Invalid.

(∀ x)Mx is obviously true. However, the conclusion is false as ~(∃ x)Mx is false, and so is (∃ x)(Mx & Tx).

6. (∃ x)(Mx & (∀ y)((My & ~ Syy) ⊃ Sxy)) therefore (∃ x)(Mx & Sxx)

This is valid:

7. (∀ x)(Hx ⊃ Ax), therefore (∀ x)((∃ y)(Hy & Oxy) ⊃ (∃ y)(Ay & Oxy))

This is valid:

8. (∀ x)(∀ y)((Rxy & Py) ⊃ Nx), ~(∃ x)(Nx & Fx), (∀ x)(∀ y)((Rxy & (Ny & ~ Py)) ⊃ ~ Fx), therefore (∀ x)(∀ y)((Rxy & Ny) ⊃ ~ Fx)

This is valid:

9. ~(∃ x)(Px & Cx) ⊃ (∃ x)(Px & Dx), therefore (∃ x)(Px & (~ Cx ⊃ Dx))

This is valid, surprisingly!

Why is it valid? Well, if ~(∃ x)(Px & Cx) ⊃ (∃ x)(Px & Dx) is true, then either someone contributes to Oxfam or someone dies. If someone contributes to Oxfam then that person is someone who will die if she doesn’t. (Why is this true? Because of the material conditional! It is true if the antecedent is false.) On the other hand, if someone dies, then that person is someone who will die if she doesn’t contribute to Oxfam. (Why is this true? Because of the material conditional! It is true if the consequent is true.)

10. ~(∃ x)(Ax & ~ Kx), (∀ x)(Gx ⊃ Ix), ~(∃ x)(Ix & Kx) therefore (∀ x)(Gx ⊃ ~ Ax).

{I have treated “no-one” as “nothing” here.}

This is valid.

Questions {10.4}

1.

a = PS

Sx = x is an axiomatic system.

Txy = x is a theorem of y.

Ox = x is a tautology.

Vx = x is a variable.

Cx = x is post-consistent.

Sa, (∀ x)(Txa ⊃ Ox), ~(∃ x)(Vx & Ox), (∀ x)((Sx & ~(∃ y)(Vy & Tyx)) ⊃ Cx), therefore Ca

This is valid.

With this argument, (as with the others) it is helpful to keep in mind what each name stands for. The name ’a’ names PS. It’s a system. The name ’b’ names a propositional variable which is a theorem of PS. So that is the sensible thing to substitute into the second and third premises, not a.

2.

p = Every decision is to be referred to the central authority.

Px = x is a program.

Dx = x is delayed.

Ax = x receives approval.

p ⊃ (∃ x)(Px & Dx), (∀ x)(Px ⊃ Ax), ~(∃ x)(Dx & Ax), therefore ~ p.

It is possible to expand p as follows:

Cx = x is a decision

Rx = x is to be referred to the central authority,

and p is then (∀ x)(Cx ⊃ Rx).

But this plays no role in the argument.

It is valid either way. Here is the tree for when we use ’p’.

3.

Tx = x is true.

Fx = x is false.

Kxy = x knows y.

Px = x is a person.

j = John.

(∀ x)(Tx ⊃ ~ Fx) & (∀ x)(~ Fx ⊃ Tx), (∀ x)(Fx ⊃ ~(∃ y)(Py & Kyx)), (∃ x)(Kjx) & Pj Therefore (∃ x)Tx.

This is valid. Consider the following tree:

The tree is quite short, when you know what substitutions to make, to make things close.

Question {10.5}

For each of these we need to find a counterexample to the arguments. One way to do this is to do a tree for each and read off the counterexample

Here are some suggestions:

(1) To show that reflexivity and symmetry does not produce transitivity:

Let the domain be {a,b,c}

and R is interpreted as:

In this interpretation the premises are true and the conclusion is false.

See if you can think of a way of determining whether a relation is reflexive, symmetry or transitive at a mere glance of its table.

(2) To show that reflexivity and transitivity does not produce symmetry:

Let the domain be {a,b}

and R is interpreted as:

In this interpretation the premises are true and the conclusion is false.

(3) To show that symmetry and transitivity does not produce reflexivity:

Let the domain be {a}

and R is interpreted as:

In this interpretation the premises are true and the conclusion is false.

Question {10.6}

This is the tree for the argument (∀ x)(∀ y)(Rxy ⊃ Ryx), (∀ x)(∀ y)(∀ z)((Rxy & Ryz) ⊃ Rxz), (∀ x)(∃ y)Rxy therefore (∀ x)Rxx.