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