Practice Problems: FOL Symbolization

The following are some practice problems on symbolization in FOL; i.e., they cover Part V of forall x: Calgary.

To enter logical symbols on the keyboard, use:

not ¬ -, ~
and ∧ /\, &
or ∨ \/
if then → ->, >
if and only if ↔︎ <->, <>
contradiction ⊥ !?, _|_
universal quantifier ∀ A, @
existential quantifier ∃ E, 3

We'll use the symbolization key from lecture:

domain: people

H(x) x is a hero g Greta
V(x) x is a villain a Autumn
C(x) x wears a cape
I(x) x inspires
A(x, y) x admires y
Y(x, y) x is younger than y

Single quantifiers

"Some"

The determiner "some" (usually) indicates existence. In FOL, it is (again, usually) symbolized using the existential quantifier x.

"Some hero wears a cape" (and also the plural "Some heroes wear capes"!) say that there is at least one x which is both a hero and wears a cape.

V.1
Some hero wears a cape.

"Every", "All"

The determiners "every" and "all" indicate a general claim. In FOL, it is (again) symbolized using the universal quantifier x.

"Every hero wears a cape" (and also the plural "All heroes wear capes") say that for every x, if x is a hero, x also wears a cape.

V.2
Every hero wears a cape.

"No"

The determiner "no" works like "all" and "every", except where "All Ps are Qs" says of every x that if it is P, then it is also Q, "No Ps are Qs" says of every x that if it is P, it cannot be Q. In other words, you can symbolize "No heroes wear capes" the same way you would "Every hero does not wear a cape".

A bit of reflection shows that "No hero wears a cape" is the denial (negation) of "Some heros do wear capes". So we can also symbolize it as the negation of the symbolization of "Some heroes wear capes".

V.3
No hero wears a cape.

"Only"

"Only" is to "every" as "only if" is to "if". While "All heroes wear capes" says that for every x, x wears a cape if x is a hero, "Only heroes wear capes" says that for every x, x wears a cape only if x is a hero.

V.4
Only heroes wear a cape.

Mix and match

The above basic symbolizations already take us quite far. There are two ways we can extend them to more complex sentences. One way of making a sentence more complex is by involving sentence connectives like negation, "or", "and", "neither nor", etc. For instance, "Not all heroes wear capes" can be symbolized by putting a ¬ in front of the symbolization of "All heroes wear capes".

V.5
Not all heroes wear capes.
V.6
Either all heroes wear capes, or none do.

Another way is to make make the restriction on the determiner and/or the property ascribed more complicated. E.g., to symbolize "All heroes admired by Greta either don't inspire or wear a cape" we have to express the restriction "x is a hero admired by Greta" using what we know from TFL (in this case, we use a conjunction: "H(x) ∧ A(g, x)"), and do the same with "either x doesn't inspire or x wears a cape").

V.7
All heroes admired by Greta either don't inspire or wear a cape.

Coordination with "and" can become tricky in FOL. For instance, if you want to symbolize "All heroes and villains admire Greta" you'll notice that x((H(x) ∧ V(x)) → A(x, g)) doesn't work. This says "Everyone who is both a hero and a villain admires Greta." But what you want to say is that everyone who is either a hero or a villain admires Greta. (Alternatively, think of it as "All heroes admire Greta, and all villains do as well.")

V.8
All heroes and villains admire Greta.

Expressing properties

Formulas with a free variable like H(x) express properties (in this case, the property of being a hero), and formulas with two free variables express relations (e.g., Y(x, y) is the relation of being younger than). These can be combined to express properties and relations that you don't have predicates for in your symbolization key. I(x) ∧ H(x), say, expresses the property of being an inspiring hero, and that is why we symbolize "Every inspiring hero wears a cape" by x((I(x) ∧ H(x)) → C(x)). But in some cases, the symbolization is less obvious. For instance, if you want to symbolize "All villains are older than Greta," you'll have to express the relation "x is older than y", for which there is no predicate in the symbolization key. However, there is a predicate for y is younger than x, and x is older than y if and only if y is younger than x.

V.9
All villains are older than Greta.
V.10
Greta is the same age as some villain.

(Hint: two people are the same age if and only if neither is younger than the other.)

The indefinite article "a", "an"

The indefinite article sometimes works like an existential determiner, and sometimes like a universal.

"Greta admires a hero" says that there is a hero whom Greta admires, so it can be symbolized the same way as "Some heroes are admired by Greta".

V.11
Greta admires a hero.

But note that "If someone is a hero, Greta admires them" doesn't say that: rather, it says the same as "All heros are admired by Greta".

V.12
If someone is a hero, Greta admires them.

Anything, any

"Anything", "anyone", and "any" are determiner that sometimes call for an existential and sometimes a universal quantifier in the symbolization. Compare the following:

V.13
Any hero admires Greta.
V.14
If any hero admires Greta, Autumn does.

Mixed quantifiers

