0
$\begingroup$

For a NOT gate if $x_1$ is input and $x_2$ is the corresponding output, I see the equivalent CNF (conjunctive normal form) is $(x_1 \lor x_2) \land (\overline x_1 \lor \overline x_2)$.

My expectations was that the CNF should not include $x_2$ as it is the output of the gate. I was rather hoping the formula to be of a form $x_2=F(x_1, b_1, b_2, ...)$ where $b_1$, $b_2$, .. are the boolean constants such that when $x_1$ is zero, the $F(.,.,..)$ would yield true just like the NOT gate.

Can anyone help me understand, how come this CNF including $x_2$ is equivalent to a NOT gate. How to draw a truth table for this CNF form as in what value to assign for $x_2$!

$\endgroup$
0
$\begingroup$

Your formula does actually look like $x_2 = F(x_1)$, it's just written with different symbols.

First, we can rewrite the two clauses using implication. Since $(a \to b) \iff (\neg a \lor b)$, we can rewrite the formula as

$$ (\neg x_1 \to x_2) \land (x_2 \to\neg x_1) $$

Now, you can recognize that this is $(a \to b) \land (b \to a)$, which is to say $a \iff b$.

$\iff$ as a boolean operator behaves the same way as $=$; it evaluates to true when its left hand side and right hand side are the same. So your formula is equivalent to

$$ x_2 \iff \neg x_1 $$

Viewing this as a constraint (assuming $x_1$ can be treated as "fixed"), $x_2$ is fixed as $x_2 := \neg x_1 $

$\endgroup$
  • $\begingroup$ @ Curtis F - This definitely proves that the CNF formula is equivalent to NOT gate. However, my specific confusion is - supposes I've a CNF solver which upon receiving the CNF formula above confirms two sets of satisfying assignments ($x_1$=1, $x_2$=0) and ($x_1$=0, $x_2$=1). This means if I choose to use CNF SAT solver instead of solving NOT gate directly, I'll get two solutions, whereas direct solution will yield only $x_1$=0 as valid assignment. Put another way, typically in a Karp-reduction, we transform input x in a problem A to f(x) in B in polynomial time. Here what is f(x) here ? $\endgroup$ – KGhatak Aug 12 at 12:45

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.