Boolean algebra

Boolean algebra, developed in 1854 by George Boole in his book Laws of Thought, is a variant of algebra as taught in high school. Boolean algebra differs from ordinary algebra in three ways: in the values that variables may assume, which are of a logical instead of a numeric character; in the operations applicable to those values; and in the properties of those operations, that is, the laws they obey.

Values

Whereas ordinary algebra deals with real and complex numbers, Boolean algebra deals with bits, that is, the values 0 and 1. Bits may be isolated, or grouped into binary words or bit vectors of a given length, for example the eight words of length 3, namely 000, 001, 010, 011, 100, 101, 110, and 111. Boolean algebra is also applicable to subsets of a given set, for example the eight subsets of the set {0,1,2}, namely {}, {0}, {1}, {0,1}, {2}, {0,2}, {1,2}, and {0,1,2}.

For the purposes of Boolean algebra, sets are not different from bit vectors in any essential way. Bit vectors can be viewed as sets by treating them as subsets of the set of positions in the vector, with 1 at a given position denoting membership of that position in the subset and 0 nonmembership. For example taking the positions in the bit vector 110 to be 2,1,0 in that order, 110 can be regarded as the set {1,2} and 001 as the set {0}. Implementations of the programming language Pascal commonly take advantage of this correspondence to implement sets as binary words.

Operations

Certain operations of ordinary algebra, in particular addition x+y, multiplication xy, and negation -x, have their counterparts in Boolean algebra, namely the Boolean operations OR, AND, and NOT respectively. When applied to bits and binary words these operations are called respectively disjunction x∨y, conjunction x∧y, and negation ¬x. Some authors use instead the same arithmetic operations as ordinary algebra reinterpreted for Boolean algebra, treating x+y as synonymous with x∨y and xy with x∧y.

When applied to sets these operations are standardly named union X∪Y, intersection X∩Y, and complement -X respectively, but they are essentially the same Boolean operations as those applicable to binary words, and satisfy the same laws.

Conjunction x∧y behaves on 0 and 1 exactly as it does for ordinary algebra: if either x or y is 0 then so is x∧y, but if both are 1 then so is x∧y. Disjunction x∨y works almost like addition, with 0∨0 = 0 and 1∨0 = 0∨1 = 1. However there is a difference: 1∨1 is not 2 but 1.

Complement resembles ordinary negation in that it exchanges values. But whereas in ordinary algebra negation interchanges 1 and -1, 2 and -2, etc. while leaving 0 fixed, in Boolean algebra complement interchanges 0 and 1. One can think of ordinary negation as reflecting about 0, and Boolean complement as reflecting about the midpoint of 0 and 1. But whereas 0 exists as a number, the midpoint of 0 and 1 does not exist as a Boolean value, in fact there is no value that is left unchanged by Boolean complement.

The behavior of the Boolean operations on individual bits is extended to bit vectors, and hence sets, "coordinate-wise," meaning locally to each bit position. Thus the disjunction of two bit vectors, and hence the union of two sets, is computed at each bit position by taking the disjunction of the bits at that position. For example 1010∨0110 = 1110 while 1010∧0110 = 0010. There is therefore no flow of information between bit positions, only within bit positions. Shifting a word left or right does not constitute a Boolean operation because information flows between bit positions.

Laws

Following the convention mentioned above of denoting the Boolean operations with their numeric counterparts, namely writing x∨y as x+y and so on, Boolean algebra can be seen to satisfy many of the same laws as ordinary algebra. In particular the following laws are common to both kinds of algebra.

x+(y+z)	=	(x+y)+z
x(yz)	=	(xy)z
x+y	=	y+x
xy	=	yx
x(y+z)	=	xy+xz
x+0	=	x
x0	=	0
x1	=	x

Boolean algebra however obeys some additional laws, namely the following and their consequences.

x+x = x

xx = x

x(x+y) = x

x+xy = x

A consequence of the first of these laws is 1+1 = 1, which is false in ordinary algebra, where 1+1 = 2. Taking x = 2 in the second law shows that it is not an ordinary algebra law either. The third and fourth laws can be falsified in ordinary algebra by taking x = y = 1.

In both ordinary and Boolean algebra, negation works by exchanging pairs of elements, whence in both algebras it satisfies

--x = x

But whereas ordinary algebra satisfies

(-x)(-y)	=	xy
(-x)+(-y)	=	-(x+y)

Boolean algebra satisfies

(-x)(-y)	=	-(x+y)
(-x)+(-y)	=	-(xy)

These last two laws are called De Morgan's laws.