Verify the correctness of the following equalities: 1^(°)…

Verify the correctness of the following equalities: \[ \begin{aligned} &1^{\circ}\ \overline{\overline{A}\,\overline{B}}=A+B; \qquad 2^{\circ}\ \overline{\overline{A}+\overline{B}}=AB; \qquad 3^{\circ}\ A+B=AB+A\triangle B;\\ &4^{\circ}\ \overline{A\triangle B}=AB+\overline{A}\,\overline{B}; \qquad 5^{\circ}\ A\triangle B=\big(\overline{A\overline{B}}\big)\triangle\big(\overline{\overline{A}B}\big);\\ &6^{\circ}\ \overline{\textstyle\bigcup_{i=1}^{n} A_i}=\textstyle\bigcap_{i=1}^{n}\overline{A_i}; \qquad 7^{\circ}\ \overline{\textstyle\bigcap_{i=1}^{n} A_i}=\textstyle\bigcup_{i=1}^{n}\overline{A_i}. \end{aligned} \] Here $A\triangle B = A\overline{B}+\overline{A}B$ is the symmetric difference of $A$ and $B$.

Step 1: Preliminaries

The symmetric difference $A\triangle B$ is the event "exactly one of $A$, $B$ occurs":

\[ A\triangle B = A\overline{B} + \overline{A}B. \]

The two events $A$ and $B$ split $\Omega$ into four non-overlapping pieces:

The rule $X+\overline{X}Y=X+Y$ will also be useful. It follows from the second distributive law: $X+\overline{X}Y=(X+\overline{X})(X+Y)=\Omega(X+Y)=X+Y$.

Step 2: $1^{\circ}$ $\;\overline{\overline{A}\,\overline{B}}=A+B$

By De Morgan's law for a product, $\overline{XY}=\overline{X}+\overline{Y}$ with $X=\overline{A}$, $Y=\overline{B}$:

\[ \overline{\overline{A}\,\overline{B}} = \overline{\overline{A}}+\overline{\overline{B}} = A+B. \qquad \textbf{True.} \]

In words: the opposite of "neither occurs" is "at least one occurs".

Step 3: $2^{\circ}$ $\;\overline{\overline{A}+\overline{B}}=AB$

By De Morgan's law for a sum, $\overline{X+Y}=\overline{X}\,\overline{Y}$:

\[ \overline{\overline{A}+\overline{B}} = \overline{\overline{A}}\;\overline{\overline{B}} = AB. \qquad \textbf{True.} \]

In words: the opposite of "at least one fails" is "both occur".

Step 4: $3^{\circ}$ $\;A+B=AB+A\triangle B$

Write out the right side and group the terms containing $A$:

\[ AB + A\overline{B} + \overline{A}B = A(B+\overline{B}) + \overline{A}B = A + \overline{A}B = A+B. \qquad \textbf{True.} \]

The last step is the rule $X+\overline{X}Y=X+Y$. In words: "at least one occurs" splits into "both occur" and "exactly one occurs". In the picture, $A+B$ consists of the three pieces $AB$, $A\overline{B}$, $\overline{A}B$.

Step 5: $4^{\circ}$ $\;\overline{A\triangle B}=AB+\overline{A}\,\overline{B}$

Apply De Morgan twice:

\[ \overline{A\triangle B} = \overline{A\overline{B}+\overline{A}B} = \overline{A\overline{B}}\cdot\overline{\overline{A}B} = (\overline{A}+B)(A+\overline{B}). \]

Multiply out and remove impossible products ($\overline{A}A=\varnothing$, $B\overline{B}=\varnothing$):

\[ = \overline{A}A + \overline{A}\,\overline{B} + BA + B\overline{B} = \overline{A}\,\overline{B} + AB. \qquad \textbf{True.} \]

In words: "not exactly one occurs" means "both occur or neither occurs" — the two white pieces in the picture.

Step 6: $5^{\circ}$ $\;A\triangle B=\big(\overline{A\overline{B}}\big)\triangle\big(\overline{\overline{A}B}\big)$

Let $U=\overline{A\overline{B}}=\overline{A}+B$ and $V=\overline{\overline{A}B}=A+\overline{B}$ (De Morgan). By the definition of the symmetric difference,

\[ U\triangle V = U\overline{V} + \overline{U}V. \]

We need the complements: $\overline{V}=\overline{\overline{\overline{A}B}}=\overline{A}B$ and $\overline{U}=A\overline{B}$. Then

• $U\overline{V} = (\overline{A}+B)\,\overline{A}B = \overline{A}B$, because $\overline{A}B\subseteq\overline{A}+B$ (absorption);
• $\overline{U}V = A\overline{B}\,(A+\overline{B}) = A\overline{B}$, because $A\overline{B}\subseteq A+\overline{B}$ (absorption).

\[ U\triangle V = \overline{A}B + A\overline{B} = A\triangle B. \qquad \textbf{True.} \]

A useful general fact is behind this: $X\triangle Y = \overline{X}\triangle\overline{Y}$ ("exactly one of $X,Y$ occurs" is the same as "exactly one of them fails"). Here $U=\overline{A\overline{B}}$ and $V=\overline{\overline{A}B}$, and $A\overline{B}\triangle\overline{A}B = A\overline{B}+\overline{A}B$ because these two pieces never overlap.

Step 7: $6^{\circ}$ $\;\overline{\bigcup_{i=1}^{n} A_i}=\bigcap_{i=1}^{n}\overline{A_i}$

Take any outcome $\omega$:

\[ \begin{aligned} \omega\in\overline{\textstyle\bigcup_i A_i} &\iff \omega \text{ belongs to none of } A_1,\dots,A_n\\ &\iff \omega\notin A_1 \text{ and } \omega\notin A_2 \text{ and } \dots \text{ and } \omega\notin A_n\\ &\iff \omega\in\overline{A_1}\text{ and }\dots\text{ and }\omega\in\overline{A_n} \iff \omega\in\textstyle\bigcap_i\overline{A_i}. \end{aligned} \]

True — this is De Morgan's law for $n$ events: "none of the events occurs" = "each of them fails".

Step 8: $7^{\circ}$ $\;\overline{\bigcap_{i=1}^{n} A_i}=\bigcup_{i=1}^{n}\overline{A_i}$

\[ \begin{aligned} \omega\in\overline{\textstyle\bigcap_i A_i} &\iff \text{it is not true that } \omega \text{ belongs to all } A_i\\ &\iff \omega\notin A_i \text{ for at least one } i\\ &\iff \omega\in\overline{A_i}\text{ for at least one } i \iff \omega\in\textstyle\bigcup_i\overline{A_i}. \end{aligned} \]

True — "not all events occur" = "at least one of them fails".

Note that $7^{\circ}$ also follows from $6^{\circ}$: apply $6^{\circ}$ to the events $\overline{A_1},\dots,\overline{A_n}$ and take complements of both sides.

Step 9: Truth-table check of $3^{\circ}$, $4^{\circ}$ and $5^{\circ}$

Column $A+B$ = column $AB+A\triangle B$ ($3^{\circ}$); column $\overline{A\triangle B}$ = column $AB+\overline{A}\,\overline{B}$ ($4^{\circ}$); column $U\triangle V$ = column $A\triangle B$ ($5^{\circ}$). ✓