626
Boolean Algebra and Computer Logic
There are many ways to define a Boolean algebra. Indeed, in our definition
of Boolean algebra, we could have omitted the associative properties, since these
can be derived from the remaining properties of the definition. It is much more
convenient, however, to include them.
isomorphic Boolean Algebras
What Is Isomorphism?
Two instances of a structure are isomorphic if there is a bijection (called an isomorphism) that maps the elements of one instance onto the elements of the other
so that important properties are preserved. (Isomorphic graphs were discussed in
Section 6.1.) If two instances of a structure are isomorphic, each is a mirror image
of the other, with the elements simply relabeled. The two instances are essentially
the same. Therefore, we can use the idea of isomorphism to classify instances of a
structure, lumping together those that are isomorphic.
example 7
Consider the two partially ordered sets
S 1 = 51, 2, 3, 5, 6, 10, 15, 306; x r y 4 x divides y
S 2 = `(51, 2, 36); A s B 4 A # B
The Hasse diagram of each partially ordered set appears in Figure 8. 1. These two
diagrams certainly appear to be mirror images of each other; just by looking at the
diagrams, an obvious relabeling of the nodes, as shown in Figure 8.2, suggests itself.
The important properties of a partially ordered set are which elements are related,
and the Hasse diagram displays this information. For example, Figure 8.1a shows
that 1, because of its position at the bottom of the graph, is related to every element
in S 1 . Is this property preserved under the relabeling of Figure 8.2? Yes, because
[ is the image of 1 under that relabeling, and [ is related to every element in S 2 .
Similarly, all the other “is related to” properties are preserved under the relabeling.
2
figure 8.1
■
PraCtiCe 4 Prove that 0′ = 1 and 1′ = 0. (Hint: 1′ = 0 will follow by duality from 0′ = 1. To show
0′ = 1, use the theorem on the uniqueness of complements.)
Boolean Algebra and Computer Logic
There are many ways to define a Boolean algebra. Indeed, in our definition
of Boolean algebra, we could have omitted the associative properties, since these
can be derived from the remaining properties of the definition. It is much more
convenient, however, to include them.
isomorphic Boolean Algebras
What Is Isomorphism?
Two instances of a structure are isomorphic if there is a bijection (called an isomorphism) that maps the elements of one instance onto the elements of the other
so that important properties are preserved. (Isomorphic graphs were discussed in
Section 6.1.) If two instances of a structure are isomorphic, each is a mirror image
of the other, with the elements simply relabeled. The two instances are essentially
the same. Therefore, we can use the idea of isomorphism to classify instances of a
structure, lumping together those that are isomorphic.
example 7
Consider the two partially ordered sets
S 1 = 51, 2, 3, 5, 6, 10, 15, 306; x r y 4 x divides y
S 2 = `(51, 2, 36); A s B 4 A # B
The Hasse diagram of each partially ordered set appears in Figure 8. 1. These two
diagrams certainly appear to be mirror images of each other; just by looking at the
diagrams, an obvious relabeling of the nodes, as shown in Figure 8.2, suggests itself.
The important properties of a partially ordered set are which elements are related,
and the Hasse diagram displays this information. For example, Figure 8.1a shows
that 1, because of its position at the bottom of the graph, is related to every element
in S 1 . Is this property preserved under the relabeling of Figure 8.2? Yes, because
[ is the image of 1 under that relabeling, and [ is related to every element in S 2 .
Similarly, all the other “is related to” properties are preserved under the relabeling.
2
figure 8.1
■
PraCtiCe 4 Prove that 0′ = 1 and 1′ = 0. (Hint: 1′ = 0 will follow by duality from 0′ = 1. To show
0′ = 1, use the theorem on the uniqueness of complements.)