Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

closed as off-topic by Jonas Meyer, RecklessReckoner, Solid Snake, Zachary Selk, Yiorgos S. Smyrlis Jun 8 '15 at 6:35

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Jonas Meyer, RecklessReckoner, Solid Snake, Zachary Selk, Yiorgos S. Smyrlis
If this question can be reworded to fit the rules in the help center, please edit the question.

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. – arjafi 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.) – arjafi Feb 21 '13 at 5:51
@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):

Non-simplified circuit

Ok. So, to "simplify" to NAND gates, I'm just going to brute-force it using the conversions from this page:

(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: NAND 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.

share|cite|improve this answer
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

Not the answer you're looking for? Browse other questions tagged or ask your own question.