Difference between revisions of "Boolean algebra"
(OK, the other page did say one useful thng; put it here.) |
DavidB4-bot (Talk | contribs) m (→See also: clean up) |
||
| (8 intermediate revisions by 5 users not shown) | |||
| Line 1: | Line 1: | ||
| − | '''Boolean algebra''' or ''' | + | '''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') | P = (Q+R)•(T') | ||
and manipulate them the way one would manipulate ordinary algebraic equations. | and manipulate them the way one would manipulate ordinary algebraic equations. | ||
| Line 8: | Line 8: | ||
==Boolean Algebra and Computer Hardware== | ==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. | + | 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]] [[transistor]]s 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 [[ASCII|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) | S = (A•B•C) + (A•B'•C') + (A'•B•C') + (A'•B'•C) | ||
D = (A•B) + (A•C) + (B•C) | D = (A•B) + (A•C) + (B•C) | ||
A modern computer processing chip has tens of millions of transistors, all calculating boolean operations. | A modern computer processing chip has tens of millions of transistors, all calculating boolean operations. | ||
| + | |||
| + | ===Computer Programming=== | ||
| + | The operations of boolean logic are also 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". | ||
==Three Basic Operations== | ==Three Basic Operations== | ||
| − | The three basic operations of boolean algebra are AND (analogous to [[multiplication]]), OR (analogous to [[addition]]), and NOT. See the | + | 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. |
| − | {| class="wikitable" align="left" | + | {| class="wikitable" align="center" |
| − | ! colspan=3 | AND: A•B=C | + | ! colspan=10 | Truth Table for the Operators |
| + | |- alight="left" | ||
| + | ! colspan=3 | AND: A•B=C || || colspan=3 | OR: A+B=C || || colspan=2 | NOT A'=B | ||
|- align="center" | |- align="center" | ||
| '''A''' || '''B''' || '''C''' || rowspan=5 | || '''A''' || '''B''' || '''C''' || rowspan=5 | || '''A''' || '''B''' | | '''A''' || '''B''' || '''C''' || rowspan=5 | || '''A''' || '''B''' || '''C''' || rowspan=5 | || '''A''' || '''B''' | ||
| Line 27: | Line 34: | ||
| 1 || 0 || 0 || 1 || 0 || 1 | | 1 || 0 || 0 || 1 || 0 || 1 | ||
|- align="center" | |- align="center" | ||
| − | | 1 || 1 || 1 || 1 || | + | | 1 || 1 || 1 || 1 || 1 || 1 |
|} | |} | ||
| + | |||
===AND=== | ===AND=== | ||
| + | [[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. | ||
| + | |||
| + | {{clear}} | ||
===OR=== | ===OR=== | ||
| + | [[Image:VennOr1.gif|right|250px|thumb|Pictorial description of 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. | 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=== | ||
| − | NOT is | + | NOT is the Boolean equivalent of inversion. It is represented by an apostrophe (A') or an overbar (<math>\bar A</math>). 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. | 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. | ||
| Line 44: | Line 56: | ||
==Derived Functions== | ==Derived Functions== | ||
| − | From the three functions mentioned above, other functions can be derived. Some common | + | 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. |
{| class="wikitable" align="left" | {| class="wikitable" align="left" | ||
| Line 57: | Line 69: | ||
| 1 || 0 || 1 || 1 || 0 || 0 || 1 || 0 || 1 | | 1 || 0 || 1 || 1 || 0 || 0 || 1 || 0 || 1 | ||
|- align="center" | |- align="center" | ||
| − | | 1 || 1 || 0 || 1 || | + | | 1 || 1 || 0 || 1 || 1 || 0 || 1 || 1 || 0 |
|} | |} | ||
| Line 66: | Line 78: | ||
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. | 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. | ||
| − | + | ||
| − | + | ||
{{clear}} | {{clear}} | ||
| − | [[Category: | + | == See also == |
| + | *[http://www.learn-c.com/boolean.htm Boolean logic tutorial] | ||
| + | |||
| + | [[Category:Logic]] | ||
| + | [[Category:Computer Science]] | ||
[[Category:Electronics]] | [[Category:Electronics]] | ||
Revision as of 15:03, June 23, 2016
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. 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
The operations of boolean logic are also 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".
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.
