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.
Notation
∧ – 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.
That means:
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).
Thanks to The Legend of Peter for his great guide, all credit to his effort. you can also read the original guide from Steam Community. enjoy the game.
