Reasoning in the Presence of Inconsistency

Fangzhen Lin

Abstract

Classical logic suffers from the "explosion principle" (Ex Falso Quodlibet), where a single contradiction allows for the derivation of any arbitrary conclusion. This paper introduces a paraconsistent logic based on a restricted resolution principle. By tracking the ancestry of proofs and employing a three-valued semantics, the proposed system remains nontrivial in the face of inconsistency while maintaining faithfulness to classical logic in consistent domains. This framework provides a formal logical justification for the behavior of practical AI systems like Prolog.

Introduction

In classical logic, a single contradiction—such as "The meeting is at 2 PM" and "The meeting is not at 2 PM"—can lead a reasoner to logically conclude that "The moon is made of green cheese." This "explosion" is a significant drawback for Artificial Intelligence and database systems, where real-world data is often messy and contains conflicting information from various sources.

A robust reasoning system should be "contradiction-tolerant," capable of isolating local inconsistencies without compromising the validity of conclusions drawn from consistent parts of the knowledge base. The author proposes a logic ($L$) that satisfies three key criteria: it must be faithful to standard logic when data is consistent, nontrivial when contradictions exist, and computable (recursively enumerable) for practical implementation.

Methodology

The core of the proposed logic is a modification of the Resolution Principle, a standard method for automated theorem proving.

Restricted Resolution

Standard resolution proves a formula $B$ from a set of facts $G$ by showing that $G \cup \{\neg B\}$ leads to an empty clause (a contradiction). The author's innovation is to track the "ancestry" of the derivation. A conclusion $B$ is only considered "inferred" if the contradiction found specifically involves information from the negated goal $\neg B$. This "connection" requirement ensures that pre-existing, unrelated contradictions in $G$ do not trigger false proofs for irrelevant goals.

Three-Valued Semantics

To provide a mathematical foundation, the paper introduces a three-valued logic. In addition to the standard truth values t (true) and f (false), a third value p (paradox or potential) is introduced to model situations where a statement might be both true and false without breaking the entire logical framework.

Truth tables for negation (-) and disjunction (\/) in the proposed three-valued logic.

As shown in the truth tables above, the logic handles the paradox value p such that it propagates through logical connectives without collapsing the system into triviality. Notably, the disjunction table reflects a specific design where the paradox value interacts uniquely with falsity.

Key Results and Discussion

The author establishes several critical properties for the proposed logic:

  1. Soundness and Completeness: The resolution rule is proven sound with respect to the three-valued semantics. For literal statements (simple facts), the system is complete, ensuring that semantic consequences can be derived algorithmically.
The logical equivalence between the proof-theoretic relation (||-) and the semantic consequence (|=).
  1. Faithfulness to Classical Logic: The logic is a "faithful extension," meaning its behavior is indistinguishable from standard first-order logic until a contradiction is encountered.
  2. Computational Realism: Unlike some previous paraconsistent logics that are undecidable, this system is recursively enumerable, making it suitable for computer programs.
  3. Formalizing Practical Systems: The logic provides a formal justification for the behavior of systems like Prolog. In Prolog, a query is answered "yes" if it can be derived from the program; if the program has an internal contradiction that does not touch the query, the system remains functional. This work provides the formal logical framework for that intuitive behavior.

Limitations and Future Work

While the logic is robust, the author acknowledges that the three-valued semantics does not perfectly preserve all classical laws, such as the full distribution of disjunction over conjunction during transformation to conjunctive normal form. Future work includes extending these ideas more fully into infinite first-order languages and exploring connections to other formalisms like "coupled tableaux."

Summary updated

Abstract

In this paper, we propose a logic which is nontrivial in the presence of inconsistency. The logic is based on the resolution principle and coincides with the classical logic when premises are consistent. Some results of interesting to Automated Theorem Proving are a sound and sometimes complete three-valued semantics for the resolution rule and a refutation process which is much in the spirit of the problem reduction format.
BibTeX
@inproceedings{lin1987reasoning,
  author = {Fangzhen Lin},
  title = {{Reasoning in the Presence of Inconsistency}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1987},
}
Figure