User:Gert

Quantification

---

For the following exercises, assume the existence of a model with the universe of discourse below:

U = { cat1,cat2,cat3,dog1,dog2,dog3 }

Now do the following exercises about the interpretation function I of the model.

Exercise 1 For I(cat¹) and I(lilly), specify one plausible value each so that the formula cat¹(lilly) becomes true in M.

Check your answer

I(cat¹) = {<cat1>,<cat2>,<cat3>}

For I(lilly), each of the following 3 values will now make cat¹(lilly) true in M:
a. I(lilly) = cat1 , or
b. I(lilly) = cat2 , or
c. I(lilly) = cat3 .

We prove this for case (b):

1. [[cat¹(lilly)]]^M = 1 iff <[[lilly]]^M> ∈ I(cat¹)
2. iff <I(lilly)> ∈ I(cat¹)
3. iff <cat2> ∈ {<cat1>,<cat2>,<cat3>}

Hence: since (3) is the case, so are (2) and the righthand side of (1). Finally, since the righthand side of (1) is the case, the lefthand side is the case as well. Hence [[cat¹(lilly)]]^M is true in model M. That is what we intended to prove!

Exercise 2 Assume that I(cat¹) = {<cat1>,<cat2>,<cat3>}. What values of I(lilly) would make the formula ¬cat¹(lilly) true in M?

Check your answer

For I(lilly), each of the following 3 values will make ¬cat¹(lilly) true in M.:
a. I(lilly) = dog1 , or
b. I(lilly) = dog2 , or
c. I(lilly) = dog3.

We prove this for case (a):

1. [[¬cat¹(lilly)]]^M = 1 iff [[cat¹(lilly)]]^M = 0
2. iff <[[lilly]]^M> ∉ I(cat¹)
3. iff <I(lilly)> ∉ I(cat¹)
4. iff <dog1> ∉ {<cat1>,<cat2>,<cat3>}.

Hence: since (4) is the case, so are (3), (2), and the righthand side of (1). Finally, since the righthand side of (1) is the case, the lefthand side is the case as well. Hence [[¬cat¹(lilly)]]^M is true in model M. That is what we intended to prove!

Exercise 3 Look at the following English sentences:

i. Every cat is an animal.
ii. Every dog is an animal.
iii. Every animal is either a dog or a cat.
iv. No cat is a dog.

Suppose that for each of these sentences we have a formula of first order logic with the same meaning as the sentence. Assume furthermore that cat¹, dog¹, and animal¹ are predicates in the logical language.

Without specifying precise logical formalae at this point, give plausible values of I(cat¹), I(dog¹), and I(animal¹) that will make the logical formulae corresponding to the 4 English sentences above true in M.

Check your answer

I(cat¹) = {<cat1>,<cat2>,<cat3>}
I(dog¹) = {<dog1>,<dog2>,<dog3>}
I(animal¹) = {<cat1>,<cat2>,<cat3>,<dog1>,<dog2>,<dog3>}

Note that I(animal¹) = I(cat¹) ∪ I(dog¹).

Exercise 4 Assume a model M = <U,I> as described below:

U = {cat1,cat2,cat3,dog1,dog2,dog3}

I(lilly) = cat1
I(fido) = dog2
I(cat¹) = {<cat1>,<cat2>,<cat3>}
I(dog¹) = {<dog1>,<dog2>,<dog3>}
I(animal¹) = {cat1,cat2,cat3,dog1,dog2,dog3}

a. What has to be true of I(likes²) if the formula likes²(lilly,fido) is true in M and the formula likes²(fido,lilly) is false in M?

Check your answer

The pair <cat1,dog2> is a member of I(likes²), whereas the pair <dog2,cat1> is not a member of I(likes²).

b. What has to be true of I(likes²) if the formula corresponding to the English sentence Lilly likes a dog. is true in M?

Check your answer

At least one of the pairs <cat1,dog1>, <cat1,dog2>, <cat1,dog3> is a member of I(likes²).

c. What has to be true of I(likes²) if the formula corresponding to the English sentence Lilly likes every dog. is true in M?

Check your answer

All the pairs <cat1,dog1>, <cat1,dog2>, <cat1,dog3> are members of I(likes²).

d. What has to be true of I(likes²) if the formula corresponding to the English sentence Every cat likes every dog. is true in M?

Check your answer

All the pairs <cat1,dog1>, <cat1,dog2>, <cat1,dog3>, <cat2,dog1>, <cat2,dog2>, <cat2,dog3>, <cat3,dog1>, <cat3,dog2>, <cat3,dog3> are members of I(likes²).

e. What has to be true of I(likes²) if the formula corresponding to the English sentence There is some cat which likes every dog. is true in M?

Check your answer

Either the three pairs <cat1,dog1>, <cat1,dog2>, <cat1,dog3> are members of I(likes²) or the three pairs <cat2,dog1>, <cat2,dog2>, <cat2,dog3> are members of I(likes²), or the three pairs <cat3,dog1>, <cat3,dog2>, <cat3,dog3> are members of I(likes²).

