Boolean algebra

A Boolean algebra is a Lattice which satisfies the following properties:

    There exists some element 0, such that av0=a for all a                 (bounded below)
    There exists some element 1, such that a^1=a for all a                 (bounded above)
    For all a,b,c, (avb)^c=(a^c)v(b^c)                                     (distributive law)
    For all a, there exists an element ~a such that av~a=1 and a^~a=0      (existence of complements)

Complements are guaranteed to be unique within bounded distributive lattices. Note the definition of Boolean algebrae is very similar to that of rings, except elements have complements instead of inverses. Moreover the distributive law can be shown to hold both ways, i.e. (a^b)vc=(avc)^(bvc).

The power set of any given set S forms a Boolean algebra under the partial ordering "is a subset of", where 0 = {} and 1 = S. Any subalgebra of this is called an algebra of sets, and in particular, an algebra of sets closed under arbitrary unions is called a Topology.

When [George Boole]? originally defined his Boolean Algebra, he only defined one algebraic system. There are, however, infinitely many algebraic systems that all have very strong and important commonality with each other. All of these systems are referred to in modern algebra as Boolean algebras. The one that Boole defined is the simplest of these.

Boole's original description of his algebra was in terms of real arithmetic and polynomials. He used the values 0 and 1 and defined various operations as polynomial functions of one or two variables. For example, NOT(x) can be defined as (1-x), AND(x,y) as xy and OR(x,y) as 1-(1-x)(1-y). A quick bit of arithmetic shows that the following operation tables hold:

      x  NOT     x  y   AND  OR
      0  1       0  0     0   0
      1  0       0  1     0   1
                 1  0     0   1
                 1  1     1   1

The axioms given above can also be shown to be true with these definitions. In most modern introductory treatments as well as most basic engineering texts, the polynomial definitions are never mentioned and the function tables are used to start with. Since the truth tables suffice entirely for Boole's original algebra, the polynomials are merely excess baggage and are pretty much just of historical interest. The truth table definition does not give the full generality of the axiomatic definition, however, and any serious theoretical work would generally start from that definition.

Even the simplest Boolean algebra is quite useful. The values 0 and 1 can be identified with logical falsity and truth, equality of expressions (quantified over all possible values, of course) can be identified with logical equivalence, and algebraic derivation can be identified with simple propositional deduction. The result is that classical syllogistic deductions can be done without all of the weighty baggage of Aristotelian logic. Instead, just a few axioms suffice. Another major application is in logical circuit design and optimization. Having a consistent and simple number system allows enormously complex circuits to be designed and built.

/Talk