# 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 $\struct {S, \vee, \wedge, \neg}$, where $\vee$ and $\wedge$ are binary, and $\neg$ is a unary operation.

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

 $(\text {BA}_1 0)$ $:$ $S$ is closed under $\vee$, $\wedge$ and $\neg$ $(\text {BA}_1 1)$ $:$ Both $\vee$ and $\wedge$ are commutative $(\text {BA}_1 2)$ $:$ Both $\vee$ and $\wedge$ distribute over the other $(\text {BA}_1 3)$ $:$ Both $\vee$ and $\wedge$ have identities $\bot$ and $\top$ respectively $(\text {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 $\struct {S, \vee, \wedge, \neg}$, where $\vee$ and $\wedge$ are binary, and $\neg$ is a unary operation.

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

 $(\text {BA}_2 0)$ $:$ Closure: $\ds \forall a, b \in S:$ $\ds a \vee b \in S$ $\ds a \wedge b \in S$ $\ds \neg a \in S$ $(\text {BA}_2 1)$ $:$ Commutativity: $\ds \forall a, b \in S:$ $\ds a \vee b = b \vee a$ $\ds a \wedge b = b \wedge a$ $(\text {BA}_2 2)$ $:$ Associativity: $\ds \forall a, b, c \in S:$ $\ds a \vee \paren {b \vee c} = \paren {a \vee b} \vee c$ $\ds a \wedge \paren {b \wedge c} = \paren {a \wedge b} \wedge c$ $(\text {BA}_2 3)$ $:$ Absorption Laws: $\ds \forall a, b \in S:$ $\ds \paren {a \wedge b} \vee b = b$ $\ds \paren {a \vee b} \wedge b = b$ $(\text {BA}_2 4)$ $:$ Distributivity: $\ds \forall a, b, c \in S:$ $\ds a \wedge \paren {b \vee c} = \paren {a \wedge b} \vee \paren {a \wedge c}$ $\ds a \vee \paren {b \wedge c} = \paren {a \vee b} \wedge \paren {a \vee c}$ $(\text {BA}_2 5)$ $:$ Identity Elements: $\ds \forall a, b \in S:$ $\ds \paren {a \wedge \neg a} \vee b = b$ $\ds \paren {a \vee \neg a} \wedge b = b$

## Proof

### Definition 1 implies Definition 2

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

Axiom $(\text {BA}_2 \ 0)$

From Axiom $(\text {BA}_1 \ 0)$, we have that $\struct {S, \vee, \wedge, \neg}$ 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 $(\text {BA}_2 \ 1)$

From Axiom $(\text {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 $(\text {BA}_2 \ 2)$
$\forall a, b, c \in S: a \vee \paren {b \vee c} = \paren {a \vee b} \vee c$
$\forall a, b, c \in S: a \wedge \paren {b \wedge c} = \paren {a \wedge b} \wedge c$

Axiom $(\text {BA}_2 \ 3)$

For all $a, b \in S$:

$a = a \vee \paren {a \wedge b}$
$a = a \wedge \paren {a \vee b}$

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

Axiom $(\text {BA}_2 \ 4)$

From Axiom $(\text {BA}_1 \ 2)$, we have that both $\vee$ and $\wedge$ distribute over the other.

Hence:

$\forall a, b, c \in S: a \wedge \paren {b \vee c} = \paren {a \wedge b} \vee \paren {a \wedge c}$
$\forall a, b, c \in S: a \vee \paren {b \wedge c} = \paren {a \vee b} \wedge \paren {a \vee c}$

Axiom $(\text {BA}_2 \ 5)$

We have:

 $\ds \paren {a \wedge \neg a} \vee b$ $=$ $\ds \bot \vee b$ Boolean Algebra: Axiom $(\text {BA}_1 \ 4)$ $\ds$ $=$ $\ds b$ Boolean Algebra: Axiom $(\text {BA}_1 \ 3)$

 $\ds \paren {a \vee \neg a} \wedge b$ $=$ $\ds \top \wedge b$ Boolean Algebra: Axiom $(\text {BA}_1 \ 4)$ $\ds$ $=$ $\ds b$ Boolean Algebra: Axiom $(\text {BA}_1 \ 3)$

All axioms are fulfilled.

$\Box$

### Definition 2 implies Definition 1

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

Axiom $(\text {BA}_1 \ 0)$

From Axiom $(\text {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, $\struct {S, \vee, \wedge, \neg}$ is closed under $\vee$, $\wedge$ and $\neg$.

Axiom $(\text {BA}_1 \ 1)$

From Axiom $(\text {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 $(\text {BA}_1 \ 2)$

From Axiom $(\text {BA}_2 \ 4)$, we have that:

$\forall a, b, c \in S: a \wedge \paren {b \vee c} = \paren {a \wedge b} \vee \paren {a \wedge c}$
$\forall a, b, c \in S: a \vee \paren {b \wedge c} = \paren {a \vee b} \wedge \paren {a \vee c}$

From Axiom $(\text {BA}_1 \ 1)$, we have that $\vee$ and $\wedge$ are commutative on $S$, and so:

$\forall a, b, c \in S: \paren {a \vee b} \wedge c = \paren {a \wedge c} \vee \paren {b \wedge c}$
$\forall a, b, c \in S: \paren {a \wedge b} \vee c = \paren {a \vee c} \wedge \paren {b \vee c}$

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

Axiom $(\text {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 $(\text {BA}_1 \ 3)$

We have demonstrated Boolean Algebra: Axiom $(\text {BA}_1 \ 4)$ above.

Then:

 $\ds \bot \vee b$ $=$ $\ds \paren {a \wedge \neg a} \vee b$ Boolean Algebra: Axiom $(\text {BA}_1 \ 4)$ $\ds$ $=$ $\ds b$ Boolean Algebra: Axiom $(\text {BA}_2 \ 5)$
 $\ds \top \wedge b$ $=$ $\ds \paren {a \vee \neg a} \wedge b$ Boolean Algebra: Axiom $(\text {BA}_1 \ 4)$ $\ds$ $=$ $\ds b$ Boolean Algebra: Axiom $(\text {BA}_2 \ 5)$

From Axiom $(\text {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$