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

cs.stackexchange https://cs.stackexchange.com/questions/35147

  •  01-11-2019
  •  | 
  •  

Question

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?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top