IV.3 Formal semantics of First Order Logic
Truth Table [Slide 116]
Again one could use truth tables to deﬁne the semantics of ﬁrst order
formulae but ...
Example 30.
Let ∀A ∈ ℕ (A + 1 > A) be a formula

 A 
A + 1 > A 

 1 
true 
2  true 
… 
In order to determine the truth value of ∀A ∈ ℕ (A + 1 > A) one needs
to consider all rows in above truth table.
Truth tables are not suitable to determine the semantics or reason
about ﬁrst order formulae.
Semantics of formula [Slide 117]
We will use a denotational semantics to deﬁne the formal semantics of a
ﬁrst order formula.
Formulae × State ↦ Bool
 Formulae: set of all possible ﬁrst order formulae
 Bool: set of semantic Boolean values {tt,ﬀ}
 State: a ‘snapshot’ of the semantic values of the propositional
variables and integer variables in a formula
State [Slide 118]
A State is the union of
 an integer state State^{e} which is a mapping from the set of integer
variables Var^{e} to the set of integer values Val and
 a Boolean state State^{b} which is a mapping from the set of
propositional variable Var^{b} to the set of Boolean values Bool.
State : (Var^{e} ↦ Val) ∪ (Var^{b} ↦ Bool)
where Var^{e} ∩ Var^{b} = ∅.
We will use σ_{0},σ_{1},σ_{2},… to denote states and Σ to denote the set of all
possible states.
Example 31.
Let P be a Boolean variable and A be an integer variable then σ_{0} s.t.
σ_{0}(P) = tt and σ_{0}(A) = 5 is a state.
