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

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?

• Take a random 3CNF with enough clauses, say five times the number of variables. Mar 13 at 22:02

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.
• 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. Oct 14, 2021 at 13:45