Automated deduction 2026-11-05
Automated deduction uses an algorithm to construct or check a mathematical proof from explicit assumptions and inference rules. The representation might use propositional logic, first-order logic or a specialized theory such as linear arithmetic. Soundness means the rules preserve truth; finding a proof additionally requires a search strategy.
For a small resolution example, the clauses , and yield and then the empty clause. This is a contradiction, so the original clauses cannot all hold. To prove a conclusion from assumptions, a refutation method adds its negation and searches for such a contradiction. In first-order logic, unification determines which terms can instantiate matching predicates. A procedure that eventually finds every valid proof need not terminate on every invalid claim: this distinction explains why proof search and proof checking have different computational costs.
Ground clause 2026-10-31
A first-order clause containing no variables. Its first-order terms are ground terms, so resolution between such first-order clauses reduces to propositional logic on the ground atoms.
Ground resolution 2026-10-31
The use of resolution on ground clauses. A finite refutation ends in the empty ground clause and establishes unsatisfiability of the chosen ground instances. Herbrand's theorem explains the completeness of searching for such refutations for universal equality-free first-order clauses.
J. A. Robinson 2026-11-05
J. A. Robinson introduced the resolution principle in his 1965 paper on machine-oriented logic. His clause-based resolution calculus, using unification, supports a complete refutation procedure for first-order logic: an unsatisfiable clause set has a derivation of the empty clause.[ref]
For example, resolving with uses the first-order substitution and produces . The rule separates the logical justification of a step from the search for useful clauses. A complete search procedure can still run indefinitely on a satisfiable input; completeness does not supply a decision algorithm for all first-order logic.
Replace each implication by a logical disjunction and use the conjunctive normal form for exclusive or from part (a). The resulting Boolean clauses areHere the displayed array is a list of the six Boolean clauses, whose logical conjunction is equivalent to all four constraints.
Use resolution first on , then on , and finally on :Removing the repeated Boolean literal in the final Boolean clause uses idempotence. Neither nor is needed: even the weaker assumptions that the coin has at least one outcome and that at least one person wins already force , once the two implications hold.
Proof complexity 2026-11-05
Proof complexity measures resources needed to express proofs in a specified propositional proof system. Typical quantities include the total number of symbols, the number of inference steps and the space needed to retain intermediate formulas. A short theorem statement can require a much longer proof, and changing the allowed rules can change the required length dramatically.
For example, a resolution refutation of an unsatisfiable clause set derives the empty clause by resolving pairs of clauses on opposite literals. Verifying a supplied derivation is a local computation on its lines; searching for those lines can be much harder. A lower bound must therefore identify the proof rules and the family of clause sets to which it applies.
More generally, a propositional proof system can be represented by a polynomial-time computable map whose range is exactly the propositional tautologies. Every tautology then has a proof, and every produced formula is valid. If one such system had polynomial-length proofs for every tautology, tautologies would have polynomially checkable certificates, implying . Conversely that equality would provide such a certificate-based system. This connects proof length to computational verification.
Refutation 2026-11-05
A refutation of a collection of logical assumptions is a derivation of a contradiction from them. To prove a logical formula by refutation in classical propositional logic, add its negation to the assumptions and derive falsity. The correctness of this inference follows from the rules of the chosen proof system.
For example, the clauses , and have a resolution refutation: the first two resolve to , and with yields the empty clause. No truth assignment satisfies the three original clauses. This distinguishes the semantic claim of unsatisfiability from a syntactic certificate establishing it. In automated proving, producing a refutation is useful because another program can check the individual inference steps without repeating the search.
Unification Created 2026-10-20 Updated 2026-11-05
Unification finds a substitution making given first-order terms syntactically identical. In first-order unification, a substitution replaces variables by first-order terms while leaving function symbols fixed. A most general unifier captures the necessary identifications: every other unifier follows by a further substitution.[ref]
For example, and have most general unifier . The variable remains free; assigning it a particular first-order term gives a more specific unifier. Requiring forces both and , so distinct constant symbols make it impossible.
Syntactic identity is essential. With addition treated as a binary function symbol, the first-order terms and are different even though their values agree under ordinary arithmetic. Equational unification incorporates specified identities and is a different problem. For finite first-order terms, the occurs check rejects : a finite first-order term cannot equal one of its proper subterms. Unification makes resolution possible by aligning atomic formulas before inference.
Unifier 2026-11-05
A unifier of first-order terms is a first-order substitution for which . The first-order substitution replaces variables by first-order terms; it does not alter function symbols. For example, unifies with .
A most general unifier leaves every identification not forced by the original equations available for later choice. For , one solution is . The remaining variable is free. Replacing it by any finite first-order term gives a more specific unifier; arbitrarily choosing during the initial computation would discard that generality.
Not every pair is unifiable. Distinct constant symbols cannot be made equal by replacing variables, and the occurs check rejects for finite first-order terms. These are structural restrictions, not numerical inequalities. Unifiers allow a resolution step to align the relevant atomic formulas before the logical inference is performed.[ref]
An Efficient Unification Algorithm by Alberto Martelli and Ugo Montanari. Introduction and Section2, substitutions and solved equation systems