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.
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.
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