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:
- 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.
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.
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!