© 1996-2018

IV.3 Formal semantics of First Order Logic

Truth Table [Slide 116]

Again one could use truth tables to define the semantics of first order formulae but ...

Example 30.

Let A (A + 1 > A) be a formula

A + 1 > A


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 first order formulae.

Semantics of formula [Slide 117]

We will use a denotational semantics to define the formal semantics of a first order formula.

Formulae × State   Bool

  • Formulae: set of all possible first 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 Statee which is a mapping from the set of integer variables Vare to the set of integer values Val and
  • a Boolean state Stateb which is a mapping from the set of propositional variable Varb to the set of Boolean values Bool.

State : (Vare   Val) (Varb   Bool)

where Vare Varb = .

We will use σ012, 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.

Contact | Home | ITL home | Course | Proofs | Algebra | FL