Satisfiablity 2

Question

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?

Thanks in advance!

Answer 1

No. It is not satisfiable.

You can see this by focusing on a subset of the clauses. In particular: $$\{x, y\},\{x,¬y\},\{¬x, y\},\{¬x,¬y\}$$ Think of them as ordered pairs, $$(x, y),(x,¬y),(¬x, y),(¬x,¬y)$$ Notice that we have all $4$ possible clauses which can be formed from $x$ and $y$. Also, since they are all distinct clauses, any assignment of $0$ or $1$ to $x$ and $y$ will give distinct values for the $4$ ordered pairs.

Since there are $4$ possible ordered pairs of $0$'s and $1$'s (and our clauses must evaluate to $4$ distinct pairs), any assignment must take on all values from the set,

$$\{(0, 0),(0,1),(1, 0),(1,1)\}$$

Hence we must have $(0,0)$

In particular, it is not satisfiable.

Answer 2

Hint:

• You need to assign each variable $\mathtt{true}$ or $\mathtt{false}$ value, so that each clause is satisfied.
• The easiest way to do this for general $2$-CNF is to construct the implication graph. Each clause $\{\alpha, \beta\}$ gives you two implications $\neg \alpha \to \beta$ and $\neg \beta \to \alpha$, for example $\{x,\neg y\}$ would give you $\neg x \to \neg y$ and $y \to x$.
• The formula is satisfiable if and only if the implication graph contains no pair of paths $\alpha \to^* \neg \alpha$ and $\neg\alpha \to^* \alpha$ for some $\alpha$.
• In your particular case you can observe that the first four clauses are all the possible clauses of two variables, hence are not satisfiable together (for any valuation there will be a clause where the negations match exactly the $\mathtt{true}$'s).

I hope this helps $\ddot\smile$