ic
Section 8.1 Boolean Algebra Structure
627
{1, 2, 3}
Ø
30
2
6
15
10
3
5
1
{2, 3}
{3}
{1, 2}
{1, 3}
{2}
{1}
figure 8.2
More formally, the relabeling is accomplished by the following bijection f
from the set of nodes in Figure 8.1a onto the set of nodes in Figure 8.1b.
f (1) = [
f (2) = 516
f (3) = 526
f (5) = 536
f (6) = 51, 26
f (10) = 51, 36
f (15) = 52, 36
f (30) = 51, 2, 36
The bijection f is an isomorphism from poset (S 1 , r) to poset (S 2 , s). Because this
isomorphism exists, the posets (S 1 , r) and (S 2 , s) are isomorphic. (The function
f
−1
would be an isomorphism from (S 2 , s) to (S 1 , r).)
In Example 7 it was relatively easy to find an isomorphism because of the
visual representation that captured the important properties (which elements
are related). Suppose that instead of a partially ordered set, we have a structure (like a Boolean algebra) where binary or unary operations are defined on
a set. Then the important properties pertain to how these operations act. An
isomorphism must preserve the effects of performing these operations. Each
instance of two such structures that are isomorphic must be the mirror image
of the other in the sense that “operate and then map” must equal “map and then
operate.”
Figure 8.3 illustrates this general idea for a binary operation. In Figure 8.3a,
the binary operation is performed on a and b, resulting in c, then c is mapped to d.
In Figure 8.3b, a and b are mapped to e and f, on which a binary operation is
performed, resulting in the same element d as before. Remember,
operate and map = map and operate
Still another view of this little equation appears in the commutative diagram of
Figure 8.4.