Interpretation

An interpretation of first-order logic consists of a non-empty domain  and mappings for function and predicate symbols. Every -place function symbol is mapped to a function from  to , and every -place predicate symbol is mapped to a function from  to the set comprised of two values true and false.

The domain  is the range of all variables in formulas of first-order logic, and is called the domain of the interpretation.

For a given interpretation, the truth table of any formula is defined by the following rules.

1. The truth tables for propositional connectives apply to evaluate the value of  ( AND ),  ( OR ),  ( implies ), and  (NOT ).

2.  ("for all , ") is true if  is true for any element of  as value of  at free occurrences of  in . Otherwise,  is false.

3.  ("there exists an  such that ") is true if  is true for at least one element of  as value of  at free occurrences of  in . Otherwise,  is false.

Truth tables for infinite domains of interpretation are infinite. The formulas of first-order logic that are tautologies in any interpretation are called valid formulas. A formula is called satisfiable if it takes at least one true value in some interpretation. A formula whose truth table contains only false in any interpretation is called unsatisfiable.

The Löwenheim-Skolem theorem establishes that any satisfiable formula of first-order logic is satisfiable in an  (aleph-0) domain of interpretation. Hence, aleph-0 domains are sufficient for interpretation of first-order logic.

REFERENCES

Chang, C.-L. and Lee, R. C.-T. Symbolic Logic and Mechanical Theorem Proving. New York: Academic Press, 1997.

Kleene, S. C. Mathematical Logic. New York: Dover, 2002.

Mendelson, E. Introduction to Mathematical Logic, 4th ed. London: Chapman & Hall, pp. 12 and 57, 1997.