A very nice proof of existence

Posted on July 15, 2011 by phimuemue

We consider a propositional logic formula in conjunctive normal form, containing \(2^k-1\) clauses, where each clause has exactly k (distinct) variables.

We prove that this formula is satisfiable. First, we consider the following random experiment: We assign each occuring variable (in the whole formula) a value 1 or 0 generating a random assignment of values to variables. Then, the probability that one specific clause is satisfied, is \(1-\dfrac{1}{2^k} = \dfrac{2^k-1}{2^k}\). This is due to the fact that one single clause evaluates to false only for one single assignment of variables (the variables occuring in the clause).

So, we now introduce the following: For each clause \(C_i\), we introduce an indicator variable \(I_i\) indicating whether the corresponding clause is satisfied or not (i.e. \(I_i=1\) iff \(C_i\) is satisfied by our randomly generated assignment). The above considerations yield \(E(I_i)=P(I_i=1) = \dfrac{2^k-1}{2^k}\), where \(E(I_i\) denotes the expected value of \(I_i\) and \(P(A)\) is the probability of event \(A\).

Moreover, we now define \(X=I_1 + I_2 + \dots + I_{2^k-1}\) as the sum over all indication variables. This means, \(X\) stands for the number of satisfied clauses. We compute the expected value \(E(X) = E(I_1 + I_2 + \dots + I_{2^k-1}) = E(I_1) + E(I_2) + \dots + E(I_{2^k-1})\) (since the expected value is linear). This means, we can conclude \(E(X) = \dfrac{2^k-1}{2^k} + \dfrac{2^k-1}{2^k} + \dots + \dfrac{2^k-1}{2^k} = (2^k-1) \cdot \dfrac{2^k-1}{2^k}\).

This can be simplified to \(E(X) = 2^k - 2 + \dfrac{1}{2^k}\). This means, in average, we have \(2^k - 2 + \dfrac{1}{2^k}\) clauses satisfied. Due to the principle of average, this means, that there must exist some assignment of variables such that the number of satisfied clauses \(X \geq 2^k - 2 + \dfrac{1}{2^k}\).

But since \(X\) must be a natural number, this can be restated so that we now know that there must exist an assignemt of variables such that \(X \geq 2^k - 1\), which is the next natural number. But since \(2^k - 1\) is exactly the number of clauses, we now know that all clauses are satisfied, and, thus, the whole formula is satisfied.

Thus, the formula is satisfiable.

I personally find this proof so nice because usually existence proofs involve some routine to construct an explicit solution which is then used as a proof of existence. However, this existence proof purely relies on the averaging principle, and proves the existence of a satisfying assignment without explicitly constructing it. Moreover, the proof uses the probabilistic method, which I consider a very elegant technique.