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.
Contact the MathWorld Team
1/4 * (4 - 1/2)