Multiple choice

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.
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Since all clauses must be true for a formula (in conjunctive Normal Form) to be true, hence at least for one truth assignments all clauses will evaluate to true.

Keep practicing — related questions