Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

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 not I,g |= φ.
  • I,g |= (φ ∧ ψ) iff I,g |= φ and I,g |= ψ.
  • I,g |= (φ ∨ ψ) iff I,g |= φ or I,g |= ψ.
  • I,g |= (φ → ψ) iff I,g |= ψ whenever I,g |= φ (equivalently not φ or ψ).
  • I,g |= ∀x φ iff for every d in D, I,g[x↦d] |= φ (here g[x↦d] is the assignment equal to g except x maps to d).
  • I,g |= ∃x φ iff for some d in D, 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:

  1. Start: ∀x (P(x) → ∃y Q(x,y)).
  2. Eliminate implication: ∀x (¬P(x) ∨ ∃y Q(x,y)).
  3. Move ¬ inward (none further) and standardize variable names (none needed).
  4. Prenex: quantifiers already fronted: ∀x ∃y (¬P(x) ∨ Q(x,y)).
  5. Skolemize: remove ∃y by introducing Skolem function f(x): ∀x (¬P(x) ∨ Q(x,f(x))). (State: satisfiability preserved.)
  6. Drop universal quantifiers (by convention when producing clauses): ¬P(x) ∨ Q(x,f(x)).
  7. 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:

  1. ∀x (Man(x) → Mortal(x)).
  2. 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:

  1. Resolve ¬Man(x) ∨ Mortal(x) with Man(Socrates) by unifying x with Socrates to get Mortal(Socrates).
  2. 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

  1. What is the semantic clause for I,g |= ∃x φ? (short answer)
  2. Does Skolemization preserve logical equivalence or satisfiability? (short answer)
  3. 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?