Boolean Algebra (Help Needed)

Question

How would I draw the gate-level logic circuit of the following Boolean expression? $$ (((A \land B \lor C) \lor D \land E \land F) \lor G \land (H \lor I \land J)). $$ Then how would I implement this Boolean expression using NAND gates only?

Answer 1

Here's the non-simplified circuit (using order of operations from left-to-right unless otherwise noted by parenthesis):

Ok. So, to "simplify" to NAND gates, I'm just going to brute-force it using the conversions from this page: http://en.wikipedia.org/wiki/Logical_NAND

(Good grief! This took longer than I thought it would. I can't imagine what this problem is good for other than punishing helpless students...)

Actually, what I'm going to do, is simplify the expression just to $\uparrow$ (NANDs) and $\neg$ (not), as $\neg P = P\uparrow P$, and is easy to do in the circuit.

The (Starting) expression:

$$\left((A\wedge B\vee C)\vee D\wedge E\wedge F\right) \vee G \wedge(H\vee I\wedge J)$$

Part 1

$$(A\wedge B\vee C)$$ $$(\neg [A\uparrow B]\vee C)\equiv \neg([A\uparrow B]\wedge \neg C) \equiv [A\uparrow B] \uparrow \neg C$$

Adding in the next term (D): $$\begin{align}\left([A\uparrow B] \uparrow \neg C\right) \vee D &\equiv\neg \left([A\uparrow B] \uparrow \neg C\right) \wedge \neg D \\ & \equiv \left([A\uparrow B] \wedge \neg C\right) \wedge \neg D \\ & \equiv \left([A\uparrow B]\right) \wedge (\neg C\wedge \neg D) \end{align}$$

Now add in the next two terms (E, F): $$\begin{align} \left([A\uparrow B]\right) \wedge (\neg C\wedge \neg D) \wedge E \wedge F& \equiv \left([A\uparrow B]\right) \wedge (\neg C\wedge \neg D) \wedge \neg[E \uparrow F]\\ &\equiv \left([A\uparrow B]\right) \wedge \neg (\neg C\uparrow\neg D) \wedge \neg[E \uparrow F]\\ &\equiv \left([A\uparrow B]\right) \wedge \neg\big(\neg (\neg C\uparrow\neg D) \uparrow\neg[E \uparrow F]\big)\\ &\equiv \neg \Big(\left([A\uparrow B]\right) \uparrow \neg\big(\neg (\neg C\uparrow\neg D) \uparrow\neg[E \uparrow F]\big)\Big) \end{align}$$

Let's call that big old thing $P$, so I don't have to keep copy/pasting it...

Part 2

Now let's look at the last expression in parentheses: $$\begin{align} H\vee I \wedge J & \equiv \neg(\neg H \wedge \neg I) \wedge J\\ &\equiv (\neg H \uparrow \neg I) \wedge J\\ &\equiv \neg\Big((\neg H \uparrow \neg I) \uparrow J\Big)\\ \end{align}$$ Let's call that $Q$.

Part 3

Let's now put it together: $$\begin{align}P \vee G \wedge Q &\equiv (\neg P \uparrow \neg G) \wedge Q\\ &\equiv \neg \Big((\neg P \uparrow \neg G) \uparrow Q\Big) \end{align}$$

The circuit

Oh--and did I mention we're not done? Here's the circuit:

Is this totally simplified? No--some double negations can be taken out. But, it is valid per the problem statement.

FYI: I created the graphics in LabVIEW, and tested both expressions output (to catch careless errors), and they match.