ic
Section 8.1 Boolean Algebra Structure
621
concrete example of the idea, we also call it by our word for the idea (this object
is a “chair”).
The formalization helps us focus on the essential features common to all
examples of Boolean algebras, and we can use these features—these facts from
the definition of a Boolean algebra—to prove other facts about Boolean algebras.
Then these new facts, once proved in general, hold in any particular instance of
a Boolean algebra. To use our analogy, if we ascertain that in a typical human
skeleton, “the thighbone is connected to the kneebone,” then we don’t need to
reconfirm the fact in every person we meet.
We denote a Boolean algebra by 3B, + , # , ′, 0, 14.
example 2
Let B = 50, 16 (the set of integers 0 and 1) and define binary operations + and #
on B by x + y = max(x, y), x # y = min(x, y). Then we can illustrate the operations of + and # by the following tables.
+
0
1
#
0
1
0
0
1
0
0
0
1
1
1
1
0
1
A unary operation ′ can be defined by means of a table, as follows, instead of by
a verbal description.
′
0
1
1
0
Thus 0′ = 1and 1′ = 0. Then 3B, + , # , ′, 0, 14 is a Boolean algebra. We can
verify the 10 properties by checking all possible cases. Thus, for property 2b, the
associativity of # , we show that
(0 # 0) # 0 = 0 # (0 # 0) = 0
(0 # 0) # 1 = 0 # (0 # 1) = 0
(0 # 1) # 0 = 0 # (1 # 0) = 0
(0 # 1) # 1 = 0 # (1 # 1) = 0
(1 # 0) # 0 = 1 # (0 # 0) = 0
(1 # 0) # 1 = 1 # (0 # 1) = 0
(1 # 1) # 0 = 1 # (1 # 0) = 0
(1 # 1) # 1 = 1 # (1 # 1) = 1
For property 4a, we show that
0 + 0 = 0
1 + 0 = 1
■
PraCtiCe 1 Verify property 4b for the Boolean algebra of Example 2.
Section 8.1 Boolean Algebra Structure
621
concrete example of the idea, we also call it by our word for the idea (this object
is a “chair”).
The formalization helps us focus on the essential features common to all
examples of Boolean algebras, and we can use these features—these facts from
the definition of a Boolean algebra—to prove other facts about Boolean algebras.
Then these new facts, once proved in general, hold in any particular instance of
a Boolean algebra. To use our analogy, if we ascertain that in a typical human
skeleton, “the thighbone is connected to the kneebone,” then we don’t need to
reconfirm the fact in every person we meet.
We denote a Boolean algebra by 3B, + , # , ′, 0, 14.
example 2
Let B = 50, 16 (the set of integers 0 and 1) and define binary operations + and #
on B by x + y = max(x, y), x # y = min(x, y). Then we can illustrate the operations of + and # by the following tables.
+
0
1
#
0
1
0
0
1
0
0
0
1
1
1
1
0
1
A unary operation ′ can be defined by means of a table, as follows, instead of by
a verbal description.
′
0
1
1
0
Thus 0′ = 1and 1′ = 0. Then 3B, + , # , ′, 0, 14 is a Boolean algebra. We can
verify the 10 properties by checking all possible cases. Thus, for property 2b, the
associativity of # , we show that
(0 # 0) # 0 = 0 # (0 # 0) = 0
(0 # 0) # 1 = 0 # (0 # 1) = 0
(0 # 1) # 0 = 0 # (1 # 0) = 0
(0 # 1) # 1 = 0 # (1 # 1) = 0
(1 # 0) # 0 = 1 # (0 # 0) = 0
(1 # 0) # 1 = 1 # (0 # 1) = 0
(1 # 1) # 0 = 1 # (1 # 0) = 0
(1 # 1) # 1 = 1 # (1 # 1) = 1
For property 4a, we show that
0 + 0 = 0
1 + 0 = 1
■
PraCtiCe 1 Verify property 4b for the Boolean algebra of Example 2.