2
$\begingroup$

Both wikipedia and my lecturer explained how the 2 satisfiability problem work. However, I am finding it really hard understanding how this formula:

xvy≡ ¬x-->y ≡ ¬y -->x

Then breaks down the following conjectures :

(¬x v y) & (¬y v z) & (¬z v w) & (¬w v ¬x) & 
(x v ¬y) & (y v ¬z) & (z v ¬w) & (w v x)

is converted to an implcation graph.

Heres my attempt:

 (¬x v y) = (¬y-->x)

          = (¬x-->y)

but this cannot be right, as they have diffrent truth tables:

(¬y-->x)

1 0 0 0

1 0 1 1

0 1 1 0

0 1 1 1

(¬ x-->y)

1 0 0 0

0 1 1 1

1 0 0 0

0 1 1 1

I understand once you have the conjectures converted to implication, how to construct the implication graph and find out if its not satisfiable (bad loops).

Could someone please explain clearly how to break down the conjectures to implications?

$\endgroup$
  • 6
    $\begingroup$ Your first conversion is wrong. $\neg x \vee y$ is equivalent to $x\to y$ and to $\neg y\to \neg x$. $\endgroup$ – Shaull Oct 17 '13 at 14:19
6
$\begingroup$
 (¬x v y) = (¬y-->x)

$$\begin{align} \text{rule: } &A \vee B &=& (\neg A \implies B)\\ & \neg x \vee y &=& (\neg\neg x \implies y)\\ & &=& (x \implies y) &(1)\\ \end{align} $$

          = (¬x-->y)

So now this becomes:

$$\begin{align} \text{rule: } &A \implies B &=& (\neg B \implies \neg A)\\ &(x \implies y) &=& (\neg y \implies \neg x) & (2) \end{align} $$

And we get:

$$\begin{align} (x \implies y) & (1)\\ (\neg y \implies \neg x) & (2) \end{align} $$

And the truth table:

$$ \left.\begin{array}{rrrr} x & y & (\neg x \vee y) & (x \implies y) & (\neg y \implies \neg x) \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 \\ \end{array}\right. $$

As you can see they are equivalent.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Am i correct in saying for the second conjecture : (¬y v z) The implications for this is: y-->z, ¬z -->¬y ? $\endgroup$ – joker Oct 21 '13 at 17:15
  • $\begingroup$ @joker correct. $\endgroup$ – Realz Slaw Oct 21 '13 at 17:34

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.