Boolean Algebra
Boolean Algebra
_Boolean algebra_ is the branch of algebra in which the values of the variables and constants have exactly two values: _true_ and _false_ , usually denoted 1 and 0 respectively.
Operators
The basic operators in Boolean algebra are AND , OR , and NOT .
The secondary operators are _eXclusive OR_ (often called XOR ) and _eXclusive NOR_ ( XNOR , sometimes called equivalence ). They are secondary in the sense that they can be composed from the basic operators.
The AND of two values is true only whenever both values are true. It is written as xy or x⋅y. The values of _and_ for all possible inputs is shown in the following truth table:
x | y | xy |
|---|---|---|
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
The OR of two values is true whenever either or both values are true. It is written as x+y. The values of _or_ for all possible inputs is shown in the following truth table:
x | y | x+y |
|---|---|---|
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 1 |
The NOT of a value is its opposite; that is, the _not_ of a true value is false whereas the _not_ of a false value is true. It is written as $\overline{x}$ or ¬x. The values of _not_ for all possible inputs is shown in the following truth table:
x | $\overline{x}$ |
|---|---|
0 | 1 |
1 | 0 |
The XOR of two values is true whenever the values are different. It uses the ⊕ operator, and can be built from the basic operators: x⊕y=$x\overline{y} + y\overline{x}$ The values of _xor_ for all possible inputs is shown in the following truth table:
x | y | x⊕y |
|---|---|---|
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
The XNOR of two values is true whenever the values are the same. It is the NOT of the XOR function. It uses the ⊙ operator: x⊙y=$\overline{x \oplus y}$. The _xnor_ can be built from basic operators: x⊙y=xy + $\overline{xy}$ The values of _xnor_ for all possible inputs is shown in the following truth table:
x | y | x⊙y |
|---|---|---|
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
Just as algebra has basic rules for simplifying and evaluating expressions, so does Boolean algebra.
Laws
A law of Boolean algebra is an identity such as x+(y+z)=(x+y)+z between two Boolean terms, where a Boolean term is defined as an expression built up from variables, the constants 0 and 1, and operations _and_ , _or_ , _not_ , _xor_ , and _xnor_ .
Like ordinary algebra, parentheses are used to group terms. When a _not_ is represented with an overhead horizontal line, there is an implicit grouping of the terms under the line. That is, $x \cdot \overline{y+z}$ is evaluated as if it were written $x \cdot (\overline{y+z})$
Order of Precedence
The order of operator precedence is
1. _not_
2. _and_
3. _xor_
4. _xnor_
5. _or_
Operators with the same level of precedence are evaluated from left-to-right.
Fundamental Identities
Law | Example |
|---|---|
Commutative Law – The order of application of two separate terms is not important. | x+y=y+x , x⋅y=y⋅x |
Associative Law – Regrouping of the terms in an expression doesn't change the value of the expression. | (x+y)+z = x+(y+z) , x⋅(y⋅z)=(x⋅y)⋅z |
Idempotent Law – A term that is _or'_ ´ed or _and_ ´ed with itself is equal to that term. | x+x=x , x⋅x=x |
Annihilator Law – A term that is _or'_ ´ed with 1 is 1; a term _and_ ´ed with 0 is 0. | x+1=1, x⋅0=0 |
Identity Law – A term _or_ ´ed 0 or _and_ ´ed with a 1 will always equal that term. | x+0=x , x⋅1=x |
Complement Law – A term _or_ ´ed with its complement equals 1 and a term _and_ ´ed with its complement equals 0. | $x+\overline{x}=1$ , $x\cdot\overline{x}=0$ |
Absorptive Law – Complex expressions can be reduced to a simpler ones by absorbing like terms. | x+xy=x, x+$\overline{x}$y=x+y, x(x+y)=x |
Distributive Law – It's OK to multiply or factor-out an expression. | x⋅(y+z)=xy+xz, (x+y)⋅(p+q)=xp+xq+yp+yq, (x+y)(x+z)=x+yz |
DeMorgan's Law – An _or_ ( _and_ ) expression that is negated is equal to the _and_ ( _or_ ) of the negation of each term. | $\overline{x+y}=\overline{x}\cdot\overline{y}$, $\overline{x \cdot y} = \overline{x} + \overline{y}$ |
Double Negation – A term that is inverted twice is equal to the original term. | $\overline{\overline{x}}=x$ |
Relationship between XOR and XNOR | $x \odot y=\overline{x \oplus y}=x \oplus \overline{y}=\overline{x} \oplus y$ |
Sample Problems
Problems in this category are typically of the form "Given a Boolean expression, simplify it as much as possible" or "Given a Boolean expression, find the values of all possible inputs that make the expression _true_ ." Simplify means writing an equivalent expression using the fewest number of operators.