Which of the following is TRUE about formulae in Conjunctive Normal Form?

Answer: For any CNF formula, there exists a truth assignment that makes at least half of the clauses true.

Proof (probabilistic method):

• Choose a truth assignment by setting each variable independently to true or false with probability 1/2.

• Consider any clause, which is an OR of one or more literals. If a clause has k literals, the probability it is false under the random assignment is the probability that all k literals are false, which equals (1/2)^k.

• Since k >= 1, (1/2)^k <= 1/2, so the probability the clause is true is at least 1/2.

• Let Xi be the indicator random variable for clause i being true. Then E[Xi] >= 1/2 for every clause, so the expected total number of true clauses is E[sum Xi] >= m/2, where m is the number of clauses.

• Therefore there exists some assignment achieving at least m/2 true clauses (if every assignment had fewer than m/2 true clauses, the expectation would be < m/2, a contradiction).

Remarks:

• The claim "For any formula, there is a truth assignment for which all the clauses evaluate to true" is false: for example, the CNF containing the clauses (x) and (not x) is unsatisfiable.

• The claim "There is a formula such that for each truth assignment, at most one-fourth of the clauses evaluate to true" is impossible because the argument above guarantees some assignment satisfies at least half the clauses.

• The probabilistic proof can be turned into a deterministic algorithm (method of conditional expectation) that constructs an assignment satisfying at least half the clauses.