1
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

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

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.