Boolean algebra (structure)

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 PowerSet 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 [[Axiom}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.

/Talk