Since we now understand what it means for two propositions to be logically equivalent, we can pre-emptively determine cases where the truth values of propositions match, thus finding substitutions for propositions. These are commonly referred to as propositional identities or laws.
Double negation
The negation of the negation of a proposition is logically equivalent to the proposition itself: $$ \begin{equation}\begin{aligned} \neg (\neg p)\equiv p\\ \end{aligned}\end{equation} $$
| $p$ | $\neg p$ | $\neg (\neg p$) |
|---|---|---|
| $T$ | $F$ | $T$ |
| $F$ | $T$ | $F$ |
De Morgan’s Laws
The negation of a disjunction is logically equivalent to the conjunction of the negations of the individual propositions: $$ \begin{equation}\begin{aligned} \neg (p\lor q)\equiv \neg p \land \neg q\\ \end{aligned}\end{equation} $$
| $p$ | $q$ | $\neg p$ | $\neg q$ | $p\lor q$ | $\neg (p\lor q)$ | $\neg p \land \neg q$ |
|---|---|---|---|---|---|---|
| $T$ | $T$ | $F$ | $F$ | $T$ | $F$ | $F$ |
| $T$ | $F$ | $F$ | $T$ | $T$ | $F$ | $F$ |
| $F$ | $T$ | $T$ | $F$ | $T$ | $F$ | $F$ |
| $F$ | $F$ | $T$ | $T$ | $F$ | $T$ | $T$ |
The negation of a conjunction is logically equivalent to the disjunction of the negations of the individual propositions: $$ \begin{equation}\begin{aligned} \neg (p\land q)\equiv\neg p \lor \neg q\\ \end{aligned}\end{equation} $$
| $p$ | $q$ | $\neg p$ | $\neg q$ | $p\land q$ | $\neg (p\land q)$ | $\neg p \lor \neg q$ |
|---|---|---|---|---|---|---|
| $T$ | $T$ | $F$ | $F$ | $T$ | $F$ | $F$ |
| $T$ | $F$ | $F$ | $T$ | $F$ | $T$ | $T$ |
| $F$ | $T$ | $T$ | $F$ | $F$ | $T$ | $T$ |
| $F$ | $F$ | $T$ | $T$ | $F$ | $T$ | $T$ |
Challenge
Using truth tables, prove the following logical equivalences:
- $p\lor 0\equiv p$ (Identity Law)
- $p\land 1\equiv p$ (Identity Law)
- $p\lor 1\equiv 1$ (Annulment Law)
- $p\land 0\equiv 0$ (Annulment Law)
- $p\lor p\equiv p$ (Idempotent Law)
- $p\land p\equiv p$ (Idempotent Law)
- $p\lor \neg p\equiv 1$ (Complement Law)
- $p\land \neg p\equiv 0$ (Complement Law)
- $p\lor q \equiv q\lor p$ (Commutative Law)
- $p\land q\equiv q\land p$ (Commutative Law)
- $p\lor (q\lor r) \equiv (p\lor q)\lor r$ (Associative Law)
- $p\land (q\land r) \equiv (p\land q)\land r$ (Associative Law)
- $p\lor (p\land q) \equiv p$ (Absorption Law)
- $p\land (p\lor q) \equiv p$ (Absorption Law)
- $p\lor (q\land r) \equiv (p\lor q)\land (p\lor r)$ (Distributive Law)
- $p\land (q\lor r) \equiv (p\land q)\lor (p\land r)$ (Distributive Law)
Created using natural intelligence