Boolean algebra An
algebra that is particularly important in computing. Formally it is a
complemented distributive lattice. In a Boolean algebra there is a
set of elements
B that consists of only 0 and 1. Further there will be two
dyadic operations, usually denoted by ∧ and ∨ (or by . and +) and called
and and
or respectively. There is also a
monadic operation, denoted here by ′, and known as the
complement operation. These operations satisfy a series of laws, given in the table, where
x,
y, and
z denote arbitrary elements of
B.
There are two very common examples of Boolean algebras. The first consists of the set
B = {FALSE, TRUE}
with the dyadic
AND and
OR operations replacing ∧ and ∨ respectively, and the
NOT operation producing complements. Thus 1 and 0 are just TRUE and FALSE respectively. This idea can be readily extended to the set of all
n-tuples (
x1,
x2,…,
xn)
where each
xi is in
B. The AND and OR operations are then extended to operate between corresponding pairs of elements in each
n-tuple to produce another
n-tuple; the NOT operation negates each item of an
n-tuple.
The second common example of a Boolean algebra is the set of subsets of a given set
S, with the operations of
intersection and
union replacing ∧ and ∨ respectively; set
complement fills the role of Boolean algebra complement.
Boolean algebras, named for George Boole, the 19th-century English mathematician, are fundamental to many aspects of computing – logic design, logic itself, and aspects of algorithm design.
