AATA Boolean Algebras

Section 19.2 Boolean Algebras

Let us investigate the example of the power set,

P (X),

of a set

X

more closely. The power set is a lattice that is ordered by inclusion. By the definition of the power set, the largest element in

P (X)

X

itself and the smallest element is

\emptyset,

the empty set. For any set

A

P (X),

we know that

A \cap X = A

and

A \cup \emptyset = A .

This suggests the following definition for lattices. An element

I

in a poset

X

is a largest element if

a ⪯ I

for all

a \in X .

An element

O

is a smallest element of

X

O ⪯ a

for all

a \in X .

🔗

Let

A

be in

P (X) .

Recall that the complement of

A

A^{'} = X ∖ A = {x : x \in X and x \notin A} .

🔗

We know that

A \cup A^{'} = X

and

A \cap A^{'} = \emptyset .

We can generalize this example for lattices. A lattice

L

with a largest element

I

and a smallest element

O

is complemented if for each

a \in L,

there exists an

a^{'}

such that

a \lor a^{'} = I

and

a \land a^{'} = O .

🔗

In a lattice

L,

the binary operations

\lor

and

\land

satisfy commutative and associative laws; however, they need not satisfy the distributive law

a \land (b \lor c) = (a \land b) \lor (a \land c);

🔗

however, in

P (X)

the distributive law is satisfied since

A \cap (B \cup C) = (A \cap B) \cup (A \cap C)

🔗

for

A, B, C \in P (X) .

We will say that a lattice

L

is distributive if the following distributive law holds:

a \land (b \lor c) = (a \land b) \lor (a \land c)

🔗

for all

a, b, c \in L .

🔗

Theorem 19.15.

🔗

A lattice

L

is distributive if and only if

a \lor (b \land c) = (a \lor b) \land (a \lor c)

🔗

for all

a, b, c \in L .

Proof.

Let us assume that

L

is a distributive lattice.

\begin{aligned} a \lor (b \land c) & = [a \lor (a \land c)] \lor (b \land c) \\ = a \lor [(a \land c) \lor (b \land c)] \\ = a \lor [(c \land a) \lor (c \land b)] \\ = a \lor [c \land (a \lor b)] \\ = a \lor [(a \lor b) \land c] \\ = [(a \lor b) \land a] \lor [(a \lor b) \land c] \\ = (a \lor b) \land (a \lor c) . \end{aligned}

The converse follows directly from the Duality Principle.

🔗

A Boolean algebra is a lattice

B

with a greatest element

I

and a smallest element

O

such that

B

is both distributive and complemented. The power set of

X,

P (X),

is our prototype for a Boolean algebra. As it turns out, it is also one of the most important Boolean algebras. The following theorem allows us to characterize Boolean algebras in terms of the binary relations

\lor

and

\land

without mention of the fact that a Boolean algebra is a poset.

🔗

Theorem 19.16.

🔗

A set

B

is a Boolean algebra if and only if there exist binary operations

\lor

and

\land

B

satisfying the following axioms.

$a \lor b = b \lor a$ and $a \land b = b \land a$ for $a, b \in B .$
$a \lor (b \lor c) = (a \lor b) \lor c$ and $a \land (b \land c) = (a \land b) \land c$ for $a, b, c \in B .$
$a \land (b \lor c) = (a \land b) \lor (a \land c)$ and $a \lor (b \land c) = (a \lor b) \land (a \lor c)$ for $a, b, c \in B .$
There exist elements $I$ and $O$ such that $a \lor O = a$ and $a \land I = a$ for all $a \in B .$
For every $a \in B$ there exists an $a^{'} \in B$ such that $a \lor a^{'} = I$ and $a \land a^{'} = O .$

Proof.

Let

B

be a set satisfying (1)–(5) in the theorem. One of the idempotent laws is satisfied since

\begin{aligned} a & = a \lor O \\ = a \lor (a \land a^{'}) \\ = (a \lor a) \land (a \lor a^{'}) \\ = (a \lor a) \land I \\ = a \lor a . \end{aligned}

Observe that

I \lor b = (b \lor b^{'}) \lor b = (b^{'} \lor b) \lor b = b^{'} \lor (b \lor b) = b^{'} \lor b = I .

Consequently, the first of the two absorption laws holds, since

\begin{aligned} a \lor (a \land b) & = (a \land I) \lor (a \land b) \\ = a \land (I \lor b) \\ = a \land I \\ = a . \end{aligned}

The other idempotent and absorption laws are proven similarly. Since

B

also satisfies (1)–(3), the conditions of Theorem 19.14 are met; therefore,

B

must be a lattice. Condition (4) tells us that

B

is a distributive lattice.

For

a \in B,

O \lor a = a;

hence,

O ⪯ a

and

O

is the smallest element in

B .

To show that

I

is the largest element in

B,

we will first show that

a \lor b = b

is equivalent to

a \land b = a .

Since

a \lor I = a

for all

a \in B,

using the absorption laws we can determine that

a \lor I = (a \land I) \lor I = I \lor (I \land a) = I

a ⪯ I

for all

a

B .

Finally, since we know that

B

is complemented by (5),

B

must be a Boolean algebra.

Conversely, suppose that

B

is a Boolean algebra. Let

I

and

O

be the greatest and least elements in

B,

respectively. If we define

a \lor b

and

a \land b

as least upper and greatest lower bounds of

{a, b},

then

B

is a Boolean algebra by Theorem 19.14, Theorem 19.15, and our hypothesis.

🔗

Many other identities hold in Boolean algebras. Some of these identities are listed in the following theorem.

🔗

Theorem 19.17.

🔗

Let

B

be a Boolean algebra. Then

$a \lor I = I$ and $a \land O = O$ for all $a \in B .$
If $a \lor b = a \lor c$ and $a \land b = a \land c$ for $a, b, c \in B,$ then $b = c .$
If $a \lor b = I$ and $a \land b = O,$ then $b = a^{'} .$
$(a^{'})^{'} = a$ for all $a \in B .$
$I^{'} = O$ and $O^{'} = I .$
$(a \lor b)^{'} = a^{'} \land b^{'}$ and $(a \land b)^{'} = a^{'} \lor b^{'}$ (De Morgan’s Laws).

Proof.

We will prove only (2). The rest of the identities are left as exercises. For

a \lor b = a \lor c

and

a \land b = a \land c,

we have

\begin{aligned} b & = b \lor (b \land a) \\ = b \lor (a \land b) \\ = b \lor (a \land c) \\ = (b \lor a) \land (b \lor c) \\ = (a \lor b) \land (b \lor c) \\ = (a \lor c) \land (b \lor c) \\ = (c \lor a) \land (c \lor b) \\ = c \lor (a \land b) \\ = c \lor (a \land c) \\ = c \lor (c \land a) \\ = c . \end{aligned}

🔗

Subsection Finite Boolean Algebras

🔗

A Boolean algebra is a finite Boolean algebra if it contains a finite number of elements as a set. Finite Boolean algebras are particularly nice since we can classify them up to isomorphism.

🔗

Let

B

and

C

be Boolean algebras. A bijective map

ϕ : B \to C

is an isomorphism of Boolean algebras if

\begin{aligned} ϕ (a \lor b) & = ϕ (a) \lor ϕ (b) \\ ϕ (a \land b) & = ϕ (a) \land ϕ (b) \end{aligned}

🔗

for all

a

and

b

B .

🔗

We will show that any finite Boolean algebra is isomorphic to the Boolean algebra obtained by taking the power set of some finite set

X .

We will need a few lemmas and definitions before we prove this result. Let

B

be a finite Boolean algebra. An element

a \in B

is an atom of

B

a \neq O

and

a \land b = a

for all

b \in B

with

b \neq O .

Equivalently,

a

is an atom of

B

if there is no

b \in B

with

b \neq O

distinct from

a

such that

O ⪯ b ⪯ a .

🔗

Lemma 19.18.

🔗

Let

B

be a finite Boolean algebra. If

b

is a element of

B

with

b \neq O,

then there is an atom

a

B

such that

a ⪯ b .

Proof.

b

is an atom, let

a = b .

Otherwise, choose an element

b_{1},

not equal to

O

b,

such that

b_{1} ⪯ b .

We are guaranteed that this is possible since

b

is not an atom. If

b_{1}

is an atom, then we are done. If not, choose

b_{2},

not equal to

O

b_{1},

such that

b_{2} ⪯ b_{1} .

Again, if

b_{2}

is an atom, let

a = b_{2} .

Continuing this process, we can obtain a chain

O ⪯ \dots ⪯ b_{3} ⪯ b_{2} ⪯ b_{1} ⪯ b .

Since

B

is a finite Boolean algebra, this chain must be finite. That is, for some

k,

b_{k}

is an atom. Let

a = b_{k} .

🔗

Lemma 19.19.

🔗

Let

a

and

b

be atoms in a finite Boolean algebra

B

such that

a \neq b .

Then

a \land b = O .

Proof.

Since

a \land b

is the greatest lower bound of

a

and

b,

we know that

a \land b ⪯ a .

Hence, either

a \land b = a

a \land b = O .

However, if

a \land b = a,

then either

a ⪯ b

a = O .

In either case we have a contradiction because

a

and

b

are both atoms; therefore,

a \land b = O .

🔗

Lemma 19.20.

🔗

Let

B

be a Boolean algebra and

a, b \in B .

The following statements are equivalent.

$a ⪯ b .$
$a \land b^{'} = O .$
$a^{'} \lor b = I .$

Proof.

(1)

\Rightarrow

(2). If

a ⪯ b,

then

a \lor b = b .

Therefore,

\begin{aligned} a \land b^{'} & = a \land (a \lor b)^{'} \\ = a \land (a^{'} \land b^{'}) \\ = (a \land a^{'}) \land b^{'} \\ = O \land b^{'} \\ = O . \end{aligned}

(2)

\Rightarrow

(3). If

a \land b^{'} = O,

then

a^{'} \lor b = (a \land b^{'})^{'} = O^{'} = I .

(3)

\Rightarrow

(1). If

a^{'} \lor b = I,

then

\begin{aligned} a & = a \land (a^{'} \lor b) \\ = (a \land a^{'}) \lor (a \land b) \\ = O \lor (a \land b) \\ = a \land b . \end{aligned}

Thus,

a ⪯ b .

🔗

Lemma 19.21.

🔗

Let

B

be a Boolean algebra and

b

and

c

be elements in

B

such that

b ⪯̸ c .

Then there exists an atom

a \in B

such that

a ⪯ b

and

a ⪯̸ c .

Proof.

By Lemma 19.20,

b \land c^{'} \neq O .

Hence, there exists an atom

a

such that

a ⪯ b \land c^{'} .

Consequently,

a ⪯ b

and

a ⪯̸ c .

🔗

Lemma 19.22.

🔗

Let

b \in B

and

a_{1}, \dots, a_{n}

be the atoms of

B

such that

a_{i} ⪯ b .

Then

b = a_{1} \lor \dots \lor a_{n} .

Furthermore, if

a, a_{1}, \dots, a_{n}

are atoms of

B

such that

a ⪯ b,

a_{i} ⪯ b,

and

b = a \lor a_{1} \lor \dots \lor a_{n},

then

a = a_{i}

for some

i = 1, \dots, n .

Proof.

Let

b_{1} = a_{1} \lor \dots \lor a_{n} .

Since

a_{i} ⪯ b

for each

i,

we know that

b_{1} ⪯ b .

If we can show that

b ⪯ b_{1},

then the lemma is true by antisymmetry. Assume

b ⪯̸ b_{1} .

Then there exists an atom

a

such that

a ⪯ b

and

a ⪯̸ b_{1} .

Since

a

is an atom and

a ⪯ b,

we can deduce that

a = a_{i}

for some

a_{i} .

However, this is impossible since

a ⪯ b_{1} .

Therefore,

b ⪯ b_{1} .

Now suppose that

b = a_{1} \lor \dots \lor a_{n} .

a

is an atom less than

b,

a = a \land b = a \land (a_{1} \lor \dots \lor a_{n}) = (a \land a_{1}) \lor \dots \lor (a \land a_{n}) .

But each term is

O

a

with

a \land a_{i}

occurring for only one

a_{i} .

Hence, by Lemma 19.19,

a = a_{i}

for some

i .

🔗

Theorem 19.23.

🔗

Let

B

be a finite Boolean algebra. Then there exists a set

X

such that

B

is isomorphic to

P (X) .

Proof.

We will show that

B

is isomorphic to

P (X),

where

X

is the set of atoms of

B .

Let

a \in B .

By Lemma 19.22, we can write

a

uniquely as

a = a_{1} \lor \dots \lor a_{n}

for

a_{1}, \dots, a_{n} \in X .

Consequently, we can define a map

ϕ : B \to P (X)

ϕ (a) = ϕ (a_{1} \lor \dots \lor a_{n}) = {a_{1}, \dots, a_{n}} .

Clearly,

ϕ

is onto.

Now let

a = a_{1} \lor \dots \lor a_{n}

and

b = b_{1} \lor \dots \lor b_{m}

be elements in

B,

where each

a_{i}

and each

b_{i}

is an atom. If

ϕ (a) = ϕ (b),

then

{a_{1}, \dots, a_{n}} = {b_{1}, \dots, b_{m}}

and

a = b .

Consequently,

ϕ

is injective.

The join of

a

and

b

is preserved by

ϕ

since

\begin{aligned} ϕ (a \lor b) & = ϕ (a_{1} \lor \dots \lor a_{n} \lor b_{1} \lor \dots \lor b_{m}) \\ = {a_{1}, \dots, a_{n}, b_{1}, \dots, b_{m}} \\ = {a_{1}, \dots, a_{n}} \cup {b_{1}, \dots, b_{m}} \\ = ϕ (a_{1} \lor \dots \lor a_{n}) \cup ϕ (b_{1} \land \dots \lor b_{m}) \\ = ϕ (a) \cup ϕ (b) . \end{aligned}

Similarly,

ϕ (a \land b) = ϕ (a) \cap ϕ (b) .

🔗

We leave the proof of the following corollary as an exercise.

🔗

Corollary 19.24.

🔗

The order of any finite Boolean algebra must be

2^{n}

for some positive integer

n .

Prev Top Next