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.
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:
- 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.
- 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.
- Computational Realism: Unlike some previous paraconsistent logics that are undecidable, this system is recursively enumerable, making it suitable for computer programs.
- 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