TOPICS
Search

Interpretation


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

The domain D 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 F ^ G (F AND G), F v G (F OR G), F=>G (F implies G), and ¬F (NOT F).

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

3.  exists xF ("there exists an x such that F") is true if F is true for at least one element of D as value of x at free occurrences of x in F. Otherwise,  exists xF 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 (aleph-0) domain of interpretation. Hence, aleph-0 domains are sufficient for interpretation of first-order logic.


See also

First-Order Logic, Löwenheim-Skolem theorem, Model, Satisfiable, Unsatisfiable

This entry contributed by Alex Sakharov (author's link)

Explore with Wolfram|Alpha

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.

Referenced on Wolfram|Alpha

Interpretation

Cite this as:

Sakharov, Alex. "Interpretation." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. https://mathworld.wolfram.com/Interpretation.html

Subject classifications