Project ForgeDiscrete Mathematics
Propositional Logic
GATE 2007
Hard
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 to true
- BFor any formula, there is a truth assignment for which all the clauses evaluate to true
- CThere is a formula such that for each truth assignment, at most one-fourth of the clauses evaluate to true
- DNone of the above
Explanation
Standard probabilistic-method argument: under a uniformly random truth assignment, a clause with k≥1 literals is satisfied with probability 1-2⁻ᵏ ≥ 1/2, so the expected number of satisfied clauses is at least half the total — meaning some assignment must achieve at least half. This directly rules out (C) (no formula can force below half in the best case) and (B) is false in general (unsatisfiable formulas exist).
Source: GATE CS 2007 (2007)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.