A boolean algebra is a mathematical system; it consists of a non empty set S with one or more operations defined on S, and a set of axioms that the elements of S satisfy. A mathematical system can be thought of as a skeleton, like a human skeleton. Whether people are black or white, Caucasian or Chinese, their skeletons have common characteristics. Likewise, concrete examples of a
mathematical system share common properties. When we study mathematical systems, we need to study properties common to all examples of such systems. Real numbers form an important number system. Before formally defining a boolean algebra, we examine two concrete examples. Look for the properties common to both because they will help us define a boolean algebra.
Let U be an arbitrary set and P(U) its power set. Let A,B, and Cbe any three
elements of P(U). You may recall from the language of sets that the union, intersection,
and complementation operations on P(U) satisfy the following:
Commutative properties
AUB=BUA A∩B=B∩A
Associative properties
AU(BUC)=(AUB)UC A∩(B∩C) = (A∩B)∩C
Distributive properties
A∩(BUC)=(A∩B)U(A∩C) AU(B∩C) = (AUB)∩(AUC)
Identity properties
AUO=A A∩U=A
Complement properties
AUA' =U A∩A'= O
A boolean algebra consists of a nonempty set B containing two distinct elements 0 and 1, two binary operators + and., and a unary operator' satisfying the following conditions for all x,y, and z in B:
Commutative laws
x+y=y+x x.y=y.x
Associative laws
x+(y+z)=(x+y)+z x . ( y . z ) = ( x . y ) . z
Distributive laws
x.(y+z)=(x.y)+(x.z) x+(y.z)=(x+y).(x+z)
Identity laws
x+0=x x.1=x
Complement laws
x+x'=1 x.x'=O
In symbols, the boolean algebra is denoted by (B, +,., ', 0, 1) .
We clarify a few points before we go any further:
■ The operations +,., and' are called sum, product, and complementation, respectively. (For instance, in Example 12.1, the binary operators are n and U; the unary operator is complementation.) These operators are generic symbols: the operator + does not stand for addition nor the operator, for multiplication.
■ Since + and. are binary operators, both x +y and x .y belong to B for all x and y in B; since' is a unary operator.
■ The elements 0 and 1 are the zero element and the unit element,
respectively. Again, they are generic symbols for the zero element and
the unit element, respectively; they need not be the familiar numbers
zero and one. In Example 12.1, the zero element is 0 and the unit
element is U; in Example 12.2, they are 1 and 30, respectively.
■ When it is clear from the context, we designate the boolean algebra (B, +,-, ', 0, 1) as the boolean algebra B for convenience.
■ The operator, in x.y is usually omitted for convenience; thus xy = x.y. No parentheses appear when there is no danger of confusion. For instance, (xy) + (xz) = xy + xz and x + y + z = x + (y + z) = (x + y) + z.
■ Precedence rules govern evaluating expressions in boolean algebra:
First, parenthesized subexpressions are evaluated. Complementation has the highest priority among the operators,followed by. and then +.
For example, xy + zx' = (xy) + [z(x')].
■ The 10 axioms are paired off in two columns. In each pair, an axiom can be obtained from the other by swapping + with., and 0 with 1. These are dual axioms. For instance, the dual of x + x' = 1 (axiom 9) is x. x' = 0 (axiom 10). (In a boolean algebra, the dual of every true statement is also true. This property is the principle of duality.)
According to the definition, a boolean algebra contains at least two elements, the zero and the unit. Consequently we can ask: Does any boolean algebra contain exactly two elements? The answer is yes. See examples in boolean examples.