Propositional Independence - Formula-Variable Independence and Forgetting

Abstract

Independence -- the study of what is relevant to a given problem of reasoning -- has received an increasing attention from the AI community. In this paper, we consider two basic forms of independence, namely, a syntactic one and a semantic one. We show features and drawbacks of them. In particular, while the syntactic form of independence is computationally easy to check, there are cases in which things that intuitively are not relevant are not recognized as such. We also consider the problem of forgetting, i.e., distilling from a knowledge base only the part that is relevant to the set of queries constructed from a subset of the alphabet. While such process is computationally hard, it allows for a simplification of subsequent reasoning, and can thus be viewed as a form of compilation: once the relevant part of a knowledge base has been extracted, all reasoning tasks to be performed can be simplified.

Cited by in corpus (22)

• Redundancy in Logic I: CNF Propositional Formulae
• Foundations for Uniform Interpolation and Forgetting in Expressive Description Logics
• When You Must Forget: beyond strong persistence when forgetting in answer set programming
• A Syntactic Operator for Forgetting that Satisfies Strong Persistence
• Prime Implicates and Prime Implicants: From Propositional to Modal Logic
• Variable Forgetting in Reasoning about Knowledge
• On Quantifying Literals in Boolean Logic and Its Applications to Explainable AI
• Compositional Belief Update
• On the Explanatory Power of Decision Trees
• On Forgetting in Tractable Propositional Fragments
• Belief Merging by Source Reliability Assessment
• An Approach to Forgetting in Disjunctive Logic Programs that Preserves Strong Equivalence
• Dual Forgetting Operators in the Context of Weakest Sufficient and Strongest Necessary Conditions
• On the Computational Complexity of Non-dictatorial Aggregation
• A Logical Study of Partial Entailment
• On the size of data structures used in symbolic model checking
• Reasoning About Action and Change
• Forgetting and consolidation for incremental and cumulative knowledge acquisition systems
• Bijective Faithful Translations among Default Logics
• Where Fail-Safe Default Logics Fail
• Computing with Logic as Operator Elimination: The ToyElim System
• On Sufficient and Necessary Conditions in Bounded CTL: A Forgetting Approach