5
$\begingroup$

I'm having some trouble understanding the following:

When we look at satisfiability problems in conjunctive normal form, an underconstrained problem is one with relatively few clauses constraining the variables. For eg. here is a randomly generated 3-CNF sentence with five symbols and five clauses. (Each clause contains 3 randomly selected distinct symbols, each of which is negated with 50% probability.)

(¬D ∨ ¬B ∨ C) ∧ (B ∨ ¬A ∨ ¬C) ∧ (¬C ∨ ¬B ∨ E) ∧ (E ∨ ¬D ∨ B) ∧ (B ∨ E ∨ ¬C)

16 of the 32 possible assignments are models of this sentence, so, on an average, it would take just 2 random guesses to find the model.

I don't understand the last line- saying that there are 32 possible assignments. How is it 32? And how are only 16 of them models of the sentence? Thanks.

$\endgroup$
10
$\begingroup$

There are 5 (Boolean) variables in the formula. Each of these could be either true or false. This means that there are $2^5=32$ ways of assigning values to these variables.

Of the 32 possibilities, only 16 of them make the formula true – this would have to be checked by hand (or machine).

$\endgroup$
  • 6
    $\begingroup$ To add slightly to this answer — the specific phrase that there are 16 "models" of the formula is a turn of phrase from the study of formal logic, and is just another way to say that there are that many different ways to assign boolean "meanings" to the variables in order to make the formula true; i.e. sixteen satisfying assignments. $\endgroup$ – Niel de Beaudrap Sep 25 '12 at 13:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.