# An exact formula for satisfiability

Let $\phi = \bigwedge_{i = 1}^m \bigvee_{j = 1}^n l_{i,j}$ be an instance of SAT. As in a previous post, let $c_i$ denote the i-th clause. Moreover, let $F(c_i) = \{ \sigma \colon \{ x_1, \dots, x_n\} \to \{ \top, \bot \} \colon \sigma( \bigvee_{j = 1}^n l_{i,j} ) = \bot \}$. We know that $|F(c_i)| = 2^{n - |c_i|}$.

Evidently, $\bigcup_{i = 1}^m F(c_i)$ is the set of assignments falsifying $\phi$. But, by the Inclusion-Exclusion principle, $\left| \bigcup_{i = 1}^m F(c_i)\right| = \sum_{i = 1}^m (-1)^{i - 1} \sum_{I \subseteq \{1,\dots,n\}, |I| = j} \left| \bigcap_{j \in I} F(c_j)\right|$.

Since $\phi$ is satisfiable if and only if $\left|\bigcup_{i = 1}^m F(c_i)\right| < 2^n$, considering $\phi$ as the set of its clauses, easy calculations will lead to

Theorem: The formula $\phi$ is satisfiable if and only if $\sum_{I \subseteq \phi} (-1)^{|I|} \left| \bigcap_{c \in I} F(c) \right| > 0$.

### Information

This entry was posted on April 1, 2011 by in Computer Science, Mathematics, Theoretical Computer Science.