Turing Complete: De Morgan’s Law or How to NAND

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

Following, I will use these symbols:
∧ – 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

De Morgan’s Law allows replacing AND and OR with each other under specific circumstances.
¬ (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

As you probably know double negation has no effect.
¬¬ 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.

Related Posts:

Post Author: Robins Chew

Leave a Reply

Your email address will not be published. Required fields are marked *