ads Boolean Algebras

Section 13.3 Boolean Algebras

In order to define a Boolean algebra, we need the additional concept of complementation. A lattice must have both a greatest element and a least element in order for complementation to take place. The following definition will save us some words in the rest of this section.

🔗

Definition 13.3.1. Bounded Lattice.

🔗

A bounded lattice is a lattice that contains both a least element and a greatest element.

🔗

We use the symbols

0 0

and

1 1

for the least and greatest elements of a bounded lattice in the remainder of this section.

🔗

Definition 13.3.2. The Complement of a Lattice Element.

🔗

Let

[L; \lor, \land]

be a bounded lattice. If

a \in L,

then

a

has a complement if there exists

b \in L

such that

\begin{matrix} a \lor b = 1 1 \\ and \\ a \land b = 0 0 \end{matrix}

🔗

Notice that by the commutative laws for lattices, if

b

complements

a,

then

a

complements

b .

🔗

Definition 13.3.3. Complemented Lattice.

🔗

Let

L = [L; \lor, \land]

be a bounded lattice.

L

is a complemented lattice if every element of

L

has a complement in

L .

Example 13.3.4. Set Complement is a Complement.

In Chapter 1, we defined the complement of a subset of any universe. This turns out to be a concrete example of the general concept we have just defined, but we will reason through why this is the case here. Let

L = P (A),

where

A = {a, b, c} .

Then

[L; \cup, \cap]

is a bounded lattice with

0 = \emptyset

and

1 = A .

To find the complement, if it exists, of

B = {a, b} \in L,

for example, we want

D

such that

\begin{matrix} {a, b} \cap D = \emptyset \\ a n d \\ {a, b} \cup D = A \end{matrix}

It’s not too difficult to see that

D = {c},

since we need to include

c

to make the first condition true and can’t include

a

b

if the second condition is to be true. Of course this is precisely how we defined

A^{c}

in Chapter 1. Since it can be shown that each element of

L

has a complement (see Exercise 1),

[L; \cup, \cap]

is a complemented lattice. Note that if

A

is any set and

L = P (A),

then

[L; \cup, \cap]

is a complemented lattice where the complement of

B \in L

B^{c} = A - B .

🔗

In Example 13.3.4, we observed that the complement of each element of

L

is unique. Is this always true in a complemented lattice? The answer is no. Consider the following.

Example 13.3.5. A Lattice for which complements are not unique.

Let

L = {1, 2, 3, 5, 30}

and consider the lattice

[L; \lor, \land]

(under “divides”). The least element of

L

is 1 and the greatest element is 30. Let us compute the complement of the element

a = 2 .

We want to determine

\bar{a}

such that

2 \land \bar{a} = 1

and

2 \lor \bar{a} = 30 .

Certainly,

\bar{a} = 3

works, but so does

\bar{a} = 5,

so the complement of

a = 2

in this lattice is not unique. However,

[L; \lor, \land]

is still a complemented lattice since each element does have at least one complement.

🔗

Definition 13.3.6. Complementation as an operation.

🔗

If a complemented lattice has the property that the complement of every element is unique, then we consider complementation to be a unary operation. The usual notation for the complement of

a

\bar{a} .

🔗

The following theorem gives us an insight into when uniqueness of complements occurs.

🔗

Theorem 13.3.7. One condition for unique complements.

🔗

[L; \lor, \land]

is a complemented, distributive lattice, then the complement of each element

a \in L

is unique.

Proof.

Let

a \in L

and assume to the contrary that

a

has two complements, namely

a_{1}

and

a_{2} .

Then by the definition of complement,

\begin{matrix} a \land a_{1} = 0 and a \lor a_{1} = 1, \\ a n d \\ a \land a_{2} = 0 and a \lor a_{2} = 1, \end{matrix} .

Then

\begin{aligned} a_{1} & = a_{1} \land 1 1 = a_{1} \land (a \lor a_{2}) \\ = (a_{1} \land a) \lor (a_{1} \land a_{2}) \\ = 0 0 \lor (a_{1} \land a_{2}) \\ = a_{1} \land a_{2} \end{aligned}

On the other hand,

\begin{aligned} a_{2} & = a_{2} \land 1 1 = a_{2} \land (a \lor a_{1}) \\ = (a_{2} \land a) \lor (a_{2} \land a_{1}) \\ = 0 0 \lor (a_{2} \land a_{1}) \\ = a_{2} \land a_{1} \\ = a_{1} \land a_{2} \end{aligned}

Hence

a_{1} = a_{2},

which contradicts the assumption that

a

has two different complements.

🔗

Definition 13.3.8. Boolean Algebra.

🔗

A Boolean algebra is a lattice that contains a least element and a greatest element and that is both complemented and distributive. The notation

[B; \lor, \land, \bar{}]

is used to denote the boolean algebra with operations join, meet and complementation.

🔗

Since the complement of each element in a Boolean algebra is unique (by Theorem 13.3.7), complementation is a valid unary operation over the set under discussion, which is why we will list it together with the other two operations to emphasize that we are discussing a set together with three operations. Also, to help emphasize the distinction between lattices and lattices that are Boolean algebras, we will use the letter

B

