A logical notion of conditional independence: properties and applications

摘要

We propose a notion of conditional independence with respect to prepositional logic and study some of its key properties. We present several equivalent formulations of the proposed notion, each oriented towards a specific application of logical reasoning such as abduction and diagnosis. We suggest a framework for utilizing logical independence computationally by structuring a propositional logic database around a directed acyclic graph. This structuring explicates many of the independences satisfied by the underlying database. Based on these structural independences, we develop an algorithm for a class of structured databases that is not necessarily Horn. The algorithm is linear in the size of a database structure and can be used for deciding entailment, computing abductions and diagnoses. The presented results are motivated by similar results in the literature on probabilistic and constraint-based reasoning.