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$

1 Answer 1

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$
5
  • $\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, 2014 at 19:40
  • $\begingroup$ I should say set $S$ may not contain all the variables in formula $\Phi$ $\endgroup$
    – chibro2
    Dec 11, 2014 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, 2014 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, 2014 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, 2014 at 20:28

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .