Soundness and Completeness of a Logic Programming Approach to Default Logic

Grigoris Antoniou, Elmar LangetepeAAAI 1994

Abstract

Default Logic provides a robust framework for nonmonotonic reasoning, yet its computational implementation remains a significant challenge. Traditional approaches often necessitate the development of specialized semantics for logic programming. This paper presents an alternative methodology: translating Default Logic into standard logic programs using SLDNF-resolution. By introducing the "LogProg" translation scheme for Horn default theories, the authors demonstrate that standard Prolog-style execution is sufficient to identify the extensions of a default theory. We discuss the soundness and completeness of this approach and its implications for efficient nonmonotonic reasoning.

1. Introduction

In classical logic, reasoning is monotonic; the addition of new information cannot invalidate previously established conclusions. However, human cognition frequently employs nonmonotonic reasoning, where assumptions are made in the absence of contrary evidence (e.g., assuming a bird can fly unless it is identified as a penguin). Raymond Reiter’s Default Logic is a primary formalism for such reasoning, but its inherent complexity makes direct implementation difficult.

Historically, researchers have attempted to bridge the gap between Default Logic and computation by redefining the semantics of logic programming—specifically how negation is handled. This paper "flips the script" by maintaining the well-established standard semantics of logic programming (SLDNF-resolution) and instead focusing on a sophisticated translation of the default theory into a format compatible with existing logic engines.

2. The LogProg Translation Methodology

The authors propose a translation scheme, denoted as $LogProg(P, D)$, which converts a Horn default theory into a normal logic program. A Horn default theory consists of a set of definite clauses ($P$) and a set of defaults ($D$). The translation involves several critical components:

2.1 State Tracking

To manage the nonmonotonic nature of the reasoning process, the system maintains a list ($L$) representing the "current process." This list serves as a record of the defaults that have been applied during the derivation, allowing the system to track the evolution of the knowledge base.

2.2 Supplementary Programs and Negation

Standard Horn logic is ill-equipped to handle negative literals (e.g., $\neg p$). To address this, the authors generate a supplementary program ($\underline{P}$). This program includes contrapositive versions of the original rules, enabling the system to derive negative conclusions necessary for consistency checking. For example, if a rule exists such that $p \leftarrow q$, the supplementary program would include the logic for $\neg q \leftarrow \neg p$.

2.3 The Control Structure

The core of the translation is a process predicate that functions as a search engine. This predicate systematically attempts to apply defaults, verifies their applicability, and utilizes backtracking to explore the various possible "extensions" (sets of plausible conclusions) of the theory.

2.4 Consistency Verification

A default is only applicable if its "justification" is consistent with the current knowledge base. The $LogProg$ framework handles this by temporarily asserting facts during the proof search and using Negation as Failure (NAF) to ensure that no contradictions arise from the application of a default.

The primary contribution of this work is the realization that "exotic" or specialized logic programming semantics are unnecessary for solving nonmonotonic problems. Standard SLDNF-resolution is sufficiently expressive if the input theory is structured correctly.

By conceptualizing the search for a default extension as a sequential "process" of rule application, the authors transform a high-level logical problem into a state-space search problem. This is a domain where logic programming, and Prolog in particular, excels due to built-in backtracking and unification mechanisms.

4. Formal Results: Soundness and Completeness

The authors provide rigorous mathematical proofs for the validity of the $LogProg$ approach:

  • Soundness: They prove that if the translated logic program generates an answer substitution, that result corresponds precisely to a valid extension of the original default theory.
  • Completeness: For "hierarchical" programs—those where the dependency graph of predicates is acyclic—the authors prove that if a default extension exists, the logic program is guaranteed to find it.

These results suggest that parallel logic programming systems could be leveraged to build highly efficient, automated nonmonotonic reasoners.

5. Limitations and Future Directions

While the $LogProg$ approach is a significant step forward, it currently operates under several constraints:

  • Syntactic Restrictions: The method is limited to Horn default theories where literals are ground and propositional. It does not currently support complex conjunctions or full first-order logic.
  • Finiteness: The set of defaults ($D$) must be finite.
  • Hierarchical Dependency: The completeness proof relies on the program being hierarchical, which precludes certain recursive definitions.

Future research aims to relax these restrictions, particularly by allowing conjunctions in defaults and expanding the framework to handle non-hierarchical programs. Additionally, the authors intend to perform empirical benchmarks against other nonmonotonic reasoning implementations, such as truth maintenance systems (TMS).

Summary updated

BibTeX
@inproceedings{antoniou1994soundness,
  author = {Grigoris Antoniou and Elmar Langetepe},
  title = {{Soundness and Completeness of a Logic Programming Approach to Default Logic}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure