LearnTronics
Math
Boolean Algebra — mathematics using only 0 and 1
In the previous lesson we introduced base 2, where every digit is either 0 or 1. Boolean algebra becomes simpler still: for the moment, each variable represents only one Boolean value at a time.
0 or 1.
Those two values can also be read as false / true, off / on, or low / high when we apply the mathematics to logic and digital electronics.
Variables and operators
Let A and B be Boolean variables. Each may have only the value 0 or 1. The fundamental operations are:
| Operation | Words | Common notation | Meaning |
|---|---|---|---|
| NOT | NOT A | ~A also ¬A or |
Reverse the value |
| AND | A AND B | A·B or AB | 1 only when both are 1 |
| OR | A OR B | A + B | 1 when either or both are 1 |
| XOR | A XOR B | A ⊕ B | 1 when exactly one is 1 |
In Boolean algebra:
1 + 1 = 1 because 1 OR 1 is still 1.
1 · 1 = 1 because 1 AND 1 is 1.
The basic truth tables
| A | B | A·B | A+B | A⊕B |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 |
| A | ~A |
|---|---|
| 0 | 1 |
| 1 | 0 |
A truth table is therefore not merely a logic diagram aid. It is also a mathematical way to define a Boolean operation completely.
Boolean identities
Because Boolean variables can only be 0 or 1, many useful relationships can be written as compact algebraic laws.
| Law | Expression | Meaning |
|---|---|---|
| Identity — AND | A·1 = A | AND with 1 leaves A unchanged. |
| Identity — OR | A+0 = A | OR with 0 leaves A unchanged. |
| Null — AND | A·0 = 0 | AND with 0 always produces 0. |
| Null — OR | A+1 = 1 | OR with 1 always produces 1. |
| Idempotent — AND | A·A = A | Repeating A does not change it. |
| Idempotent — OR | A+A = A | Repeating A does not change it. |
| Complement — AND | A·~A = 0 | A and NOT A cannot both be 1. |
| Complement — OR | A+~A = 1 | Either A or NOT A must be 1. |
| Double negation | ~(~A) = A | Negating twice returns the original value. |
Proving one identity
Consider:
There are only two possible values for A, so we can test both:
| A | A + 0 | Equal to A? |
|---|---|---|
| 0 | 0 | Yes |
| 1 | 1 | Yes |
Because the two columns match for every possible value of A, the identity is proven.
Commutative, associative, and distributive laws
| Law | Boolean form | What it allows |
|---|---|---|
| Commutative AND | A·B = B·A | Swap the order of AND terms. |
| Commutative OR | A+B = B+A | Swap the order of OR terms. |
| Associative AND | (A·B)·C = A·(B·C) | Regroup AND operations. |
| Associative OR | (A+B)+C = A+(B+C) | Regroup OR operations. |
| Distributive | A·(B+C) = A·B + A·C | Distribute AND across OR. |
| Boolean distributive | A + B·C = (A+B)·(A+C) | OR can also distribute across AND. |
The last relationship often surprises students because ordinary arithmetic does not have a matching form. Boolean algebra has its own structure and should be learned on its own terms.
Absorption
| Law | Expression | Result |
|---|---|---|
| Absorption | A + A·B | A |
| Absorption | A·(A+B) | A |
Why A + A·B simplifies to A
If A is 1, the expression is already 1 regardless of B. If A is 0, then A·B is also 0. So B can never change the final answer.
De Morgan's laws
De Morgan's laws show how NOT moves across AND and OR operations:
In words:
- NOT (A AND B) is the same as (NOT A) OR (NOT B).
- NOT (A OR B) is the same as (NOT A) AND (NOT B).
Verify De Morgan with a truth table
| A | B | A·B | ~(A·B) | ~A | ~B | ~A+~B |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
The final two columns match on every row, so the two expressions are equivalent.
Simplifying an expression
Suppose we begin with:
So the entire original expression reduces to just A.
From algebra to circuits
A Boolean expression can describe the same function as a network of logic gates. Simplifying the algebra can therefore reduce the number of gates, connections, or operations needed to produce the same result.
That is one reason Boolean algebra is so useful in digital electronics: two expressions may look different but still produce exactly the same output for every possible input.
For the language and circuit interpretation of these operators, see Tutorial 0024 — AND, OR, NOT.