Find the conjunctive normal form in the smallest possible number of variables of $x+x^{'}y$.

Question

Find the conjunctive normal form in the smallest possible number of variables of $x+x^{'}y$.

$x+x^{'}y=(x+yy^{'})+x^{'}y$

How can I proceed?Please help.

The answer is given to be $x+y$ which I don't know how to get.Please help.

Answer 1

Note that to convert an expression into conjuctive normal form, we use a combination of five rules classified under:

• Double Negation

• De Morgan Laws

• Distributive Laws

Note that they are already outlined here.

---

Now, we can just use Rule 4 of the answer (Distributive law no.1) to get the required result as $$x \lor x' = \text { identity } $$

Answer 2

$$x + x'y \overset{Distribution}{=} (x+x')(x+y) \overset{Complement}{=}1(x+y)\overset{Identity}{=}x+y$$