f. What has to be true of I(likes²) if the formula corresponding to the English sentence Some cat likes some dog. is true in M?

Check your answer

One of the pairs <cat1,dog1>, <cat1,dog2>, <cat1,dog3>, <cat2,dog1>, <cat2,dog2>, <cat2,dog3>, <cat3,dog1>, <cat3,dog2>, <cat3,dog3> is a member of I(likes²).

g. What has to be true of I(likes²) if the formula corresponding to the English sentence A cat likes a dog and a dog likes a cat is true in M?

Check your answer

Note that the sentence does not require that the cats and the dogs in the two relationships are the same. Hence:

There are a and b ∈ {cat1, cat2, cat3} and there are c and d ∈ {dog1, dog2, dog3} such that
<a,c> and <d,b> are both members of I(likes²).

h. What has to be true of I(likes²) if the formula corresponding to the English sentence There is a cat and there is a dog for whom
it is true that the cat likes the dog and the dog likes the cat is true in M?

Check your answer

This time the cat and the dog have to be the same. Hence:

There is an a ∈ {cat1, cat2, cat3} and there is a c ∈ {dog1, dog2, dog3} such that
<a,c> and <c,a> are both members of I(likes²).

i. What has to be true of I(likes²) if the formula corresponding to the English sentence Every cat likes herself is true in M?

Check your answer

All the pairs <cat1,cat1>,  <cat2,cat2>, and <cat3,cat3> are members of I(likes2).

Exercise 5 Translate the following English sentences into first order predicate logic. Give what you think is the most likely reading of the English sentence.

a. Lucy is a student.	

Check your answer

student(lucy)

b. Lucy knows a student.

Check your answer

∃x(student(x) : know(lucy,x))

c. Every student likes linguistics.

Check your answer

∀x (student(x) : like(x,linguistics))

d. Not every student likes linguistics.

Check your answer

¬∀x(student(x) : like(x,linguistics))

e. If every student likes linguistics, then Lucy likes linguistics.

Check your answer

∀x(student(x) : like(x,linguistics)) ⊃ like(lucy,linguistics)

f. Some student does't like linguistics.

Check your answer

∃x(student(x) : ¬like(x,linguistics))

g. Not one student likes linguistics.

Check your answer

¬∃x(student(x) : like(x,linguistics))

h. Every smart student takes linguistics.

Check your answer

∀x((student(x) ∧ smart(x)) : take(x,linguistics))

i. No smart student gives a bad presentation.

Check your answer

¬∃x((student(x) ∧ smart(x)) : ∃y((presentation(y) ∧ bad(y)) : give(x,y)))

j. Every student likes an interesting presentation.

Check your answer

∀x(student(x) : ∃y((presentation(y) ∧ interesting(y)) : like(x,y)))

k. One presentation intrigued every student but that presentation did not intrigue any professor.

Check your answer

∃x(presentation(x) : (∀y(student(y) : intrigue(x,y) ∧ ¬∃z(professor(z) : intrigue(x,z)))))

l. For every student there is a professor that this student does not like.

Check your answer

∀x(student(x) : ∃y(professor(y) : ¬like(x,y)))

m. Some student does not like any professor.

Check your answer

∃x(student(x) : ¬∃y(professor(y) : like(x,y)))

n. Not every student likes a professor.

Check your answer

¬∀x(student(x) : ∃y(professor(y) : like(x,y)))

o. A professor likes every student who likes linguistics.

Check your answer

∃x(professor(x) : ∀y((student(y) ∧ like(y,linguistics)) : like(x,y)))

p. A professor likes every student who gives a good presentation.

Check your answer

∃x(professor(x) : ∀y((student(y) ∧ ∃z((presentation(z) ∧ good(z)) : give(y,z)) : like(x,y))

q. Some professor who smokes likes no student who smokes.

Check your answer

∃x((professor(x) ∧ smoke(x)) : ¬∃y((student(y) ∧ smoke(y)) : like(x,y)))

r. A professor who smokes likes every student who does not smoke.

Check your answer

∃x((professor(x) ∧ smoke(x)) : ∀y((student(y) ∧ ¬smoke(y)) : like(x,y)))

s. Every student likes herself.

Check your answer

∀x(student(x) : like(x,x))

t. One student does not like herself.

Check your answer

∃x(student(x) : ¬like(x,x))

u. No student likes herself.

Check your answer

¬∃x(student(x) : like(x,x))

v. Not every student likes herself.

Check your answer

¬∀x(student(x) : like(x,x))

w. Lucy likes herself.

Check your answer

like(lucy,lucy)

x. One student knows a professor who does not know him.

Check your answer

∃x(student(x) : ∃y((professor(y) ∧ ¬know(y,x)) : know(x,y)))