Boolean logic: why is the "opposite" of and equal to or?

Question

In boolean logic, why is the "opposite" of AND (&) equal to OR (|)?

For example, why would !(A & B) be equal to (!A | !B)?

I understand that not A would simply be !A, but why does AND change to OR?

Answer 1

This is called DeMorgan's law, and let us think about it like this... By the way, let

• $\land$ be &&
• $\lor$ be ||
• $\neg$ be !

You have a door, and the door has two locks. To open the door you therefore need keys $A$ and $B$, written $A \land B$.

Well, suppose that someone is not able to open the door. Well, then that must be because they don't have both keys, or, $\neg (A \land B)$.

But analysing this situation, if you do not have two keys, you either lack $A$ or you lack $B$, or in other words, you either $\neg A$ or you $\neg B$.

Hence, $\neg (A \land B) = \neg A \lor \neg B$.

You can go through the exercise with a door where you need 1 of 2 keys to open for the reverse case.