Let be an instance of SAT. As in a previous post, let
denote the i-th clause. Moreover, let
. We know that
.
Evidently, is the set of assignments falsifying
. But, by the Inclusion-Exclusion principle,
.
Since is satisfiable if and only if
, considering
as the set of its clauses, easy calculations will lead to
Theorem: The formula is satisfiable if and only if
.
Pingback: A quick satisfiability check « Marco Benini