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

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

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

!a && !b == !(a || b)

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)

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

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.

Now let me show you what an OR and a NOT look like 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

Comments

[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