/Users/billy/gits/moc-2021/tutes/week05.dvi
School of Computing and Information Systems
COMP30026 Models of Computation Tutorial Week 5
23–27 August 2021
Semantics of Predicate Logic
We will introduce some additional notation in this tutorial to enable us to discuss interpretations
more explicitly. The data of an interpretation, I, involves the following choices, which associate
symbols (syntax) with objects and functions (semantics).
• A non-empty set D called the domain. Also written ID to distinguish it as “the domain of
I”. This set can be finite or infinite.
• For each constant a, an object of the domain I(a) ∈ D. This is the object that I decides a
to denote (it’s a name for that object).
• For each n-place function symbol f , a function I(f) : Dn → D. This is the function on objects
that I decides f to denote.
• For each n-place predicate symbol P , a function I(P ) : Dn → {f , t}. This is the truth-function
on objects that I decides P to denote.
A valuation σ : vars → D picks out an object for each variable, and we extend it to assign objects
to every term by adding it to the interpretation. So, given an interpretation I and valuation σ, the
object assigned to a term t is denoted I(σ, t), and is defined recursively on the term t as follows.
• I(σ, a) = I(a), for any constant a
• I(σ, x) = σ(x), for any variable x
• I(σ, f(t1, t2, . . . , tn)) = I(f)(I(σ, t1), I(σ, t2), . . . , I(σ, tn)) where f(t1, t2, . . . , tn) is a term
constructed from an n-place function symbol f and n-many terms ti.
We can now associate truth values to formulas. We will write I(σ,G) to denote the truth-value of
a formula G in an interpretation I with valuation σ. This is defined recursively on G.
• I(σ, P (t1, t2, . . . , tn)) = t iff I(P )(I(σ, t1), I(σ, t2), . . . , I(σ, tn)) = t
• I(σ,¬G) = t iff I(σ,G) = f
• I(σ,G ∧H) = t iff I(σ,G) = t and I(σ,H) = t
• . . . similarly for ∨,⇒,⇔,⊕
• I(σ, ∀xG) = t iff I(σx 7→d, G) = t for every d ∈ ID
• I(σ, ∃xG) = t iff I(σx 7→d, G) = t for at least one d ∈ ID
We say a formula G is true in an interpretation I, and write I � G, exactly when I(σ,G) = t for
any valuation σ. A formula is satisfiable if there is an interpretation I such that I � G, and valid
if this is true for every interpretation.
The exercises
T5.1 Consider the following interpretation I with domain ID = {Jemima,Thelma, Louise}. We
interpret names such that I(a) = Jemima, I(b) = Thelma, I(c) = Louise, and we interpret
predicate symbols as the following truth functions:
I(F ) Jemima Thelma Louise
Jemima f f t
Thelma t t f
Louise f t f
I(M)
Jemima t
Thelma f
Louise t
These tables define the truth-functions I(F ) : ID ×ID → {f , t}, which decides who “follows”
whom, and I(M) : ID → {f , t}, which decides who “is muddy”. For I(F ), the row determines
the first argument, and the column determines the second.
Let v be a valuation such that v(x) = Louise, v(y) = Thelma, v(z) = Jemima.
For each formula G, use the semantics from the first page to evaluate the truth of G in the
interpretation I with valuation v, that is, what is I(v,G)? You should spell out the details
of evaluating a couple of them, and then intuitively explain the rest.
(i) F (x, a)
(ii) ∃y F (x, y)
(iii) ∀x(∃y F (x, y))
(iv) ∀y F (b, y)
(v) ∃x(∀y F (x, y))
T5.2 We define a new interpretation I as follows. Let ID = N = {0, 1, 2, 3, . . . }. We interpret the
name a as the zero object, so I(a) = 0 ∈ N, the function symbol s as the successor function
I(s) : N → N, such that I(s)(x) = x + 1, the predicate symbol P as the truth-function
I(P ) : N × N × N → {f , t} which is true of numbers x, y, z iff x + y = z, and the predicate
symbol L as the truth-function I(L) : N × N → {f , t}, which is true of numbers x and y iff
x ≤ y.
For each formula G, decide whether I � G. Remember this requires the truth of I(v,G) for
any valuation v.
(i) P (s(a), a, s(s(a)))
(ii) ∃xP (s(s(a)), s(a), s(x))
(iii) P (s(s(a)), s(a), s(x))
(iv) ∀x∀y∀z(P (x, y, z)⇒ P (y, x, z))
(v) ∀x(∃yL(s(y), x))
(vi) L(x, s(x))
T5.3 For each formula G, modify the interpretation I from T5.1 so that I � G. Remember
this requires the truth of I(v,G) for any valuation v. You will need to provide a function
I(g) : ID → ID for the function symbol g in (iii).
(i) ¬∀x∃y F (x, y)
(ii) M(a) ∧M(b) ∧M(c) ∧ ¬∀x M(x)
(iii) ∀x F (x, g(x))
(iv) M(x)