Equivalence of Definitions of Boolean Algebra

From ProofWiki
Jump to navigation Jump to search

Theorem

The following definitions of the concept of Boolean Algebra are equivalent:

Definition 1

A Boolean algebra is an algebraic system $\left({S, \vee, \wedge, \neg}\right)$, where $\vee$ and $\wedge$ are binary, and $\neg$ is a unary operation.

Furthermore, these operations are required to satisfy the following axioms:

\((BA_1 \ 0)\)   $:$   $S$ is closed under $\vee$, $\wedge$ and $\neg$             
\((BA_1 \ 1)\)   $:$   Both $\vee$ and $\wedge$ are commutative             
\((BA_1 \ 2)\)   $:$   Both $\vee$ and $\wedge$ distribute over the other             
\((BA_1 \ 3)\)   $:$   Both $\vee$ and $\wedge$ have identities $\bot$ and $\top$ respectively             
\((BA_1 \ 4)\)   $:$   $\forall a \in S: a \vee \neg a = \top, a \wedge \neg a = \bot$             


Definition 2

A Boolean algebra is an algebraic system $\left({S, \vee, \wedge, \neg}\right)$, where $\vee$ and $\wedge$ are binary, and $\neg$ is a unary operation.

Furthermore, these operations are required to satisfy the following axioms:

\((BA_2 \ 0)\)   $:$   Closure:      \(\displaystyle \forall a, b \in S:\) \(\displaystyle a \vee b \in S \)             
\(\displaystyle a \wedge b \in S \)             
\(\displaystyle \neg a \in S \)             
\((BA_2 \ 1)\)   $:$   Commutativity:      \(\displaystyle \forall a, b \in S:\) \(\displaystyle a \vee b = b \vee a \)             
\(\displaystyle a \wedge b = b \wedge a \)             
\((BA_2 \ 2)\)   $:$   Associativity:      \(\displaystyle \forall a, b, c \in S:\) \(\displaystyle a \vee \left({b \vee c}\right) = \left({a \vee b}\right) \vee c \)             
\(\displaystyle a \wedge \left({b \wedge c}\right) = \left({a \wedge b}\right) \wedge c \)             
\((BA_2 \ 3)\)   $:$   Absorption Laws:      \(\displaystyle \forall a, b \in S:\) \(\displaystyle \left({a \wedge b}\right) \vee b = b \)             
\(\displaystyle \left({a \vee b}\right) \wedge b = b \)             
\((BA_2 \ 4)\)   $:$   Distributivity:      \(\displaystyle \forall a, b, c \in S:\) \(\displaystyle a \wedge \left({b \vee c}\right) = \left({a \wedge b}\right) \vee \left({a \wedge c}\right) \)             
\(\displaystyle a \vee \left({b \wedge c}\right) = \left({a \vee b}\right) \wedge \left({a \vee c}\right) \)             
\((BA_2 \ 5)\)   $:$   Identity Elements:      \(\displaystyle \forall a, b \in S:\) \(\displaystyle \left({a \wedge \neg a}\right) \vee b = b \)             
\(\displaystyle \left({a \vee \neg a}\right) \wedge b = b \)             


Proof

Definition 1 implies Definition 2

Let $\left({S, \vee, \wedge, \neg}\right)$ be an algebraic system which satisfies the criteria of Definition 1.


Axiom $(BA_2 \ 0)$

From Axiom $(BA_1 \ 0)$, we have that $\left({S, \vee, \wedge, \neg}\right)$ is closed under $\vee$, $\wedge$ and $\neg$.

That is:

$\forall a, b \in S: a \vee b \in S$
$\forall a, b \in S: a \wedge b \in S$
$\forall a \in S: \neg a \in S$


Axiom $(BA_2 \ 1)$

From Axiom $(BA_1 \ 1)$, we have that $\vee$ and $\wedge$ are commutative on $S$.

That is:

$\forall a, b \in S: a \vee b = b \vee a$
$\forall a, b \in S: a \wedge b = b \wedge a$


Axiom $(BA_2 \ 2)$

From Operations of Boolean Algebra are Associative:

$\forall a, b, c \in S: a \vee \left({b \vee c}\right) = \left({a \vee b}\right) \vee c$
$\forall a, b, c \in S: a \wedge \left({b \wedge c}\right) = \left({a \wedge b}\right) \wedge c$


Axiom $(BA_2 \ 3)$

From Absorption Laws (Boolean Algebras):

For all $a, b \in S$:

$a = a \vee \left({a \wedge b}\right)$
$a = a \wedge \left({a \vee b}\right)$

