Back

Ruby and DeMorgan’s Theorem

I’m not sure how prevalent it is in computer science curriculum, but as an electrical engineering major, DeMorgan’s Theorem was an important part of my training in the design of logic circuits and I have found it very useful as a software developer as well. In digital logic design, it would be expressed like this:

deMorgan1

Or in psuedo-code:

!A and !B == !(A or B)

and conversely:

!A or !B == !(A and B)

Basically if you swap OR for AND and move the NOT from the individual terms to the result, the resulting expression is equivalent.

This concept can be particularly useful in ruby because it has both an if and unless condition. I ran into this debugging some code just the other day. A system was setup to send alerts when errors occurred, and this was the condition in the code:

unless already_reported_errors.include?(e) && !Rails.env.development?
  send_alert(e)
end

At first glance, this expression might appear to do the logical thing and only report new errors when not in development. However, if you wrap your head around the double negative, you see that it doesn’t do that at all. This becomes much easier to see if you transform the expression using DeMorgan’s Theorem. Negating the entire expression is the equivalent of changing unless to if. Therefore, the equivalent expression is:

if !already_reported_errors.include?(e) || Rails.env.development?

Which very clearly will send alerts for all errors in the development environment, clearly not the intention. I’m pretty sure the second term was added later as you might have guessed.

Whether debugging or writing code, if a two term boolean expression is difficult to reason about, try transforming it using Demorgan’s Theorem to see if the result is easier to understand.

Leave a Reply

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