Prove that overlineAB+AoverlineB+overlineA…
Prove that \[ \overline{A}B+A\overline{B}+\overline{A}\,\overline{B}=\overline{AB}. \]
Explanation of Method
Two events $A$ and $B$ split the sample space into four non-overlapping pieces: $AB$, $A\overline{B}$, $\overline{A}B$ and $\overline{A}\,\overline{B}$. The left side collects three of these pieces, so it must be "everything except $AB$", which is $\overline{AB}$. We show this three ways: by the laws of the algebra of events, by the four-piece picture, and by a truth table.
Step 1: Method 1 — the algebra of events
Group the terms with $\overline{A}$
\[ \overline{A}B+A\overline{B}+\overline{A}\,\overline{B} = \overline{A}B+\overline{A}\,\overline{B}+A\overline{B} = \overline{A}(B+\overline{B}) + A\overline{B}. \]
Use $B+\overline{B}=\Omega$
\[ = \overline{A}\,\Omega + A\overline{B} = \overline{A} + A\overline{B}. \]
Use the rule $X+\overline{X}Y = X+Y$
This rule says: in the sum "$X$ or (not $X$ and $Y$)", the words "not $X$" can be dropped. Proof: using the second distributive law, $X+\overline{X}Y = (X+\overline{X})(X+Y) = \Omega(X+Y) = X+Y$.
With $X=\overline{A}$, $Y=\overline{B}$ (note $\overline{X}=A$):
\[ \overline{A} + A\overline{B} = \overline{A} + \overline{B}. \]
Use De Morgan's law
\[ \overline{A}+\overline{B} = \overline{AB}. \]
Putting it together:
\[ \overline{A}B+A\overline{B}+\overline{A}\,\overline{B} = \overline{A}+A\overline{B} = \overline{A}+\overline{B} = \overline{AB}. \quad\blacksquare \]
Step 2: Method 2 — start from the right side
By De Morgan, $\overline{AB}=\overline{A}+\overline{B}$. Split each event according to the other one ($\overline{A}=\overline{A}\,\Omega=\overline{A}(B+\overline{B})$ and $\overline{B}=(A+\overline{A})\overline{B}$):
\[ \overline{A}+\overline{B} = \overline{A}B+\overline{A}\,\overline{B} + A\overline{B}+\overline{A}\,\overline{B}. \]
The term $\overline{A}\,\overline{B}$ appears twice; by the idempotent law $\overline{A}\,\overline{B}+\overline{A}\,\overline{B}=\overline{A}\,\overline{B}$:
\[ = \overline{A}B + A\overline{B} + \overline{A}\,\overline{B}, \]
which is the left side. ✓
Step 3: Method 3 — the four pieces of $\Omega$
For any outcome, $A$ either occurs or not, and $B$ either occurs or not. So every outcome lies in exactly one of four pieces:
| Piece | $A$ occurs? | $B$ occurs? | In the left side? |
|---|---|---|---|
| $AB$ | yes | yes | no |
| $A\overline{B}$ | yes | no | yes |
| $\overline{A}B$ | no | yes | yes |
| $\overline{A}\,\overline{B}$ | no | no | yes |
- shaded: $\overline{A}B+A\overline{B}+\overline{A}\,\overline{B}$
The left side consists of all pieces except $AB$, i.e. of all outcomes where "$A$ and $B$ both occur" is false. That is precisely the definition of $\overline{AB}$.
Step 4: Method 4 — truth table
| $A$ | $B$ | $\overline{A}B$ | $A\overline{B}$ | $\overline{A}\,\overline{B}$ | Left side | $AB$ | $\overline{AB}$ |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
The columns "Left side" and $\overline{AB}$ agree in all four rows. ✓
Step 5: In words
The left side says: "only $B$ occurs, or only $A$ occurs, or neither occurs". These are all the possibilities except one — that both occur. So the left side means "it is not true that both $A$ and $B$ occur", which is $\overline{AB}$.
Result
| Identity | Short proof |
|---|---|
| $\overline{A}B+A\overline{B}+\overline{A}\,\overline{B}=\overline{AB}$ | $=\overline{A}(B+\overline{B})+A\overline{B} = \overline{A}+A\overline{B} = \overline{A}+\overline{B} = \overline{AB}$ |
| Laws used | $B+\overline{B}=\Omega$; $\ X+\overline{X}Y=X+Y$; De Morgan $\overline{AB}=\overline{A}+\overline{B}$ |