# Boolean Logic - Realization with using only 4 NAND gates

I am currently preparing the next semester of my program at university and I am stuck at a question of the "Digital Circuits" class.

[...] pump P1 runs when the fill-level of the tank falls below 90% (U=0), however only when the opacity sensor gives output (S1=1) at the same time. If the lower fill-level sensor signals with L=0 that the fill-level is below 50%, pump P1 runs (P1=1) independently of the opacity sensor signals (S1), as long as U=0 at the same time. [...]

The task is first to derive the Boolean equation for the combinational logic of the pump controller (output signal).

I ended up with P1 = U'*(S1+L').

We are then to realize the controller using only NAND2 gates with the hint that if 4 NAND2 gates are not sufficient to realize the circuit, we should consider further simplifying the Boolean equation.

This is where my problem lies:

I can only get to realizing the circuit with 5 NAND2 gates:

P1 = U'*(S1+L') = U'*(S1+L')'' = U'*(S1'*L)'

simulate this circuit – Schematic created using CircuitLab

I don't see any way how I could possibly simplify it any further. Maybe somebody could give me a hint.

Unless I have made an error (very likely) I believe this can be done with 3 NAND gates. The truth table must look like this: $$\begin{smallmatrix}\begin{array}{rrr|cc} U & S1 & L & P1 & \text{comments}\\ \hline 0 & 0 & 0 & 1 &\\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & x & \text{can't happen}\\ 1 & 0 & 1 & 0\\ 1 & 1 & 0 & x & \text{can't happen}\\ 1 & 1 & 1 & 0\\ \end{array}\end{smallmatrix}$$ Using a Karnaugh map to find the Boolean expression yields a realization that uses 3 2-input NAND-gates.

• I am not sure the don't care cases are justified based on the question wording...Although they do make sense, as the tank can't be both filled more than 90% and less than 50%. This is probably the right approach. Jul 29, 2021 at 18:21
• Yeah, added this to comment too, looks like it is the only way to get less than 5 NANDs. Upvoted Jul 29, 2021 at 18:25
• Just a thought. Why would the problem statement writer take the time to say that if L=0 the pump runs independent of S1 only if U=0, too? This extra wording has to mean something. Or else why did they bother saying it? It's too definite to be an accident.
– jonk
Jul 29, 2021 at 18:56
• Thanks for the elaborations, they helped me and confirmed that the way I understood the question, it is not really possible to get below 5 NAND2 gates. I am sorry that I omitted part of the problem text. It states that a running pump means P1=1. It also states U=1 and L=0 is possible, because the 50% sensor may be defect and in this case the pump shall not run (P1=0). (That's why i used paranthesis (U'*S1)+(U'*L') = U'*(S1+L'). I think the wording is unclear, but its a question from last year (cant ask the prof). more important is that, my basic understanding is correct. So thank you all! :) Jul 29, 2021 at 23:14
• I'm pretty sure a double-check for U0 when L0 is low is carried over from a real-world requirement not to overflow the tank in case of a failed sensor. So "can't happen" of this answer ignores a safety requirement, which is... let's say, not ideal. Please do not follow the Boeing example. Jul 30, 2021 at 9:30

Eliminating unnecessary words we get…

pump P1 runs … if U=0 only when S1=1…
pump P1 runs =1 independently of S1 only if U=0
pump P1 runs if L=U=0 and S1=x

  P1 = U’*S1 + L’ = ((U*U)’*S1)’*L)’
shows 3 (a*b)‘s meaning 3 NAND’s

• This runs the pump for all cases of L0, not only those of L0 & U0. Jul 30, 2021 at 11:14

Why those parentheses? When L=0, output is independent of any other input, right?

So it is P1 = U'*S1+L' and it can be realized with 4 nands.

• When L=0, output is independent of any other input, right - As long as U=0.... Not quite independent Jul 29, 2021 at 19:17
• Yes, but I mean it is dictated by external factors. Jul 29, 2021 at 19:19
• U is an input, not an external factor. Jul 29, 2021 at 19:20
• When it is under 50%, it is always under %90. So when L=0, U is always 0. External factor is that they being tied by physical reality. Jul 29, 2021 at 19:31
• This physical reality is reflected by "don't cares" in Carl's answer. I didn't check the equivalence of your final expression to his, maybe they are equivalent. But these steps should be elaborated. Jul 29, 2021 at 19:33

Try starting with a complemented output to reduce the number of inversions you need:

P1' = U + S1'*L


If you look at the Karnaugh map for P1, you can see that it's easier to simplify P1' than P1.

• I don't think it helps to reduce the number of NANDs Jul 29, 2021 at 17:36
• @EugeneSh. Changing things so that the pump is ON when the output is 0 does improve things over saying that the pump is ON when the output is 1. So complementing the output does impact the result.
– jonk
Jul 29, 2021 at 19:15
• @jonk Of course, you can redefine the signals to their complements (not only output but the inputs too). But it is not what the problem is asking to do. Jul 29, 2021 at 19:16
• @EugeneSh. Does the problem statement say anything about the output logic value with respect to pump operation? If so, I may have missed it. Otherwise, I'm not sure I understand the "But it is not what the problem is asking to do." Could you elaborate?
– jonk
Jul 29, 2021 at 19:18
• @jonk Actually, you are right. The cited text does not mention the polarity of P1 Jul 29, 2021 at 19:19

There's an active discussion here about the problem statement and its interpretation. I'm taking the position that:

1. You reflected the problem statement to us, accurately.
2. The writer could not possibly have accidentally written the part about the pump ignoring S1 when L=0 only if U=0, as well.

A careful reading of the problem statement suggests that it may not be making an explicit statement about the logic level required for the pump to be ON. It does appear to state that P1 is the pump. Then it also appears to say that P1=1 when the pump is ON. So there is a conflation of two things -- the pump itself is called P1 and also a logic symbol P1 is suggested, too.

But if one either must figure that the content writer accidentally added that indication about U or else is allowing you to make the choice about a logic level distinct from the pump state, I'd go with the latter.

And no, I don't find a lot of shelter in that argument. But I do find at least a little. Also, you noted that the question went on to suggest "simplifying the logic" if you cannot get to four NANDs. I'll take that as an added clue or suggestion, as well.

Therefore, you have your answer. Don't assume that the pump is ON when the output is 1. Instead, plan that the output is 0 when the pump is ON.

• It appears that it does state the logic level for the pump: "pump P1 runs (P1=1)" Jul 29, 2021 at 19:24
• @EugeneSh. You may be right. Let me see if I can develop a counter-argument! Hmm. Okay. Is P1 necessarily the output I must develop just because they say that P1 is 1 when the pump is ON? Maybe P1 is just an abstract variable, not necessarily the logic I must use. I might instead choose to create /P1 (P1'). But yeah. I'm feeling less certain, again. I'll edit to reflect it.
– jonk
Jul 29, 2021 at 19:25
• I guess if you develop a controller box with predefined interfaces... Jul 29, 2021 at 19:27
• @EugeneSh. I added some comments. One thing about P1 is that it is conflated. They use P1 to label the pump itself. They then use P1 as a logic symbol. A pump is not a logic symbol. These are distinctly different. You cannot set P1=1 if P1 is a pump. ;) I find some (not much) shelter in that.
– jonk
Jul 29, 2021 at 19:31