Variable Elimination for Prime-Implicate 0-1 Relaxations of Boolean Constraints

This paper studies what happens to a Boolean constraint when some variables are removed. A remaining assignment can be kept because at least one completion is allowed, or because every completion is allowed. The distinction matters for linear relaxations. The relaxation considered here uses all prime implicates, the minimal clauses satisfied by every allowed assignment. Existential elimination commutes with coordinate projection of this relaxation and therefore preserves integrality. Universal elimination can destroy integrality. The paper gives a four-variable example, an odd-cycle construction, a sufficient condition based on monotonicity, and a separate example distinguishing Boolean complementation from blocker duality. This version explains the objects through examples before introducing their equivalent descriptions. It gives direct attribution for the classical prime-implicate selection rule and includes the ordinary proofs of the general results. Small-dimensional computational counts from the earlier version are reported separately and are not used in those proofs.