# Difference between revisions of "Boolean algebra"

m (NAND, etc.) |
(rewrite and expand) |
||

Line 1: | Line 1: | ||

− | '''Boolean | + | '''Boolean algebra''' is a division of mathematics which deals with boolean variables, which are variables which can only have two values. Typically these values are 0 and 1, especially within the fields of [[electronics]] or [[computers]], however boolean variables can have other values, such as "true" and "false". Boolean algebra was invented in the nineteenth century by an [[English]] mathematician named George Boole. |

+ | ==Three Basic Operations== | ||

+ | The three basic operations of boolean algebra are AND ([[multiplication]]), OR ([[addition]]), and NOT. See the table below for a numerical description. From these functions, the other functions of boolean algebra can be derived. | ||

− | [[ | + | {| class="wikitable" align="left" |

+ | ! colspan=3 | AND: A•B=C !! !! colspan=3 | OR: A+B=C !! !! colspan=2 | NOT A'=B | ||

+ | |- align="center" | ||

+ | | '''A''' || '''B''' || '''C''' || rowspan=5 | || '''A''' || '''B''' || '''C''' || rowspan=5 | || '''A''' || '''B''' | ||

+ | |- align="center" | ||

+ | | 0 || 0 || 0 || 0 || 0 || 0 || 0 || 1 | ||

+ | |- align="center" | ||

+ | | 0 || 1 || 0 || 0 || 1 || 1 || 1 || 0 | ||

+ | |- align="center" | ||

+ | | 1 || 0 || 0 || 1 || 0 || 1 | ||

+ | |- align="center" | ||

+ | | 1 || 1 || 1 || 1 || 0 || 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. | ||

+ | |||

+ | Just as in traditional [[algebra]], [[exponent]]s can be represented as a series of multiplications in boolean algebra, but the results are different. A<sup>n</sup> can be represented as the value A multiplied n times, or A•A•A•A... = C. Boolean multiplication returns a "true" (or a 1) if all values are "true" (or 1), but in this case, all values are always the same. So if A = 0, C = 0, and if A = 1, C = 1. This means that A<sup>n</sup> simply reduces to A! | ||

+ | |||

+ | ===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 a function which is not the equivalent of an algebraic function. 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. | ||

+ | |||

+ | ===Order of Operations=== | ||

+ | The [[order of operations]] 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. | ||

+ | |||

+ | ==Derived Functions== | ||

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

+ | |||

+ | {| class="wikitable" align="left" | ||

+ | ! colspan=3 | NAND: (A•B)'!! !! colspan=3 | NOR: (A+B) !! !! colspan=3 | XOR (A'B + AB') | ||

+ | |- align="center" | ||

+ | | '''A''' || '''B''' || '''C''' || rowspan=5 | || '''A''' || '''B''' || '''C''' || rowspan=5 | || '''A''' || '''B''' || '''C''' | ||

+ | |- align="center" | ||

+ | | 0 || 0 || 1 || 0 || 0 || 1 || 0 || 0 || 0 | ||

+ | |- align="center" | ||

+ | | 0 || 1 || 1 || 0 || 1 || 0 || 0 || 1 || 1 | ||

+ | |- align="center" | ||

+ | | 1 || 0 || 1 || 1 || 0 || 0 || 1 || 0 || 1 | ||

+ | |- align="center" | ||

+ | | 1 || 1 || 0 || 1 || 0 || 0 || 1 || 1 || 1 | ||

+ | |} | ||

+ | |||

+ | ===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. | ||

+ | |||

+ | {{clear}} | ||

+ | |||

+ | [[Category:Mathematics]] | ||

+ | [[Category:Electronics]] |

## Revision as of 23:08, December 12, 2007

**Boolean algebra** is a division of mathematics which deals with boolean variables, which are variables which can only have two values. Typically these values are 0 and 1, especially within the fields of electronics or computers, however boolean variables can have other values, such as "true" and "false". Boolean algebra was invented in the nineteenth century by an English mathematician named George Boole.

## Contents

## Three Basic Operations

The three basic operations of boolean algebra are AND (multiplication), OR (addition), and NOT. See the table below for a numerical description. From these functions, the other functions of boolean algebra can be derived.

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 | 0 | 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.

Just as in traditional algebra, exponents can be represented as a series of multiplications in boolean algebra, but the results are different. A^{n} can be represented as the value A multiplied n times, or A•A•A•A... = C. Boolean multiplication returns a "true" (or a 1) if all values are "true" (or 1), but in this case, all values are always the same. So if A = 0, C = 0, and if A = 1, C = 1. This means that A^{n} simply reduces to A!

### 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 a function which is not the equivalent of an algebraic function. 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

The order of operations 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.

## Derived Functions

From the three functions mentioned above, other functions can be derived. Some common derivatives 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 | 0 | 0 | 1 | 1 | 1 |

### 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.