<p>It is not obvious but easy to see that, for some fixed set of satisfying assignments, there is no 2CNF that can satisfy the set of satisfying assignment exactly, when I discover this, I wonder at most how many satisfying assignments are there for a 2CNF with n variables.</p>

<p>Here, all variables must appear in the formula, the formulas I mean here doesn't include such kind of 2CNF:</p>

<ol>
<li><p>there are n-r variables appearing in formula as positive or negative literals or both. (n>r)</p></li>
<li><p>there are r variables not appearing in formula as any form. (r>1)</p></li>
</ol>

<p>If n = 1, that is trivially 1; like formula <span class="math-container">$(x_1 \vee x_1)$</span>, if we don't allow such clause containing two same literals, just <span class="math-container">$(x_1 )$</span> is still a 2CNF, but not exact 2CNF.</p>

<p>else if n = 2, that is 3; like formula <span class="math-container">$(x_1 \vee x_2)$</span></p>

<p>else if n = 3, that is 5; like formula <span class="math-container">$(x_1 \vee x_2)\wedge({x}_1 \vee x_3)$</span></p>

<p>else if n = 4, that is 9; like formula <span class="math-container">$(x_1 \vee x_2)\wedge({x}_1 \vee x_3) \wedge({x}_1 \vee x_4)$</span></p>

<p>for other n?</p>

<p>well, for the form <span class="math-container">$(x_1 \vee x_2)\wedge({x}_1 \vee x_3) \wedge({x}_1 \vee x_4)...\wedge({x}_1 \vee x_n)$</span>, it can be obtained that there are <span class="math-container">$(2^{n-1}+1)$</span> satisfying assignments.</p>

<p>Will the number be any larger?</p>

CC BY-SA 4.0
2020-05-18T23:42:00.187Z
I can't tell what your question is.  The first sentence is very hard to read; it has too many clauses and appears to be a run-on sentence.  Please [edit] your post to state your question clearly.  If you are looking for an algorithm for some task, please specify what are the inputs and what is the desired output.
D.W.
CC BY-SA 4.0
2020-05-20T10:44:09.627Z
@D.W. Well, the question is difficult to parse, but I believe it asks what is the maximum possible number of satisfying assignments of a 2-CNF in which exactly $n$ variables occur, and specifically, if the maximum is $2^{n-1}+1$ (a 2-CNF attaining this value is presented) or larger. (I assume that clauses of the form $x_i\lor\neg x_i$ are disallowed, otherwise the maximum is trivially $2^n$.)
Emil Jeřábek
CC BY-SA 4.0
2020-05-20T12:35:58.527Z
The maximum is indeed $2^{n-1}+1$. This can be easily proved by induction on the number of clauses.
Emil Jeřábek
CC BY-SA 4.0
2020-05-20T16:07:21.713Z
The question needs to be edited to make it clear what is being asked.  $(x_1 \lor \neg x_1) \land (x_2 \lor \neg x_2) \land \cdots)$ achieves $2^n$.   $(x_1 \lor x_2) \land (x_1 \lor x_2) \land (x_1 \lor x_2) \land \cdots$ achieves $2^n \times 3/4$.
D.W.
<sat>
At most how many satisfying assignments are there for a 2SAT with n variables?
Bubble
# At most how many satisfying assignments are there for a 2SAT with n variables?

(Asked by: username_0 on 2020-05-18)

It is not obvious but easy to see that, for some fixed set of satisfying assignments, there is no 2CNF that can satisfy the set of satisfying assignment exactly, when I discover this, I wonder at most how many satisfying assignments are there for a 2CNF with n variables.

Here, all variables must appear in the formula, the formulas I mean here doesn't include such kind of 2CNF:

1. there are n-r variables appearing in formula as positive or negative literals or both. (n>r)
2. there are r variables not appearing in formula as any form. (r>1)

If n = 1, that is trivially 1; like formula $(x\_1 \vee x\_1)$, if we don't allow such clause containing two same literals, just $(x\_1 )$ is still a 2CNF, but not exact 2CNF.

else if n = 2, that is 3; like formula $(x\_1 \vee x\_2)$

else if n = 3, that is 5; like formula $(x\_1 \vee x\_2)\wedge({x}\_1 \vee x\_3)$

else if n = 4, that is 9; like formula $(x\_1 \vee x\_2)\wedge({x}\_1 \vee x\_3) \wedge({x}\_1 \vee x\_4)$

for other n?

well, for the form $(x\_1 \vee x\_2)\wedge({x}\_1 \vee x\_3) \wedge({x}\_1 \vee x\_4)...\wedge({x}\_1 \vee x\_n)$, it can be obtained that there are $(2^{n-1}+1)$ satisfying assignments.

Will the number be any larger?

**Tags:** sat

> **Comments:**
> **username_1**: I can't tell what your question is.  The first sentence is very hard to read; it has too many clauses and appears to be a run-on sentence.  Please [edit] your post to state your question clearly.  If you are looking for an algorithm for some task, please specify what are the inputs and what is the desired output.  
> **username_2**: @username_1 Well, the question is difficult to parse, but I believe it asks what is the maximum possible number of satisfying assignments of a 2-CNF in which exactly $n$ variables occur, and specifically, if the maximum is $2^{n-1}+1$ (a 2-CNF attaining this value is presented) or larger. (I assume that clauses of the form $x_i\lor\neg x_i$ are disallowed, otherwise the maximum is trivially $2^n$.)  
> **username_2**: The maximum is indeed $2^{n-1}+1$. This can be easily proved by induction on the number of clauses.  
> **username_1**: The question needs to be edited to make it clear what is being asked.  $(x_1 \lor \neg x_1) \land (x_2 \lor \neg x_2) \land \cdots)$ achieves $2^n$.   $(x_1 \lor x_2) \land (x_1 \lor x_2) \land (x_1 \lor x_2) \land \cdots$ achieves $2^n \times 3/4$.  

---

## 0 answers

