Logic Programming in Artificial Intelligence

IJCAI 1991

TL;DR

This paper surveys the evolution of logic programming beyond its initial theorem-proving roots, focusing on extensions crucial for artificial intelligence. It argues that while full first-order logic isn't always necessary, incorporating non-monotonic reasoning, abduction, and metareasoning makes logic programming a more powerful tool for knowledge representation and AI applications.

What Problem Does This Paper Address?

Logic programming, initially developed with a theorem-proving backward-chaining strategy, faced challenges in effectively representing and reasoning with the complexities of artificial intelligence. Specifically, early logic programming struggled with:

  • Non-monotonic Reasoning: The ability to revise conclusions when new information emerges, a common aspect of human reasoning (e.g., assuming a bird can fly unless it's an ostrich).
  • Abduction: Inferring the best explanation for an observation, crucial for tasks like fault diagnosis or understanding incomplete information.
  • Knowledge Representation: Representing nuanced knowledge, including exceptions, beliefs, and temporal aspects, in a way that is both declarative and executable.
  • Bridging Declarative and Procedural Paradigms: Reconciling the "what" (declarative) with the "how" (procedural) of computation.

The paper addresses how logic programming has evolved to tackle these issues, making it a more robust framework for AI.

Methods

The paper outlines several key developments and techniques that extend the capabilities of logic programming:

  • If-and-Only-If (iff) Form: Moving beyond the "if" (Horn clause) form to "if and only if" definitions, which better capture bidirectional relationships and are crucial for non-monotonic reasoning and abduction.
  • Negation by Failure: A mechanism for handling negation in logic programs, where "not P" is true if P fails to be proven. This is shown to be a key component for implementing non-monotonic reasoning.
  • Abduction: Techniques for generating hypotheses to explain observations. This is often achieved by treating "failed" proof attempts as potential abductive hypotheses.
  • Metalogic Programming: Using logic programs to reason about other logic programs. This allows for meta-level reasoning, handling concepts like belief, uncertainty, and temporal aspects, and is implemented using metapredicates like demo(Program, Goal).
  • Real Negation: Introducing explicit negation (¬) in rule conclusions, in addition to negation by failure ("not"). This allows for more expressive representations, especially for exceptions.
  • Constraint Logic Programming (CLP): Integrating constraint solving techniques into logic programming, enabling more efficient handling of specific domains like numerical constraints or finite domains.
  • Terminological Reasoning: Incorporating structured terms and reasoning about their relationships (satisfiability, subsumption), which is useful for representing taxonomies and class hierarchies.

Datasets

Not discussed in the paper. The paper focuses on theoretical extensions and conceptual frameworks rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • The "If-and-Only-If" Equivalence: A core insight is that the "if-and-only-if" form of definitions, when combined with appropriate equality axioms, can simulate both forward and backward reasoning, and that reasoning with the "if-halves" can simulate reasoning with the "only-if halves" (and vice-versa). This is fundamental to understanding how negation by failure works.
  • Negation by Failure as Non-Monotonic Reasoning: The paper highlights how negation by failure, when interpreted through the "completion" of a logic program, provides a mechanism for non-monotonic reasoning, effectively handling exceptions and default assumptions.
  • Abduction as a Natural Extension: Abduction is presented not as a separate paradigm but as a natural extension of logic programming, particularly when using the "if-and-only-if" form and treating failed proofs as hypotheses.
  • Metalogic for Expressiveness: Metaprogramming is crucial for handling meta-level concepts like belief, time, and uncertainty, which are essential for more sophisticated AI applications. It allows logic programming to reason about its own reasoning processes.
  • The Power of Restricted Logic: The paper suggests that while full first-order logic is powerful, many AI applications can be effectively addressed with extensions to Horn clauses and specific reasoning mechanisms, rather than requiring the full complexity of first-order logic.

Key Results

The paper doesn't present quantitative results in the traditional sense. Instead, its "results" are conceptual:

  • Demonstration of Equivalence: Showing how different forms of logic (e.g., if vs. iff, negation by failure vs. explicit negation) can be related and how one can simulate the other.
  • Framework for Non-Monotonicity: Establishing negation by failure and the "completion" semantics as a viable approach for non-monotonic reasoning in logic programming.
  • Integration of Abduction: Providing a conceptual framework for integrating abductive reasoning into logic programming.
  • Foundation for Advanced AI: Arguing that the discussed extensions (non-monotonicity, abduction, metareasoning, CLP) provide a more robust foundation for knowledge representation and reasoning in AI.

Limitations and Future Work

  • Computational Overhead: The paper acknowledges that metaprogramming can have computational overhead, suggesting that techniques like partial evaluation can alleviate this.
  • Semantics of Negation: While discussing extensions for negation, the paper notes that different semantic frameworks (e.g., three-valued logic, stable models) are being explored to handle the complexities of negation in logic programs.
  • Need for Empirical Studies: The paper mentions that while extensions like "real negation" are essential for naturalness in practice (e.g., in legislation), empirical studies are needed to fully understand their impact and applications.
  • Identifying Characteristic Applications: The authors suggest that while disjunctive logic programming and other extensions have been developed, identifying their characteristic applications remains an area for future work.
  • Integration of Diverse Techniques: The paper implies that a significant future direction is the seamless integration of logic programming with other AI techniques like constraint solving, terminological reasoning, and learning.

Summary updated

BibTeX
@inproceedings{1991logic,
  title = {{Logic Programming in Artificial Intelligence}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1991},
}
Figure