(Last modified Mon Oct 01 21:10 2007)

The semantics of FOL formulae tells us how to determine the truth-value of any FOL formula, with respect to some specific interpretation I.  We will describe the semantics by showing how the truth-value of each syntactic kind of formula is determined by its parts, if any.  Because we show how to determine the truth value for every way of constructing a FOL formula (i.e., for PL formulae, predicates, existential quantifications, and universal quantifications — there are no other ways), we have shown how to determine the truth value of every PL formula — the semantics are complete. 

In the discussion below, α and β are assumed to be syntactically correct FOL formulae. 

PL formulae

The semantics of PL formulae with respect to an interpretation I are unchanged in FOL. 

Predicates

The truth value that a predicate maps its terms to is given by the interpretation I. 

Quantifications

First, two notational conveniences: 

• If I is an interpretation, then I[a→o] is the interpretation that is the same as I but also gives object o the name a. 
• If F is a formula, then F[a/v] is the formula obtained by writing F with unused name a in place of every occurrence of free variable v. 

We define these so that we can give the semantics of quantifiers in terms of the semantics of formulae already defined. 

Existentially-quantified formulae

• I assigns true to ∃v F if I[a→o] assigns true to F[a/v] for one or more objects o in the domain. 
• I assigns true to ∃v F if I[a→o] assigns true to F[a/v] for no object o in the domain. 

Universally-quantified formulae

• I assigns true to ∀v F if I[a→o] assigns false to F[a/v] for no object o in the domain. 
• I assigns true to ∀v F if I[a→o] assigns false to F[a/v] for one or more objects o in the domain. 

FOL syntax semantics interpretation

Thomas A. Alspaugh
Assistant Professor, Informatics Dept.
School of Information and Computer Sciences