Electronics & Telecommunication (University) 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.

Unification and resolution

Unification finds substitutions that make logical terms identical; resolution uses unification to derive contradictions (refutation) and is a central proof method in first-order logic and automated theorem proving.

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

Unification and resolution are the core techniques used in automated reasoning, logic programming (Prolog), and many AI systems that manipulate symbolic knowledge. An engineer uses these when implementing a theorem prover, a rule-based system, or when converting natural rules into machine-checkable proofs (for verification, planning or knowledge-based agents).

Key ideas

  • Literal: An atom or its negation. Example: P(x) and ¬P(x).

  • Clause: A disjunction of literals. In clausal form (CNF) a knowledge base is a set of clauses. Example: P(x) ∨ ¬Q(x,a).

  • Substitution: A finite map from variables to terms, written as a set {x1/t1, x2/t2, ...}. Applying a substitution σ to a term t is written tσ and means replace variables as specified.

  • Composition of substitutions: If σ and τ are substitutions, their composition σ∘τ means first apply τ then σ. This is not commutative.

  • Unifier: A substitution σ is a unifier of two terms s and t if sσ = tσ (the terms become syntactically identical after applying σ).

  • Most General Unifier (MGU): A unifier θ is a most general unifier of s and t if for any other unifier σ there exists a substitution δ such that σ = θ∘δ. Intuitively, θ makes the fewest commitments. We often write θ = mgu(s,t).

  • Occurs-check: When trying to set a variable x to term t, you must check that x does not occur in t; otherwise substitution would make an infinite term. A unification algorithm that rejects such cases performs the occurs-check. Complexity note: the standard unification algorithm (Martelli–Montanari) runs in linear time in the size of the input terms in typical implementations; adding an explicit occurs-check can increase cost, though near-linear implementations exist.

  • Conjunctive Normal Form (CNF): A formula is in CNF if it is a conjunction of clauses, each clause being a disjunction of literals. Conversion to CNF for first-order logic uses standard steps: eliminate implications, move negation inwards, standardize variables apart, skolemize existential quantifiers, drop universal quantifiers, and distribute to get CNF. Skolemization replaces existential quantifiers with Skolem functions (or constants) and preserves satisfiability (but not equivalence).

  • Resolution rule (first-order with unification): Given two clauses containing complementary literals L and ¬M, if there exists a substitution θ that is an MGU of L and M, then the resolvent clause is (C1 / C2)θ where C1 is the rest of first clause and C2 the rest of second clause, and complementary literals removed. This is the single inference step used in resolution-based theorem proving. Factoring: from a clause with multiple unifiable literals, unify them using their MGU and remove duplicates; factoring is used as an additional inference to ensure completeness.

  • Refutation completeness: The resolution method (with unification, variable standardizing, skolemization and factoring) is refutation-complete: if a set of FOL sentences is unsatisfiable, resolution will eventually derive the empty clause (contradiction), given fair search. This is Robinson's completeness result (needs precise assumptions: clauses in CNF, infinite search space handled fairly).

Derivations universities commonly ask for:

  1. Step-by-step unification using Robinson's algorithm: show pair queue, apply variable binding, perform occurs-check, substitute across pending pairs, iterate until success or failure. Draw a table with columns: pair, substitution produced, remaining pairs, cumulative substitution.

  2. Resolution refutation proof: show conversion of premises and negated query to CNF (with explicit skolem functions if existential), then apply resolution steps with MGUs annotated. Draw a resolution tree: nodes = clauses, edges show which literals were resolved and the MGU used; root is empty clause when refutation succeeds.

Diagram to draw for an exam answer: a binary tree (or DAG) with leaves labeled input clauses, internal nodes labeled derived resolvent clauses; annotate each internal node with the two parent clauses and the MGU used, and mark which complementary literals were resolved.

Assumptions to state in proofs: all clauses are in clausal form (CNF), variables in different clauses are standardized apart before unifying, Skolemization steps are applied, and occurs-check is performed unless you justify omission (Prolog-style implementations omit it and gain performance but lose soundness in presence of cyclic terms).

Formulas

σ = {x/t} — substitution replacing variable x by term t. (σ: substitution; unit: dimensionless; applies to terms and formulas)

tσ — term t after applying substitution σ. (t: term; σ: substitution; dimensionless; used whenever applying substitutions)

σ ∘ τ — composition of substitutions σ after τ (apply τ, then σ). (σ, τ: substitutions; dimensionless)

mgu(s, t) = θ — θ is a most general unifier of terms s and t. (s,t: terms; θ: substitution)

Resolvent = (C1 \ {L}) ∪ (C2 \ {¬M}) θ — where L ∈ C1 and ¬M ∈ C2 are complementary literals, and θ = mgu(L, M). (C1,C2: clauses; L,M: literals; θ: substitution)

KB ⊧ Q iff KB ∪ {¬Q} is unsatisfiable — proof by refutation. (KB,Q: formulas; logical entailment ⊧)

Note: All symbols are dimensionless; these are syntactic/logical formulas, not physical equations.

