# Proof

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

$[[x]]_I$ $[[y]]_I$ $[[\neg x]]_I$ $[[\neg y]]_I$ $[[x\wedge y]]_I$ $[[\neg(x\wedge y)]]_I$ $[[(\neg x)\vee (\neg y)]]_I$
$1$ $1$ $0$ $0$ $1$ $0$ $0$
$0$ $1$ $1$ $0$ $0$ $1$ $1$
$1$ $0$ $0$ $1$ $0$ $1$ $1$
$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\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