# A very nice proof of existence

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.