patternModerate
How many possible assignments does a CNF sentence have?
Viewed 0 times
assignmentshowcnfpossiblesentencedoesmanyhave
Problem
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.)
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.
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.
Solution
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).
Of the 32 possibilities, only 16 of them make the formula true – this would have to be checked by hand (or machine).
Context
StackExchange Computer Science Q#4729, answer score: 10
Revisions (0)
No revisions yet.