# Boolean Algebra (Help Needed)

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?

-
Let me make sure I'm parsing that right... if $\vee$ is OR and $\wedge$ is AND, is the expression: $$\left((A\wedge B\vee C)\vee D\wedge E\wedge F\right) \vee G \wedge(H\vee I\wedge J)$$ –  apnorton Feb 21 '13 at 1:47
Please do not deface your questions. –  Arthur Fischer Feb 21 '13 at 5:37
I have flagged this question due to the actions of the OP on this question (as well as his others). (The other questions were linked in the flag, and hopefully a moderator can do something about the abuse.) –  Arthur Fischer Feb 21 '13 at 5:51
–  Martin Sleziak Feb 21 '13 at 6:45
@Arjang: Please stop rolling back the question to its original status. While it seems like it this might be beneficial, you should note that every time you do so, it bumps the question to the top of the page only for the OP to come back and ruin the question again. –  JavaMan Feb 21 '13 at 6:50

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.

-
Yes, image uploaded. Regards –  Amzoti Feb 21 '13 at 2:20
@SilentMan Ha. I doubt anyone would call it simpler. But I did reduce it to NANDs. :) –  apnorton Feb 21 '13 at 3:19
@SilentMan No problem. :) I'd like to let you know that there is an "accept" button (the green checkmark next to my post) that you can activate if you think I've satisfactorily answered your question. (It also gives me 15pts of reputation, but of course that has absolutely nothing to do with me saying this ;)) –  apnorton Feb 21 '13 at 3:37