◀ ▲ ▶Branches / Logic / Proof

Proof

(related to Lemma: De Morgan's Laws (Logic))

• Let $x,y$ be propositions.
• In the following, we will use the semantics of propositional logic, and the definitions of the conjunction "$\wedge$", the disjunction "$\vee$", and the negation "$\neg$".
• We can construct a truth table for $\neg(x\wedge y)$ and $(\neg x)\vee(\neg y)$ respectively:

• Since the values in both columns to the right of the table are equal, it follows that the equivalence $\neg(x\wedge y)\Leftrightarrow(\neg x)\vee (\neg y)$ is a tautology.

• Similarly, we construct truth tables for $\neg(x\vee y)$ and $(\neg x)\wedge(\neg y)$ respectively: $[[x]]_I$| $[[y]]_I$| $[[\neg x]]_I$| $[[\neg y]]_I$| $[[x\vee y]]_I$| $[[\neg(x\vee y)]]_I$| $[[(\neg x)\wedge (\neg y)]]_I$ $1$| $1$| $0$| $0$| $1$| $0$| $0$ $0$| $1$| $1$| $0$| $1$| $0$| $0$ $1$| $0$| $0$| $1$| $1$| $0$| $0$ $0$| $0$| $1$| $1$| $0$| $1$| $1$

• Since the values in both columns to the right of the table are equal, it follows that the equivalence $\neg(x\vee y)\Leftrightarrow(\neg x)\wedge (\neg y)$ is a tautology.

• Altogether, we have shown the laws $$\begin{array}{c}\neg(x\wedge y)=(\neg x)\vee (\neg y)\\\neg(x\vee y)=(\neg x)\wedge (\neg y)\end{array}.$$
  ∎

Thank you to the contributors under CC BY-SA 4.0!

Github:

References

Bibliography

1. Mendelson Elliott: "Theory and Problems of Boolean Algebra and Switching Circuits", McGraw-Hill Book Company, 1982