Simplify the given boolean expression into the "Canonical Conjunctive Normal Form“.

Question

Simplify the boolean expression, into the “Canonical Conjunctive Normal Form":

$$x_0\overline{x_0} + x_1\overline{x_1} + \overline{x_2}+x_3$$

---

Here's my attempt:

$$\begin{align} x_0\overline{x_0} + x_1\overline{x_1} + \overline{x_2}+x_3 &\equiv (x_0\overline{x_0} + x_1) \cdot (x_0\overline{x_0} + \overline{x_1}) + \overline{x_2} + x_3\\ &\equiv (x_0 + x_1) \cdot (\overline{x_0} + x_1) \cdot (x_0 + \overline{x_1}) \cdot (\overline{x_0}+ \overline{x_1})+\overline{x_2}+x_3 \\ &\equiv (\overline{x_2} + x_3+(x_0 +x_1) \cdot (\overline{x_0} + x_1)) \cdot (\overline{x_2} + x_3+(x_0 +x_1) \cdot (\overline{x_0} + \overline{x_1})) \\ &\equiv (\overline{x_2}+x_3+x_0+x_1) \cdot (\overline{x_2}+x_3+\overline{x_0}+x_1)\cdot (\overline{x_2}+x_3+x_0+x_1) \cdot (\overline{x_2}+x_3+ \overline{x_0} + \overline{x_1}) \end{align}$$

I know I can simplify the first and third terms, but let's assume that this is my final answer. Is my working out correct? I'm a little unsure because I've never really worked with terms with multiple conjugations and disjunctions at one time.

Answer 1

Note that $x_0\overline{x_0}$ is equal to either $1\cdot 0$ or $0\cdot 1$, both of which equal $0$. Similarly, $x_1\overline{x_1}=0$.

So what remains is $\overline{x_2} + x_3$, which is indeed in conjunctive normal form (aka, a product of sums). Here, we have just one factor in that product.