Exercise Sheet “Logic: FOA1”
Wolfgang Schreiner, Wolfgang Windsteiger
RISC Institute, Johannes Kepler University Linz
March 4, 2021
1. Take the following formula in first-order logic:
∀x : p(x) ∨ ¬q(x) ∧ r(x) → ∃y : s(x) ↔ ∀z : t(y, z) ∧ u(x, z)
a) Transform this formula into standard syntax by writing a pair of parentheses around
every logical connective and quantifier:
(¬..) (..∧..) (..∨..) (..→..) (..↔..) (∀..) (∃..)
b) Give the set of free variables fv(F) of this formula F (sketch its computation).
c) Generate a syntax tree for this formula (annotating every non-atomic formula with its
free variables).
Solution(s):
a) (∀x : ((p(x) ∨ ((¬q(x)) ∧ r(x))) → (∃y : (s(x) ↔ (∀z : (t(y, z) ∧ u(x, z)))))))
b) { }
fv(t(y,z) ∧ u(x,z)) = {x,y,z}
fv(∀z:...) = {x,y}
fv(..↔..) = {x,y}
fv(∃y:...) = {x}
fv(..∧..) = {x}
fv(..∨..) = {x}
fv(..→..) = {x}
fv(∀x:..) = { }
c)
∀
|{}
---
| |
x →
|{x}
----------
| |
∨ ∃
|{x} |{x}
--- ---
| | | |
p ∧ y ↔
| |{x} |{x,y}
x ------ -----
| | | |
¬ r s ∀
|{x} | | |{x,y}
q x - ---
| | | |
x x z ∧
|{x,y,z}
-----
| |
t u
| |
--- ---
| | | |
y z x z
2. Take the following formula in first-order logic:
x ∈ N → ∃y : y ∈ N ∧ p(y) ∧ ∃z : z ∈ N ∧ p(z) ∧ x = y + z
a) Transform this formula into standard syntax by writing a pair of parentheses around
every logical connective and quantifier and around every application of an infix
operator (predicate or function):
(¬..) (..∧..) (..∨..) (..→..) (..↔..) (∀..) (∃..)
(..+..) (..∈..) (..=..)
b) Give the set of free variables fv(F) of this formula F (sketch its computation).
c) Generate a syntax tree for this formula (annotating every non-atomic formula with its
free variables).
Solution(s):
a) ((x ∈ N) → (∃y : ((y ∈ N) ∧ (p(y) ∧ (∃z : ((z ∈ N) ∧ (p(z) ∧ (x = (y + z)))))))))
b) {x}
fv(x=y+z) = {x,y,z}
fv(..∧..) = {x,y,z}
fv(..∧..) = {x,y,z}
fv(∃z:..) = {x,y}
fv(..∧..) = {x,y}
fv(..∧..} = {x,y}
fv(∃y:..) = {x}
fv(..→..) = {x}
c) →
|{x}
-----
| |
∈ ∃{x}
| |
--- ---
| | | |
x N y ∧
|{x,y}
-----
| |
∈ ∧{x,y}
| |
--- ---
| | | |
y N p ∃
| |{x,y,z}
y ---
| |
z ∧{x,y,z}
|
-----
| |
∈ ∧{x,y,z}
| |
--- ---
| | | |
z N p =
| |
z ---
| |
x +
|
---
| |
y z
3. Write the following expression in standard prefix form (no conditions under quantifier,
every quantifier binds exactly one variable, etc.) and generate a syntax tree for it:
s
1
∀x : ∃y > 2x : ≥ x2
x+y
Solution(s):
√
∀x : ∃y : > (y, ·(2, x)) ∧ ≥ ( (÷(1, +(x, y))), ^(x, 2))
4. Write the following expression in standard prefix form (no conditions under quantifier,
every quantifier binds exactly one variable, etc.) and generate a syntax tree for it:
∀n : ∃p > n : ∀1 < k < p : ¬(k | p) ∧ ¬(k | (p + 2))
Solution(s):
∀n : (∃p : (>(p, n) ∧ (∀k : ((<(1, k) ∧ <(k, p)) → ((¬(|(k, p))) ∧ (¬(|(k, +(p, 2)))))))))
∀
|{}
---
| |
n ∃
|{n}
---
| |
p ∧
|{n,p}
-----
| |
> ∀
| |{p}
--- ----
| | | |
p n k →
|{k,p}
----------
| |
∧ ∧
|{k,p} |
----- --------
| | | |
< < ¬ ¬
| | |{k,p} |{k,p}
--- --- "|" "|"
| | | | | |
1 k k p --- ---
| | | |
k p k +
|
---
| |
p 2
5. Translate the following natural language sentence into a first-order logic formula.
Every number can be written as the product of a hot and a cool number.
Hint: you may assume that all variables denote numbers (so it is not necessary to have a
predicate “is a number”). Use in your formulation unary predicates isHot(x) and isCool(x),
binary function x · y, and binary predicate x = y.
Solution(s):
∀x : ∃y, z : isHot(y) ∧ isCool(z) ∧ x = y ∗ z
6. Translate the following sentence into a first-order logic formula in standard from (under
every quantifier there is only one variable).
If G is a connected graph and A and B are two vertices in G then there is a path
from A to B in G.
Hints: above statement is to be interpreted as universally quantified for all variables.
Introduce predicates for notions such as “connected graph”.
Analyze the syntactical structure of the resulting formula, i.e. generate a syntax tree and
list all free/bound variables.
Solution(s):
∀G : ∀A : ∀B : isConnectedGraph(G) ∧ isVertexIn(A, G) ∧ isVertexIn(B, G) → ∃p : isPath(p, A, B, G)
7. Let p be a unary predicate. Express the statements
a) there exists at most one value x such that p(x) holds.
b) there exists exactly one value x such that p(x) holds
using the standard quantifiers of first-order logic.
Solution(s):
a) ∀x1 , x2 : p(x1 ) ∧ p(x2 ) → x1 = x2 (or: ¬∃x1 , x2 : x1 6= x2 ∧ p(x1 ) ∧ p(x2 ))
b) (∃x : p(x)) ∧ (∀x1 , x2 : p(x1 ) ∧ p(x2 ) → x1 = x2 )