Prove that: 1^(°) overlineoverlineA overlineB = A+B; 2^(°)…
Prove that: \[ 1^{\circ}\quad \overline{\overline{A}\,\overline{B}} = A+B; \qquad\qquad 2^{\circ}\quad \overline{\overline{C}+\overline{D}} = CD. \]
Explanation of Method
Two events are equal when they consist of exactly the same outcomes. We therefore take an arbitrary outcome $\omega$ and show, by a chain of equivalent statements, that $\omega$ belongs to the left side exactly when it belongs to the right side. The key logical rules are: "not (P and Q)" is the same as "not P or not Q", "not (P or Q)" is the same as "not P and not Q", and "not not P" is the same as P. We confirm the result with a Venn diagram and a truth table.
Step 1: Notation
| Symbol | Set language | Meaning |
|---|---|---|
| $\overline{A}$ | $\Omega\setminus A$ | $A$ does not occur (opposite event) |
| $AB$ | $A\cap B$ | both $A$ and $B$ occur |
| $A+B$ | $A\cup B$ | at least one of $A$, $B$ occurs |
Two simple facts we will use:
- Double complement: $\overline{\overline{A}} = A$ ("it is not true that $A$ does not occur" means "$A$ occurs").
- $\omega\in\overline{X}$ exactly when $\omega\notin X$.
Step 2: Proof of $1^{\circ}$: $\;\overline{\overline{A}\,\overline{B}} = A+B$
In words first
$\overline{A}\,\overline{B}$ is the event "neither $A$ nor $B$ occurs". Its opposite is "it is not true that neither occurs", i.e. "at least one of them occurs" — which is exactly $A+B$.
Proof by elements
Take any outcome $\omega\in\Omega$. Then
\[ \begin{aligned} \omega\in\overline{\overline{A}\,\overline{B}} &\iff \omega\notin \overline{A}\,\overline{B} &&\text{(definition of complement)}\\ &\iff \text{not}\big(\omega\in\overline{A} \text{ and } \omega\in\overline{B}\big) &&\text{(definition of product)}\\ &\iff \omega\notin\overline{A} \ \text{ or } \ \omega\notin\overline{B} &&\text{(not (P and Q) = not P or not Q)}\\ &\iff \omega\in A \ \text{ or } \ \omega\in B &&\text{(double complement)}\\ &\iff \omega\in A+B &&\text{(definition of sum)}. \end{aligned} \]
Every step is an "if and only if", so both events contain exactly the same outcomes: $\overline{\overline{A}\,\overline{B}} = A+B$. $\blacksquare$
- $\overline{A}\,\overline{B}$: neither $A$ nor $B$
- $A+B$: everything else
Check with a truth table
Write $1$ if the event occurs and $0$ if it does not. There are only four possible combinations for $A$ and $B$:
| $A$ | $B$ | $\overline{A}$ | $\overline{B}$ | $\overline{A}\,\overline{B}$ | $\overline{\overline{A}\,\overline{B}}$ | $A+B$ |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 | 1 | 1 |
The last two columns are identical in every row, which confirms $1^{\circ}$.
Step 3: Proof of $2^{\circ}$: $\;\overline{\overline{C}+\overline{D}} = CD$
In words first
$\overline{C}+\overline{D}$ is the event "$C$ does not occur or $D$ does not occur", i.e. "at least one of them fails". Its opposite is "none of them fails", i.e. "both $C$ and $D$ occur" — which is $CD$.
Proof by elements
\[ \begin{aligned} \omega\in\overline{\overline{C}+\overline{D}} &\iff \omega\notin \overline{C}+\overline{D} &&\text{(definition of complement)}\\ &\iff \text{not}\big(\omega\in\overline{C} \text{ or } \omega\in\overline{D}\big) &&\text{(definition of sum)}\\ &\iff \omega\notin\overline{C} \ \text{ and } \ \omega\notin\overline{D} &&\text{(not (P or Q) = not P and not Q)}\\ &\iff \omega\in C \ \text{ and } \ \omega\in D &&\text{(double complement)}\\ &\iff \omega\in CD &&\text{(definition of product)}. \end{aligned} \]
Hence $\overline{\overline{C}+\overline{D}} = CD$. $\blacksquare$
Check with a truth table
| $C$ | $D$ | $\overline{C}$ | $\overline{D}$ | $\overline{C}+\overline{D}$ | $\overline{\overline{C}+\overline{D}}$ | $CD$ |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 | 1 | 1 |
Again the last two columns agree in every row.
Step 4: A shortcut — $2^{\circ}$ follows from $1^{\circ}$
Identity $1^{\circ}$ holds for any events. Take the complement of both of its sides: $\overline{A}\,\overline{B} = \overline{A+B}$. Now put $A=\overline{C}$ and $B=\overline{D}$; since $\overline{\overline{C}}=C$ and $\overline{\overline{D}}=D$ we get
\[ CD = \overline{\overline{C}+\overline{D}}, \]
which is exactly $2^{\circ}$. Both identities are forms of De Morgan's laws:
\[ \overline{XY} = \overline{X}+\overline{Y}, \qquad \overline{X+Y} = \overline{X}\,\overline{Y}. \]
Indeed, with $X=\overline{A}$, $Y=\overline{B}$ the first law gives $\overline{\overline{A}\,\overline{B}} = A+B$; with $X=\overline{C}$, $Y=\overline{D}$ the second law gives $\overline{\overline{C}+\overline{D}} = CD$.
Step 5: An everyday example
A student takes two exams. $A$ = "passes mathematics", $B$ = "passes physics".
- $\overline{A}\,\overline{B}$ = "fails both exams"; its opposite is "passes at least one exam" $= A+B$.
- $\overline{A}+\overline{B}$ = "fails at least one exam"; its opposite is "passes both exams" $= AB$.
Result
| Identity | Why it holds | Meaning |
|---|---|---|
| $\overline{\overline{A}\,\overline{B}} = A+B$ | De Morgan: $\overline{XY}=\overline{X}+\overline{Y}$ with $X=\overline{A},\ Y=\overline{B}$ | the opposite of "neither occurs" is "at least one occurs" |
| $\overline{\overline{C}+\overline{D}} = CD$ | De Morgan: $\overline{X+Y}=\overline{X}\,\overline{Y}$ with $X=\overline{C},\ Y=\overline{D}$ | the opposite of "at least one fails" is "both occur" |