Motivation
A rule about every object should not require a separately written copy for every name. From “every inspected parcel is cleared” and “parcel A is inspected,” a reasoner should find the substitution that makes the rule applicable. With nested terms and several variables, matching becomes a mathematical problem: all occurrences of one variable must receive the same replacement. Guessing independently at each occurrence can create a proof of something the premises never said.
Unification solves that agreement problem. Resolution uses the agreement to eliminate complementary literals from clauses. Keeping the two operations separate helps explain why an inference engine can be sound even when it runs forever: each step may preserve consequences, while the space of possible steps is infinite. We will prove a terminating unification procedure, sound first-order resolution, and a complete finite propositional refutation procedure. The scope of each guarantee matters.
Basic first-order interpretations and entailment are assumed from the earlier reasoning unit.
Definitions
Definition 4.1.1
(Terms and substitutions)
A finite term is a variable, a constant, or an expression built from finite terms. Function symbols are syntactic constructors in the unification problem. Two different constructors do not match, even if a particular interpretation could assign them equal values. A substitution replaces finitely many variables by terms and extends through every constructor. Repeated occurrences of a variable receive the same term. Composition is defined by ; its order must be respected.
Definition 4.1.2
(Unifier and most general unifier)
A unifier of equations is a substitution making every pair syntactically identical. A most general unifier, or MGU, is a unifier such that every unifier factors as on the variables of the original equations. Most general does not mean a uniquely spelled substitution: renaming unused variables can give an equivalent answer.
Definition 4.1.3
(Clauses and resolution)
A literal is an atom or its negation. A clause is a disjunction of literals with its variables implicitly universally quantified. The empty clause is false under every interpretation. Before combining two clauses, rename their variables so that they have disjoint variable sets; their universal quantifiers are independent. For atoms , resolving and with a unifier of and yields ; typically an MGU is chosen.
For general formulas, implication elimination, moving negations inward, variable renaming, and distribution lead toward clause form. Existential variables require particular care. In , replacing by a fresh function preserves satisfiability in an expanded language: a model can choose a witness for each , and a model of the expanded formula supplies those witnesses when is forgotten. It does not give logical equivalence in the original vocabulary. A witness depending on cannot generally be replaced by one constant. Here we assume ordinary classical semantics with nonempty domains and the usual witness-selection setting.
Theorem/Proposition
Theorem 4.1.4
(Finite-term unification by equation simplification)
For a finite set of equations between finite first-order terms, the following procedure terminates and either reports failure when no unifier exists or constructs an MGU. Delete ; decompose matching constructors componentwise; orient a variable equation as ; fail on distinct constructors or when occurs properly inside ; otherwise substitute for everywhere and record that binding. Compose recorded bindings in their application order.
Theorem 4.1.5
(Resolution: sound steps and finite propositional completeness)
A first-order resolution step with a genuine unifier is sound: the parent clauses entail the resolvent. For finitely many propositional clauses over finitely many atoms, systematic variable elimination by all positive/negative resolvent pairs decides satisfiability. It derives an empty clause exactly when the original clauses are unsatisfiable. The finite completeness proof below does not by itself prove completeness of an unrestricted first-order implementation.
Proof sketch or proof idea
Proof
(Correctness and termination of equation simplification)
Deleting an identity and decomposing preserve exactly the syntactic unifiers. Distinct constructors cannot become identical by substituting variables. If occurs properly in , replacing variables by finite terms cannot make : the right side contains as a proper subtree and so is strictly larger. This is the occurs check. Infinite cyclic terms would be a different term model.
For an allowed equation , any solution must assign the substituted value of . Applying the binding to all other equations therefore loses no solutions. Conversely, any solution of the transformed equations extends through this binding to a solution of the old system. Repeating this factorization property shows that every original solution is an instance of the recorded final substitution. At successful termination all residual equations have disappeared, so the recorded substitution is itself a unifier and is most general.
Termination needs more than saying the expressions get smaller, since substitution can enlarge them. Use the lexicographic measure consisting of the number of distinct unsolved variables, the total term-symbol count in unsolved equations, and the number of equations with nonvariable left side and variable right side. Elimination strictly reduces the first component, even if substitution enlarges the second. Decomposition and identity deletion reduce the second without increasing the first. Orientation is applied only to such a , preserving the first two components and reducing the third. This well-founded measure rules out an infinite run.
Proof X-ray
Why the occurs check is a mathematical boundary
The argument uses finite trees, not merely a programming convention. In , replacing by a finite tree would require that tree to contain itself as a proper part. An implementation that accepts a cyclic graph here is solving a different problem. Its answer cannot be used silently as a finite-term substitution in this theorem.
Proof
(Soundness of a resolution step)
For resolution soundness, a model of universally quantified parent clauses also satisfies their substitution instances under every assignment. After unification the selected atoms agree. If all literals of the resolvent were false, the first parent would force that atom true and the second would force it false. This contradiction proves the resolvent in every model of the parents. Renaming apart prevents an accidental identification of variables belonging to different universal statements.
Proof
(Eliminating one atom preserves satisfiability)
To prove the finite completeness claim, first discard tautological clauses and duplicate literals. Eliminate one propositional atom . Write clauses containing it positively as , clauses containing it negatively as , and retain clauses not containing it. The remainders contain neither sign of . Remove the first two families and insert every , again discarding tautologies. Any model of the old set satisfies the new set by soundness.
Conversely, fix a truth assignment to the remaining atoms satisfying the new set. An that is false requires true; a that is false requires false. Both requirements cannot occur, since their pair's resolvent would be false. Choose to meet the requirement if there is one, and arbitrarily otherwise. This extends the assignment to a model of the old set. Thus elimination preserves satisfiability in both directions. Induct on the finite number of atoms. At the end only constant true or empty clauses remain, and unsatisfiability means an empty clause is present. Every inserted clause was a resolvent, giving refutation completeness for this finite setting.
Proof X-ray
Where the extension step needs every resolvent
The easy direction is soundness: every resolvent is entailed, so a model of the old set satisfies the new one. The real idea is the converse. In a model of the new set, a false remainder forces true, and a false remainder forces false. Both demands cannot arise together, because the clause is in the new set and would then be false. So the resolvents are exactly the clauses that keep the demands on consistent, and omitting a single pair could leave a model that cannot be extended. Dropping tautologies is harmless since they are true everywhere; finiteness of the atoms is used only to repeat the step until no atom remains.
Worked examples
Worked example 4.1.6
(An MGU requires composing substitutions)
Unify with . Decomposition gives and . Bind , then bind and apply it to the earlier image of . The result is . Direct substitution makes both atoms . Merely recording without the later replacement is an unfinished description of the composed answer. No restriction on any unrelated variable is needed.
Concept lensStructural
Unifiers ordered by generality
Write when for some substitution , so is an instance of . The unifiers of a solvable problem form a set under this preorder, and an MGU is a least element: it lies below every unifier, that is, every unifier is an instance of it. Any two MGUs are instances of each other and differ only by renaming variables. For and , both and are MGUs, and the unifier is the first one followed by .
Worked example 4.1.7
(Refuting a universally quantified rule)
Use clauses , , and . Resolve the first with the second using , obtaining . Resolve that with to obtain the empty clause. Consequently the rule and fact entail : adding its negation made the premises inconsistent. The contradiction establishes the stated consequence, not a claim that every atom in the language is true in the original consistent knowledge base.
Worked example 4.1.8
(Elimination constructs either a contradiction or an extension)
The propositional clauses , , , and give when is eliminated. Resolving with gives , then gives the empty clause. If is removed instead, assignment satisfies the eliminated system. Because is false, the first original clause requires ; this choice also satisfies the second. The extension part of the proof supplies an actual model.
Common mistakes
Counterexample mode
Matching each occurrence independently is unsound
and with distinct constants cannot unify: they require both and . A program that matches the first occurrence with and the second with has not found a substitution. The repair is one shared equation system and consistent propagation of every binding.
Common mistake
(Confusing soundness, completeness and termination)
Soundness, refutation completeness, and termination are distinct. Finite propositional elimination terminates but may produce exponentially many clauses. First-order languages with function symbols can have infinitely many ground terms, so “try all instances” is not a finite decision algorithm. A fair resolution calculus with the required additional rules, including factoring, has a broader refutation-completeness theorem, but its proof is not supplied by the finite argument above. An arbitrary strategy that repeatedly revisits one irrelevant clause need not inherit that guarantee.
Common mistake
(Treating equality as built into resolution)
Equality is another boundary. If is intended as genuine identity, ordinary predicate resolution alone does not automatically provide substitution of equals, congruence for functions, and all other equality properties. An equality-aware calculus or suitable axioms are required. Likewise, a failure to find a proof within a time limit establishes no countermodel. Exact finite inference and resource-limited search should not be labeled with the same certainty.
Common mistake
(Resolving without renaming variables apart)
The clauses and are jointly unsatisfiable, since gives while gives . Unifying with without renaming fails the occurs check and finds no resolvent. After renaming the second clause to , the MGU yields the empty clause.
Summary
Unification enforces shared variable commitments and produces a most general substitution for finite terms. Resolution eliminates complementary instances while preserving logical consequence. Finite propositional elimination is complete because every reduced model can be extended back through the eliminated atom. Infinite term spaces, strategy fairness, factoring and equality require additional analysis; a sound step rule alone does not settle those questions.
Exercises
Quick check
(Find an MGU for and . Verify it by direct substitution and identify any variables left free.)
Turn the atom equation into component equations and decompose until each equation has a variable on one side.
Solution · Answer
The equations are , and . Decomposing the middle equation agrees with the last. An MGU is ; is unrestricted. Both atoms become . Every other unifier must choose a value for and consequently that same value inside , which verifies the factorization property.
Quick check
(Explain why and cannot unify with finite terms. Derive the equation that triggers the occurs check.)
Substitute the first binding into the second equation and look at where the variable now occurs.
Solution · Answer
The equations are and . Substitute the first into the second to obtain . Orient it as . The right side contains properly, so the occurs check fails. The apparent cycle is not a finite-term solution.
Quick check
(Eliminate from . Determine satisfiability, then recover a model of the original set.)
Collect the clauses by the sign of and form every positive–negative resolvent, discarding tautologies.
Solution · Answer
Positive remainders are and , and the negative remainder is . Their resolvents are and the tautology . Discard the tautology, leaving . Choose true. The third original clause then requires true; with that choice all three clauses hold. Deriving a unit clause is not the same as deriving the empty clause.
Quick check
(Explain why replacing by with one new constant can change satisfiability in the presence of other sentences. Require and , and use a two-element model.)
Test the two-element model in which is equality, then see what the constant version forces.
Solution · Answer
The two required sentences together with are satisfied on with equality: each object witnesses itself. The proposed replacement, together with the explicit identity axiom for , requires every object equal the same , impossible with two distinct elements. Without that axiom, an unrestricted predicate could instead relate every pair, so merely choosing one equality interpretation would not prove unsatisfiability. A fresh function can choose the witness depending on and preserves the original possibility. This example uses genuine equality semantics; ordinary predicate-only resolution does not automatically implement equality reasoning.