The Formal Grammar of First-Order Logic

This guide breaks down the formal grammar of First-Order Logic (FOL) into its core components: the alphabet (the allowed symbols) and the formation rules (how to correctly combine those symbols into well-formed formulas).

1. The Alphabet (Symbols)

The language of FOL is constructed from seven types of symbols.

Logical Symbols (The Logical Framework)

• x, y, z, ... Variables: Represent objects in the domain of discourse.
• ∧, ∨, ¬, →, ↔ Logical Connectives: Represent logical operations (and, or, not, implies, if and only if).
• ∀, ∃ Quantifiers: Universal (∀, "for all") and Existential (∃, "there exists").
• (, ) Parentheses: Used for grouping and defining scope.
• = Equality Symbol (optional but common).

Non-Logical Symbols (The "Content" of a Theory)

• a, b, c, ... 0, Alice Constants: Name specific objects in the domain.
• f, g, h, ... motherOf, + Functions: Map objects to other objects. Each has an arity (number of arguments).
• P, Q, R, ... Likes, >, Prime Predicates: Represent properties or relations. Each has an arity.

2. The Formation Rules (Syntax)

The grammar is defined recursively, building complex expressions from simple ones.

Step 1: Terms (Naming Objects)

Terms are expressions that refer to objects.

Base Case:
- Every variable is a term.
- Every constant symbol is a term.

Recursive Step:
- If f is an n-ary function and t₁, t₂, ..., tₙ are terms, then f(t₁, t₂, ..., tₙ) is a term.

Examples: x, 0, motherOf(Alice), +(x, y), f(a, g(b))

Step 2: Atomic Formulas (The Simplest Statements)

Atomic formulas are the most basic well-formed statements.

- If P is an n-ary predicate and t₁, t₂, ..., tₙ are terms, then P(t₁, t₂, ..., tₙ) is an atomic formula.
- If t₁ and t₂ are terms, then (t₁ = t₂) is an atomic formula.

Examples: Loves(John, Mary), Prime(7), (x = y)

Step 3: Well-Formed Formulas (WFFs)

Well-formed formulas (WFFs) represent statements that can be true or false.

Base Case: Every atomic formula is a WFF.

Recursive Steps:
1. Negation: If φ is a WFF, then ¬φ is a WFF.
2. Binary Connectives: If φ and ψ are WFFs, then (φ ∧ ψ), (φ ∨ ψ), (φ → ψ), (φ ↔ ψ) are WFFs.
3. Quantification: If φ is a WFF and x is a variable, then ∀x φ and ∃x φ are WFFs.

Examples:

• ¬Prime(4) ("4 is not prime")
• (Loves(J, M) ∧ Loves(M, J)) ("John and Mary love each other")
• ∀x (Cat(x) → Mammal(x)) ("All cats are mammals")
• ∀x ∃y Loves(x, y) ("Everybody loves somebody")

Bound vs. Free Variables

A crucial concept defined by the grammar.

• Free Occurrence: An occurrence of a variable x is free if it is not inside the scope of a quantifier that uses x (∀x or ∃x).
• Bound Occurrence: An occurrence of a variable x is bound if it is inside the scope of a quantifier that uses x.

Sentence: A WFF with no free variables is called a sentence. Sentences have a definite truth value.

Example: In (P(x) ∧ ∀x Q(x)), the first x is free and the second is bound. This is not a sentence.

Summary

Concept	Description	Example
Term	Names an object	x, Alice, fatherOf(x)
Atomic Formula	A simple statement	Loves(J, M), (x = 5)
WFF	A statement with a truth value	¬P(a), ∀x (P(x) → Q(x))
Sentence	A WFF with no free variables	∃x P(x), ∀y (y = y)