Recently I'm studying 3SAT problem, which is a NP-complete problem. I feel that it's easy to find a boolean formula which is satisfiable,but how about boolean formulas which are unsatisfiable, namely 3-co-SAT problem. Can you help me provide some examples of 3-co-SAT?

The definition of 3SAT problem is supplemented here, which is quoted from the book Computational Theory.

3SAT = {$<\phi>|\phi$ is a satisfiable 3cnf-formula}

Then the definition of 3-co-SAT is

3-co-SAT = {$<\phi>|\phi$ is an unsatisfiable 3cnf-formula}

Is there any problem about the definition of the above sat, 3-co-sat problem?

Can you help me provide some examples of 3-co-SAT?


The formula $$(x\vee y \vee z) \wedge (\overline{x}\vee y \vee z) \wedge(x\vee \overline{y} \vee z) \wedge(x\vee y \vee \overline{z}) \wedge(\overline{x}\vee \overline{y} \vee z) \wedge(\overline{x}\vee y \vee \overline{z}) \wedge(x\vee \overline{y} \vee \overline{z}) \wedge(\overline{x}\vee \overline{y} \vee \overline{z})$$ is in $3$-co-SAT.

  • $\begingroup$ Thank you very much for your answer. It's easy to find that the formula of 3 variables. And how about 1 variables, 2 variables, 4 variables, 5 variables,...? $\endgroup$
    – lz9866
    Oct 14 at 7:27
  • $\begingroup$ For 1 variable, you could choose $(x\vee x \vee x) \wedge (\overline{x}\vee\overline{x}\vee \overline{x})$. A good way to find an unsatisfiable formula is to use a truth table. $\endgroup$
    – Nathaniel
    Oct 14 at 13:45
  1. Pick any unsatisfiable CNF SAT instance.
  2. Transform the CNF to 3-SAT.
  3. The new instance is an element of 3-co-SAT.

Any unsatisfiable satisfiability instance undergoing the same 3-SAT CNF transformation is an example of 3-co-SAT.


Your Answer

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

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