# Satisfiabilty 2-sat

Im trying to work out whether the following clause is satisfiable:

{x, y},{x,¬y},{¬x, y},{¬x,¬y},{x, z},{x,¬z},{y, z},{y,¬z}


My basic understanding is to work this out, you must give each literal a true or false assignment to work out if each clause is satisfiable so:

x=1, y=1, z=1,

{1,1}, {x,0}, {0,1}, {0,0}, {1,1}, {1,0}, {1,1}, {1,0}


Therefore the clause {x,y} and {x,z} are satisfiable?

I also heard you can switch the statement so:

x=1, y=0, z=1,

This means {x,y} is not satisfiable.

If we changed z to 0 as well {x,z} would not be satisfiable. What really confuses me here is when the truth assignments are changed, neither clauses are satisfiable.

Where am I going wrong?

## 1 Answer

You seem to assume that both literals in a clause must be true in order to satisfy the clause. However, it is sufficient that one of them is true. So with your first assignment all clauses but {¬x,¬y} are satisfied.

You also mix up some terminology:

• A clause is a single group of literals like {x,y}. What you are trying to satisfy overall is a group of clauses or a formula.
• When you are considering a specific assignment of values, you talk about clauses that are "satisfied", not "satisfiable". Satisfiability is a property of the formula as a whole. (A single clause is always satisfiable.)

PS: Since your formula only uses 3 variables it is feasible to try out each possible assignment of values in order to see if the formula is satisfiable.

• Specifically, "satisfiable" means "can be made true by some assignment"; "satisfied" means "is made true by this assignment". – David Richerby May 3 '14 at 9:07