0
$\begingroup$

Is there a 2SAT instance of variables $(a,b,c,d,e,f,g)$ that has exactly the solution set $S=\{ (1,0,0,0,0,0,0),(0,1,0,0,0,0,0),(0,0,1,0,0,0,0),(1,1,0,1,0,0,0),(1,0,1,0,1,0,0),(0,1,1,0,0,1,0),(1,1,1,1,1,1,1) \}$? It sounds plausible, but other than enumeration, I can't seem to find a way to prove/disprove that it exists.

$\endgroup$
1
  • 1
    $\begingroup$ What's wrong with enumeration? $\endgroup$
    – Nathaniel
    Jan 15 at 9:22

2 Answers 2

1
$\begingroup$

Let me teach you a systematic way to answer this type of question.

First, write a program to enumerate over all possible clauses, test for each whether it is satisfied by every assignment in $S$, and keep the ones that are satisfied. There are only $O(n^2)$ possible clauses, where $n$ is the number of variables, so this is feasible.

Next, create a formula $\varphi$ by taking the conjunction of all of those clauses. By construction, every assignment in $S$ is satisfied by $\varphi$. Test whether there is any other satisfying assignment to $\varphi$. If there is, the answer is that there is no formula whose solution set is exactly $S$. If there is not, then you have found that there is such a formula, and $\varphi$ is one such.

Since this is your exercise, I will let you write out the details of the proof for why this algorithm works, and how to test whether there is any other satisfying assignment to $\varphi$ (see, e.g., Finding all solutions if you can find one, Rina Dechter and Alon Itai, UC Irvine tech report, 1992-09-16; or Network Flow and 2-Satisfiability, Feder, Algorithmica 1994, vol 11, pp.291--319, Section 8; or just use a SAT solver).

$\endgroup$
1
  • $\begingroup$ Thanks --- I can immediately see that my question is answered in the negative because there is no clause which is satisfied by every assignment in $S$! $\endgroup$ Jan 16 at 3:21
1
$\begingroup$

Let $\varphi$ a 2CNF with $S$ as solution set.

  • Since $(1,1,1,1,1,1,1)$ satisfies $\varphi$, each clause must contain a positive litteral.
  • Since $(1,0,0,0,0,0,0)$ satisfies $\varphi$, each clause must contain either a negative litteral $\neq a$ or $a$.
  • Since $(0,1,0,0,0,0,0)$ satisfies $\varphi$, each clause must contain either a negative litteral $\neq b$ or $b$.
  • Since $S \neq \{0,1\}^7$, no clause can contain a variable and its negation.
  • Since $(0,0,1,0,0,0,0)$ satisfies $\varphi$, there is no clause $(a\lor b)$ in $\varphi$ (and neither $a$ alone or $b$ alone).

Using the above properties, we conclude that each clause contains a positive litteral and a negative litteral.

But the last claim prove that $\mu = (0, 0, 0, 0, 0, 0, 0)$ satisfies $\varphi$. Since $\mu\notin S$, we conclude by contradiction that such a $\varphi$ cannot exist.

$\endgroup$
7
  • $\begingroup$ Thank you for your answer! Ok, I understand everything from the assertion that every clause must contain a negative literal to the end. But what I don't understand is why any literal in the potential instance can't contain ~a,~b, or ~c. $\endgroup$ Jan 15 at 21:20
  • $\begingroup$ I don't understand your question. What does "a litteral can't contain ~a" mean? $\endgroup$
    – Nathaniel
    Jan 15 at 21:23
  • $\begingroup$ In your second bullet point, you say that "each clause must contain either a negative literal $\neq a$", which means, that ~a can't be in any literal (I'm using ~ to mean NOT). $\endgroup$ Jan 15 at 21:24
  • $\begingroup$ There is a either in this sentence, and I think you are sometimes confusing clause and litteral. In the second point, the litterals satisfied by $(1, 0, 0,0,0,0,0)$ are only $a$, $\neg b$, $\neg c$, …, $\neg g$, hence my comment. $\endgroup$
    – Nathaniel
    Jan 15 at 21:29
  • $\begingroup$ Sorry, you're right: I meant "in any clause" instead of "in any literal". What I'm asking though is why can't there be, for example, $(\neg a \lor b)$, in $\varphi$? $\endgroup$ Jan 16 at 2:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.