two-valued logic

two-valued logic
digital logic

   <logic> (Commonly known as "{Boolean algebra}") A mathematical
   system concerning the two {truth values}, TRUE and FALSE and
   the functions {AND}, {OR}, {NOT}.  Two-valued logic is one of
   the cornerstones of {logic} and is also fundamental in the
   design of {digital electronics} and {programming languages}.

   The term "Boolean" is used here with its common meaning -
   two-valued, though strictly {Boolean algebra} is more general
   than this.

   Boolean functions are usually represented by {truth tables}
   where "0" represents "false" and "1" represents "true".  E.g.:

   	A | B | A AND B
   	--+---+--------
   	0 | 0 |    0
   	0 | 1 |    0
   	1 | 0 |    0
   	1 | 1 |    1

   This can be given more compactly using "x" to mean "don't
   care" (either true or false):

   	A | B | A AND B
   	--+---+--------
   	0 | x |    0
   	x | 0 |    0
   	1 | 1 |    1

   Similarly:

           A | NOT A       A | B | A OR B
           --+------       --+---+--------
           0 |  1          0 | 0 |   0
           1 |  0          x | 1 |   1
                           1 | x |   1

   Other functions such as {XOR}, {NAND}, {NOR} or functions of
   more than two inputs can be constructed using combinations of
   AND, OR, and NOT.  AND and OR can be constructed from each
   other using {DeMorgan's Theorem}:

   	A OR B   =  NOT ((NOT A) AND (NOT B))
   	A AND B	 =  NOT ((NOT A) OR (NOT B))

   In fact any Boolean function can be constructed using just NOR
   or just NAND using the identities:

   	NOT A  =  A NOR A
   	A OR B  =  NOT (A NOR B)

   and {DeMorgan's Theorem}.

   (2003-06-18)