Prime Forms in Possibilistic Logic

Guilin Qi, Laurent PerrusselToulouse 2013 · OpenAlex

Abstract

Possibilistic logic provides a robust framework for representing uncertain and inconsistent knowledge by assigning weights to formulas based on a possibility distribution. A significant challenge in this field is finding an efficient way to characterize and compile these knowledge bases. This paper introduces Prioritized Prime Implicants (PPIs), a novel semantic characterization that generalizes the classical notion of propositional prime implicants. Unlike previous attempts at weighted generalizations, PPIs satisfy key desirable properties, including the ability to handle inconsistent information and the capacity to fully reconstruct the original knowledge base. We present the theoretical foundations of PPIs, their formal properties, and an algorithmic approach for their computation.

Introduction

In automated reasoning, the efficiency of a system often depends on how knowledge is represented. In classical logic, prime implicants serve as the fundamental "building blocks"—minimal sets of literals that guarantee the truth of a formula. They are essential for tasks such as hardware verification, diagnosis, and knowledge compilation.

However, real-world AI applications must frequently contend with uncertainty and conflicting data. Possibilistic logic addresses this by attaching weights (certainty levels) to formulas. While researchers have previously attempted to define "Weighted Prime Implicants" (WPIs) for this logic, these definitions often failed to meet basic logical requirements. Specifically, some consistent knowledge bases (KBs) lacked WPIs entirely, and many definitions could not handle the inherent contradictions that arise when merging information from multiple sources. This paper proposes a new "prime form" that resolves these inconsistencies.

The Limitations of Existing Weighted Implicants

Previous attempts to generalize prime implicants into the possibilistic domain encountered three primary failures:

  1. Existence: Some consistent KBs resulted in an empty set of WPIs.
  2. Reconstruction: It was not always possible to reconstruct the original KB from its WPIs, meaning the WPIs did not truly "characterize" the knowledge.
  3. Inconsistency Handling: They struggled with the "explosion principle" of classical logic, where a single contradiction renders the entire system useless.

Methodology: Prioritized Prime Implicants

The authors introduce a novel semantic tool: the paraconsistent $\alpha$-cut. In standard possibilistic logic, contradictions are typically managed by "blocking" lower-weighted information to maintain consistency. The authors argue that to fully represent a KB, one must adopt a paraconsistent approach—allowing contradictory literals to coexist as long as they possess different weights.

Defining the PPI

A Prioritized Prime Implicant is defined as a set of weighted literals that may be inconsistent. The framework relies on two key innovations:

  • Inconsistency Tolerance: By allowing PPIs to be inconsistent, the logic can remain informative even when sensors or sources disagree.
  • Lexicographic Ordering: To determine which implicant is "prime" (minimal), the authors use a stratified approach. This prioritizes literals with the highest weights, ensuring that the most certain information is preserved during the minimization process.

Algorithmic Approach

The paper outlines an incremental algorithm to compute these PPIs. The process begins at the highest weight level and works downward, incorporating new literals at each step while maintaining the lexicographic constraints required for minimality.

Key Insights and Results

Through formal proofs and constructed examples (such as a multi-sensor traffic light scenario), the authors demonstrate several critical findings:

  • Property Satisfaction: PPIs satisfy "Property 2," meaning a formula can be inferred from a KB if and only if it can be inferred from the disjunction of its PPIs. This confirms that PPIs are a valid summary or "compilation" of the KB.
  • Syntax Independence: The computation of PPIs is independent of how the rules are written, ensuring the system is robust against different formatting of the same logical facts.
  • Formal Soundness and Completeness: The authors prove that for any consistent KB, at least one consistent PPI exists, and their definition meets all three "desirable properties" for characterizing possibilistic knowledge bases.

Conclusion and Future Work

The introduction of PPIs marks a significant step forward in the compilation of uncertain knowledge. By embracing inconsistency rather than simply suppressing it, PPIs provide a more accurate reflection of complex data environments.

However, challenges remain regarding distance measures. Many AI applications, such as belief revision, rely on measuring the "distance" between two sets of beliefs. Current distance functions assume consistency; because PPIs can be inconsistent, new mathematical frameworks are needed to calculate these distances. Additionally, while the provided algorithm is theoretically sound, its performance on large-scale, real-world datasets remains a subject for future empirical study.

Summary updated

Abstract

Possibilistic logic is a weighted logic used to represent uncertain and inconsistent knowledge. Its semantics is often defined by a possibility distribution, which is a function from a set of interpretations to a totally ordered scale. In this paper, we consider a new semantic characteristics of knowledge bases in possibilistic logic (or possibilistic knowledge bases) by a generalized notion of propositional prime implicant, which we call prioritized
\nprime implicant. We first consider several desirable
\nproperties of a prioritized prime implicant for characterizing possibilistic knowledge bases. Some examples show that existing generalizations of prime
\nimplicant in possibilistic logic do not satisfy all of
\nthese properties. We then provide a novel definition of prioritized prime implicant, which is a set
\nof weighted literals that may be inconsistent. We
\nshow that the prioritized prime implicants satisfy
\nall the desirable properties. Finally, we discuss the
\nproblem of computing prioritized prime implicants
\nof a possibilistic knowledge base.
BibTeX
@inproceedings{qi2013prime,
  author = {Guilin Qi and Laurent Perrussel},
  title = {{Prime Forms in Possibilistic Logic}},
  booktitle = {Toulouse},
  year = {2013},
}
Figure