A Boolean algebra is a terminate distributive lattice.
A complement in a terminate lattice is an operator * that determines for an element x an element x*, such that xnx* = o and xux* = i.
Theorem: In a Boolean algebra every element x has unique complement. Proof: Suppose there were two complements x* and x' then xnx* = xnx' (since both are equal to o) and xux* = xux' (since both are equal to i) but in a distributive lattice these equalities imply x* = x'.
Theorem: For any x we have x** = x. And o* = i, i* = o. And x = y if and only if x* = y*. Proof: These follow from the symmetry of the definition of complement, and from the properties of o and i that; oni = o, oui = i. And the uniqueness of the complement.
Theorem (DeMorgan's Laws): In a Boolean algebra (xny)* = x* u y* and (xuy)* = x* n y*. Proof: (xny)u(x* u y*) = (x u x* u y*)n(y u x* u y*) = (i u y*)n(i u x*) = ini = i and (xny)n(x* u y*) = (x n y n x*)u(x n y n y*) = (ony)u(onx) = ouo = o. This proves xny and x*uy* are complements. The proof for xuy and x*ny* follows by duality.
Theorem: x =< y if and only if x* >= y*. Proof: by De Morgan's laws: x =< y <=> xuy = y <=> (xuy)* = y* <=> x*ny* = y* <=> x* >= y*.
Important examples of Boolean algebras are provided by the algebras of all the subsets of a given set. The order relation is that of one set being a subset of another, written A c B, meaning a member of A is always a member of B. For any systems A, B, C we have: A c A (reflexivity). If A c B and B c A then A = B (antisymmetry). If A c B and B c C then A c C (transitivity). The relation of being a subset is therefore an order relation.
The set of all elements x such that x is in A and x is in B, denoted AnB, is called the intersection of A and B. Intersection is an idempotent, commutative and associative operation. For all A and B we have (AnB) c A. The relation A c B means the same as AnB = A. The largest set contained in A and B is their intersection.
The set of all elements x such that x is in A or x is in B (or both) denoted AuB is called the union of A and B. Union is an idempotent, commutative and associative operation. For all A and B we have A c(AuB). The relation A c B means the same as AuB = B. The smallest set containing A and B is their union.
The full set I and the null set O are the first and last elements. For any set A, within the given context, we have O c A c I. The set of all members x such that x is in A but not x in B is a set denoted A – B called the difference of A and B. The complement of a set A is the difference I – A, also denoted –A. We have –I = O, –O = I, –(–A) = A, Au(–A) = I, An(–A) = O. If A c B then (–B)c (–A): note the reversal of order. The operations of intersection and union are duals of each other: (–A)u(–B) = –(AnB) and (–A)n(–B) = –(AuB). We can express the difference of sets in terms of complement and intersection: A – B = An(–B). The union of the two differences of A and B is called the symmetric difference of A and B, denoted A ÷ B = (A – B)u(B – A).