answer = **option A**

**To Prove:** For any formula, there is a truth assignment for which at least half the clauses evaluate to true

**Proof:**

Consider an arbitrary truth assignment. For each of its clause $i$, introduce a random variable. $$X_i = \begin{cases} 1 & \text{if clause } i \text{ is satisfied;} \\ 0 & \text{otherwise.} \end{cases}$$

Then, $X = \sum _i X_i$ is the number of satisfied clauses.

Given any clause $c$, it is unsatisfied only if all of its $k$ constituent literals evaluates to false; as they are joined by OR operator coz the formula is in CNF.

Now, because each literal within a clause has a $\frac{1}{2}$ chance of evaluating to true independently of any of the truth value of any of the other literals, the probability that they are all false is $\left( \frac{1}{2} \right)^k = \frac{1}{2^k}$.

Thus, the probability that $c$ is satisfied(true) is $1- \frac{1}{2^k}$

So, $E(X_i) =1 \times \left( 1- \frac{1}{2^k} \right) = 1- \frac{1}{2^k}$

This means that $E(X_i) \geq \frac{1}{2}$

(try putting arbitrary valid values of k to see that)

Summation on both sides to get $E(X)$,

Therefore, we have $E(X) = \sum_i E(X_i) \geq \frac{m}{2}$; where $m$ is the number of clauses.

$E(X)$ represents expected number of satisfied(to true) clauses.

So, there must exist an assignment that satisfies(to true) at least half of the clauses.