Wikipedia: Boolean algebra

A Boolean algebra is a lattice (A, ^, v) which has 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 the smallest element 0 and the largest element 1 are unique, 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 true.

Examples

The most important Boolean algebra, and the one originally described by [George Boole]?, has only two elements, 0 and 1, and is defined by 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.

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.

Homomorphisms and isomorphisms

A homomorphism between the Boolean algebras A and B is a function f : A -> B such that for all a, b in A:

: f(a v b) = f(a) v f(b)
: f(a ^ b) = f(a) ^ f(b)
: f(0) = 0
: f(1) = 1

It then follows that f(~a) = ~f(a) for all a in A as well. The class of all Boolean algebras, together with this notion of morphism, forms a category. An isomorphism from A to B is a homomorphism from A to B which is bijective. The inverse of an isomorphism is also an isomorphism, and we call the two Boolean algebras A and B isomorphic. From the standpoint of Boolean algebra theory, they cannot be distinguished; they only differ in the notation of their elements.

Representing Boolean algebras

It can be shown that every finite Boolean algebra is isomorphic to the Boolean algebra of all subsets of a finite set; in particular, the number of elements of every finite Boolean algebra is a power of two.

Every Boolean algebra is isomorphic to the Boolean algebra of all closed-open sets in some topological space; this is the content of the celebrated [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) (this operation is called "symmetric difference" in the case of sets and XOR in the case of logic) 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.

: we have to mention ideals.

/Talk