< 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)