Inside every processor are billions of tiny circuits that make decisions using only two values: true and false, or 1 and 0. The mathematics that describes these decisions is Boolean algebra, and the physical devices that carry them out are logic gates. Learning to simplify Boolean expressions is a core skill in FSc and A Level computer science, digital electronics and university courses on computer architecture.
Where Boolean Algebra Came From
In 1847 and more fully in 1854, the English mathematician George Boole, a largely self-taught schoolteacher who became a professor at Queen's College Cork in Ireland, showed that logical reasoning could be written as algebra. Almost a century later, in 1937, Claude Shannon's master's thesis at MIT showed that Boole's algebra described electrical switching circuits perfectly. That insight turned an abstract branch of logic into the design language of every digital device.
The Three Basic Operations
Boolean variables take only the values 0 (false) and 1 (true). There are three fundamental operations.
- AND, written \(A \cdot B\) or simply \(AB\): equals 1 only when both inputs are 1.
- OR, written \(A + B\): equals 1 when at least one input is 1.
- NOT, written \(\overline{A}\) or \(A'\): flips 0 to 1 and 1 to 0.
The truth table lists every possible input combination. With two inputs there are \(2^2 = 4\) rows.
| A | B | A AND B | A OR B |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Note that \(1 + 1 = 1\) in Boolean algebra. The plus sign means OR, not ordinary addition.
Derived Gates
From AND, OR and NOT we build other useful gates.
- NAND \(\overline{AB}\): the opposite of AND. Output is 0 only when both inputs are 1.
- NOR \(\overline{A + B}\): the opposite of OR. Output is 1 only when both inputs are 0.
- XOR \(A \oplus B = A\overline{B} + \overline{A}B\): output is 1 when the inputs differ.
- XNOR \(\overline{A \oplus B}\): output is 1 when the inputs are the same.
NAND and NOR are called universal gates because any circuit at all can be built from NAND gates alone (or NOR gates alone). For example, \(\overline{A} = \overline{A \cdot A}\), so a NAND with both inputs tied together is a NOT gate. Chip manufacturers like this because they can mass-produce one kind of gate.
The Laws of Boolean Algebra
These laws let us rewrite expressions without changing their meaning.
- Identity: \(A + 0 = A\), \(A \cdot 1 = A\)
- Null: \(A + 1 = 1\), \(A \cdot 0 = 0\)
- Idempotent: \(A + A = A\), \(A \cdot A = A\)
- Complement: \(A + \overline{A} = 1\), \(A \cdot \overline{A} = 0\)
- Double negation: \(\overline{\overline{A}} = A\)
- Commutative, associative and distributive laws, as in ordinary algebra, plus a second distributive law: \(A + BC = (A + B)(A + C)\)
- Absorption: \(A + AB = A\), \(A(A + B) = A\)
- De Morgan's laws:
$$ \overline{A + B} = \overline{A} \cdot \overline{B}, \qquad \overline{A \cdot B} = \overline{A} + \overline{B} $$
A handy shortcut that follows from these is \(A + \overline{A}B = A + B\).
Worked Example 1: Simplifying an Expression
Simplify \(F = AB + A\overline{B} + \overline{A}B\).
Step 1: Factor \(A\) from the first two terms.
$$ F = A(B + \overline{B}) + \overline{A}B $$
Step 2: Apply the complement law, \(B + \overline{B} = 1\).
$$ F = A \cdot 1 + \overline{A}B = A + \overline{A}B $$
Step 3: Use the distributive law \(A + \overline{A}B = (A + \overline{A})(A + B)\).
$$ F = 1 \cdot (A + B) = A + B $$
Check with a truth table. For inputs (0,0), (0,1), (1,0), (1,1), the original expression gives 0, 1, 1, 1, and \(A + B\) also gives 0, 1, 1, 1. The two match on every row, so the simplification is correct. A circuit that needed three AND gates, two NOT gates and a three-input OR gate has shrunk to a single OR gate.
Worked Example 2: Using De Morgan's Law
Simplify \(G = \overline{\overline{A} + B} + AB\).
Step 1: Apply De Morgan's law to the first term.
$$ \overline{\overline{A} + B} = \overline{\overline{A}} \cdot \overline{B} = A\overline{B} $$
Step 2: Substitute back.
$$ G = A\overline{B} + AB $$
Step 3: Factor and use the complement law.
$$ G = A(\overline{B} + B) = A \cdot 1 = A $$
Check: when \(A = 1, B = 0\): \(\overline{0 + 0} + 0 = 1 + 0 = 1 = A\). When \(A = 0, B = 1\): \(\overline{1 + 1} + 0 = 0 = A\). The output simply follows \(A\), so input \(B\) is irrelevant and the circuit needs no gates at all.
Worked Example 3: Designing a Half Adder
How does a computer add two bits? Adding single bits \(A\) and \(B\) produces a sum bit \(S\) and a carry bit \(C\).
| A | B | S | C |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Step 1: Read off the sum column. \(S = 1\) when exactly one input is 1, so \(S = \overline{A}B + A\overline{B} = A \oplus B\).
Step 2: Read off the carry column. \(C = 1\) only when both inputs are 1, so \(C = AB\).
Step 3: Build it. One XOR gate gives the sum and one AND gate gives the carry. That is a half adder. Check the last row: \(1 + 1 = 2 = 10_2\), giving sum 0 and carry 1, exactly as the table says.
Chain two half adders with an OR gate and you get a full adder, which also accepts a carry from the previous column. Line up 64 full adders and you have the adder inside a 64-bit processor.
Writing Expressions from Truth Tables
A reliable method for any truth table is sum of products: for each row where the output is 1, write an AND term containing every variable (complemented if that variable is 0), then OR all those terms together. The result is always correct but often long, so you then simplify using the laws above or a Karnaugh map, which groups adjacent 1s visually to spot simplifications quickly.
Did You Know?
- Claude Shannon's 1937 thesis linking Boolean algebra to switching circuits is often called the most important master's thesis of the twentieth century.
- The Apollo Guidance Computer that helped land astronauts on the Moon in 1969 was built almost entirely from three-input NOR gates.
- With \(n\) inputs there are \(2^{2^n}\) possible Boolean functions: 16 for two inputs, but 256 for three.
Key Takeaways
- Boolean algebra works with only 0 and 1, using AND, OR and NOT.
- Laws such as complement, absorption and De Morgan's let you simplify expressions and therefore circuits.
- Always verify a simplification with a truth table.
- NAND and NOR are universal: any digital circuit can be built from just one of them.
- A half adder (XOR for sum, AND for carry) is the first step towards a full processor adder.
If Boolean simplification, K-maps or circuit design questions are slowing you down, Amathify's experts and PhD scholars can provide step-by-step solutions and assignment help; just reach us via WhatsApp or the Ask a Question form.
Stuck on a problem or assignment?
Our experts and PhD scholars solve maths, physics and chemistry — step by step.