Boolean Algebra

Boolean algebra
    n 1: a system of symbolic logic devised by George Boole; used in
         computers [syn: {Boolean logic}, {Boolean algebra}]
    

Boolean algebra

   <mathematics, logic> (After the logician {George Boole})

   1. Commonly, and especially in computer science and digital
   electronics, this term is used to mean {two-valued logic}.

   2. This is in stark contrast with the definition used by pure
   mathematicians who in the 1960s introduced "Boolean-valued
   {models}" into logic precisely because a "Boolean-valued
   model" is an interpretation of a {theory} that allows more
   than two possible truth values!

   Strangely, a Boolean algebra (in the mathematical sense) is
   not strictly an {algebra}, but is in fact a {lattice}.  A
   Boolean algebra is sometimes defined as a "complemented
   {distributive lattice}".

   Boole's work which inspired the mathematical definition
   concerned {algebras} of {sets}, involving the operations of
   intersection, union and complement on sets.  Such algebras
   obey the following identities where the operators ^, V, - and
   constants 1 and 0 can be thought of either as set
   intersection, union, complement, universal, empty; or as
   two-valued logic AND, OR, NOT, TRUE, FALSE; or any other
   conforming system.

    a ^ b = b ^ a    a V b  =  b V a     (commutative laws)
    (a ^ b) ^ c  =  a ^ (b ^ c)
    (a V b) V c  =  a V (b V c)          (associative laws)
    a ^ (b V c)  =  (a ^ b) V (a ^ c)
    a V (b ^ c)  =  (a V b) ^ (a V c)    (distributive laws)
    a ^ a  =  a    a V a  =  a           (idempotence laws)
    --a  =  a
    -(a ^ b)  =  (-a) V (-b)
    -(a V b)  =  (-a) ^ (-b)             (de Morgan's laws)
    a ^ -a  =  0    a V -a  =  1
    a ^ 1  =  a    a V 0  =  a
    a ^ 0  =  0    a V 1  =  1
    -1  =  0    -0  =  1

   There are several common alternative notations for the "-" or
   {logical complement} operator.

   If a and b are elements of a Boolean algebra, we define a <= b
   to mean that a ^ b = a, or equivalently a V b = b.  Thus, for
   example, if ^, V and - denote set intersection, union and
   complement then <= is the inclusive subset relation.  The
   relation <= is a {partial ordering}, though it is not
   necessarily a {linear ordering} since some Boolean algebras
   contain incomparable values.

   Note that these laws only refer explicitly to the two
   distinguished constants 1 and 0 (sometimes written as {LaTeX}
   \top and \bot), and in {two-valued logic} there are no others,
   but according to the more general mathematical definition, in
   some systems variables a, b and c may take on other values as
   well.

   (1997-02-27)