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

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.

I am not able to understand the solution here

https://math.stackexchange.com/questions/663565/confusion-in-conjunctive...

Plzz provide some detailed explanation

shivani
23 Sep 2017 11:09 am

Try to solve it using contradicting examples:

1. For any formula, there is a truth assignment for which at least half the clauses evaluate to true. // take AND of x and y in this 1/4 is true as when x=y=T , so statement is false

2. For any formula, there is a truth assignment for which all the clauses evaluate to true. // take OR of x and y ,it is never always T as x=y=F , so statement is false

3. There is a formula such that for each truth assignment, at most one-fourth of the clauses evaluate to true. // take OR of x and y ,3/4 is true as and when any of x or y is T  ,so statement is false

4. None of the above.

So, d is right answer.

maneeshrajan
24 Sep 2017 06:38 pm

Even this seems no intuitive to me.

How are you evaluating clauses to be half, 1/4, 3/4.

For second statement I got it that For any formula, there is no truth assignment for which all the clauses evaluate to true.