0
$\begingroup$

I am learning how to implement basic logic gates using NAND. I have learnt that you can use De Morgan's theorem as such:

$a+b = \bar{\bar a} + \bar{\bar b} = \overline{(\bar a *\bar b)}$

In other words, we would need two NOT gates (which are basically NAND gates), and another NAND gate.

However, I want to practise Boolean algebra simplification. Using a truth table I have formed the Sum of Products:

$f(a,b)=ab' + a'b + ab$

I have worked down a number of paths unsuccessfully. I would appreciate if someone could either show the steps of simplification, or give me some guidance on the laws to use to achieve this simplification. If there are any notation mistakes I have made, please let me know :)

$\endgroup$
  • $\begingroup$ So your goal is to write $f$ using nothing but NANDs? $\endgroup$ – Draconis Jan 17 at 5:08
  • $\begingroup$ If you want to write $\vee$ (the OR function) using only NANDs, I'm afraid you can't do better than three gates. Two to invert the inputs, and then one to combine them. $\endgroup$ – Draconis Jan 17 at 5:19
  • $\begingroup$ Sum of products is also a good step, but remember that what you're going for is a sum: it's simply $a+b$, in that notation. $\endgroup$ – Draconis Jan 17 at 5:21
  • $\begingroup$ …actually, y'know what, I'll just make this an answer. $\endgroup$ – Draconis Jan 17 at 5:29
1
$\begingroup$

Unfortunately, you've gotten as far as you can get on this problem.

(Note: I'm going to write AND, OR, NOT, and NAND as $\wedge \vee \neg \uparrow$ respectively, since the standard sum/product/overbar notation tends to end up with lots of stacked bars, and I don't like those.)

You currently have:

$$(a \wedge \neg b) \vee (\neg a \wedge b) \vee (a \wedge b)$$

At this point, you could use NANDs to build all those NOTs and ANDs and ORs…but building an OR was your goal in the beginning! Normally, going into sum-of-products form is exactly the right next step to take, but here you're stuck, because you started with a simple sum in the first place.

It turns out the simplest way to build an OR gate out of NANDs is exactly what you were doing at first.

$$\neg a = a \uparrow a$$

$$a \vee b = \neg a \uparrow \neg b$$

$$a \vee b = (a \uparrow a) \uparrow (b \uparrow b)$$

To my knowledge, nobody's ever found a way to build OR with less than three NANDs, and I very much doubt it's possible (though I wouldn't know how to prove that).

$\endgroup$
  • 1
    $\begingroup$ You can prove it (if it’s true) using exhaustive search. $\endgroup$ – Yuval Filmus Jan 17 at 6:08
  • $\begingroup$ And since you are looking for a solution with only two NAND gates, it’s not very exhausting :-) $\endgroup$ – gnasher729 Jan 17 at 10:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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