Boolean algebra definition 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 not strictly an algebra
, but is in fact a lattice
. A Boolean algebra is sometimes defined as a "complemented distributive lattice
Boole's work which inspired the mathematical definition concerned algebras
, involving the operations of 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
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.