First-Order Conditional Logic Revisited

Nir Friedman, Joseph Y. Halpern, Daphne Koller

Introduction

Conditional logic serves as the formal foundation for "default reasoning"—the ability of an intelligent system to make common-sense assumptions that remain valid until new evidence suggests otherwise. A classic example is the inference that "if something is a bird, it typically flies." While this type of reasoning is well-understood in propositional logic, extending it to first-order logic (FOL) introduces significant theoretical hurdles. This paper revisits first-order conditional logic, proposing a unifying framework based on plausibility structures to address long-standing inconsistencies in the field.

The Challenge: The Lottery Paradox

The primary obstacle in moving from propositional to first-order default reasoning is the Lottery Paradox. In a standard propositional setting, we might say "Player A typically does not win." However, in first-order logic, we use quantifiers like "for all" ($\forall$) and "there exists" ($\exists$).

Consider a lottery with an infinite number of players. It is reasonable to believe of any specific individual that they will likely lose. However, in many existing first-order frameworks, if the logic holds this belief for every individual, it is forced to conclude that no one wins. This contradicts the fundamental premise that the lottery must have a winner. This paradox demonstrates that many logical frameworks which work for simple statements become inconsistent or "broken" when applied to populations and quantifiers.

Proposed Framework: Plausibility Measures

To resolve these contradictions, the authors introduce a framework based on plausibility measures. Unlike strict probability distributions or simple linear rankings, plausibility measures map sets of possible worlds to a partially ordered set of values. This approach is more general and flexible, allowing for a more nuanced representation of uncertainty.

Statistical vs. Subjective Conditionals

A key contribution of the paper is the formal distinction between two types of conditional statements:

  1. Statistical Conditionals ($\mathcal{L}^{stat}$): These are objective observations about a population (e.g., "90% of birds fly").
  2. Subjective Conditionals ($\mathcal{L}^{subj}$): These represent degrees of belief regarding specific individuals (e.g., "I believe Tweety is likely to fly").

The authors focus on the subjective side, developing a new axiom system, $C^{subj}$. They successfully prove that this system is both sound (all provable statements are true within the semantics) and complete (all true statements are provable).

Key Insights

The Breakdown of the "KLM Coincidence"

In propositional logic, several different approaches to default reasoning—such as $\epsilon$-semantics, possibility theory, and preferential structures—all converge on the same set of rules, known as the KLM axioms. The authors reveal that this convergence is a "coincidence" of the propositional level. In first-order logic, these approaches diverge sharply. Frameworks that seem identical in simple cases behave very differently when quantifiers are introduced.

Avoiding the "And Rule" Trap

The paper identifies that many existing first-order default logics (such as those proposed by Delgrande) inadvertently include an "infinitary" version of the And Rule. This specific logical rule is what triggers the lottery paradox. By utilizing plausibility structures, the authors are able to weaken the logic just enough to bypass the paradox while maintaining its utility for practical reasoning.

Rigid vs. Non-rigid Designators

The research also highlights the role of naming. If a name like "Tweety" is a rigid designator (referring to the same individual in every possible world), the logic becomes much stricter. If the name can refer to different individuals across different scenarios, the logic must be adjusted accordingly.

Results and Comparisons

The authors demonstrate that their plausibility-based approach is uniquely robust. By introducing the "Crooked Lottery" example—where one individual is slightly more likely to win than others but still unlikely to win overall—they show that even sophisticated measures like possibility measures fail where plausibility structures succeed. Other popular methods, such as $\kappa$-rankings or well-founded preferential structures, are shown to be "too strong," as they satisfy an extra axiom ($V3$) that inevitably leads to inconsistency in lottery-style scenarios.

Limitations and Future Work

While the paper establishes a new standard for first-order subjective conditional logic, several challenges remain:

  • The Bridge Problem: The framework distinguishes between statistical facts and subjective beliefs but does not yet provide a formal mechanism for how a statistical fact (e.g., "Most birds fly") should update a subjective belief about a specific instance.
  • The Irrelevance Problem: The current logic does not automatically handle irrelevance. For instance, knowing "birds typically fly" should lead to the conclusion that "yellow birds typically fly" unless specified otherwise. While plausibility structures provide a path to solve this, it is not fully realized in this work.
  • Computational Complexity: As a theoretical advancement, the paper does not address the computational overhead required to implement these axioms in automated reasoning systems.

Conclusion

By revisiting first-order conditional logic through the lens of plausibility, this paper provides a path out of the logical traps that have hindered default reasoning for decades. The $C^{subj}$ system offers a sound and complete foundation for reasoning about defaults in complex, quantified environments, effectively resolving the Lottery Paradox.

Summary updated

Abstract

Conditional logics play an important role in recent attempts to formulate theories of default reasoning. This paper investigates first-order conditional logic. We show that, as for first-order probabilistic logic, it is important not to confound statistical conditionals over the domain (such as ``most birds fly''), and subjective conditionals over possible worlds (such as ``I believe that Tweety is unlikely to fly''). We then address the issue of ascribing semantics to first-order conditional logic. As in the propositional case, there are many possible semantics. To study the problem in a coherent way, we use plausibility structures. These provide us with a general framework in which many of the standard approaches can be embedded. We show that while these standard approaches are all the same at the propositional level, they are significantly different in the context of a first-order language. Furthermore, we show that plausibilities provide the most natural extension of conditional logic to the first-order case: We provide a sound and complete axiomatization that contains only the KLM properties and standard axioms of first-order modal logic. We show that most of the other approaches have additional properties, which result in an inappropriate treatment of an infinitary version of the lottery paradox.
BibTeX
@inproceedings{friedman1996first,
  author = {Nir Friedman and Joseph Y. Halpern and Daphne Koller},
  title = {{First-Order Conditional Logic Revisited}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure