Boolean Algebra

Boolean algebra or boolean logic is the formal mathematical discipline that deals with "truth values"—"true" or "false". Its fundamental operations are "and", "or" and "not". One can write "propositions" (equations) of boolean algebra, such as

P = (Q+R)•(T')

and manipulate them the way one would manipulate ordinary algebraic equations.

Boolean algebra as a formal mathematical study was pioneered by (and is named after) English mathematician George Boole in the 1830s.

The terms "boolean algebra" and "boolean logic" are used interchangeably. The words are not capitalized (except at the beginning of a sentence, of course) even though they are named after a person.

Boolean Algebra and Computer Hardware[edit]

The thing that elevates boolean algebra from a somewhat obscure branch of mathematics to one of the driving forces of modern society is that it is the basis for computers. Boolean logic is implemented in electrical circuitry by means of gates (built from many CMOS and nMOS transistors wired together) representing the basic AND, NOT, and OR operators. These gates are then wired together to create computer chips. Therefore, everything a computer does must be represented in boolean logic. All numbers are represented internally in binary (base 2) notation, with digits ("bits") 1 and 0, corresponding to "true" and "false", respectively; and each letter is represented by a binary code.

Computation is then done by boolean algebra operations. For example, addition is performed by performing this function on each bit:

S = (A•B•C) + (A•B'•C') + (A'•B•C') + (A'•B'•C)
D = (A•B) + (A•C) + (B•C)

A modern computer processing chip has tens of millions of transistors, all calculating boolean operations.

Computer Programming[edit]

The operations of boolean logic are also extremely important in computer software. Modern computer programming languages usually have some kind of "boolean" data type. For example, in the C++ language, it is called "bool".

Three Basic Operations[edit]

The three basic operations of boolean algebra are AND (analogous to multiplication), OR (analogous to addition), and NOT (analogous to inversion). See the tables below for a numerical and pictorial descriptions. From these functions, the other functions of boolean algebra can be derived. In the following descriptions, we will use the 1-and-0 notation rather than the true-and-false notation.

Truth Table for the Operators
AND: A•B=C				OR: A+B=C				NOT A'=B
A	B	C		A	B	C		A	B
0	0	0		0	0	0		0	1
0	1	0		0	1	1		1	0
1	0	0		1	0	1
1	1	1		1	1	1

AND[edit]

AND is the boolean equivalent of multiplication. The product of two numbers are non-zero if both numbers are non-zero. In words, the AND function states: "If A AND B are true then C is true". The AND function is commutative, so it results in the same answer no matter what order the values are in. For example, A • B = B • A, and A • (B • C) = (A • B) • C.

OR[edit]

OR is the boolean equivalent of addition. The sum of two positive numbers is non-zero if either number is non-zero. In words, the OR function states: "If A OR B is true then C is true". Like AND, the OR function is commutative.

NOT[edit]

NOT is the Boolean equivalent of inversion. It is represented by an apostrophe (A') or an overbar (). NOT reverses the value of any variable: if A = 0, A' = 1, and if A = 1, A' = 0.

NOT can be combined with AND and NOT for interesting results. A•A' (A AND NOT A) always equals 0 (false), since no matter the value of A, one of the two values is always 0. Similarly, A+A' (A OR NOT A) always equals 1 (true), since no matter the value of A, one of the two values is always 1.

Order of Operations[edit]

By convention, the order of operations (sometimes called "operator precedence") for boolean algebra is the same as that for traditional algebra, except that there are fewer functions for boolean algebra: parenthesis are evaluated first, followed by multiplication then addition. Bars over multiple variables are treated at the same level as parenthesis. In practice, considerations of operation order are never a problem.

Derived Functions[edit]

From the three functions mentioned above, other functions can be derived. Some common ones are NAND, NOR and XOR. See the table below for a numerical description.

NAND: (A•B)'				NOR: (A+B)				XOR (A'B + AB')
A	B	C		A	B	C		A	B	C
0	0	1		0	0	1		0	0	0
0	1	1		0	1	0		0	1	1
1	0	1		1	0	0		1	0	1
1	1	0		1	1	0		1	1	0

NAND and NOR[edit]

NAND and NOR are formed by simply performing a NOT on the output of an AND or OR operation, respectively. NAND can be expressed symbolically as A NAND B = (AB)' and NOR can be expressed symbolically as A NOR B = (A+B)'.

XOR[edit]

XOR (or "exclusive OR") gives a 1 ("true") if either of its inputs are 1, but not both. Symbolically this can be broken down into its basic operations by the expression: A XOR B = A'B + B'A.

See also[edit]

• Boolean logic tutorial