A small guide on De Morgan’s Law.
It will allow you to replace NAND gates with AND, OR and NOT gates – or to replace these with NAND gates.
You might even be able to somewhat reduce your gate count.
∧ – AND
∨ – OR
¬ – NOT
⊼ – NAND
⊽ – NOR
[a NAND b] is equals to combining a and b with AND and negating the whole term:
a ⊼ b = ¬ (a ∧ b)
The same is true for NOR regarding OR:
a ⊽ b = ¬ (a ∨ b)
De Morgan’s Law
¬ (a ∧ b) = ¬a ∨ ¬b
¬ (a ∨ b) = ¬a ∧ ¬b
So, if you have [a AND b] negated as a whole [NOT (a AND b)] you can rewrite it by “dragging” the negation into the term (make a ¬a and b ¬b) and replacing AND with OR.
This applies to [a OR b] as well (you just have to replace the OR with AND instead).
As you might have noticed ¬ (a ∧ b) is nothing else than a NAND b.
a ⊼ b = ¬a ∨ ¬b
a ⊽ b = ¬a ∧ ¬b
You can of course verify this by booting up Turing Complete and placing down both [a NAND b] and [(NOT a) or (NOT b)].
Reducing gate count using De Morgan’s Law
¬¬ a = a
You can use this in conjunction with De Morgan’s Law to reduce your gate count, if applicable.
Just have a closer look any time you use a lot of NOT-gates – you might be able to get rid of some of them.
For example ¬(¬a ∨ ¬b) uses 4 gates.
¬(¬a ∨ ¬b) = (¬¬a ∧ ¬¬b) = (a ∧ b)
Now it only uses a single AND gate.
[¬a ∨ ¬b] uses 3 gates.
But you can replace all 3 of those gates with just a single NAND:
[¬a ∨ ¬b] = [¬ (a ∧ b)] = [a ⊼ b]
(see Morgan’s Law section, this is the same term as the definition there).