14,740 views
54 votes
54 votes

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

  1. For any formula, there is a truth assignment for which at least half the clauses evaluate to true.

  2. For any formula, there is a truth assignment for which all the clauses evaluate to true.

  3. There is a formula such that for each truth assignment, at most one-fourth of the clauses evaluate to true.

  4. None of the above.

5 Answers

Best answer
62 votes
62 votes

Answer is 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.

edited by
4 votes
4 votes

answer = option A
check : http://goo.gl/ZruULw

edited by
3 votes
3 votes
Easy proof:

You can divide the max-terms into 2  classes such that both are complementary having 2^(n-1) max-terms each for n variables.There is a clear one-one correspondance.Now when you linearly iterate over any one of those classes,atleast one of the two(the image of function in other class or the element itself)must be true.
0 votes
0 votes

This is an intuitive answer.

Using predicate logic, and toying around with the properties of quantifiers, and their negations; we can simplify any CNF to the form of LHS → RHS

When LHS is False, RHS would be unconditionally True.

So, we got the formula to be True for at least half the cases. Hence, Option A.

Answer:

Related questions

66 votes
66 votes
6 answers
1
Kathleen asked Sep 21, 2014
19,176 views
The control signal functions of a $4$-$bit$ binary counter are given below (where $X$ is “don’t care”):$$\small {\begin{array}{|c|c|c|c|l|}\hline\textbf{Clear}& ...
68 votes
68 votes
9 answers
3