# Equivalence of Definitions of Boolean Algebra

## 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)$
$\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)$

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)$
$\exists \bot \in S: \forall a \in S: a \wedge \neg a = \bot$
$\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$