<aside> 🔖 A compound proposition that can never be true is called a contradiction. A compound proposition that is always true is a tautology(恒真式). All other proposition are contingencies.
</aside>
We’ve seen that for instance $p\rarr q \ and\ \neg p \vee q$ represent the same logical function.
Two columns u and v are the iff $u \lrarr v$ consists entirely of T.
ie. $u \lrarr v$ is a tautology.
When $u \lrarr v$ is a tautology,
we say $u\equiv v$(logically equivalent to)
| $u$ | $v$ | $u\lrarr v$ |
|---|---|---|
| T | T | T |
| F | F | T |
| Equivalence | Name |
|---|---|
| $p \wedge T \equiv p \\ p\vee F \equiv p$ | Identity laws |
| $p \vee T \equiv T\\p\wedge F \equiv F$ | Domination laws |
| $p \wedge p \equiv p \\ p\vee p \equiv p$ | Idempotent laws |
| $\neg(\neg p) \equiv p$ | Double negation law |
| $p\vee q \equiv q \vee p\\ p\wedge q \equiv q\wedge p$ | Commutative laws |
| $(p \vee q )\vee r \equiv p \vee (q \vee r) \\ (p \wedge q )\wedge r \equiv p \wedge (q \wedge r)$ | Associative laws |
| $p \vee (q \wedge r) \equiv (p \vee q)\wedge (p \vee r) \\ p \wedge (q \vee r) \equiv (p \wedge q)\vee (p \wedge r)$ | Distributive laws |
| $\neg (p \wedge q ) \equiv \neg p \vee \neg q\\\neg (p \vee q ) \equiv \neg p \wedge \neg q$ | De Morgan’s laws |
| $p \vee (p \wedge q) \equiv p \\ p \wedge (p \vee q) \equiv p$ | Absorption laws |
| $\neg (p \wedge q ) \equiv \neg p \vee \neg q\\\neg (p \vee q ) \equiv \neg p \wedge \neg q$ | Negation laws |
for propositional logic
$$ \neg (p \wedge q ) \equiv \neg p \vee \neg q\\ and \\ \neg (p \vee q ) \equiv \neg p \wedge \neg q $$
$$ \underline{Note}\text{ the similarity to}\\ \overline{A\cap B} = \bar{A}\cup\bar{B}\\\overline{A\cup B}=\bar{A}\cap\bar{B} \\ \text{De Morgan's Laws for Sets} $$
Exercise: Verify these by forming four-row truth tables
| p | q | $\neg (p \wedge q )$ | $\neg p \vee \neg q$ | $\neg (p \vee q )$ | $\neg p \wedge \neg q$ |
|---|---|---|---|---|---|
| T | T | F | F | T | T |
| T | F | T | T | F | F |
| F | T | T | T | F | F |
| F | F | T | T | F | F |
$$ p\vee q\equiv\neg\neg(p\vee q)\\\equiv\neg(\neg(p\vee q))\\\equiv\neg(\neg p\wedge\neg q) $$
| $a+b = b+a\\ a\times b=b\times a$ | Commutative laws | $p\vee q \equiv q \vee p\\ p\wedge q \equiv q\wedge p$ |
|---|---|---|
| $(a+b)+c=a+(b+c)\\ (a×b)×c=a×(b×c)$ | Associative laws | $(p \vee q )\vee r \equiv p \vee (q \vee r)\equiv p\vee q\vee r \\ (p \wedge q )\wedge r \equiv p \wedge (q \wedge r)\equiv p\wedge q\wedge r$ |
| $a×(b+c)=a×b+a×c$ | Distributive laws | $p \vee (q \wedge r) \equiv (p \vee q)\wedge (p \vee r) \\ p \wedge (q \vee r) \equiv (p \wedge q)\vee (p \wedge r)$ |