The Logic of Qualitative Probability

James P. Delgrande, Bryan RenneIJCAI 2015

Abstract

This paper introduces a new logic for qualitative probability (LQP) that addresses the long-standing challenge of formalizing event comparisons without relying on infinite or exponentially complex axiom schemes. By extending the comparison operator from single events to finite sequences of formulas, the authors develop a system that remains purely qualitative while internalizing the arithmetic necessary for probability theory. We demonstrate that LQP is sound and complete with respect to probability measures on finite sets and serves as a strictly more expressive framework than previous quantitative and qualitative logics.

Introduction

In artificial intelligence and formal epistemology, it is often more practical to reason about the relative likelihood of events—stating that "Event A is at least as likely as Event B"—rather than assigning precise numerical values. This approach, known as qualitative probability, avoids the arbitrary nature of exact percentages in contexts where data is sparse or subjective.

However, formalizing this intuition has proven mathematically difficult. Since de Finetti’s early work in the 1930s, researchers have struggled to create a logic that is both complete and manageable. Early systems were found to be incomplete, and subsequent corrections by Kraft, Scott, and Segerberg required "formidable" axiom schemes—rules that were either infinite in number or grew exponentially as the number of events increased. This paper presents a solution to this complexity by introducing a logic that is "schematically finite," using a handful of simple rules to capture the full behavior of probability measures.

Methodology: From Single Events to Sequences

The core innovation of the Logic of Qualitative Probability (LQP) is a shift in syntax. Traditional qualitative logics compare two individual formulas, such as $\phi \preceq \psi$. LQP instead compares finite sequences of formulas:

$$\phi_1 \oplus \dots \oplus \phi_n \preceq \psi_1 \oplus \dots \oplus \psi_m$$

In this framework, the $\oplus$ operator acts as a "summing" placeholder. The intended semantic meaning is that the sum of the probabilities of the events on the left is less than or equal to the sum of the probabilities on the right. This sequence-based approach allows the logic to handle the "counting" or additive properties of probability internally, without needing to assume external arithmetic or numerical constants.

Axiomatization and Completeness

The authors define a set of schematically finite axioms—including Commutativity, Addition, and Cancellation—to govern these sequences. These axioms map directly to the standard Kolmogorov axioms of probability. Using Scott’s Theorem (1964), the authors prove that LQP is both sound and complete. This means that any statement provable in the logic is true in all finite probability models, and every valid statement about probability comparisons in those models can be proven within the logic.

Key Insights

Internalizing Linear Inequalities

Despite being a qualitative logic, LQP is expressive enough to encode rational linear inequalities. For example, the statement "the probability of $A$ is at least twice the probability of $B$" can be expressed simply as $B \oplus B \preceq A$. This allows the system to represent specific probability thresholds (e.g., $P(p) \geq 1/3$) using only the comparison of sequences, bridging the gap between qualitative and quantitative reasoning.

Nesting and Expressive Superiority

Unlike many previous quantitative systems, such as Fagin et al.’s AX$_{meas}$, LQP allows for the nesting of probability operators. This enables the logic to reason about the probability of a probability statement (e.g., "It is likely that Event A is more probable than Event B"). The authors demonstrate that LQP is a conservative extension of Gärdenfors’ logic and is strictly more expressive than major quantitative frameworks developed in the 1990s.

Results and Comparative Analysis

The primary result of this work is the simplification of the logical foundations of probability. By replacing infinite axiom schemes with a finite set of rules, the authors have made qualitative probability more accessible for both human reasoning and automated theorem proving. The system successfully subsumes previous work while adding the power to represent complex numerical relationships through purely structural means.

Limitations and Future Directions

While LQP provides a robust framework for finite outcome sets, it currently faces two primary limitations:

  1. Finite Models: The completeness proof is restricted to models with a finite number of possible worlds. While sufficient for many AI applications, it does not yet extend to continuous probability spaces.
  2. Computational Complexity: The paper focuses on the logical and expressive properties of the system; a detailed analysis of the computational complexity of deciding validity within LQP remains a task for future research.

Future work will focus on extending the logic to infinite outcome sets to fully compete with Segerberg’s PK logic and exploring the integration of LQP into automated decision-support systems.

Summary updated

BibTeX
@inproceedings{delgrande2015logic,
  author = {James P. Delgrande and Bryan Renne},
  title = {{The Logic of Qualitative Probability}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}

Loading related content...

Figure