1
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ Take a random 3CNF with enough clauses, say five times the number of variables. $\endgroup$
    – Yuval Filmus
    Mar 13, 2022 at 22:02

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\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, 2021 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, 2021 at 13:45
  • $\begingroup$ I reviewed this question, can you give me some examples of 4 variables, 5 variables? I tried to find it, but I couldn't find it. $\endgroup$
    – lz9866
    May 9, 2022 at 14:02
1
$\begingroup$
  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.

Improve this answer
$\endgroup$

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.