First-Order Logic Basics: Complete Beginner's Guide

First-order logic is a precise language for writing statements a computer can reason about. It extends true/false propositional logic with objects and relations: "Socrates is human" becomes Human(Socrates), and "all humans are mortal" becomes ∀x (Human(x) → Mortal(x)) — "for every x, if x is human then x is mortal". From these two statements alone, a logic engine derives Mortal(Socrates).

FOL underpins knowledge representation, database queries, and program verification; SQL, Prolog, and formal specifications all borrow from it. When an AI must prove a conclusion truly follows from its knowledge — no guesswork — first-order logic defines what "follows" means.

Key Concepts

• Constant: names a specific object, such as Socrates or 5.
• Variable: a placeholder for objects, usually x, y, z.
• Predicate: a relation or property, such as Human(x) or Loves(x, y).
• Universal quantifier ∀: "for every" — ∀x P(x) claims P holds for all objects.
• Existential quantifier ∃: "there exists" — ∃x P(x) claims P holds for at least one object.
• Connectives: ¬ (not), ∧ (and), ∨ (or), → (implies), ↔ (if and only if).
• Model: an assignment of objects and truth values used to test whether a formula holds.
• Validity: a formula is valid if it is true in every possible model.

Formulas

• Universal implication: ∀x (Human(x) → Mortal(x)) — the standard pattern for general rules.
• Existential statement: ∃x (Bird(x) ∧ ¬Flies(x)) — "some bird does not fly"; a penguin satisfies it.
• Quantifier order matters: ∀x ∃y Loves(x, y) lets everyone love someone different, while ∃y ∀x Loves(x, y) demands one single person loved by all. Swapping quantifiers changes the meaning completely. Assumption: a fixed, non-empty domain of objects.

Worked Example

Test the two formulas on a tiny world with domain {a, b} where Loves holds only for the pairs (a, b) and (b, a). First, ∀x ∃y Loves(x, y): for x = a, y = b works since (a, b) is in the relation; for x = b, y = a works. Both objects pass, so the formula is TRUE — 4 pair-checks, 2 passes needed and found. Second, ∃y ∀x Loves(x, y): try y = a — we need (a, a), which is absent, so y = a fails; try y = b — we need (b, b), also absent, so y = b fails. Both candidates fail, so the formula is FALSE. Same 4 checks, opposite result: this tiny computation proves quantifier order changes truth.

Common Misconceptions

• ∀x ∃y means the same as ∃y ∀x. The worked example disproves it: per-x choice versus one shared choice.
• Logic can capture everything. Uncertainty, time, and the frame problem need other tools.
• Unprovable means false. Some true statements are simply unprovable in a given system.

Real-World Applications

• Prolog: programs written as FOL-style facts and rules, queried by inference.
• SQL: WHERE clauses and joins are rooted in first-order logic over tables.
• Verification: proving chips and critical software correct with logical formulas.
• Knowledge bases: millions of assertions about the everyday world.

Constants, variables, predicates, and correctly ordered quantifiers give machines a language for exact reasoning — the foundation of Prolog, database theory, formal verification, and the reasoning heart of classical AI.