These exercises are to guide your studying and initial work with first-order logic – chapter 8 from AIMA, our text.
I find it useful to use a sort of iterative approach: I’ll read a text and only understand bits of it. I think about a couple of the basic things, understand them, and then leave it. I come back to it later, re-read, and get just a little bit further. And so on.
Intersperse that with looking for other resources. Perhaps some passage in the text is really hard to understand. Do a bit of searching and see if you can find somewhere else that explains the same thing but in a different way that helps you understand.
At some point, you – as a CS student – ought to feel compelled to write a bit of code to aid your studying, either to verify a calculation, or see if you understand an algorithm. This is another element of your iteration.
Just keep iterating with those until you’re certain you have a good understanding.
Work through these exercises to guide your studying and in preparation for our next class. Combine it with reading chapter 8. You already know propositional logic; first-order logic (FOL) adds objects, relations among them, and quantifiers that say “for all” and “there exists.”
Work through Parts 1–7. Commit to an answer before you check anything, even if you’re guessing. Write in pen, or mark your first answer so you can see what changed.
Then read §8.1–8.2 of the textbook. Part 8 tells you what to look for. (They get into the weeds with ontology and such; you can ignore that for now.)
Go back and revise any answers the reading changed. Changed answers are good: they show you what you learned.
You don’t need to know any official definitions yet. Use common sense and the world described in Part 1.
One question the reading raised for you, or one answer on this worksheet you’re still unsure about.
We will start with some translations between FOL and ordinary language.
In a 4 by 4 wumpus world, the rule “the player perceives a breeze in a square adjacent to a pit” requires 16 PL sentences. Similar for the gold and glittering, the wumpus and smelly squares, and so on.
Writing all those down is a pain, right? And searching through such a large KB is going to be slow, right?
The first advantage of FOL: more efficient representation. In first-order logic, we only need one single sentence that is a direct translation of the rule above: something like
For all squares, if s has a pit, the player will perceive a breeze in any square adjacent to s.
and things like
If the player perceives a breeze in a square s, there exists a square t such that s and t are adjacent and t has a pit.
Or in FOL syntax:
∀ s ∀ t Pit(s) ∧ Adjacent(s, t) ⇒ Breeze(t)
and
∀ s Breeze(s) ⇒ ( ∃ t (Adjacent(s, t) ∧ Pit(t) )
One sentence for all the squares. Fewer sentences overall mean that our inference runs more efficiently.
Most questions on this worksheet are about one small world, the Dorm Floor. It contains exactly six objects: four people and two pets. Nothing else exists in it.
| Symbol | Kind | What it means | True of / holds for |
|---|---|---|---|
| Ada, Ben, Cy, Dot, Rex, Tab | constants | names for the six objects | — |
| Person(x) | predicate | x is a person | Ada, Ben, Cy, Dot |
| Dog(x) | predicate | x is a dog | Rex |
| Cat(x) | predicate | x is a cat | Tab |
| Bird(x) | predicate | x is a bird | nothing |
| Owns(x, y) | predicate | x owns y | (Ada, Rex), (Ben, Tab) |
| Likes(x, y) | predicate | x likes y | (Ada, Rex), (Ada, Tab), (Ben, Tab), (Cy, Rex), (Cy, Ada), (Dot, Ada) |
| Roommate(x) | function | x’s roommate | Ada → Ben, Ben → Ada, Cy → Dot, Dot → Cy |
If a pair is not listed, the relation doesn’t hold. For example, Rex likes nobody. We’ll only apply Roommate to people. (Technically, an FOL function has to give back something for every object. AIMA discusses this in §8.2.2; ignore it for now.)
Quick checks. Write T or F, or the object asked for.
In propositional logic, every symbol was true or false. FOL has two kinds of expressions:
Predicates and connectives (∧, ∨, ¬, ⇒) build sentences. Functions
build terms. In Python terms: a function like roommate(x)
returns a person, while a predicate like is_dog(x) returns
a bool.
For each expression, write term, sentence, or broken (not a legal expression). For terms, name the object. For sentences, say T or F.
For each broken one, explain in a few words what went wrong.
A quantifier checks a sentence for objects in the world. Because the Dorm Floor has only six objects, you can check by looping over all of them:
domain = ["Ada", "Ben", "Cy", "Dot", "Rex", "Tab"]
# ∀x P(x) "for every x, P(x)"
all(P(x) for x in domain)
# ∃x P(x) "there exists an x such that P(x)"
any(P(x) for x in domain)The variable x is like a loop variable: it takes each object in turn. ∀ succeeds only if every object passes; ∃ succeeds if at least one does.
Write T or F for each sentence. For ∃, name an object that makes it true. For ∀, name an object that makes it false (a counterexample).
likes(a, b).This is the most common FOL mistake, so slow down here. Remember that the loop visits every object in the world, including ones the English sentence isn’t “about.”
English: “Cy likes every dog.” Two students offer:
Trace (A) through the loop. What happens when x = Ada? Is (A) true or false in the Dorm Floor?
Trace (B). What happens when x = Ada? When x = Rex? Is (B) true or false?
Does Cy like every dog in this world? Which of (A) or (B) says what the English says?
English: “Cy likes some cat.” Two students offer:
Is (C) true or false? Which objects did you need to check?
Is (D) true or false? Find an x that makes Cat(x) ⇒ Likes(Cy, x) true. (Recall from propositional logic when P ⇒ Q is true.)
Does Cy like some cat in this world? Which of (C) or (D) is right, and why is the other one far too easy to make true?
Fill in the rule of thumb: ∀ usually goes with ______, and ∃ usually goes with ______.
Two quantifiers in a row work like nested loops: the first quantifier is the outer loop. Here are two sentences that use the same symbols in a different order:
Here is (E) as Python. The inner any restarts for each
x, so each person can pick a different y.
all((not person(x)) or any(likes(x, y) for y in domain)
for x in domain)Say (E) in plain English.
Is (E) true in the Dorm Floor? For each person, name someone or something they like.
Write (F) as Python in the same style. Which loop is on the outside now?
Say (F) in plain English. How is it different from (E)?
Is (F) true in the Dorm Floor? If not, explain why each possible y fails.
Challenge: What is the smallest number of new Likes facts you could add to the world to make (F) true? Which facts?
Negation. Consider this sentence:
Say (G) in plain English. Is it true in the Dorm Floor? Which objects make it so?
Which of these means the same as (G)? Test each one in the world.
Complete the pattern: ¬∀x P is equivalent to ______, and ¬∃x P is equivalent to ______. What law from propositional logic does this remind you of? (Hint: think of ∀ as a giant ∧ over all the objects.)
Empty cases. There are no birds in the Dorm Floor.
FOL has a built-in symbol, =, meaning “is the same object as.” So Roommate(Cy) = Dot is true. Two different variables can still refer to the same object unless you rule it out.
Translate into FOL, then say whether it’s true in the Dorm Floor: “Every dog has an owner.”
Translate back into natural English (not “for all x, if x is…”), then say whether it’s true: ∀x (Person(x) ⇒ ∃y (Cat(y) ∧ Likes(x, y)))
A student writes “At least two people like Tab” as ∃x ∃y (Likes(x, Tab) ∧ Likes(y, Tab)). Describe a world where only one person likes Tab but this sentence is still true. Then fix the sentence.
Challenge: Translate “Only Ada owns Rex.” Hint: it says two things. Ada owns Rex, and anything that owns Rex must be ______.
As you read, look for these. Jot a sentence or two for each.
Models. In propositional logic, a model was one row of a truth table. How does AIMA describe a model for FOL? How is the Dorm Floor table an example of one?
Terms and functions. Find AIMA’s explanation of why functions must be total. What does it suggest doing about something like “the left leg of a crown”?
Quantifiers. Find the passage where AIMA warns about ∧ and ⇒. Compare it to your answers in Part 4, and revise if needed. 4. Equality. Find AIMA’s example about Richard having two brothers. How does it connect to Part 7, question 3?
You’ll need some predicates for “this square has a pit”, “the player perceives a breeze in this square”, and similar for the stench.
Write the rules for pits, breezes, and the stench.
There is a wumpus in exactly one square. Write that in FOL. Use the above “only Ada owns Rex” for inspiration for the “only one square” part.
Write the rule for the gold and glitter percept.
That’s enough for now – handling the arrow and killing the wumpus requires some notion of time, which leads into the text’s notion of temporal logic.