Incremental Java
DeMorgan's Theorem and Negating Conditions

Negating Conditions

It's often useful to negate a condition. The negation of a condition evaluates to false when the condition evaluates to true. The negation evaluates to true when the condition evaluates to false.

Clearly, all we need to do is to add the ! (the negation operator) in front of a condition to negate it.

But, there are ways to write negations of conditions without using !. It's useful to know these alternate ways.

Negating Expressions with Equality/Relational Operators

Here's a table that summarizes the negation of expressions using equality and relational operators.

Expression Negation of Expression
exprleft == exprright exprleft != exprright
exprleft != exprright exprleft == exprright
exprleft > exprright exprleft <= exprright
exprleft >= exprright exprleft < exprright
exprleft < exprright exprleft >= exprright
exprleft <= exprright exprleft > exprright

What may surprise you is the last four rows. For example, the negation x > y is x <= y. Why? Shouldn't it be x < y?

Definitely not. Think about this way. Suppose I say "I am older than you". Suppose are ages are integers. When am I lying? (This is the same as saying, when is the negation of "I am older than you" true). I'm certainly lying if I'm younger than you.

But I'm also lying if we're the same age. I wouldn't be older than you, if our ages are the same.

So the negation of "I am older than you" is "I am younger than you or the same age". And when you write that as a condition, it becomes <=.

DeMorgan's Theorem

DeMorgan's Theorem has to do with negating conditions whose main operator are conditional AND and conditional OR. This is && and ||.

Let's think about DeMorgan's Theorem. Suppose I say "I am going to buy you ice cream AND I am going to buy you cookies". When would I be lying? That is, when would the negation of what I say be true?

Suppose I just bought ice cream. Then I'd be lying, since I told you I'd also get cookies. Similarly, if I bought just cookies, then I didn't buy ice cream. Certainly, I'm lying if I don't buy you anything. Thus, I am lying if "I don't buy you ice cream OR I don't buy you cookies".

This OR is considered inclusive.

If I had said "I am going to buy you ice cream OR I am going to buy you cookies", I could also buy both.

Now let's consider the negation of the OR statement. When would I be lying?

Suppose I just bought ice cream. That's OK, because I said I'd buy one or the other. Suppose I bought cookies. That's fine too. Suppose I bought both ice cream and cookies. Well, you can't say I lied, right? What if I didn't buy either? Then, I'm lying.

So the negation of the OR statement is "I am not going to buy you ice cream AND I am not going to buy you cookies".

Both these equivalences make up DeMorgan's Theorem.

We didn't get rid of the !, but we did move it closer to the expression. If the expression contains a relational or equality operator, we can use the rules above to negate them. If they contain logical operators, we can apply DeMorgan's again. Eventually we get rid of the !.

Pushing Negation Inward

One way of looking at DeMorgan's Theorem is that it pushes negations inward. Initially, we had the ! operator applied to a large expression, then we pushed it to a smaller subexpression. We also flip AND to OR, and OR to AND.

Now, DeMorgan's Theorem is an equality, which means that we can push negations outwards too (just do the reverse). However, mostly you push negations inward.