622
Boolean Algebra and Computer Logic
Bear in mind that Example 2 illustrates a particular instance of the Boolean
algebra structure. Any Boolean algebra must, by the definition, have at least two
elements, a 0 element and a 1 element. The specific Boolean algebra in Example
2 has just those two elements, the integers 0 and 1. But if you want to do a proof
about Boolean algebras in general, you cannot assume that 0 and 1 are the only elements. This means that if you know that x and y are two elements in an arbitrary
Boolean algebra and that x ∙ y, that does not mean that y = x′.
example 3
Let S = 5a, b, c6. Then `(S ) has eight elements:
[, 5a6, 5b6, 5c6, 5a. b6, 5a, c6, 5b, c6, 5a, b, c6
so using those eight elements together with the operations of union, intersection, and complementation gives an eight-element Boolean algebra. The empty
set is the 0 element, and 51, 2, 36 is the 1 element. We could show the tables
for union and intersection, but let’s just look at complementation. Remember that
x c x′ = 5a, b, c6.
′
[
5a, b, c6
5a6
5b, c6
5b6
5a, c6
5c6
5a. b6
5a. b6
5c6
5a, c6
5b6
5b, c6
5a6
5a, b, c6
[
Here 5a, c6 and 5c6 are two distinct elements of this Boolean algebra, but 5a, c6 is
not 5c6′.
There are many other properties that hold in any Boolean algebra. We can
prove these additional properties by using the properties in the definition.
example 4
The idempotent (pronounced eye′-dem-po-tent) property
x + x = x
holds in any Boolean algebra because
x + x = (x + x) # 1
(4b)
= (x + x) # (x + x′)
(5a)
= x + (x # x′)
(3a)
= x + 0
(5b)
= x
(4a)