Problem Set for Tutorial 1 — TDDD08∗
Victor Lagerkvist†1
1
Department of Computer and Information Science, Linköping University, Linköping, Sweden
1 Syntax of First-Order Logic
1.1 Exercise
Which of the following expressions are well-formed formulas in first-order logic?
1. ∀x(p(x) → q(x)) where p and q are predicate symbols. Yes.
2. p(x) → q(x) where p and q are predicate symbols. Yes.
3. ∃x(p(f (x)) ∧ q(x)) where p and q are predicate symbols and f a function symbol. Yes.
4. ∃x(p(f (x)) ∧ ∃xq(x)) where p and q are predicate symbols and f a function symbol. Yes.
5. ∀x(f (x) ∧ p(x)) where f is a function symbol and p a predicate symbol. No.
6. ∀xp(f (x)) where p is a predicate symbol and f a function symbol. Yes.
7. ∀xf (p(x)) where p is a predicate symbol and f a function symbol. No.
1.2 Exercise
Translate the following sentences into first-order logic:
1. “All employees have income.”
2. “Some employees are on holidays.”
3. “No employees are unemployed.”
4. “Some employees are not satisfied by their salary policy.”
Possible translations:
1. ∀x(employee(x) → income(x)).
∗
Some exercises taken from TDDD72.
†
victor.lagerkvist@liu.se
1
2. ∃x(employee(x) ∧ holiday(x)).
3. ∀x(employee(x) → ¬unemployed(x)).
4. ∃x(employee(x) ∧ ¬satisfied(x, salary policy)).
1.3 Exercise
Translate the following formulas into natural language:
1. ∀x((strongEngine(x) ∧ car(x) ∧ wheels(x, 4)) → fast(x)).
2. ∀x∀y((parent(x, y) ∧ ancestor(y)) → ancestor(x)).
3. ∀x∀y((car(x) ∧ onRoad(x, y) ∧ highway(y) ∧ normalConditions(y)) → fastSpeedAllowed(x)).
Possible translations:
1. Four-wheel cars with strong engines are fast.
2. A parent of an ancestor is also an ancestor.
3. Under normal conditions, cars on highways can drive fast.
2 Semantics of First-Order Logic
2.1 Exercise
Consider the formula
∀x(shaves(barber, x) ↔ ¬shaves(x, x)),
which in natural language can be read as “The barber is a man in a town who shaves all those, and
only those, men in town who do not shave themselves.”. Does it have a model, i.e., is it satisfiable?
Solution: The formula does not have a model. Assume there exists a model M over a universe
{d0 , d1 , . . .}, and assume for simplicity that barberM = d0 , i.e., the constant symbol barber is
mapped to the element d0 from the universe D. Assume first that shaves(d0 , d0 ) is true in M . Then
¬shaves(d0 , d0 ) must be true, too, which is a contradiction. Similarly, assume that shaves(d0 , d0 )
is not true. Then ¬shaves(d0 , d0 )) is true, and we conclude that shaves(d0 , d0 ) must also be true,
which is again a contradiction.
2.2 Exercise
Consider the formula nat(0) ∧ ∀x (nat(x) → nat(f (x))). Provide two interpretations: one which is a
model and one which is not.
Possible interpretations:
1. A model: an interpretation I with universe D = N = {0, 1, 2, . . .}, where natI = D, and fI is
the function fI (x) = x + 1 over N.
2. A non-model: an interpretation I with universe D = N = {0, 1, 2, . . .}, where |natI | = k for
some k ≥ 1, and fI is the function fI (x) = x + 1 over N.
