Boolean algebra

A Boolean algebra is a lattice (A, ^, v) which satisfies the following properties:

    There exists an element 0, such that a v 0 = a for all a in A        (bounded below)
    There exists an element 1, such that a^1=a for all a in A            (bounded above)
    For all a,b,c in A: (a v b) ^ c = (a ^ c) v (b ^ c)                  (distributive law)
    For every a in A there exists an element ~a in A such that 
    a v ~a = 1 and a ^ ~a = 0                                            (existence of complements)

From these axioms, one can directly show that every element has only one complement, and that the dual version of the distributive law, (a ^ b) v c = ( a v c) ^ (b v c), holds.

The most important Boolean algebra, and the one originally described by [George Boole]?, has only two elements, 0 and 1, and the rules

   v   0  1     ^   0  1
       ----         ----
   0 | 0  1     0 | 0  0
   1 | 1  1     1 | 0  1

It has applications in logic, where 0 is interpreted as "false", 1 is "true", ^ is "and", v is "or", and ~ is "not". Expressions involving the Boolean operations and variables represent statement forms, and two such expressions can be shown to be equal using the above axioms if and only if the corresponding statement forms are logically equivalent.

The two-element Boolean algebra is also used for circuit design in electrical engineering; here 0 and 1 represent the two different states of digital circuits, typically high and low voltage. Circuits are described by expressions containing variables, and two such expressions are equal for all values of the variables if and only if the corresponding circuits have the same input - output behavior. Furthermore, every possible input - output behavior can be modeled by a suitable Boolean expression.

The power set of any given set S forms a Boolean algebra with the two operations v = union and ^ = intersection. The smallest element 0 is the empty set and the largest element 1 is the set S itself. It can be shown that every finite Boolean algebra is of this type; in particular, the number of elements of every finite Boolean algebra is a power of two.

Other examples of Boolean algebras arise from topological spaces: if X is a topological space, then subsets of X which are both open and closed form a Boolean algebra with the operations v = union and ^ = intersection. In fact, every Boolean algebra can be represented in this way; this is the content of the [Stone representation theorem for Boolean algebras]?.

Every Boolean algebra (A, ^, v) gives rise to a ring (A, +, *) by defining a + b = (a ^ ~b) v (b ^ ~a) and a * b = a ^ b. This ring has the property that a * a = a for all a in A; rings like that are called Boolean rings. One can show that every Boolean ring arises from a Boolean algebra, and vice versa: the categories of Boolean rings and Boolean algebras are equivalent.

---

/Talk