Difference between revisions of "Boolean algebra"
m (→Derived Functions) |
(→AND) |
||
| Line 33: | Line 33: | ||
===AND=== | ===AND=== | ||
| − | [[Image:VennAnd1.gif|right|250px|thumb|Pictorial | + | [[Image:VennAnd1.gif|right|250px|thumb|Pictorial description of AND]] |
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. | 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. | ||
Revision as of 23:14, September 3, 2008
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 1830's.
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.
Contents
Boolean Algebra and Computer Hardware
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. Computers do everything 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. Computers are then designed in terms of boolean algebra equations. For example, addition is performed by 32 copies of these equations:
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.
Three Basic Operations
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
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
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
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
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
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
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
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.
Boolean Algebra and Computer Programming
The operations of boolean logic are extremely important in computer software. Modern computer languages usually have some kind of "boolean" data type. For example, in the C++ language, it is called "bool".
