Converting a 2-SAT formula into an implication graph
(¬x v y) = (¬y--&gt;x)



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


          = (¬x--&gt;y)



So now this becomes:

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

And we get:

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

And the truth table:

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

As you can see they are equivalent.