Logic Programming with General Clauses and Defaults Based on Model Elimination

Marco A. Casanova, Ramiro A. de T. Guerreiro, Andrea SilvaIJCAI 1989

Abstract

This research expands the boundaries of logic programming by moving beyond the limitations of standard Prolog. By utilizing "Weak Model Elimination" (WME) instead of traditional SLD-resolution, the authors create a framework that supports full first-order logic and non-monotonic reasoning through the use of defaults.

Introduction

Most logic programming languages, most notably Prolog, are built on Horn clauses—statements with at most one positive literal. While efficient, this restriction prevents programmers from expressing full first-order logic; for example, representing disjunctions like "Either A or B is true" is difficult. Furthermore, Prolog’s Negation as Failure (NAF) is often too rigid for real-world reasoning.

This paper addresses two main gaps:

  1. Expressivity: Building a logic programming system that handles arbitrary clauses and indefinite answers (e.g., "The answer is either X or Y").
  2. Flexibility: Incorporating "defaults" (e.g., "Birds typically fly, unless they are penguins") into a more powerful logic framework.

Methodology

The core engine of this research is Weak Model Elimination (WME). Unlike the resolution method used in Prolog, WME maintains "chains" of literals and keeps track of resolved literals (R-literals) to ensure the system can find proofs in full first-order logic.

Key methodological contributions include:

  • Answer Extraction: The authors adapt "answer literals" to WME, allowing the system to return specific variable substitutions that satisfy a query rather than just a boolean result.
  • Clausal Defaults: Raymond Reiter’s Default Logic is translated into a clausal format compatible with WME. This enables "tentative" conclusions that remain valid unless contradicted by known facts.
  • The "Typical Individual" Constant: To handle variables in default rules, the authors propose substituting variables with a unique constant ($P_0$) during consistency checks. This represents a "typical" member of a class, avoiding the computational complexity of checking every possible substitution.
Example of a derivation step using Weak Model Elimination with defaults.

Key Insights and Results

The authors provide theoretical proofs for the soundness and completeness of their version of WME for general clauses. A major insight is that indefinite answers are a feature: in full first-order logic, a query might correctly conclude that $P(a) \lor P(b)$ is true without knowing which specific literal holds.

By integrating defaults, the system becomes non-monotonic, meaning new information can cause the retraction of previous conclusions. This aligns more closely with human common-sense reasoning than standard mathematical logic. Key results include:

  • Soundness/Completeness Theorems: Establishing the theoretical validity of WME for answer computation.
  • Definite Answer Variant: A variation of the method tuned to return only single-conjunction answers for high-certainty applications.
  • Consistency Testing: The "typical individual" approach provides a concrete implementation path for default reasoning without logical paradoxes.

Discussion and Limitations

While WME is more expressive than SLD-resolution, it is also more computationally expensive. The performance trade-offs in production-scale systems require further exploration. Additionally, when using defaults, the notion of an "answer" becomes more complex. Future work is needed to handle how answers should be revised or flagged as atypical when new evidence contradicts a previously held default.

Conclusion

This paper establishes a theoretical foundation for a more expressive logic programming paradigm. By combining Weak Model Elimination with default reasoning, it bridges the gap between formal logic and the flexible, non-monotonic reasoning required for real-world applications.

Summary updated

BibTeX
@inproceedings{casanova1989logic,
  author = {Marco A. Casanova and Ramiro A. de T. Guerreiro and Andrea Silva},
  title = {{Logic Programming with General Clauses and Defaults Based on Model Elimination}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1989},
}
Figure