Advanced Topics: De Morgan’s Laws

Say that you hear a bit o’ fake news on the internet with the article’s headline reading, “Aliens from Mars conquer the Earth”, followed by “DEBUNKED”. Which part was not true? Was it actually Aliens from Venus instead of Mars? Did Aliens from Mars conquer Jupiter instead of Earth? Maybe Aliens don’t exist so they didn’t conquer Earth (unlikely). Regardless, we can use logical operators for this statement.

boolean marsAliens = false;
boolean earthConquered = false;

boolean fakeNews = !(marsAliens && earthConquered);

Our statement could be infinitely complex, so we use De Morgan’s Laws to simplify it and better understand it.

De Morgan’s Laws

De Morgan’s Laws were developed by Augustus De Morgan in the 1800s. They show how to simplify the negation of a complex boolean expression, which is when there are multiple expressions joined by an AND (&&) or OR (||).
For example,  (x < 3) && (y > 2) 

When you negate one of these complex expressions, you can simplify it by flipping the operators and end up with an equivalent expression. De Morgan’s Laws state the following equivalencies. Here’s an easy way to remember De Morgan’s Laws: 

• move the NOT inside, AND becomes OR 

• move the NOT inside, OR becomes AND

In Java, De Morgan’s Laws are written with the following operators:

!(a && b) is equivalent to !a || !b

!(a || b) is equivalent to !a && !b

If we go back to our original fakeNews example, we can rewrite the code after applying DeMorgan’s Law:

boolean marsAliens = false;
boolean earthConquered = false;

boolean fakeNews = !(marsAliens && earthConquered);

//or we can equivalently say

boolean fakeNews = (!marsAliens) || (!earthConquered)

You can also simplify negated boolean expressions that have relational operators like <, >, ==. You can move the negation inside the parentheses by flipping the relational operator to its opposite sign. For example, not (c equals d) is the same as saying c does not equal d. An easy way to remember this is to move the NOT, flip the sign. Notice that == becomes !=, but < becomes >=, > becomes <=, <= becomes >, and >= becomes < where the sign is flipped and an equal sign may also be added or removed.

!(c == d) is equivalent to (c != d)

!(c != d) is equivalent to (c == d)

!(c < d) is equivalent to (c >= d)

!(c > d) is equivalent to (c <= d)

!(c <= d) is equivalent to (c > d)

!(c >= d) is equivalent to (c < d)

Simplifying Expressions

Often, you can simplify boolean expressions to create equivalent expressions. For example, applying De Morgan’s Laws to 

!(x < 3 && y > 2) 

yields 

!(x < 3) || !(y > 2) 

This can then be simplified further by flipping the relational operators to remove the not. So, 

!(x < 3) || !(y > 2) 

is simplified to 

(x >= 3 || y <= 2) 

where the relational operators are flipped and the negation is removed.