De Morgan's Laws (Logic)
Contents |
Theorems
| \(\displaystyle \) | \(\displaystyle \neg p \lor \neg q\) | \(\dashv \vdash\) | \(\displaystyle \neg \left({p \land q}\right)\) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \neg p \land \neg q\) | \(\dashv \vdash\) | \(\displaystyle \neg \left({p \lor q}\right)\) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle p \land q\) | \(\dashv \vdash\) | \(\displaystyle \neg \left({\neg p \lor \neg q}\right)\) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle p \lor q\) | \(\dashv \vdash\) | \(\displaystyle \neg \left({\neg p \land \neg q}\right)\) | \(\displaystyle \) |
Their abbreviation in a tableau proof are collectively $\textrm{DM}$.
Alternative rendition
These can alternatively be rendered as:
| \(\displaystyle \vdash\) | \(\displaystyle \left({\neg p \lor \neg q}\right)\) | \(\iff\) | \(\displaystyle \left({\neg \left({p \land q}\right)}\right)\) | \(\displaystyle \) | |||
| \(\displaystyle \vdash\) | \(\displaystyle \left({\neg p \land \neg q}\right)\) | \(\iff\) | \(\displaystyle \left({\neg \left({p \lor q}\right)}\right)\) | \(\displaystyle \) | |||
| \(\displaystyle \vdash\) | \(\displaystyle \left({p \land q}\right)\) | \(\iff\) | \(\displaystyle \left({\neg \left({\neg p \lor \neg q}\right)}\right)\) | \(\displaystyle \) | |||
| \(\displaystyle \vdash\) | \(\displaystyle \left({p \lor q}\right)\) | \(\iff\) | \(\displaystyle \left({\neg \left({\neg p \land \neg q}\right)}\right)\) | \(\displaystyle \) |
They can be seen to be logically equivalent to the forms above.
Proofs
Proof by Natural Deduction
By the tableau method:
| Line | Pool | Formula | Rule | Depends upon | Notes | |
|---|---|---|---|---|---|---|
| 1 | 1 | $\neg p \lor \neg q$ | P | (None) | ||
| 2 | 2 | $p \land q$ | A | (none) | ||
| 3 | 2 | $p$ | $\land \mathcal E_1$ | 2 | ||
| 4 | 2 | $q$ | $\land \mathcal E_2$ | 2 | ||
| 5 | 5 | $\neg p$ | A | (None) | ||
| 6 | 2, 5 | $\bot$ | $\neg \mathcal E$ | 3, 5 | ||
| 7 | 7 | $\neg q$ | A | (None) | ||
| 8 | 2, 7 | $\bot$ | $\neg \mathcal E$ | 4, 7 | ||
| 9 | 1, 2 | $\bot$ | $\lor \mathcal E$ | 1, 5-6, 7-8 | ||
| 10 | 1 | $\neg \left({p \land q}\right)$ | $\lor \mathcal E$ | 2, 9 |
$\blacksquare$
| Line | Pool | Formula | Rule | Depends upon | Notes | |
|---|---|---|---|---|---|---|
| 1 | 1 | $\neg p \land \neg q$ | P | (None) | ||
| 2 | 1 | $\neg p$ | $\land \mathcal E_1$ | 1 | ||
| 3 | 1 | $\neg q$ | $\land \mathcal E_2$ | 1 | ||
| 4 | 4 | $p \lor q$ | A | (none) | ||
| 5 | 5 | $p$ | A | 5 | ||
| 6 | 1, 5 | $\bot$ | $\neg \mathcal E$ | 5, 2 | ||
| 7 | 7 | $q$ | A | 7 | ||
| 8 | 1, 7 | $\bot$ | $\neg \mathcal E$ | 7, 3 | ||
| 9 | 1, 4 | $\bot$ | $\lor \mathcal E$ | 4, 5-6, 7-8 | ||
| 10 | 1 | $\neg \left({p \lor q}\right)$ | $\neg \mathcal I$ | 4, 9 |
$\blacksquare$
| Line | Pool | Formula | Rule | Depends upon | Notes | |
|---|---|---|---|---|---|---|
| 1 | 1 | $\neg \left({p \lor q}\right)$ | P | (None) | ||
| 2 | 2 | $p$ | A | (None) | ||
| 3 | 2 | $p \lor q$ | $\lor \mathcal I_1$ | 2 | ||
| 4 | 1, 3 | $\bot$ | $\neg \mathcal E$ | 3, 1 | ||
| 5 | 1 | $\neg p$ | $\neg \mathcal I$ | 2, 4 | ||
| 6 | 6 | $q$ | A | (None) | ||
| 7 | 6 | $p \lor q$ | $\lor \mathcal I_2$ | 6 | ||
| 8 | 1, 7 | $\bot$ | $\neg \mathcal E$ | 7, 1 | ||
| 9 | 1 | $\neg q$ | $\neg \mathcal I$ | 6, 8 | ||
| 10 | 1 | $\neg p \land \neg q$ | $\land \mathcal I$ | 5, 9 |
$\blacksquare$
| Line | Pool | Formula | Rule | Depends upon | Notes | |
|---|---|---|---|---|---|---|
| 1 | 1 | $p \land q$ | P | (None) | ||
| 2 | 1 | $p$ | $\land \mathcal E_1$ | 1 | ||
| 3 | 1 | $q$ | $\land \mathcal E_2$ | 1 | ||
| 4 | 4 | $\neg p \lor \neg q$ | A | (None) | ||
| 5 | 5 | $\neg p$ | A | (None) | ||
| 6 | 1, 5 | $\bot$ | $\neg \mathcal E$ | 2, 5 | ||
| 7 | 7 | $\neg q$ | A | (None) | ||
| 8 | 1, 7 | $\bot$ | $\neg \mathcal E$ | 3, 7 | ||
| 9 | 1, 4 | $\bot$ | $\lor \mathcal E$ | 4, 5-6, 7-8 | ||
| 10 | 1 | $\neg \left({\neg p \lor \neg q}\right)$ | $\neg \mathcal I$ | 4, 9 |
$\blacksquare$
| Line | Pool | Formula | Rule | Depends upon | Notes | |
|---|---|---|---|---|---|---|
| 1 | 1 | $p \lor q$ | P | (None) | ||
| 2 | 2 | $\neg p \land \neg q$ | A | (None) | ||
| 3 | 2 | $\neg p$ | $\land \mathcal E_1$ | 2 | ||
| 4 | 2 | $\neg q$ | $\land \mathcal E_2$ | 2 | ||
| 5 | 5 | $p$ | A | (None) | ||
| 6 | 2, 5 | $\bot$ | $\neg \mathcal E$ | 5, 3 | ||
| 7 | 7 | $q$ | A | (None) | ||
| 8 | 2, 7 | $\bot$ | $\neg \mathcal E$ | 7, 4 | ||
| 9 | 1, 2 | $\bot$ | $\lor \mathcal E$ | 1, 5-6, 7-8 | ||
| 10 | 1 | $\neg \left({\neg p \land \neg q}\right)$ | $\neg \mathcal I$ | 2, 9 |
$\blacksquare$
Proofs that use the Law of the Excluded Middle
The following results require the Law of the Excluded Middle to prove, and hence are not accepted by the school of intuitionist logic.
| Line | Pool | Formula | Rule | Depends upon | Notes | |
|---|---|---|---|---|---|---|
| 1 | 1 | $\neg \left({p \land q}\right) $ | P | (None) | ||
| 2 | 2 | $\neg \left ({\neg p \lor \neg q}\right)$ | A | (None) | ||
| 3 | 3 | $\neg p $ | A | (None) | ||
| 4 | 3 | $\neg p \lor \neg q$ | $\lor \mathcal I_1$ | 3 | ||
| 5 | 2, 3 | $\bot$ | $\neg \mathcal E$ | 4, 2 | ||
| 6 | 2 | $p$ | RAA | 3-5 | The LEM is used in the assumption of RAA. | |
| 7 | 7 | $\neg q $ | A | (None) | ||
| 8 | 7 | $\neg p \lor \neg q$ | $\lor \mathcal I_2$ | 3 | ||
| 9 | 2, 7 | $\bot$ | $\neg \mathcal E$ | 8, 2 | ||
| 10 | 2 | $q$ | RAA | 7-9 | The LEM is used in the assumption of RAA. | |
| 11 | 2 | $p \land q$ | $\land \mathcal I$ | 6, 10 | ||
| 12 | 1, 2 | $\bot$ | $\neg \mathcal E$ | 11, 1 | ||
| 13 | 1 | $\neg p \lor \neg q$ | RAA | 2-12 | The LEM is used in the assumption of RAA. |
$\blacksquare$
| Line | Pool | Formula | Rule | Depends upon | Notes | |
|---|---|---|---|---|---|---|
| 1 | 1 | $\neg \left({\neg p \lor \neg q}\right)$ | P | (None) | ||
| 2 | 2 | $\neg \left ({p \land q}\right)$ | A | (None) | ||
| 3 | 2 | $\neg p \lor \neg q$ | SI: from above | 2 | Introducing a sequent proved above | |
| 4 | 1, 2 | $\bot$ | $\neg \mathcal E$ | 3, 1 | ||
| 5 | 1 | $p \land q$ | RAA | 2-4 | The LEM is used in the assumption of RAA. |
$\blacksquare$
| Line | Pool | Formula | Rule | Depends upon | Notes | |
|---|---|---|---|---|---|---|
| 1 | 1 | $\neg \left({\neg p \land \neg q}\right)$ | P | (None) | ||
| 2 | 2 | $\neg \left ({p \lor q}\right)$ | A | (None) | ||
| 3 | 2 | $\neg p \land \neg q$ | SI: from above | 2 | Introducing a sequent proved above | |
| 4 | 1, 2 | $\bot$ | $\neg \mathcal E$ | 3, 1 | ||
| 5 | 1 | $p \lor q$ | RAA | 2-4 | The LEM is used in the assumption of RAA. |
$\blacksquare$
Comment
Note that this:
- $\neg p \land \neg q \dashv \vdash \neg \left({p \lor q}\right)$
can be proved in both directions without resorting to the LEM.
All the others:
- $\neg p \lor \neg q \vdash \neg \left({p \land q}\right)$
- $p \land q \vdash \neg \left({\neg p \lor \neg q}\right)$
- $p \lor q \vdash \neg \left({\neg p \land \neg q}\right)$
are not reversible in intuitionist logic.
Proof by Truth Table
We apply the Method of Truth Tables to the propositions in turn.
As can be seen by inspection, in all cases the truth values under the main connectives match for all models.
$\begin{array}{|ccccc||cccc|} \hline
\neg & p & \lor & \neg & q & \neg & (p & \land & q) \\
\hline
T & F & T & T & F & T & F & F & F \\
T & F & T & F & T & T & F & F & T \\
F & T & T & T & F & T & T & F & F \\
F & T & F & F & T & F & T & T & T \\
\hline
\end{array}$
$\blacksquare$
$\begin{array}{|cccccc||ccc|} \hline
\neg & (\neg & p & \lor & \neg & q) & p & \land & q \\
\hline
F & T & F & T & T & F & F & F & F \\
F & T & F & T & F & T & F & F & T \\
F & F & T & T & T & F & T & F & F \\
T & F & T & F & F & T & T & T & T \\
\hline
\end{array}$
$\blacksquare$
$\begin{array}{|ccccc||cccc|} \hline
\neg & p & \land & \neg & q & \neg & (p & \lor & q) \\
\hline
T & F & T & T & F & T & F & F & F \\
T & F & F & F & T & F & F & T & T \\
F & T & F & T & F & F & T & T & F \\
F & T & F & F & T & F & T & T & T \\
\hline
\end{array}$
$\blacksquare$
$\begin{array}{|cccccc||ccc|} \hline
\neg & (\neg & p & \land & \neg & q) & p & \lor & q \\
\hline
F & T & F & T & T & F & F & F & F \\
T & T & F & F & F & T & F & T & T \\
T & F & T & F & T & F & T & T & F \\
T & F & T & F & F & T & T & T & T \\
\hline
\end{array}$
$\blacksquare$
Source of Name
This entry was named for Augustus De Morgan.
See also
- De Morgan's Laws (Set Theory) for a set theoretic application of these laws.
- De Morgan's Laws (Predicate Logic) for a predicate logic application of these laws.
Sources
- Donald Kalish and Richard Montague: Logic: Techniques of Formal Reasoning (1964): $\text{II}: \S 5$: Theorems $\text{T63 - T67}$
- E.J. Lemmon: Beginning Logic (1965): $\S 1.5$: Theorem $36$, Exercises $1 \ \text {(f), (g), (h)}$
- Alan G. Hamilton: Logic for Mathematicians (1978): $\S 1.2$: Example $1.8 \ \text{(b), (c)}$
- D.J. O'Connor and Betty Powell: Elementary Logic (1980): $\S 1.13$: Exercise $\text{(A)} \ 3, \ 8, \ 9$
- Keith Devlin: The Joy of Sets: Fundamentals of Contemporary Set Theory (1993): $\S 1.1$
- H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability (1996): Exercises $1.14: 12 \ (9), \ (10)$
- Michael R.A. Huth and Mark D. Ryan: Logic in Computer Science: Modelling and reasoning about systems (2000): $\S 1.2.1$: Exercises $1.5: 1 \ \text{(b), (f)}$
- Michael R.A. Huth and Mark D. Ryan: Logic in Computer Science: Modelling and reasoning about systems (2000): $\S 1.2.5$: Exercises $1.6: 1 \ \text{(e)}, 2 \ \text{(a), (b)}$
