DEV Community

Cover image for De Morgan's Theorem
Nathan Kallman
Nathan Kallman

Posted on • Edited on • Originally published at kallmanation.com

De Morgan's Theorem

In my last post, I hinted that De Morgan's Theorem makes "boolean code more readable" but that "we'll talk more about that later". Later is now! Let's talk about De Morgan's Theorem (or De Morgan's Laws).

De Morgan's Theorem comes in two parts, each in the same pattern:

!(a && b) == !a || !b
!(a || b) == !a && !b
Enter fullscreen mode Exit fullscreen mode

Why Does This Work?

It may not be immediately clear why this works. Why can we just swap between and 'ing, and or 'ing, if we twiddle with the not 's? One way to think about it is that and, and or are "twiddled" opposites of each other:

X Y = AND OR
false false = false false
false true = false true
true false = false true
true true = true true

and has three falses and a true while or has three trues and a false, and the order is also "twiddled" to be reversed.

First not 'ing the input can be thought of as reversing the order of the output:

NOT X NOT Y = AND
true true = true
true false = false
false true = false
false false = false

Now we can see this output is the exact opposite of an or against the opposite inputs. So:

!(!a && !b) == a || b
Enter fullscreen mode Exit fullscreen mode

Which is just a rearranged version of one of the relationships above:

!a && !b == !(a || b)
Enter fullscreen mode Exit fullscreen mode

And giving the same treatment to or first instead of and first will yield the other relationship.

But Intuitively Why Does This Work?

Well, if an apple is not red and not green, would you say that apple is also not red or green? You probably did not even question that those two statements are equivalent: not red and not green has the same meaning as not red or green. But that's exactly the De Morgan's Theorem we worked through above!

!red && !green == !(red || green)
Enter fullscreen mode Exit fullscreen mode

And if that apple was not not red nor not green; you may eventually see through my double negatives that I mean to say the apple is red and green.

!(!red || !green) == red && green
Enter fullscreen mode Exit fullscreen mode

I propose that one of those statements is much more readily understood (both in code and in english). And why De Morgan's Theorem is worth remembering: cleaning up sometimes confusing boolean expressions.

What's This To Do With Wireworld?

Look again at the NAND from the last post in this series.

Image of NAND in Wireworld

Now let me show you what an OR and a NOT look like in Wireworld.

Image of OR in Wireworld
Image of NOT in Wireworld

Look back to the NAND and do you see the pattern? My NAND is actually just an OR with its inputs first NOT'ed. That's exactly what De Morgan told us!

!(a && b) == !a || !b
Enter fullscreen mode Exit fullscreen mode

Top comments (1)

Collapse
 
quasipickle profile image
Dylan Anderson

Ah, I remember learning this in my Discrete Mathematics class in university. The professor's favourite phrase was "intuitively obvious", even for things that weren't