The specific format in which these results are expressed in axiom $(BA_2 \ 3)$ follow from Axiom $(BA_2 \ 1)$: $\vee$ and $\wedge$ are commutative on $S$.


Axiom $(BA_2 \ 4)$

From Axiom $(BA_1 \ 2)$, we have that both $\vee$ and $\wedge$ distribute over the other.

Hence:

$\forall a, b, c \in S: a \wedge \left({b \vee c}\right) = \left({a \wedge b}\right) \vee \left({a \wedge c}\right)$
$\forall a, b, c \in S: a \vee \left({b \wedge c}\right) = \left({a \vee b}\right) \wedge \left({a \vee c}\right)$


Axiom $(BA_2 \ 5)$

We have:

\(\displaystyle \left({a \wedge \neg a}\right) \vee b\) \(=\) \(\displaystyle \bot \vee b\) Boolean Algebra: Axiom $(BA_1 \ 4)$
\(\displaystyle \) \(=\) \(\displaystyle b\) Boolean Algebra: Axiom $(BA_1 \ 3)$


\(\displaystyle \left({a \vee \neg a}\right) \wedge b\) \(=\) \(\displaystyle \top \wedge b\) Boolean Algebra: Axiom $(BA_1 \ 4)$
\(\displaystyle \) \(=\) \(\displaystyle b\) Boolean Algebra: Axiom $(BA_1 \ 3)$


All axioms are fulfilled.

$\Box$


Definition 2 implies Definition 1

Let $\left({S, \vee, \wedge, \neg}\right)$ be an algebraic system which satisfies the criteria of Definition 2.


Axiom $(BA_1 \ 0)$

From Axiom $(BA_2 \ 0)$, we have that

$\forall a, b \in S: a \vee b \in S, \ a \wedge b \in S, \ \neg a \in S$

That is, $\left({S, \vee, \wedge, \neg}\right)$ is closed under $\vee$, $\wedge$ and $\neg$.


Axiom $(BA_1 \ 1)$

From Axiom $(BA_2 \ 2)$, we have that:

$\forall a, b \in S: a \vee b = b \vee a, \ a \wedge b = b \wedge a$

That is, $\vee$ and $\wedge$ are commutative on $S$.


Axiom $(BA_1 \ 2)$

From Axiom $(BA_2 \ 4)$, we have that:

$\forall a, b, c \in S: a \wedge \left({b \vee c}\right) = \left({a \wedge b}\right) \vee \left({a \wedge c}\right)$
$\forall a, b, c \in S: a \vee \left({b \wedge c}\right) = \left({a \vee b}\right) \wedge \left({a \vee c}\right)$

From Axiom $(BA_1 \ 1)$, we have that $\vee$ and $\wedge$ are commutative on $S$, and so:

$\forall a, b, c \in S: \left({a \vee b}\right) \wedge c = \left({a \wedge c}\right) \vee \left({b \wedge c}\right)$
$\forall a, b, c \in S: \left({a \wedge b}\right) \vee c = \left({a \vee c}\right) \wedge \left({b \vee c}\right)$

That is, both $\vee$ and $\wedge$ distribute over the other.


Axiom $(BA_1 \ 4)$

From Meet with Complement is Bottom:

$\exists \bot \in S: \forall a \in S: a \wedge \neg a = \bot$

From Join with Complement is Top:

$\exists \top \in S: \forall a \in S: a \vee \neg a = \top$

These elements $\bot$ and $\top$ are the only elements of $S$ which have these properties.


Axiom $(BA_1 \ 3)$

We have demonstrated Boolean Algebra: Axiom $(BA_1 \ 4)$ above.

Then:

\(\displaystyle \bot \vee b\) \(=\) \(\displaystyle \left({a \wedge \neg a}\right) \vee b\) Boolean Algebra: Axiom $(BA_1 \ 4)$
\(\displaystyle \) \(=\) \(\displaystyle b\) Boolean Algebra: Axiom $(BA_2 \ 5)$
\(\displaystyle \top \wedge b\) \(=\) \(\displaystyle \left({a \vee \neg a}\right) \wedge b\) Boolean Algebra: Axiom $(BA_1 \ 4)$
\(\displaystyle \) \(=\) \(\displaystyle b\) Boolean Algebra: Axiom $(BA_2 \ 5)$

From Axiom $(BA_1 \ 1)$, we have that $\vee$ and $\wedge$ are commutative on $S$, and so:

$b \vee \bot = b :$b \wedge \top = b


That is, $\bot$ is an identity element for $\vee$, and $\top$ is an identity element for $\wedge$.


All axioms are fulfilled.

$\Box$


Hence the result.

$\blacksquare$