ic
Section 8.1 Boolean Algebra Structure
637
29. A Boolean algebra may also be defined as a partially ordered set with certain additional properties. Let
(B, d ) be a partially ordered set. For any x, y [ B, we define the least upper bound of x and y as an
element z such that x d z, y d z, and if there is any element z * with x d z * and y d z * , then z d z * .
The greatest lower bound of x and y is an element w such that w d x, w d y, and if there is any element
w * with w * d x and w * d y, then w * d w. A lattice is a partially ordered set in which every two
elements x and y have a least upper bound, denoted by x + y, and a greatest lower bound, denoted by x # y.
a. Prove that in any lattice
(i) x # y = x if and only if x d y
(ii) x + y = y if and only if x d y
b. Prove that in any lattice
(i) x + y = y + x
(ii) x # y = y # x
(iii) (x + y) + z = x + ( y + z)
(iv) (x # y) # z = x # ( y # z)
c. A lattice L is complemented if there exists a least element 0 and a greatest element 1, and for every
x [ L there exists x′ [ L such that x + x′ = 1 and x # x′ = 0. Prove that in a complemented lattice L,
x + 0 = x
and
x # 1 = x
for all x [ L.
d. A lattice L is distributive if
x + ( y # z) = (x + y) # (x + z)
and
x # ( y + z) = (x # y) + (x # z)
for every x, y, z [ L. By parts (b) and (c), a complemented, distributive lattice is a Boolean algebra.
Which of the following Hasse diagrams of partially ordered sets do not represent Boolean algebras?
Why? (Hint: In a Boolean algebra, the complement of an element is unique.)
2
(a)
(b)
(c)
(d)
1
3
4
6
7
5
1
3
4
2
1
4
3
5
2