First-order predicate logic
First-order predicate logic (FOL) extends propositional logic with predicates, quantifiers and variables to express relations about objects; it is the foundation for knowledge representation and automated reasoning in AI.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
First-order predicate logic (FOL) is the standard formal language for expressing facts and rules about objects and their relationships. Engineers use FOL to represent knowledge in AI systems (knowledge-based agents), to perform automated reasoning (theorem proving, planning), and to translate natural-language requirements into precise statements.
Key ideas
Start with clear definitions.
- Language (of FOL): the tuple of constant symbols, function symbols, predicate symbols and logical symbols (connectives and quantifiers). Define this before using any symbol. If equality is included, '=' is a distinguished binary predicate with fixed interpretation as identity on the domain.
- Term: a variable, a constant, or the result of applying a function symbol to terms. (Terms name objects.)
- Atomic formula (or atom): an expression P(t1,...,tn) where P is an n-ary predicate symbol and t1..tn are terms. If equality is in the language, t1 = t2 is also an atomic formula.
- Formula: built from atomic formulas using logical connectives (¬, ∧, ∨, →, ↔) and quantifiers (∀, ∃).
- Universe (domain) D: the non-empty set of objects the variables range over.
- Interpretation I: a mapping that gives meaning to non-logical symbols: assigns each constant to an element of D, each n-ary function symbol to an n-ary function on D, and each n-ary predicate symbol to an n-ary relation on D.
- Variable assignment g: a function that assigns to each variable an element of D.
- Satisfaction (I, g |= φ): a formal relation that defines when formula φ is true under interpretation I with assignment g. For quantifiers: see exact semantic clauses below.
- Model: an interpretation I is a model of a set of sentences Σ if every sentence in Σ is true in I (i.e., for all sentences s in Σ: I |= s).
- Entailment (Σ |= φ): Σ semantically entails φ if every model of Σ is also a model of φ.
- Satisfiable: a sentence or set Σ is satisfiable if there exists some interpretation I that is a model of it. Unsatisfiable means no model exists.
- Valid (logically valid): a sentence φ is valid if it is true in every interpretation (written |= φ).
- Free and bound variables: a variable occurrence is bound if it lies within the scope of a quantifier that binds it; otherwise it is free. A sentence has no free variables.
Exact semantic clauses (write these on the answer-sheet):
- For an atomic formula P(t1,...,tn), I,g |= P(t1,...,tn) iff the tuple (val_I,g(t1),...,val_I,g(tn)) is in P^I, where val_I,g(t) evaluates a term under I and g.
I,g |= ¬φiff notI,g |= φ.I,g |= (φ ∧ ψ)iffI,g |= φandI,g |= ψ.I,g |= (φ ∨ ψ)iffI,g |= φorI,g |= ψ.I,g |= (φ → ψ)iffI,g |= ψwheneverI,g |= φ(equivalently not φ or ψ).I,g |= ∀x φiff for everydinD,I,g[x↦d] |= φ(hereg[x↦d]is the assignment equal to g except x maps to d).I,g |= ∃x φiff for somedinD,I,g[x↦d] |= φ.
Important logical equivalences (write and use these; mention conditions when they fail):
¬∀x φ ≡ ∃x ¬φand¬∃x φ ≡ ∀x ¬φ(quantifier negation laws).∀x (P ∧ Q) ≡ (∀x P) ∧ (∀x Q)always holds.∃x (P ∨ Q) ≡ (∃x P) ∨ (∃x Q)always holds.- Do NOT assume
∀x (P ∨ Q) ≡ (∀x P) ∨ (∀x Q)— this is false in general; explain in exam answers why.
Normal forms and proof methods you must know:
- Prenex Normal Form (PNF): a formula is in PNF when all quantifiers are at the front and the matrix (quantifier-free part) follows. Theorem (standard statement for exams): Every first-order formula is logically equivalent to a formula in prenex normal form after renaming bound variables and applying logical equivalences; for automated reasoning we then Skolemize the PNF to obtain an equisatisfiable (not equivalent) form.
- Skolemization: a transformation that removes existential quantifiers by introducing Skolem functions; Skolemization preserves satisfiability (not logical equivalence). State exactly: If φ is satisfiable then the Skolemized formula φ' is satisfiable; conversely if φ' is satisfiable then φ is satisfiable (so equisatisfiable), but φ and φ' may not be logically equivalent. If an existential quantifier has no enclosing universal quantifier, replace it with a fresh Skolem constant (a 0-ary function symbol).
- Conjunctive Normal Form (CNF) for FOL: a set of universally-quantified clauses (disjunctions of literals). Practical theorem: for resolution proof we convert sentences to a set of clauses via: eliminate implications, move ¬ inward, standardize variables, move quantifiers to front (PNF), Skolemize (remove ∃), drop universal quantifiers, distribute ∧ over ∨ to get CNF, and finally treat each clause as a disjunction of literals.
- Robinson's Resolution Theorem (informal exam form): Resolution with unification is refutation-complete for first-order logic clauses: if a set of clauses is unsatisfiable, there exists a finite derivation of the empty clause (⊥) by resolution (with unification). State clearly: completeness refers to refutation completeness (ability to derive contradiction from unsatisfiable clause sets), not that resolution is a decision procedure for validity.
Diagram to draw when asked for a model/interpretation: draw a box labelled D with a few dots inside (elements a,b,c). Next to each constant, arrow to an element. For each predicate write which ordered tuples of elements make it true (e.g., draw arrow pairs for a binary predicate). Label arrows and elements clearly.
Formulas
Each formula on its own line, followed by symbol meanings and applicability.
I,g |= ∀x φ ⇔ for all d ∈ D, I,g[x↦d] |= φ — I is an interpretation, g is a variable assignment, D is the domain; no SI units; applies when defining semantics of universal quantifier.
I,g |= ∃x φ ⇔ exists d ∈ D such that I,g[x↦d] |= φ — same symbols; applies for existential quantifier semantics.
¬∀x φ ≡ ∃x ¬φ — logical equivalence for moving negation across universal quantifier; applies in formula rewriting.
∀x (P(x) ∧ Q(x)) ≡ (∀x P(x)) ∧ (∀x Q(x)) — distribution of universal quantifier over conjunction; apply only when required.
Skolemization: ∀x ∃y φ(x,y) ⇒ ∀x φ(x, f(x)) — f is a new Skolem function; applies during conversion to CNF; note: preserves satisfiability, not equivalence.
Resolution step: from (L ∨ A) and (¬B ∨ M) derive (L ∨ M)σ, where σ = mgu(A,B) — L,M are disjunctions of literals; applies when performing clause resolution.
Worked examples
Example 1 — translate English to FOL (model-answer style) Question: Translate these sentences using domain = all people. Use predicates: Person(x) (optional), Likes(x,y), Friend(x,y), Student(x), Course(c), Enrolled(x,c).
(a) "Everyone loves someone." Answer (explain ambiguity): There are two different readings; give both.
- Reading 1 (each person has possibly different someone they love):
∀x ∃y Likes(x,y). - Reading 2 (there is one person loved by everyone):
∃y ∀x Likes(x,y). Explain why they are not equivalent: show a simple model with two people a and b where Likes(a,a) and Likes(b,b) hold; Reading 1 true, Reading 2 false.
(b) "Every student is enrolled in some course."
Answer: ∀x (Student(x) → ∃c (Course(c) ∧ Enrolled(x,c))).
Example 2 — conversion to CNF (step-by-step)
Question: Convert ∀x (P(x) → ∃y Q(x,y)) to clause form ready for resolution. Number the steps.
Answer:
- Start:
∀x (P(x) → ∃y Q(x,y)). - Eliminate implication:
∀x (¬P(x) ∨ ∃y Q(x,y)). - Move ¬ inward (none further) and standardize variable names (none needed).
- Prenex: quantifiers already fronted:
∀x ∃y (¬P(x) ∨ Q(x,y)). - Skolemize: remove
∃yby introducing Skolem functionf(x):∀x (¬P(x) ∨ Q(x,f(x))). (State: satisfiability preserved.) - Drop universal quantifiers (by convention when producing clauses):
¬P(x) ∨ Q(x,f(x)). - Clause set: single clause
{¬P(x), Q(x,f(x))}. This is ready for unification-based resolution.
Example 3 — resolution proof (model answer) Question: From premises "All men are mortal" and "Socrates is a man" prove "Socrates is mortal" using resolution.
Premises:
∀x (Man(x) → Mortal(x)).Man(Socrates). Conclusion:Mortal(Socrates).
Convert to clauses:
- From 1:
∀x (¬Man(x) ∨ Mortal(x))→ clause¬Man(x) ∨ Mortal(x). - From 2: clause
Man(Socrates). - Negate conclusion to refute:
¬Mortal(Socrates).
Resolution steps:
- Resolve
¬Man(x) ∨ Mortal(x)withMan(Socrates)by unifyingxwithSocratesto getMortal(Socrates). - Now
Mortal(Socrates)resolves with¬Mortal(Socrates)to derive empty clause ⊥. Thus by refutation the conclusion follows.
Write every substitution used: step 1 substitution {x/Socrates}.
Common mistakes
- Misapplying distribution laws: assuming ∀ distributes over ∨ or ∃ distributes over ∧ in general — give counterexamples in answers.
- Forgetting to drop universal quantifiers before listing clauses for resolution.
- Not applying unification correctly: failing to apply substitution consistently to all literals in a clause during resolution.
- Confusing domain assumptions: FOL requires non-empty domain; don't assume empty domain unless question explicitly allows it.
For your exam
Types of questions you will see:
- Definitions and short notes (define interpretation, model, satisfiable, valid, free/bound variables).
- Derivations and proofs (show semantic entailment, prove a resolution refutation, prove an equivalence or a counterexample).
- Conversions (convert to prenex form, Skolemize, produce CNF clauses step-by-step).
- Translations from English to FOL and vice versa; explain ambiguities.
- Small proofs by resolution or natural deduction.
What a full-marks answer includes:
- Precise definitions with symbols (e.g., give
I,g |= ∀x φclause exactly). - Each rewrite step clearly numbered and justified (eliminate →, push ¬, rename variables, move quantifiers, Skolemize, drop ∀, distribute to CNF).
- For proofs using resolution include every clause, all substitutions (unifiers) and show the final empty clause.
- For translation tasks specify domain and each predicate/function/constant signature and explain any ambiguity.
- If drawing a model, draw domain elements, map constants, and list predicate tuples.
Quick check
- What is the semantic clause for
I,g |= ∃x φ? (short answer) - Does Skolemization preserve logical equivalence or satisfiability? (short answer)
- Give the CNF clause resulting from
∀x (P(x) → ∃y R(x,y))after Skolemization.
Answers: 1) I,g |= ∃x φ iff there exists d in D such that I,g[x↦d] |= φ. 2) Skolemization preserves satisfiability (equisatisfiable), not necessarily logical equivalence. 3) Clause is ¬P(x) ∨ R(x, f(x)) (with new Skolem function f).
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?