De Morgan’s Laws

Some time in the 1800’s, Augustus De Morgan published a piece of logic that others had felt intuitively for centuries, and which still comes into play today on a fundamental level in areas like math and computer programming.

Consider the statement “It is hot and humid outside.”  What would it take for this sentence to be false?

If you break it down, the sentence is stating two claims – “It is hot outside,” and “It is humid outside.”  So, for the overall sentence to be false we just need at least one of these two claims to be false.

Informally, we could write the negation of the sentence as, “It is either not hot outside, not humid outside, or both.”  In logic, we take the “or both” part for granted in this type of sentence so it is typically left unsaid.

Putting the words into symbols

Symbolically, we have the following:

p = "It is hot outside"

q = "It is humid outside"

p AND q = "It is hot and humid outside"

~ ( p AND q ) = "It's not the case that it is hot and humid outside"

And here’s where De Morgan’s Laws come into play.  De Morgan says that we can re-word the last sentence this way:

~ ( p AND q ) = ~ p  OR ~ q = "It is either not hot outside, or it is not humid outside"

The essence of De Morgan’s Laws is that they let us convert an “AND” statement into an “OR” statement (or vice-versa), by way of distributing a negation symbol within the statement.

A universally applicable concept

What’s amazing about the laws is that they can manifest themselves in so many ways, and they come into play in a wide range of fields from set theory to computer programming.

I recently came across an older blog post by one of my favorite people in the WordPress community, Tom McFarlin.  The details of the post and why I found it via a Google search are perhaps material for another blog post, but within the post contents I noticed a small error that amounted to a mis-application of De Morgan’s Laws.  Even the best of us make mistakes, right? 🙂

Like a responsible citizen of the web (and someone wanting to capitalize on a chance to reach out to a person I respect from afar), I commented on the blog post and suggested a correction to the article.  It was awesome to see that Tom responded and updated his 4-year-old post based on my observation.

I should take this opportunity to say that I hope some day one of my blog posts from 4 years ago is still relevant enough to help someone out, and that I’ll still be able to respond the same day when someone points out an oversight I made.

Overall, it’s miraculous that a centuries-old abstract concept can be so basic and fundamental that it’s relevant to a discipline as distinctly modern as writing computer code.  I can remember the rule coming up repeatedly in just about every course during my math studies.  Nowadays, it pops up at least once a month, if not more often, as I’m writing code.

In a nutshell, this feeling of continuity between generations is what I love about math and logic.  People like De Morgan were thinking about ideas which they knew had widespread applications beyond anything they ever dreamed possible, knowing they’d probably never see the full extent of results their work would produce.

As for me, I’m just happy to be a part of the continuum.