{
  "id": "enwiki-001366509972",
  "slug": "resolution-logic",
  "title": "Resolution (logic)",
  "qid": "",
  "lead": "In mathematical logic and automated theorem proving, resolution is a rule of inference leading to a sound and refutation-complete theorem-proving technique for sentences in propositional logic and first-order logic. For propositional logic, systematically applying the resolution rule acts as a decision procedure for formula unsatisfiability, solving the (complement of the) Boolean satisfiability problem. For first-order logic, resolution can be used as the basis for a semi-algorithm for the unsatisfiability problem of first-order logic, providing a more practical method than one following from Gödel's completeness theorem. The resolution rule can be traced back to Davis and Putnam (1960); however, their algorithm required trying all ground instances of the given formula. This source of combinatorial explosion was eliminated in 1965 by John Alan Robinson's syntactical unification algorithm, which allowed one to instantiate the formula during the proof \"on demand\" just as far as needed to keep refutation completeness. The clause produced by a resolution rule is sometimes called a resolvent.",
  "body": "In mathematical logic and automated theorem proving, resolution is a rule of inference leading to a sound and refutation-complete theorem-proving technique for sentences in propositional logic and first-order logic. For propositional logic, systematically applying the resolution rule acts as a decision procedure for formula unsatisfiability, solving the (complement of the) Boolean satisfiability problem. For first-order logic, resolution can be used as the basis for a semi-algorithm for the unsatisfiability problem of first-order logic, providing a more practical method than one following from Gödel's completeness theorem. The resolution rule can be traced back to Davis and Putnam (1960); however, their algorithm required trying all ground instances of the given formula. This source of combinatorial explosion was eliminated in 1965 by John Alan Robinson's syntactical unification algorithm, which allowed one to instantiate the formula during the proof \"on demand\" just as far as needed to keep refutation completeness. The clause produced by a resolution rule is sometimes called a resolvent. For example, (A_1 \\lor A_2) \\land (B_1 \\lor B_2 \\lor B_3) \\land (C_1) gives rise to the set S=\\{A_1 \\lor A_2, B_1 \\lor B_2 \\lor B_3, C_1\\} . The resolution rule is applied to all possible pairs of clauses that contain complementary literals. After each application of the resolution rule, the resulting sentence is simplified by removing repeated literals. If the clause contains complementary literals, it is discarded (as a tautology). If not, and if it is not yet present in the clause set S, it is added to S, and is considered for further resolution inferences. If after applying a resolution rule the empty clause is derived, the original formula is unsatisfiable (or contradictory), and hence it can be concluded that the initial conjecture follows from the axioms. If, on the other hand, the empty clause cannot be derived, and the resolution rule cannot be applied to derive any more new clauses, the conjecture is not a theorem of the original knowledge base. One instance of this algorithm is the original Davis–Putnam algorithm that was later refined into the DPLL algorithm that removed the need for explicit representation of the resolvents. This description of the resolution technique uses a set S as the underlying data-structure to represent resolution derivations. Lists, Trees and Directed Acyclic Graphs are other possible and common alternatives. Tree representations are more faithful to the fact that the resolution rule is binary. Together with a sequent notation for clauses, a tree representation also makes it clear to see how the resolution rule is related to a special case of the cut-rule, restricted to atomic cut-formulas. However, tree representations are not as compact as set or list representations, because they explicitly show redundant subderivations of clauses that are used more than once in the derivation of the empty clause. Graph representations can be as compact in the number of clauses as list representations and they also store structural information regarding which clauses were resolved to derive each resolvent. ===Factoring=== The resolution rule, as defined by Robinson, also incorporated factoring, which unifies two literals in the same clause, before or during the application of resolution as defined above. The resulting inference rule is refutation-complete, in that a set of clauses is unsatisfiable if and only if there exists a derivation of the empty clause using only resolution, enhanced by factoring. An example for an unsatisfiable clause set for which factoring is needed to derive the empty clause is: \\begin{array}{rlcl} (1): & P(u) & \\lor & P(f(u)) \\\\ (2): & \\lnot P(v) & \\lor & P(f(w)) \\\\ (3): & \\lnot P(x) & \\lor & \\lnot P(f(x)) \\\\ \\end{array} Since each clause consists of two literals, so does each possible resolvent. Therefore, by resolution without factoring, the empty clause can never be obtained. Using factoring, it can be obtained e.g. as follows: \\begin{array}{rll} (4): & P(u) \\lor P(f(w)) & \\text{by resolving (1) and (2), with } v=f(u) \\\\ (5): & P(f(w)) & \\text{by factoring (4), with } u=f(w) \\\\ (6): & \\lnot P(f(f(w'))) & \\text{by resolving (5) and (3), with } w=w', x=f(w') \\\\ (7): & \\text{false} & \\text{by resolving (5) and (6), with } w=f(w') \\\\ \\end{array} ==Non-clausal resolution== Generalizations of the above resolution rule have been devised that do not require the originating formulas to be in clausal normal form. These techniques are useful mainly in interactive theorem proving where it is important to preserve human readability of intermediate result formulas. Besides, they avoid combinatorial explosion during transformation to clause-form, and sometimes save resolution steps. ===Non-clausal resolution in propositional logic=== For propositional logic, Murray and Manna and Waldinger use the rule \\begin{array}{c} F[p] \\;\\;\\;\\;\\;\\;\\;\\;\\;\\; G[p] \\\\ \\hline F[\\textit{true}] \\lor G[\\textit{false}] \\\\ \\end{array} , where p denotes an arbitrary formula. Here F[p] and G[p] denote formulas containing p as a subformula. F[\\textit{true}] is built by replacing every occurrence of p in F[p] by \\textit{true} . Similarly, G[\\textit{false}] is built by replacing every occurrence of p in G[p] by \\textit{false} . The resolvent F[\\textit{true}] \\lor G[\\textit{false}] is intended to be simplified using rules like q \\land \\textit{true} \\implies q , etc. In order to prevent generating useless trivial resolvents, the rule is applied only when p has at least one \"negative\" and \"positive\" occurrence in F and G , respectively. Murray has shown that this rule is complete if augmented by appropriate logical transformation rules. Traugott uses a rule that can be similarly expressed as \\begin{array}{c} F[p^+,p^-] \\;\\;\\;\\;\\;\\;\\;\\; G[p] \\\\ \\hline F[G[\\textit{true}],\\lnot G[\\textit{false}]] \\\\ \\end{array} , where the exponents of p indicate the polarity of its occurrences. While G[\\textit{true}] and G[\\textit{false}] are built as before, the formula F[G[\\textit{true}],\\lnot G[\\textit{false}]] is obtained by replacing each positive occurrence of p in F with G[\\textit{true}] and each negative occurrence with G[\\textit{false}] . Similar to Murray's approach, appropriate simplifying transformations are to be applied to the resolvent. Traugott proved his rule to be complete, provided \\land, \\lor, \\rightarrow, \\lnot are the only connectives used in formulas. Traugott's resolvent is stronger than Murray's. Moreover, it does not introduce new binary junctors, thus avoiding a tendency towards clausal form in repeated resolution. However, formulas may grow longer when a small p is replaced multiple times with a larger G[\\textit{true}] and/or G[\\textit{false}] . ===Propositional non-clausal resolution example=== As an example, starting from the user-given assumptions \\begin{array}{rccc} (1): & a & \\rightarrow & b \\land c \\\\ (2): & c & \\rightarrow & d \\\\ (3): & b \\land d &\\rightarrow & e \\\\ (4): & \\lnot (a & \\rightarrow & e) \\\\ \\end{array} the Murray rule can be used as follows to infer a contradiction: \\begin{array}{rrclccl} (5): & (\\textit{true} \\rightarrow d) & \\lor & (a \\rightarrow b \\land \\textit{false}) & \\implies & d \\lor \\lnot a & \\mbox{from (2) and (1), with } p=c \\\\ (6): & (b \\land \\textit{true} \\rightarrow e) & \\lor & (\\textit{false} \\lor \\lnot a) & \\implies & (b \\rightarrow e) \\lor \\lnot a & \\mbox{from (3) and (5), with } p=d \\\\ (7): & ((\\textit{true} \\rightarrow e) \\lor \\lnot a) & \\lor & (a \\rightarrow \\textit{false} \\land c) & \\implies & e \\lor \\lnot a \\lor \\lnot a & \\mbox{from (6) and (1), with } p=b \\\\ (8): & (e \\lor \\lnot \\textit{true} \\lor \\lnot \\textit{true}) & \\lor & \\lnot (\\textit{false} \\rightarrow e) & \\implies & e & \\mbox{from (7) and (4), with } p=a \\\\ (9): & \\lnot (a \\rightarrow \\textit{true}) & \\lor & \\textit{false} & \\implies & \\textit{false} & \\mbox{from (4) and (8), with } p=e \\\\ \\end{array} For the same purpose, the Traugott rule can be used as follows : \\begin{array}{rcccl} (10): & a \\rightarrow b \\land (\\textit{true} \\rightarrow d) & \\implies & a \\rightarrow b \\land d & \\mbox{from (1) and (2), with } p=c \\\\ (11): & a \\rightarrow (\\textit{true} \\rightarrow e) & \\implies & a \\rightarrow e & \\mbox{from (10) and (3), with } p=(b \\land d) \\\\ (12): & \\lnot \\textit{true} & \\implies & \\textit{false} & \\mbox{from (11) and (4), with } p=(a \\rightarrow e) \\\\ \\end{array} From a comparison of both deductions, the following issues can be seen: Traugott's rule may yield a sharper resolvent: compare (5) and (10), which both resolve (1) and (2) on p=c . Murray's rule introduced 3 new disjunction symbols: in (5), (6), and (7), while Traugott's rule did not introduce any new symbol; in this sense, Traugott's intermediate formulas resemble the user's style more closely than Murray's. Due to the latter issue, Traugott's rule can take advantage of the implication in assumption (4), using as p the non-atomic formula a \\rightarrow e in step (12). Using Murray's rules, the semantically equivalent formula e \\lor \\lnot a \\lor \\lnot a was obtained as (7), however, it could not be used as p due to its syntactic form. ===Non-clausal resolution in first-order logic=== For first-order predicate logic, Murray's rule is generalized to allow distinct, but unifiable, subformulas p_1 and p_2 of F and G , respectively. If \\phi is the most general unifier of p_1 and p_2 , then the generalized resolvent is F\\phi[\\textit{true}] \\lor G\\phi[\\textit{false}] . While the rule remains sound if a more special substitution \\phi is used, no such rule applications are needed to achieve completeness. Traugott's rule is generalized to allow several pairwise distinct subformulas p_1, \\ldots, p_m of F and p_{m+1}, \\ldots, p_n of G , as long as p_1, \\ldots, p_n have a common most general unifier, say \\phi . The generalized resolvent is obtained after applying \\phi to the parent formulas, thus making the propositional version applicable. Traugott's completeness proof relies on the assumption that this fully general rule is used; it is not clear whether his rule would remain complete if restricted to p_1 = \\cdots = p_m and p_{m+1} = \\cdots = p_n .",
  "categories": [
    "10639794",
    "1514103",
    "20476433",
    "20568470",
    "22904498",
    "23118434",
    "23603337",
    "24745122",
    "26868972",
    "29176179",
    "29265325"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1366509972",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1785235052.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001366509972",
    "type": "webpage",
    "title": "Resolution (logic)",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/resolution-logic",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          18
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          18
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001366509972",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1366509972",
    "note": "Immutable snapshot enwiki-001366509972"
  }
}