1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks! Now suppose I compare the satisfying assignments to set $S$ to the original formula $\Phi$ where the clauses of $S$ comes from. I am not sure if there are more satisfying assignments to $S$ than $\Phi$. Because on the one hand the number of satisfying assignments grows with the number of clauses, on the other hand there may be conflicts so that assignments that satisfies clauses $S$ may not satisfy all clauses in $\Phi$ .. $\endgroup$ – chibro2 Dec 11 '14 at 19:40
  • $\begingroup$ I should say set $S$ may not contain all the variables in formula $\Phi$ $\endgroup$ – chibro2 Dec 11 '14 at 19:46
  • $\begingroup$ How does $S$ "come from" $\Phi$? If $S$ is just $\Phi$ transformed into the conjunctive normal form, then the formulas are logically equivalent, and the satisfying assignments should be the same. $\endgroup$ – jnalanko Dec 11 '14 at 19:57
  • $\begingroup$ My wording is not clear. If $\Phi = (x_1 \vee x_2 \vee x_3) \wedge (x_4 \vee x_5 \vee x_6) \wedge (x_1 \vee \bar{x_4} \vee \bar{x_2})$, then $S_1 = \{x_1 \vee x_2 \vee x_3, ~~x_4 \vee x_5 \vee x_6\}$, and $S_2 = \{x_1 \vee \bar{x_4} \vee \bar{x_2}\}$ You see $S_1$ is a disjoint set, but there are assignments to $S_1$ that does not satisfy $\Phi$. Now suppose there are $\epsilon \cdot 2^n$ correct assignments to $\Phi$, the question is how does that compare to the number of satisfying assignments to $S$ $\endgroup$ – chibro2 Dec 11 '14 at 20:23
  • $\begingroup$ My reasoning is that if we examine a satisfying vector $\pmb{a} = (a_1,\ldots,a_{C},a_{C+1},a_n)$, where constant $C$ denotes the number of variables that appear in disjoint set $S$. Then there are $7^C \cdot 2^{n-C-1}$ satisfying vector for $S$, because the varibles that do not appear in $S$ are allow to vary over all possible assignments. But if there's at most $\epsilon 2^n$ total assignements for $\Phi$, then $7^C \times 2^{n-C-1} \le \epsilon 2^n$ $\endgroup$ – chibro2 Dec 11 '14 at 20:28

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.