# Simplifying SOP: implementing OR with NAND

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 :)

• So your goal is to write $f$ using nothing but NANDs? – Draconis Jan 17 '19 at 5:08
• 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. – Draconis Jan 17 '19 at 5:19
• 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. – Draconis Jan 17 '19 at 5:21
• …actually, y'know what, I'll just make this an answer. – Draconis Jan 17 '19 at 5:29

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).

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