[Solved]: How many satisfying assignments are there in a set of 3-CNF clauses where no clause share the same variable?

Problem Detail: 

Say I have a set of 3-CNF clauses $$\mathcal{S} = \{ x_1 \vee x_2 \vee \bar{x_3}, ~~x_4 \vee x_5 \vee x_6\}$$

where $\bar{x}$ is the negation of $x$. Each variable range over $\mathbb{Z}^2$.

How many satisfying assginments are there for $S$? In general, how many satisfying assignments are there for $S$ is the size of $S$ is k?

This is a question about what is a satisfying assignment for 3-disjunctive clause as much as it is about counting. For example when I just have $C = x_1 \vee x_2 \vee \bar{x_3}$, there are $2^3 = 8$ possible assignments: $$1 1 1\\ 0 1 1 \\ 1 0 1\\ 1 1 0\\ 1 0 0\\ 0 1 0\\ 0 0 1\\ 0 0 0 $$ But which one of these are satisfying assignments?

Asked By : chibro2

Answered By : jnalanko

As you noted, for every clause there are $2^3$ possible assignments. Exactly one of them does not satisfy the clause: it's the one that has false for all variables that appear in the clause as a positive, and true for the variables that appear as a negative. In your example it is $001$. The rest of the assignments satisfy the clause. Therefore there are $2^3 - 1 = 7$ satisfying assignments for each clause, which means there are $7^k$ possible assignments in total.

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents