Reasoning under inconsistency: the forgotten connective

Sébastien Konieczny, Jérôme Lang, Pierre MarquisIJCAI 2005

Abstract

In classical propositional logic, inconsistency leads to triviality via the principle of explosion. To manage conflicting information, researchers often resort to meta-level reasoning over sets of formulas. This paper introduces Comma Logic ($\mathcal{L}_{PS}^C$), a framework that internalizes the "comma" used to separate formulas in a set as a first-class logical connective. By defining semantics based on maximal consistency, the authors demonstrate that this single operator can unify diverse areas of AI, including belief revision, merging, and non-monotonic reasoning.

1. Introduction

The challenge of reasoning with inconsistent information is central to Artificial Intelligence. While a conjunctive formula $A \wedge \neg A$ is logically false, a set $\{A, \neg A\}$ is often viewed as a collection of potentially useful, albeit conflicting, beliefs. Traditionally, the comma in $\{A, \dots\}$ is a meta-symbol used to denote sets. This paper proposes elevating the comma to a nested logical connective, allowing for complex expressions like $\langle \phi, \langle \psi, \chi \rangle \rangle$ to be evaluated within the logic itself.

2. The Comma Connective: Syntax and Semantics

The authors extend classical propositional logic with the "chevron" notation $\langle \dots \rangle$ to represent the comma connective.

Syntax: If $\phi_1, \dots, \phi_n$ are formulas, then $\langle \phi_1, \dots, \phi_n \rangle$ is a formula. Crucially, these can be nested arbitrarily and combined with standard operators ($\neg, \wedge, \vee, \to$).

Semantics: The truth of a comma-formula is non-truth-functional. An interpretation $M$ satisfies $\langle \phi_1, \dots, \phi_n \rangle$ if the set of formulas it satisfies among $\{\phi_1, \dots, \phi_n\}$ is maximally consistent. That is, there is no other interpretation $M'$ such that the set of formulas from $\{\phi_1, \dots, \phi_n\}$ satisfied by $M'$ is a strict superset of those satisfied by $M$. This captures the intuition of preserving as much information as possible from a potentially inconsistent set.

3. A Unifying Framework for AI

A primary contribution of this work is showing that Comma Logic serves as a powerful meta-language for existing reasoning paradigms:

  • Skeptical Inference: Reasoning from the intersection of all maximal consistent subsets of a belief base can be directly expressed within the language.
  • Belief Revision: Nebel’s revision operator, which incorporates new evidence while minimally changing the existing base, is encodable using the comma connective.
  • Belief Merging: The framework can represent the combination of multiple conflicting sources, a task typically handled by specialized merging operators.
  • Supernormal Defaults: It provides a natural way to reason with "rules of thumb" that may be overridden by more specific information.

4. Expressiveness and Complexity

While Comma Logic does not increase the absolute expressive power of propositional logic (every formula has a classical equivalent), it offers significant succinctness. Translating a comma-formula into a standard one often results in an exponential blow-up in size. This succinctness comes at a computational cost:

  • Satisfiability: Checking the satisfiability of a formula with a single level of commas is $\Sigma_2^p$-complete.
  • Nesting: Each additional level of nesting increases the complexity within the polynomial hierarchy ($\Sigma_{n+1}^p$).
  • General Case: The logic with arbitrary nesting is PSPACE-complete, placing it in the same complexity class as Quantified Boolean Formulas (QBF).

5. Conclusion and Future Directions

Comma Logic provides a clean, unified syntax for reasoning under inconsistency. While the PSPACE complexity poses challenges for practical implementation, the authors also explore a cardinality-based variant—where worlds satisfy the maximum number of formulas—which is computationally more tractable ($\Delta_2^p$). Future work involves developing specialized solvers or compilers to bridge the gap between this theoretical framework and practical AI applications.

Summary updated

BibTeX
@inproceedings{konieczny2005reasoning,
  author = {Sébastien Konieczny and Jérôme Lang and Pierre Marquis},
  title = {{Reasoning under inconsistency: the forgotten connective}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2005},
}
Figure