An Inconsistency Tolerant Model for Belief Representation and Belief Revision

Samir Chopra, Rohit Parikh

Introduction

In classical logic and standard belief revision models, such as the AGM axioms, inconsistency is often treated as a "death sentence." If a set of beliefs becomes inconsistent, the "trivial update" rule typically forces the agent to either discard everything or conclude that every possible statement is true. However, this does not reflect human cognition or the reality of large-scale databases, where local contradictions often exist without compromising the entire system's utility.

This paper introduces the B-structure model, a framework for belief revision that allows an agent to hold globally inconsistent beliefs by partitioning them into smaller, potentially overlapping "subject matters." By utilizing Belnap’s four-valued logic, the model achieves computational efficiency and psychological realism while adhering to core logical principles.

The B-structure Model

The core innovation is the B-structure, which represents an agent's beliefs as a collection of pairs $(L_i, T_i)$, where $L_i$ is a sub-language (a set of topics) and $T_i$ is a local theory (beliefs about those topics). This builds upon the Language Splitting (LS) framework but allows for "cross-talk" where topics overlap.

To handle queries within this fragmented structure, the model employs Belnap’s four-valued logic. Unlike classical logic, which only recognizes true and false, this system includes none (no information) and both (inconsistent or over-defined).

Belnap’s four-valued logic lattice, showing the relationships between true, false, none (bottom), and both (top) across knowledge and truth orderings.

This logical foundation prevents a local contradiction from "poisoning" the entire system. When an agent is queried, it only examines the sub-theories relevant to the specific symbols in the query, ignoring unrelated parts of the belief base.

Key Insights: Local Omniscience and "Aboutness"

The model assumes local omniscience: agents are perfectly logical within a specific domain (e.g., physics) but may fail to see how those beliefs contradict beliefs in another domain (e.g., religion). By determining what a formula is "actually about"—its smallest language—the system isolates which parts of a massive database need to be updated, drastically reducing computational overhead.

Furthermore, the authors introduce $m$-consistency as a metric for inconsistency. A system is $m$-consistent if any $m$ sub-theories are jointly consistent, even if the global set is not. This allows for a more nuanced understanding of "graceful degradation" in knowledge systems.

Results and Computational Efficiency

The authors demonstrate that their query and update procedures are linear relative to the total number of beliefs ($n$) and only exponential relative to the size of the relevant sub-language. This makes the B-structure model significantly more practical for real-world applications than global consistency checks, which are NP-complete.

Additionally, the model successfully satisfies analogues of the core AGM axioms (B1-B5), proving it remains a "well-behaved" belief revision system despite its tolerance for inconsistency. A key finding, the Refinement Theorem, proves that splitting a belief base into smaller chunks makes it more likely to stay consistent, though it may result in missing some implicit information that would only be visible if the chunks were merged.

Limitations and Future Work

While the B-structure model offers significant advantages, the authors acknowledge certain limitations. In "Option A" (non-merging updates), disjunctive information that straddles two sub-languages might be lost. Additionally, the "non-local" behavior emerging from the interaction of many sub-theories requires further investigation. Future work will focus on implementing these procedures in software to test performance in practical knowledge-representation tasks.

Summary updated

BibTeX
@inproceedings{chopra1999inconsistency,
  author = {Samir Chopra and Rohit Parikh},
  title = {{An Inconsistency Tolerant Model for Belief Representation and Belief Revision}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1999},
}
Figure