Proving Facts about "I"

IJCAI 1987

TL;DR

This paper tackles the classic Knights and Knaves logic puzzle, arguing that existing formal theorem-proving approaches struggle due to the puzzle's reliance on indexicals (like "I"). The authors propose a novel representation using a "truth under utterance" predicate, enabling a faithful and formal proof of the puzzle's solution. This work highlights the importance of natural language processing concepts for robust automated reasoning.

What Problem Does This Paper Address?

The Knights and Knaves puzzle, famously posed by Raymond Smullyan, presents a scenario with inhabitants who are either knights (always truthful) or knaves (always liars). The challenge is to devise a statement that a specific character (a rich knave seeking a princess's hand) can utter to prove their identity. While seemingly simple, formalizing this puzzle for automated theorem provers has proven surprisingly difficult. Previous attempts, like those by Ohlbach, have led to solutions that, while technically correct, feel disconnected from the puzzle's intuitive meaning. The core issue lies in how to formally represent statements containing indexicals, particularly the pronoun "I," whose truth value is entirely dependent on the speaker and the context of the utterance.

Methods

The authors propose a new approach that moves beyond simply treating "I" as a fixed constant representing a specific individual. Instead, they introduce a predicate called TU (Truth Under Utterance). TU(p, t) is defined as true if and only if the statement t would be true if the pronoun "I" within it were replaced by the person p. This allows them to formalize the idea that the truth of a statement containing "I" depends on who is speaking.

They then axiomatize the Knights and Knaves world using this TU predicate, along with standard logical operators like not and and, and predicates for knight, knave, and rich. Crucially, they also introduce a CanSay(x, y) predicate, meaning "x can say y," and a T(t) predicate for "t is true." The key axioms capture:

  1. The relationship between being a knave and the truth value of utterances.
  2. The logical behavior of conjunction (and).
  3. The logical behavior of negation (not).
  4. The core TU predicate, linking an utterance's truth to the speaker.

With these axioms, they argue that standard resolution theorem-proving techniques can then derive the desired solution.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Indexicals are the Crux: The paper strongly argues that the difficulty in formalizing Knights and Knaves lies not in the logic itself, but in the proper handling of indexicals like "I." These words introduce context-dependent meaning that standard first-order logic struggles with.
  • Utterances, Not Just Statements: The truth value resides in the instance of an utterance, not just the abstract statement. This distinction is critical for dealing with indexicals.
  • "I" as a Pronoun, Not a Person: The authors reframe "I" from a fixed constant to a pronoun whose reference is determined by the context of the utterance, allowing for a more general and faithful representation.
  • TU as a Bridge: The TU predicate provides a formal mechanism to bridge the gap between abstract statements and their contextual truth values, making the puzzle amenable to automated reasoning.

Key Results

The paper doesn't present quantitative results in terms of accuracy or speedup, as its focus is on the formalization and conceptual approach. The key result is the demonstration that their proposed axiomatization, using the TU predicate, allows for a formal proof of the Knights and Knaves puzzle's solution that is faithful to the problem's intent. They claim this approach is more satisfactory than previous attempts.

Limitations and Future Work

  • Computational Practicability: The authors acknowledge that their axiomatization, particularly axiom 4 (the TU predicate), is a functional schema. This means it's not directly computationally practicable without a mechanism to supply substitution instances to the theorem prover. They mention an alternative representation in a related paper (Miller and Perlis 1987) that addresses this by recursively establishing all possible instances of axiom 4.
  • Broader Context: The paper suggests that this approach to handling indexicals is indicative of a broader class of problems. They express interest in exploring how generalizations of the TU predicate can handle other indexicals and a wider range of problems, moving beyond ad hoc tricks in knowledge representation.

Summary updated

BibTeX
@inproceedings{1987proving,
  title = {{Proving Facts about "I"}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1987},
}
Figure