Worked examples

  1. Unification example (model-answer style): Problem: Find mgu for s = f(g(x), x) and t = f(y, a). Solution steps:
  • Compare top-level: both are f(...), so unify argument lists (g(x), x) and (y, a).
  • Pair queue initially: {(g(x), y), (x, a)}.
  • Take (g(x), y): y is a variable not occurring in g(x), so bind y -> g(x). Substitution σ1 = {y/g(x)}.
  • Apply σ1 to remaining pair: (x, a)σ1 = (x, a) (no change because x not affected).
  • Next pair (x, a): x is a variable not in a, bind x -> a. Substitution σ2 = {x/a}.
  • Compose cumulative substitution: σ = σ2 ∘ σ1 = {x/a, y/g(a)} (note y under σ1 had g(x); after σ2 x->a, so y->g(a)).
  • Verify: sσ = f(g(a), a), tσ = f(g(a), a). So θ = {x/a, y/g(a)} is an mgu. (Show why it's most general: any other unifier must map x to a and y to g(a) up to further composition.)

Final answer (bold): mgu = {x/a, y/g(a)}.

  1. Resolution refutation example (model-answer): Problem: From premises: (1) ∀x (Human(x) → Mortal(x)), (2) Human(Socrates), show Mortal(Socrates). Method: Resolution refutation. Solution steps (full marks answer should show each conversion):
  • Express premises and negated goal in FOL: Premise1: ∀x ¬Human(x) ∨ Mortal(x). Premise2: Human(Socrates). Negated goal: ¬Mortal(Socrates).
  • All are already in CNF (no existential quantifiers). Write clauses: C1: ¬Human(x) ∨ Mortal(x). C2: Human(Socrates). C3: ¬Mortal(Socrates).
  • Standardize apart variables (only x used once, OK).
  • Resolution steps with unifiers: Resolve C1 and C2 on Human: take complementary literals ¬Human(x) ∈ C1 and Human(Socrates) ∈ C2; mgu θ = {x/Socrates}. Resolvent R1 = (¬Human(x) ∨ Mortal(x) \ {¬Human(x)}) ∪ (Human(Socrates) \ {Human(Socrates)}) applied substitution = {Mortal(Socrates)}. Now resolve R1 and C3 on Mortal(Socrates) and ¬Mortal(Socrates); mgu = {} (no substitution needed). Resolvent R2 = empty clause ☐.
  • Derivation of empty clause shows KB ∪ {¬Mortal(Socrates)} unsatisfiable. Therefore KB ⊧ Mortal(Socrates).

Full-marks answer should list CNF clauses, MGUs, and each resolvent.

  1. Unification failure due to occurs-check (short): Unify x and f(x). Pair (x, f(x)) — occurs-check finds x occurs in f(x), so no unifier (would require infinite term). State final answer: no unifier.

Common mistakes

  • Not Skolemizing correctly (skolem function arguments must include all universally quantified variables in scope of that existential).
  • Applying resolution on non-clausal formulas (must convert to CNF first).
  • Forgetting to apply cumulative substitution to all literals immediately after a binding (leading to wrong MGUs).
  • Assuming resolution is decision procedure for general FOL (it is semi-decision: refutation-complete but may not terminate for satisfiable KB).

For your exam

Typical question forms:

  • Definitions: define term, substitution, unifier, MGU, clause, resolution rule. A full answer gives precise symbolic definitions and short examples.
  • Short notes: describe conversion to CNF, Skolemization, occurs-check, and Robinson's unification algorithm with its complexity idea.
  • Derivations: carry out step-by-step unification (table of pairs and substitutions), or a resolution refutation with MGUs and resolvents shown.
  • Numericals/programming: rarely numeric; may ask to implement or trace a unification procedure (pseudo-code) or to draw a resolution proof tree.
  • Diagrams: draw resolution DAG/tree as explained in Key ideas; label nodes with clauses and edges with MGUs.

What a full-marks answer includes:

  • Clear definitions of all terms used (bold those in your notes during revision).
  • Conversion of all formulas to CNF with every intermediate step shown (eliminate →, move ¬ inward, standardize, skolemize, drop ∀, distribute ∧/∨).
  • Standardize-apart variables before resolution.
  • For each resolution step: list parent clauses, the literals resolved, the MGU, and the resulting resolvent.
  • A final statement relating the derived empty clause to entailment (KB ⊧ Q iff KB ∪ {¬Q} unsatisfiable).

Quick check

  1. What is a most general unifier (MGU)?
  2. Why perform Skolemization when turning formulas into CNF?
  3. Give one reason resolution may not terminate on a set of first-order clauses.

Answers: 1) A unifier θ such that any other unifier σ can be written σ = θ∘δ for some δ (θ makes minimal commitments). 2) To remove existential quantifiers while preserving satisfiability, replacing them by Skolem functions/constants. 3) Because FOL resolution is only semi-decidable: if the set is satisfiable, resolution search may run forever (infinite search space / loops).

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?