# 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.

## "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.

## "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".

## "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.

## 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".

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").

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.")

## 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*.

(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".

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".

## 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:

## 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).

"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.

## 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
"every*one*" and "some*one*" 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 |

## 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!)

## Identity

Different variables don't require different objects. So (in a domain
consisting only of people), ∀*x*∀*y* *A*(*x*, *y*) means that
everyone admires everyone, not that everyone admires everyone *else*.
Similarly, ∃*x*∃*y* *A*(*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": ∀*x*∀*y*(¬*x* = *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).

## 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 ∃*x* *H*(*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*.

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.

## At least, at most, exactly

Since different variables don't require different objects, ∃*x*∃*y*(*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*:

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

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.

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*).

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.

## 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."

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.