Conjunctive Normal Form evaluates true when atleast half of the clauses are true.

Question

This is an Exam question.

Which of the Following is TRUE about formulae in Conjunctive Normal form?

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

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

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

-None

The answer given is : "For any formula, there is a truth assignment for which at least half the clauses evaluate true."

To which I doubt too much!

This problem is asked earlier on this site itself but the accepted answer is somehow not at all satisfying to me.(may be I am a dumba**)

So here is what I interpreted step by step:

1. Interpretation of CNF form: E=(a+b+c)(a+b'+c)(a+b'+c')

(E is the expression/formula) In short product of sum's of literals.

2. Interpretation of term 'clauses': Here in the above case there are 3 clauses. And In the total expression I am having 3 literals a, b, c.

3. Interpretation of the problem : Now First choice says: "For any formula, there is a truth assignment for which at least half the clauses evaluate true."

Means (what i understood): We are simply asked to find for E = 1 how many clauses should evaluate to true? (As soon as I saw this question.. my first answer that popped In my head is: 100%..to which I agree still now) Why / How 100% ? My answer would be : "how on Earth would some one multiply 0's and get 1?!". What I feel those all clauses must evalute to true!!

Analogy:

π = X * Y *Z (π is simply notation where the product is stored..!) This is a product of 3 bits. With 3 bits I can have 8 possibles combinations for these.. 000,001,010,011,100,101,110,111 Now only 111 is the case when π would be 1(which is very obvious..even for a school kid )

Why? Bcoz x=y=z=1 so π=1 * 1 * 1 = 1

And in all 7 other options cases the product would be obviously zero.

That means for product of 3 term to be 'not zero' all three have to be 1 only!! (Yes ofcourse right..or am i wrong here too!!?)

This is the basis for my ans being 100%

So, I think all the clauses must evalute to true, unless that happens, E can't be 1, it would be 0 only..(?)

Plz explain the option, and also comment on my interpretation ..whether that is correct in any sort?

Any help would be much regarded!

Answer 1

As regards your attempt to interpret the problem, for your example $$E=(a+b+c)(a+b'+c)(a+b'+c')$$ there are $3$ clauses, namely $$a+b+c,\;\;a+b'+c,\;\;a+b'+c'$$ But the claim is not about assignments that make $E$ true.

Rather, the claim is that there is some assignment of truth values to the variables that makes at least half of the $3$ clauses true.

For this particular example, using $a=1$ and any truth values for $b,c$ makes all $3$ clauses true.

If instead we take the example $$E=(a)(a')(a')$$ the truth value $a=0$ makes $2$ of the $3$ clauses true, but no truth value for $a$ makes all $3$ clauses true.

Let's consider the actual claim . . .

Claim:

If $P$ is a $\text{CNF}$ expression of the form $P=P_1\land \cdots \land P_k$ with variables in $\{X_1,...,X_n\}$, there is some truth assignment to the variables $X_1,...,X_n$ such that at least half of $P_1,...,P_k$ evaluate to true.

Proof:

Choose any truth assignment for the variables.

If at least half of $P_1,...,P_k$ evaluate to true, we're done.

If not, more than half of $P_1,...,P_k$ must evaluate to false, hence by negating the chosen truth value assignments for the variables, those of $P_1,...,P_k$ which evaluated to false will evaluate to true, so again we're done.