Paraconsistency and Word Puzzles — Comprehensive Study Notes (APC, Consistency-Preferred Semantics)

Introduction and motivation

• Word puzzles and their logical representations have attracted attention (Ponnuru et al. 2004; Shapiro 2011; Baral & Dzifcak 2012; Schwitter 2013).

  • These puzzles serve as a testing ground for logical reasoning and knowledge representation techniques.

• Main problem: translating NL/CNL sentences into logic when input may be inconsistent.

  • Natural language often contains contradictions or uncertainties, which pose challenges for logical formalization.

• Many existing encodings assume consistency and fail with inconsistent input.

  • Classical logic systems struggle to handle contradictions, leading to breakdowns in reasoning.

• This paper advocates paraconsistent reasoning using Annotated Predicate Calculus (APC) to handle inconsistency.

  • Paraconsistent logics are designed to tolerate contradictions without leading to trivialization (explosion).

• Proposes a new non-monotonic semantics for APC: consistency-preferred stable models.

  • This semantics aims to balance the need to accommodate inconsistencies with the desire to maintain a reasonable degree of consistency.

• Aims to guide NL-to-logic translations with principles to prefer representations that behave sensibly under inconsistency.

  • The goal is to develop translation rules that produce logical representations that can handle inconsistencies in a meaningful way.

• Proposes integration with existing CNL translators (e.g., ACE, PENG Light) and embedding APC into ASP with preferences to enable practical implementations (Clingo + Asprin).

  • This integration would allow existing natural language processing tools to benefit from the ability to handle inconsistencies.

  • ASP (Answer Set Programming) provides a powerful framework for implementing non-monotonic reasoning.

• Scope includes theoretical foundations, methodological principles, and ready-to-run encodings (Jobs Puzzle, Zebra Puzzle, Marathon Puzzle).

  • The paper provides both a theoretical framework for APC and practical examples of how it can be applied to specific problems.

Annotated Predicate Calculus (APC): background

• APC extends predicate calculus with truth annotations for predicates.

  • Useful for handling situations where information might be contradictory or incomplete.

  • Truth annotations provide a way to represent the degree of belief or uncertainty associated with a predicate.

• Alphabet includes: variables V, function symbols F, predicate symbols P, truth annotations, quantifiers, connectives.

  • This defines the basic building blocks of the APC language.

• Truth annotations form a lattice with four values: $\bot$ (unknown), f (false), t (true), $\top$ (inconsistency).

  • These values represent different degrees of belief or evidence associated with a predicate.

  • $\bot$ represents lack of information, f represents falsehood, t represents truth, and $\top$ represents inconsistency.

• Ordering: $\bot \leq f \leq \top$ and $\bot \leq t \leq \top$.

  • This ordering defines how the truth values relate to each other in terms of information content or certainty.

  • It indicates that both truth and falsehood are more informative than the unknown, and inconsistency is the most informative value.

• Atomic APC formula: $p(t<em>1,\ldots,t</em>n):s$ where $s \in {\bot, f, t, \top}$.

  • This represents a basic statement in APC, where a predicate is associated with specific truth annotation.

  • For example, $p(a, b):t$ asserts that the predicate p holds for the objects a and b with a truth value of true.

• Atomic predicate forms: t-predicate (s = t), f-predicate (s = f), $\top$-predicate (s = $\top$), $\bot$-predicate (s = $\bot$).

  • These specify the exact truth annotation assigned to a predicate.

  • They provide a way to express different levels of certainty or belief about a predicate.

• Connectives and quantifiers: $\land, \lor, \lnot$ (ontological negation), $\leftarrow$ (ontological implication), $\sim$ (epistemic negation), <\sim (epistemic implication).

  • These logical operators allow for the construction of complex formulas.

  • Ontological connectives deal with the actual truth in the world, while epistemic connectives deal with belief and knowledge.

• Separation of ontological vs epistemic connectives helps manage how inconsistency propagates.

  • Ontological connectives deal with the actual truth in the world, while epistemic connectives deal with belief and knowledge.

  • This separation allows for a more nuanced treatment of inconsistency.

Definitions (in brief):

• Well-formed formulas (APC WFF): built from atomic with the standard logical operators and quantifiers.

• Herbrand universe U, base B, interpretations I defined over ground APC atoms.

• Ground terms, valuations $\nu$, satisfaction $\models_{\nu} \phi$ per usual APC-specific clauses (including update rules for annotations).

• Semantics: Ontological entailment $\models$ (classical-like) vs Epistemic entailment $\approx$ (conservatism in the face of inconsistency).

  • Ontological entailment is similar to classical logical entailment, while epistemic entailment is more cautious when dealing with inconsistent information.

  • Epistemic entailment aims to preserve consistency as much as possible.

• Examples illustrate how ontological vs epistemic implications behave under inconsistency:

  • Example 1: $q : t \leftarrow p : t, p : t$ has models where p and q may be t/$\top$ combinations, but q : t is entailed ontologically in all models.

  • Example 2: $P = {q : t \leftarrow p : t, p : \top}$ entails q : t ontologically because q follows in all models despite p being inconsistent in some models.

  • Example 3: Using epistemic implication $\;\sim$, inference is restricted to the most epistemically consistent models; blocks some inferences under inconsistency.

• Most e-consistent models (Definition 5): I1 $\leq_e$ I2 iff I1 $\models p : \top$ implies I2 $\models p : \top$ for all p. A model is most e-consistent if no other model is strictly more e-consistent.

  • E-consistent models prioritize minimizing the number of inconsistencies.

  • They represent the most plausible scenarios given the available information.

• Epistemic entailment $P \approx \psi$ holds iff every most e-consistent model of P is a model of $\psi$.

  • This means that an epistemic entailment only holds if it is true in all the most consistent models.

  • This ensures that inferences are drawn cautiously, avoiding conclusions that are not supported by the most consistent evidence.

• Motivation for consistency-preferred models (Definition 6): introduce a consistency-preference relation <S to rank models by how much they preserve certain facts (a lexicographic composition of preferences $S = (S</em>1, S<em>2, \ldots, S</em>n)$).

  • These models allow for ranking different models based on how well they maintain consistency.

  • The preference relation allows for prioritizing certain facts or beliefs over others.

• A model is most consistency-preferred if it not beaten any other under <S. $S</em>n$ assumed be $B_\top$ (the set all ground $\top$-predicates), guaranteeing are also e-consistent.

• Notation $\approx_S$ denotes epistemic entailment models.

Logic programming subset of APC (APCLP) and its stable-model semantics

• APCLP program form: rules of the form
  $$l0 \leftarrow l1,\ldots,l