Proof

(related to Lemma: Boolean Algebra of Propositional Logic)

Let $B$ be the set of Boolean terms. We want to show that $(B,\wedge,\vee,1,0)$ is a Boolean algebra with respect to the conjunction "$\wedge$", the disjunction "$\vee$": * It follows from the syntax of Boolean terms that $B$ contains the Boolean constants $1$ and $0$ and is closed under the operations "$\wedge$" and "$\vee$". * It is, therefore, sufficient to demonstrate that $(B,\wedge,\vee,1,0)$ is a Boolean algebra by verifying all required properties: 1. The conjunction $\wedge$ is associative as well as the disjunction $\vee$ is associative, i.e. for all \(x,y,z\in B\) $$\begin{array}{c}x\wedge(y\wedge z)=(x\wedge y)\wedge z,\\x\vee (y\vee z)=(x\vee y)\vee z.\end{array}$$ 1. The conjunction $\wedge$ is commutative and the disjunction $\vee$ is commutative, i.e. for all \(x,y \in B\) $$\begin{array}{c}x\wedge y=y \wedge x,\\x\vee y=y\vee x.\end{array}$$ 1. "\(\wedge \)" and "\(\vee \)" are distributive over each other, i.e. for all \(x,y,z\in B\) $$\begin{array}{c}x\wedge (y\vee z)=(x\wedge y)\vee (x\wedge z),\\x\vee (y\wedge z)=(x\vee y)\wedge (x\vee z).\end{array}$$ 1. The Boolean constants $1$ and $0$ have with respect to the conjunction and the disjunction the following properties: * $0\in B$ is the "smallest" element: $0\wedge x=0$ and $x\vee 0=x$ for all Boolean terms $x.$ * $1\in B$ is the "greatest" element: $1\wedge x=x$ and $x\vee 1=1$ for all Boolean terms $x.$ 1. Finally, the negation $\neg x$ is the "complent element": $x\wedge \neg x=0$ and $x\vee \neg x=1$ for all Boolean terms $x.$


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

Github:
bookofproofs


References

Bibliography

  1. Knauer Ulrich: "Diskrete Strukturen - kurz gefasst", Spektrum Akademischer Verlag, 2001
  2. Mendelson Elliott: "Theory and Problems of Boolean Algebra and Switching Circuits", McGraw-Hill Book Company, 1982