1
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ 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. $\endgroup$ – D.W. May 18 '20 at 23:42
  • $\begingroup$ @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$.) $\endgroup$ – Emil Jeřábek May 20 '20 at 10:44
  • $\begingroup$ The maximum is indeed $2^{n-1}+1$. This can be easily proved by induction on the number of clauses. $\endgroup$ – Emil Jeřábek May 20 '20 at 12:35
  • $\begingroup$ 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$. $\endgroup$ – D.W. May 20 '20 at 16:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.