Translation

powered by

Computing (FOLDOC) dictionary
(also found in
English - English (Wordnet), )

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

Boolean algebra is sometimes defined as a "complemented

Boole's work which inspired the mathematical definition

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.