Propositional Variable Forgetting and Marginalization: Semantically, Two Sides of the Same Coin

This paper investigates variable forgetting and marginalization in propositional logic. We show that for finite signatures and infinite signatures, variable forgetting and marginalization are corresponding operations, i.e., they yield semantically equivalent outputs for respective complementary inputs. This observation holds for formulas and also for sets of formulas. For formulas, both operations, variable forgetting and marginalization, are shown to be compatible with disjunctions, but not with conjunction, implication and negation. For general sets of formulas, a consequence is that the element-wise application of these operations to a set of formulas and the application to a formula equivalent to this set are not equivalent in general. However, for every deductively closed set \( X \) , we show that the element-wise application of variable forgetting or marginalization, respectively, and the application to any formula equivalent to \( X \) are equivalent. This latter observation is important because deductively closed sets play an important role in many areas, e.g., in logic-based approaches to knowledge representation and databases.