Recall from Chapter 3 that a proposition is in 3-conjunctive normal form (3CNF) if it is the…
Recall from Chapter 3 that a proposition is in 3-conjunctive normal form (3CNF) if it is the conjunction of clauses, where each clause is the disjunction of three different variables/negated variables. For example,
is in 3CNF. Recall further that a proposition ϕ is satisfiable if it’s possible to give a truth assignment for the variables of ϕ to true/false so that ϕ itself turns out to be true. We’ve previously discussed that it is believed to be computationally very difficult to determine whether a proposition ϕ is satisfiable (see p. 326)—and it’s believed to be very hard to determine whether ϕ is satisfiable even if ϕ is in 3CNF. But you’ll show here an easy way to satisfy “most” clauses of a proposition ϕ in 3CNF, using randomization
Let ϕ be a proposition in 3CNF. Consider a random truth assignment for ϕ—that is, each variable is set independently to True with probability 1 2 . Prove that a particular clause of ϕ is true under this truth assignment with probability ≥ 7/ 8 .