If the sentence you have to symbolize contains more than one determiner, you have to proceed in steps. E.g., "All heroes are younger than a villain" says that every hero has the property of being younger than a villain. And the property of being younger than a villain can be expressed by y(V(y) ∧ Y(x, y) (i.e., x is younger than a villain iff there is some villain that x is younger than).

V.15
Ax(H(x) -> x is younger than a villain)

"Some hero who is younger than a villain wears a cape", on the other hand, says that someone is a hero, satisfies "x is younger than a villain," and wears a cape.

V.16
Ex((H(x) /\ x is younger than a villain) /\ C(x))

Mixed domains

You'll have noticed that "x wears a cape" contains a determiner phrase, "a cape." So if our domain contains capes as well as people, and our symbolization key contains E(x) for "x is a cape" and R(x, y) for "x wears y" we can express the property "x wears a cape" by y(E(y) ∧ R(x, y)). However, to symbolize "everyone" and "someone" now also requires a predicate for "x is a person."

domain: people, items of clothing

H(x) x is a hero g Greta
V(x) x is a villain a Autumn
P(x) x is a person
E(x) x is a cape
I(x) x inspires
A(x, y) x admires y
Y(x, y) x is younger than y
R(x, y) x wears y
B(x, y) x belongs to y
V.17
Ax(P(x) -> x wears a cape)

Donkey sentences

Some sentences in which a pronoun refers to an embedded determiner phrase are hard to symbolize. "Every hero who admires someone is younger than they are" is an example: "they" refers to "someone". It is false if and only if some hero admires someone but isn't younger than them. Alternatively, you can think of it as saying that every hero is younger than anyone they admire. (Remember to restrict the "everyone" determiner to people!)

V.18
Every hero who admires someone is younger than they are.

Identity

Different variables don't require different objects. So (in a domain consisting only of people), xyA(x, y) means that everyone admires everyone, not that everyone admires everyone else. Similarly, xyA(x, y) doesn't mean that someone admires someone else: it is true if someone admires themselves. The identity predicate can be used to symbolize the "else": xyx = y → A(x, y)) is true if everyone satisfies "x admires everyone who is not x". Let's try this out with "Someone admires everyone else," but now also use P(x) to restrict "everyone" and "someone" to people (i.e., say that every person admires every person different from them).

V.19
Someone admires everyone else.

Uniqueness, singular only

To say that someone is a hero is to say that at least one person satisfies H(x), and so can be symbolized by xH(x). To say that there is exactly one hero is to say that there is a person who satisfies H(x), and noone else is a hero. To say "noone other than x is a hero" is to say that no hero exists who is different from x.

V.20
There is exactly one hero.

The same idea can be used to symbolize sentences containing singular "only". We already know how to symbolize plural "only" as in "only heroes". But what about "Only Greta is a hero"? That says that Greta is a hero, and noone other than Greta is also a hero.

V.21
Only Greta is a hero.

At least, at most, exactly

Since different variables don't require different objects, xy(H(x) ∧ H(y)) does not say that there are at least two heroes. It just says that someone is a hero, and someone is a hero, which is true if only one person is a hero. If you want x and y to be different you have to include ¬x = y:

V.22
There are at least two heroes.

This lets us say that there is at most one hero: we simply deny that there are at least two.

V.23
There is at most one hero.

Another way of symbolizing this would be to say that if x and y are heroes, x and y are the same.

But what about "there are at most two heroes"? For this, we have to deny that there are at least three heroes. This requires three x, y, z and we have to say that any two of x, y, z are different. In other words, ¬x = y ∧ ¬y = z is not enough.

V.24
There are at least three heroes.

To say that there are at most two heroes, put an ¬ in front of your symbolization of "There are at least three heroes." Alternatively, think of it this way: Of any heroes x, y, z, at least two have to be the same (i.e., x = y or x = z or y = z).

V.25
There are no more than two heroes.

We already know how to say that there is exactly one hero: some x is a hero, and there is no y that's different from x and also a hero. To say there are exactly two heroes is to say both that there are at least two and that there are at most two. Alternatively, think of it this way: there are two different heroes, and any hero is one of them.

V.26
There are exactly two heroes.

The, both, neither, singular possessives

The definite article "the" is used to form determiner phrases called definite descriptions, such as "the hero" or "the youngest villain". We use definite descriptions grammatically the same way we use indefinite descriptions ("a hero") or quantifiers ("all heroes", "no villains"). How do we symbolize them?

According to Russell's analysis of definite descriptions, a sentence conatining a definite description, "The A is B", should be symbolized so that it is true iff (a) exactly one thing is A and (b) that thing is also B. One way of doing that is to symbolize it as

x[(A(x) ∧ ∀y(A(y) → x = y)) ∧ B(x)]

Definite descriptions can be used also to symbolize singular possessives. E.g., "Autumn wears Greta's cape" can be paraphrased as "Autumn wears the cape that belongs to Greta."

V.27
Autumn wears Greta's cape.

Russell's idea can also be used to deal with "both" and "neither", used not as sentence connectives (as in "Neither Autum nor Greta are villains") but as determiners "Neither villain is younger than Greta". That sentence is true iff (a) there are exactly two villains and (b) each of them is not younger than Greta.

V.28
Neither villain is younger than Greta.