[proofplan]
We prove both [propositional identities](/page/1380) by exhaustive evaluation of truth values. Since $A$ and $B$ are propositions, each has exactly one of the two truth values $T$ and $F$, so there are four assignments for the ordered pair $(A,B)$. For each identity, we compute the truth value of the left-hand side and the right-hand side on all four assignments; equality of the resulting truth-value columns gives the claimed propositional equality.
[/proofplan]
[step:Reduce propositional equality to checking the four truth assignments]
Let $T$ denote the truth value true and let $F$ denote the truth value false. Because $A$ and $B$ are propositions, each has truth value either $T$ or $F$. Therefore the possible truth assignments for the ordered pair $(A,B)$ are
\begin{align*}
(T,T), \qquad (T,F), \qquad (F,T), \qquad (F,F).
\end{align*}
Two propositional expressions in $A$ and $B$ are equal precisely when they have the same truth value for each of these four assignments.
[guided]
Let $T$ denote the truth value true and let $F$ denote the truth value false. The theorem assumes that $A$ and $B$ are propositions, so the only data relevant to evaluating expressions built from $\neg$, $\vee$, and $\wedge$ is the truth value of $A$ and the truth value of $B$.
Since $A$ has two possible truth values and $B$ has two possible truth values, the ordered pair $(A,B)$ has the following four possible truth assignments:
\begin{align*}
(T,T), \qquad (T,F), \qquad (F,T), \qquad (F,F).
\end{align*}
A propositional expression in $A$ and $B$ is determined by its value on these assignments. Hence, to prove that two such expressions are equal, it is enough to verify that their truth values agree in each of the four listed cases.
[/guided]
[/step]
[step:Compare $\neg(A \vee B)$ with $(\neg A) \wedge (\neg B)$ on every assignment]
We compute the two sides under the four truth assignments:
\begin{align*}
A = T,\ B = T &: \qquad \neg(A \vee B) = \neg T = F, \qquad (\neg A) \wedge (\neg B) = F \wedge F = F, \\
A = T,\ B = F &: \qquad \neg(A \vee B) = \neg T = F, \qquad (\neg A) \wedge (\neg B) = F \wedge T = F, \\
A = F,\ B = T &: \qquad \neg(A \vee B) = \neg T = F, \qquad (\neg A) \wedge (\neg B) = T \wedge F = F, \\
A = F,\ B = F &: \qquad \neg(A \vee B) = \neg F = T, \qquad (\neg A) \wedge (\neg B) = T \wedge T = T.
\end{align*}
The two expressions have the same truth value in all four cases. Hence
\begin{align*}
\neg(A \vee B) = (\neg A) \wedge (\neg B).
\end{align*}
[/step]
[step:Compare $\neg(A \wedge B)$ with $(\neg A) \vee (\neg B)$ on every assignment]
We compute the two sides under the four truth assignments:
\begin{align*}
A = T,\ B = T &: \qquad \neg(A \wedge B) = \neg T = F, \qquad (\neg A) \vee (\neg B) = F \vee F = F, \\
A = T,\ B = F &: \qquad \neg(A \wedge B) = \neg F = T, \qquad (\neg A) \vee (\neg B) = F \vee T = T, \\
A = F,\ B = T &: \qquad \neg(A \wedge B) = \neg F = T, \qquad (\neg A) \vee (\neg B) = T \vee F = T, \\
A = F,\ B = F &: \qquad \neg(A \wedge B) = \neg F = T, \qquad (\neg A) \vee (\neg B) = T \vee T = T.
\end{align*}
The two expressions have the same truth value in all four cases. Hence
\begin{align*}
\neg(A \wedge B) = (\neg A) \vee (\neg B).
\end{align*}
[/step]
[step:Assemble the two verified identities]
Combining the two truth-value comparisons gives
\begin{align*}
\neg(A \vee B) &= (\neg A) \wedge (\neg B), \\
\neg(A \wedge B) &= (\neg A) \vee (\neg B).
\end{align*}
These are exactly the two De Morgan laws for the propositions $A$ and $B$.
[/step]
