ic
Section 8.1 Boolean Algebra Structure
631
really the only kinds of finite Boolean algebras. In a sense we have come full
circle. We defined a Boolean algebra to represent many kinds of situations; now
we find that (for the finite case) the situations, except for the labels of objects, are
the same anyway!
S e c t i o n 8 . 1 review
tecHniQueS
• Decide whether something is a Boolean algebra.
• Prove properties about Boolean algebras.
• Write the equation meaning that a function f preserves an operation from one instance of a structure to another, and verify or disprove such an
equation.
main iDeaS
• Mathematical structures serve as models or abstractions of common properties found in diverse
situations.
• If there is an isomorphism (a bijection that preserves properties) from A to B, where A and B are
instances of a structure, then except for labels, A
and B are the same.
• All finite Boolean algebras are isomorphic to
Boolean algebras that are power sets.
W
exeRciSeS 8.1
1. Let B = 50, 1, a, a′6, and let + and # be binary operations on B. The unary operation ′ is defined by
the table
′
0
1
1
0
a
a′
a′
a
Suppose you know that 3B, + , # , ′, 0, 14 is a Boolean algebra. Making use of the properties that must
hold in any Boolean algebra, fill in the following tables defining the binary operations + and # :
+
0
1
a
a′
#
0
1
a
a′
0
0
1
1
a
a
a′
a′
2. a. What does the universal bound property (Practice 3) become in the context of propositional logic?
b. What does it become in the context of set theory?
3. Define two binary operations + and # on the set Z of integers by x + y = max(x, y) and x # y = min(x, y).
a. Show that the commutative, associative, and distributive properties of a Boolean algebra hold for these
two operations on Z.
b. Show that no matter what element of Z is chosen to be 0 , the property x + 0 = x of a Boolean algebra fails to hold.
Section 8.1 Boolean Algebra Structure
631
really the only kinds of finite Boolean algebras. In a sense we have come full
circle. We defined a Boolean algebra to represent many kinds of situations; now
we find that (for the finite case) the situations, except for the labels of objects, are
the same anyway!
S e c t i o n 8 . 1 review
tecHniQueS
• Decide whether something is a Boolean algebra.
• Prove properties about Boolean algebras.
• Write the equation meaning that a function f preserves an operation from one instance of a structure to another, and verify or disprove such an
equation.
main iDeaS
• Mathematical structures serve as models or abstractions of common properties found in diverse
situations.
• If there is an isomorphism (a bijection that preserves properties) from A to B, where A and B are
instances of a structure, then except for labels, A
and B are the same.
• All finite Boolean algebras are isomorphic to
Boolean algebras that are power sets.
W
exeRciSeS 8.1
1. Let B = 50, 1, a, a′6, and let + and # be binary operations on B. The unary operation ′ is defined by
the table
′
0
1
1
0
a
a′
a′
a
Suppose you know that 3B, + , # , ′, 0, 14 is a Boolean algebra. Making use of the properties that must
hold in any Boolean algebra, fill in the following tables defining the binary operations + and # :
+
0
1
a
a′
#
0
1
a
a′
0
0
1
1
a
a
a′
a′
2. a. What does the universal bound property (Practice 3) become in the context of propositional logic?
b. What does it become in the context of set theory?
3. Define two binary operations + and # on the set Z of integers by x + y = max(x, y) and x # y = min(x, y).
a. Show that the commutative, associative, and distributive properties of a Boolean algebra hold for these
two operations on Z.
b. Show that no matter what element of Z is chosen to be 0 , the property x + 0 = x of a Boolean algebra fails to hold.