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.