First-Order Logic | Research & Encyclopedia Articles

First-Order Logic

First-order logic is a formal language, which means that it has both an alphabet and rules for constructing valid expressions, or formulas, in the language. The language consists of the following:

• Terms, including both variables (x, y, z, ...) and names (a, b, c, ...) (Subscripts are used with both variables and names to make an infinite number of them available)
• Predicates: F^j, G^k, H^m, where the lower-case letter is a number that indicates how many terms are included in the predicate (These are referred to as n-ary predicates and subscripts can be used when needed)
• Punctuation: (, )
• Connectives, including the unary connective ~ and the binary connectives (Read "... and ...."), ∨ ("... or ...."), ("If ..., then ...."), and ("... if and only if ....")
• Quantifiers: ∀ ("For all ..."), ∃ ("There exists ...") (Quantifiers must be followed by a variable)

There are only five rules for creating formulas:

• 1. An n-ary predicate followed by n terms is a formula.
• 2. If is a formula, then ~ is a formula.
• 3. If and Φ are formulas and is a binary connective, then Φ is a formula.
• 4. If is a formula and ⊕ is a quantifier, then ⊕ () is a formula.
• 5. Nothing else is a formula.

It's important to keep in mind that the rules for creating formulas are recursive. So if and Φ are formulas, then ~, ~ ∨ Φ, and ~(~ ∨ Φ) are also formulas.

An example of a formula might be the following: The names a and b stand for "Mary" and "Herbert," the variable x stands for some human being, the universal quantifier ∃ (x) stands for "there exists an x such that," and the predicate F³x, y, z stands for "x is the son of y and z." Putting these all together, we can create the sentence ∃ (x) (F³x, a, b), which in English reads, "There exists an x such that x is the son of Mary and Herbert" or more colloquially, "Some human is the son of Mary and Herbert." If Mary and Herbert do indeed have a son, then this sentence is true; otherwise, this sentence is false.

It's possible to decide whether any sequence of characters is a member of the language of first-order logic by using the rules above, but as Kurt Gödel proved in 1931 with his Undecidability Theorem, it's not always possible to determine whether or not a sentence of first-order logic is true or false.