A very nice proof of existence

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.