Logical Equivalence and De Morgan's Laws

Two statements are logically equivalent when they simply say the same thing in different words: in every possible situation, they're both true or both false. "Equivalent" literally means "equal in value," and here the value is true or false. That's useful because you can always trade one for the other, to simplify a condition or to find the right way to negate it. De Morgan's laws, named after the 19th-century logician Augustus De Morgan, look intimidating, but each is a small, familiar idea: $\neg(p \wedge q)$ (it's not true that both happened) is the same as $\neg p \vee \neg q$ (at least one didn't happen), and $\neg(p \vee q)$ (neither happened) is the same as $\neg p \wedge \neg q$ (both didn't happen). You already use these every day without noticing. The symbols just make them exact.

You've already met one equivalence: $p \to q$ and its contrapositive $\neg q \to \neg p$ have identical truth tables. That's the definition. Two statements are logically equivalent, written $\equiv$, when they agree in every row. And just like $2(x + 1)$ and $2x + 2$ in algebra, equivalent statements can replace each other anywhere, which is how you simplify a messy condition. These are the ones you'll use most:

• Double negation: $\neg\neg p \equiv p$.
• Commutative and associative: $p \wedge q \equiv q \wedge p$, and the same for $\vee$.
• Distributive: $p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)$, and with $\wedge$ and $\vee$ swapped.
• De Morgan: negation flips $\wedge$ to $\vee$ and back.
• Implication: $p \to q \equiv \neg p \vee q$.

Why does De Morgan work? Think about what it takes for "$p$ and $q$" to fail. You don't need both to be false; one failure is enough. So "not ($p$ and $q$)" means "$p$ fails or $q$ fails." In the same way, "$p$ or $q$" fails only when neither one happens, so "not ($p$ or $q$)" means "$p$ fails and $q$ fails."

A tautology is true in every row (like $p \vee \neg p$) and a contradiction is false in every row (like $p \wedge \neg p$). This gives a neat test: two statements are equivalent exactly when their biconditional is a tautology, since "they always agree" is what $\leftrightarrow$ being always true means.

A common mistake. When negating "the server is up and the disk is full," it's tempting to just negate each part and keep the "and": "the server is down and the disk is not full." That's too strong. It describes only one of the ways the original can fail. The correct negation flips the connective too: "the server is down or the disk is not full."

Compilers simplify conditions with these laws, and chip designers use De Morgan's laws to build any circuit out of a single gate type (NAND or NOR).