Efficient Propositional Constraint Propagation

Mukesh DalalAAAI 1992

Abstract

This paper introduces Propositional Fact Propagation (PFP), a method for efficiently inferring facts from a knowledge base without the need to convert formulas into Conjunctive Normal Form (CNF). By operating directly on the structure of logical formulas in Negation Normal Form (NNF), PFP is both more computationally efficient and logically powerful than standard Boolean Constraint Propagation (BCP). This makes it ideal for real-time reasoning in resource-limited AI systems.

Introduction: The CNF Bottleneck

In automated reasoning, identifying atomic truths (facts) that follow from a complex knowledge base (KB) is a core task. However, general propositional inference is NP-hard. To maintain tractability, many AI systems use Boolean Constraint Propagation (BCP).

A significant drawback of BCP is its reliance on Conjunctive Normal Form (CNF). Converting natural logical statements into CNF can cause the KB size to explode exponentially. Furthermore, BCP is "logically weak"; the conversion process often destroys the hierarchical structure of the original formulas, causing the algorithm to miss simple facts that are structurally apparent.

Propositional Fact Propagation (PFP)

The proposed Propositional Fact Propagation (PFP) algorithm avoids flattening formulas. Instead, it works with formulas in Negation Normal Form (NNF), which preserves the nesting of logical connectives.

Tree-Based Representation

PFP represents the KB as a labeled tree where internal nodes are connectives and leaves are literals. This structure allows the algorithm to traverse the KB and identify facts based on local context.

Figure 3: A tree-based representation of a nested logical formula. PFP uses this hierarchical structure to propagate facts without the need for CNF conversion.

Recursive Inference and Propagation

The algorithm employs two recursive functions, $C$ (conjunctive) and $D$ (disjunctive), to identify "obvious" facts. For example, in a conjunction $(P \land Q)$, both $P$ and $Q$ are conjunctively inferred. Once a fact is found, it is propagated to simplify the rest of the tree. If $P$ is true, $(P \lor Q)$ simplifies to "True," and $(\neg P \lor Q)$ simplifies to $Q$. This process continues until the tree reaches a fixed point.

Key Insights: Efficiency and Logical Power

The complexity of PFP is tied to $k$, the maximum nesting depth of logical connectives. The Compute-PFP algorithm terminates in $O(nk)$ time, where $n$ is the size of the KB. Since $k$ is typically small in real-world applications, PFP performs nearly linearly.

Structural Superiority

By retaining formula structure, PFP can find facts that BCP misses. For instance, PFP can identify literals that are common across all branches of a complex disjunction.

Figure 2: A disjunctive structure where the literal $p$ is present in every conjunctive branch. PFP's disjunctive identification function can directly infer $p$ as a fact from this structure.

Formal proofs demonstrate that PFP is strictly more powerful than BCP performed on a CNF-converted KB. It finds every fact BCP would find, plus additional facts revealed by the nested structure.

Conclusion

PFP offers a robust framework for "weak" entailment, providing a formal way to describe what a resource-limited agent "believes" without requiring logical omniscience. While it does not solve all tautologies, its efficiency and modularity make it a significant advancement for practical AI reasoning. Future work will explore extending PFP to first-order and modal logics.

Summary updated

BibTeX
@inproceedings{dalal1992efficient,
  author = {Mukesh Dalal},
  title = {{Efficient Propositional Constraint Propagation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1992},
}
Figure