A Logical Study of Partial Entailment
This work addresses foundational issues in logic and reasoning, potentially impacting fields like AI and rational agent modeling, but it is incremental as it builds on existing logical frameworks.
The paper introduces a novel logical notion called partial entailment in propositional logic, which captures how a formula P partially entails another formula Q under a background set, and studies its semantic and computational properties, showing that it fails for many simple inference rules and is computationally difficult.
We introduce a novel logical notion--partial entailment--to propositional logic. In contrast with classical entailment, that a formula P partially entails another formula Q with respect to a background formula set Γintuitively means that under the circumstance of Γ, if P is true then some "part" of Q will also be true. We distinguish three different kinds of partial entailments and formalize them by using an extended notion of prime implicant. We study their semantic properties, which show that, surprisingly, partial entailments fail for many simple inference rules. Then, we study the related computational properties, which indicate that partial entailments are relatively difficult to be computed. Finally, we consider a potential application of partial entailments in reasoning about rational agents.