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 .

<span>%d</span> bloggers like this:

Pingback: A quick satisfiability check « Marco Benini