Turing Complete De Morgan's Law Guide

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.

This should even help you with getting some achievements (but there’s more to them than this).

Disclaimer

This is not some super expert guide.

If you “know” boolean logic this will not do anything for you (I’m sorry).

It is meant to help out people playing this game, who are not too knowledgable regarding boolean logic.

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

Errors? Improvements?

If you found any errors or have any improvements please leave a comment.

This is it guys!! I am sure that you will love Turing Complete De Morgan’s Law Guide that we have shared with you. We are always open to discussion and suggestions from you. Just let us what you thought about the guide in the comment section.

Also, we would like to thank The Legend of Peter. He is the one behind this wonderful guide.