Linear resolution for consequence finding

DOI10.1016/0004-3702(92)90030-2MaRDI QIDQ1199916zbMATH OpenOpenAlexFDO

Publication date 17 January 1993

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0004-3702(92)90030-2

consequence-finding model elimination production field resolution SOL-resolution

Mechanization of proofs and logical operations (03B35) Logic in artificial intelligence (68T27) Knowledge representation (68T30)

Review text

Resolution is mostly used as refutational method. However, it is an old result of \textit{R. C. T. Lee} [``A completeness theorem and computer program for finding theorems derivable from given axioms, Ph. D. Thesis, Univ. California, Berkeley, CA (1967)] that resolution is also complete for consequence finding (if \(C\) is a non-tautological clause implied by a set of clauses \(\mathcal C\) then there exist a clause \(D\) such that \(D\) is derivable from \(\mathcal C\) and \(D\) subsumes \(C\)). The author of this paper uses SOL-resolution, an adapted version of model elimination, as a consequence-finding method. For the description of the problem of consequence-finding, the author develops an abstract framework around the central concept of production field. In a production field a specific subset of literals is specified of which the consequence clauses must consists (plus further syntax restrictions). The set of theorems derivable from a set of clauses which belong to a production field and are closed under subsumption form the so-called set of characteristic clauses (one of the key notions of this paper). The author gives several applications in the area of AI (abductive reasoning, prime implicates, truth maintenance systems and circumscription), where his general terminology leads to a unified and systematic treatment. The concept of SOL-resolution defined in this paper (skipping ordered linear \(r\)) is a method for consequence-finding which is close to model elimination and generalizes several other consequence- finding methods used so far [see, e.g., \textit{T. C. Przymusiński}, Artif. Intell. 38, No. 1, 49-73 (1989; Zbl 0663.68098)]. The operation of skipping is characteristic to consequence-finding (it selects a specific group of literals and ``protects them from resolution cut). It is pointed out that the techniques of reduction and resolution (as defined in the model elimination method) must be used nondeterministically and that some preference methods used in the standard literature (such as OL- resolution) are incomplete. Eventually, it is proved that SOL-resolution is sound and complete for consequence-finding. By the general, mathematically rigorous terminology and by the completeness result for an efficient (predicate logic) method of consequence-finding, the paper is an important contribution to AI-logic and automatic deduction. Some minor details only: Even in the case of propositional logic, ``\(C\) subsumes \(D\) is not equivalent to the validity of \(C\to D\) (this holds only if \(D\) is not a tautology); the restriction to nontautological clauses is also important to the validity of Lee's theorem.

Recommendations

Cites work

Cited in

(30)

This page was built for publication: Linear resolution for consequence finding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1199916)