as the generic symbol for the set of a Boolean algebra; that is,

[B; \lor, \land, \bar{}]

will stand for a general Boolean algebra.

Example 13.3.9. Boolean Algebra of Sets.

Let

A

be any set, and let

B = P (A) .

Then

[B; \cup, \cap,^{c}]

is a Boolean algebra. Here,

^{c}

stands for the complement of an element of

B

with respect to

A,

A - B .

This is a key example for us since all finite Boolean algebras and many infinite Boolean algebras look like this example for some

A .

In fact, a glance at the basic Boolean algebra laws in Table 13.3.11, in comparison with the set laws of Chapter 4 and the basic laws of logic of Chapter 3, indicates that all three systems behave the same; that is, they are isomorphic.

Example 13.3.10. Divisors of 30.

A somewhat less standard example of a boolean algebra is derived from the lattice of divisors of 30 under the relation “divides”. If you examine the ordering diagram for this lattice, you see that it is structurally the same as the boolean algebra of subsets of a three element set. Therefore, the join, meet and complementation operations act the same as union, intersection and set complementation. We might conjecture that the lattice of divisors of any integer will produce a boolean algebra, but it is only the case of certain integers. Try out a few integers to see if you can identify what is necessary to produce a boolean algebra.

🔗

Table 13.3.11. Basic Boolean Algebra Laws

Commutative Laws	$a \lor b = b \lor a$	$a \land b = b \land a$
Associative Laws	$a \lor (b \lor c) = (a \lor b) \lor c$	$a \land (b \land c) = (a \land b) \land c$
Distributive Laws	$a \land (b \lor c) = (a \land b) \lor (a \land c)$	$a \lor (b \land c) = (a \lor b) \land (a \lor c)$
Identity Laws	$a \lor 0 = 0 \lor a = a$	$a \land 1 = 1 \land a = a$
Complement Laws	$a \lor \bar{a} = 1$	$a \land \bar{a} = 0$
Idempotent Laws	$a \lor a = a$	$a \land a = a$
Null Laws	$a \lor 1 = 1$	$a \land 0 = 0$
Absorption Laws	$a \lor (a \land b) = a$	$a \land (a \lor b) = a$
DeMorgan’s Laws	$\overset{―}{a \lor b} = \bar{a} \land \bar{b}$	$\overset{―}{a \land b} = \bar{a} \lor \bar{b}$
Involution Law	$\overset{―}{\bar{a}} = a$

🔗

The “pairings” of the boolean algebra laws reminds us of the principle of duality, which we state for a Boolean algebra.

🔗

Definition 13.3.12. Principle of Duality for Boolean Algebras.

🔗

Let

B = [B; \lor, \land,^{c}]

be a Boolean algebra under

⪯,

and let

S

be a true statement for

B .

S^{*}

is obtained from

S

by replacing

⪯

with

⪰

(this is equivalent to turning the graph upside down),

\lor

with

\land,

\land

with

\lor,

0 0

with

1 1,

and

1 1

with

0 0,

then

S^{*}

is also a true statement in

B .

🔗

Exercises Exercises

🔗

1.

🔗

Determine the complement of each element

B \in L

in Example 13.3.4. Is this lattice a Boolean algebra? Why?

Answer.

\begin{array}{cc} B & Complement of B \\ \begin{matrix} \emptyset \\ {a} \\ {b} \\ {c} \\ {a, b} \\ {a, c} \\ {b, c} \\ A \end{matrix} & \begin{matrix} A \\ {b, c} \\ {a, c} \\ {a, b} \\ {c} \\ {b} \\ {a} \\ \emptyset \end{matrix} \end{array}

This lattice is a Boolean algebra since it is a distributive complemented lattice.

🔗

2.

🔗

Determine the complement of each element of $D_{6}$ in $[D_{6}; \lor, \land] .$
Repeat part a using the lattice in Example 13.2.5.
Repeat part a using the lattice in Exercise 13.1.1.
Are the lattices in parts a, b, and c Boolean algebras? Why?

🔗

3.

🔗

Determine which of the lattices of Exercise 13.1.3 of Section 13.1 are Boolean algebras.

Answer.

a and g.

🔗

4.

🔗

Let

A = {a, b}

and

B = P (A) .

Prove that $[B; \cup, \cap,^{c}]$ is a Boolean algebra.
Write out the operation tables for the Boolean algebra.

🔗

5.

🔗

It can be shown that the following statement,

S,

holds for any Boolean algebra

[B; \lor, \land, -]

(a \land b) = a

if and only if

a \leq b .

Write the dual, $S^{*},$ of the statement $S .$
Write the statement $S$ and its dual, $S^{*},$ in the language of sets.
Are the statements in part b true for all sets?
Write the statement $S$ and its dual, $S^{*},$ in the language of logic.
Are the statements in part d true for all propositions?

Answer.

$S^{*} : a \lor b = a if a \geq b$
The dual of $S : A \cap B = A if A \subseteq B$ is $S^{*} : A \cup B = A if A \supseteq B$
Yes
The dual of $S : p \land q \Leftrightarrow p if p \Rightarrow q$ is $S^{*} : p \lor q \Leftrightarrow p if q \Rightarrow p$
Yes