HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Can anyone give me an instance of 3SAT with exactly one solution?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
anyonecanwithgive3satinstanceonesolutionexactly

Problem

I need an instance of 3SAT with exactly one solution but I cannot think of or find one anywhere. Can anyone please give me an example?

Solution

If you are seeking a formula with 3 variables $x$, $y$, $z$, then you can consider clauses $(\ell_x \vee \ell_y \vee \ell_z)$ where $\ell_x$ is either $x$ or $\neg x$ (and same thing for $\ell_y$ and $\ell_z$). There is a total of 8 such clauses. If you consider a conjunction of all 8 clauses and remove exactly one of them, you get a 3-CNF formula with exactly one solution.

For exemple, if you remove the clause $(\neg x \vee y\vee z)$, then the solution to the formula is given by $x = \top$, $y = \bot$ and $z = \bot$.

Context

StackExchange Computer Science Q#135632, answer score: 17

Revisions (0)

No revisions yet.