GATE CS 2007 Q48 — Boolean Algebra

We can prove that statement A is always true using a simple probabilistic argument (the probabilistic method):

Let a CNF formula have $m$ clauses, $C_1, C_2, \dots, C_m$. Each clause $C_i$ is a disjunction of literals. Let us assign a truth value (True or False) to each variable independently and uniformly at random with a probability of $1/2$.

• For any clause $C_i$ containing $k_i$ literals, the clause evaluates to False if and only if all its $k_i$ literals evaluate to False.
• The probability of this happening is $\left(\frac{1}{2}\right)^{k_i}$.
• Since every clause must contain at least one literal ($k_i \ge 1$), the probability that $C_i$ evaluates to False is at most $\frac{1}{2}$.
• Consequently, the probability that $C_i$ evaluates to True is:
  $$\text{P}(C_i \text{ is True}) = 1 - \left(\frac{1}{2}\right)^{k_i} \ge 1 - \frac{1}{2} = \frac{1}{2}$$

By the linearity of expectation, the expected number of clauses that evaluate to True under a random assignment is:

Since the average (expected) number of satisfied clauses across all possible truth assignments is at least $m/2$, there must exist at least one specific truth assignment that satisfies at least $m/2$ (half) of the clauses.

Eliminating other options:

• Option B is false: Unsatisfiable formulas (e.g., $x \land \neg x$) have no truth assignment that satisfies all clauses.
• Option C is false: Since we proved that at least half of the clauses can always be satisfied for any formula, it is impossible to have a formula where every assignment satisfies at most one-fourth of the clauses.