# Finding a 2SAT instance that has a specific solution set

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.

• What's wrong with enumeration? Commented Jan 15, 2023 at 9:22

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).

• 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$! Commented Jan 16, 2023 at 3:21

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.

• 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. Commented Jan 15, 2023 at 21:20
• I don't understand your question. What does "a litteral can't contain ~a" mean? Commented Jan 15, 2023 at 21:23
• 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). Commented Jan 15, 2023 at 21:24
• 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. Commented Jan 15, 2023 at 21:29
• 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$? Commented Jan 16, 2023 at 2:34