[Solved]: How many possible assignments does a CNF sentence have?

Problem Detail: 

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.

Asked By : Ghost

Answered By : Dave Clarke

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).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/4729

3.2K people like this

 Download Related Notes/Documents