Pushing Negation Inward

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.

• ! ( expr_left && expr_right ) is equivalent to ! expr_left || ! expr_right )
• ! ( expr_left || expr_right ) is equivalent to ! expr_left && ! expr_right )

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.