the functions
AND,
OR,
NOT. Two-valued logic is one of
the cornerstones of
logic and is also fundamental in the
The term "Boolean" is used here with its common meaning -
than this.
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
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)
(2003-06-18)