Resources | Subject Notes | Computer Science
Boolean algebra is the algebra of two values: 0 (false) and 1 (true).
It is the mathematical foundation of digital logic and is used to design, analyse and simplify logic circuits.
Expressions use logical operators (AND, OR, NOT, XOR, XNOR) and are implemented using gates.
Write and use these to manipulate/simplify expressions.
\(A + B = B + A\) and \(A \cdot B = B \cdot A\)
\(A + (B + C) = (A + B) + C\) and \(A (B C) = (A B) C\)
\(A (B + C) = AB + AC\)
Useful for expanding or factoring expressions.
\(A \cdot 1 = A,\quad A + 0 = A\)
\(A \cdot 0 = 0,\quad A + 1 = 1\)
\(A \cdot \overline{A} = 0,\quad A + \overline{A} = 1\)
\(A + A = A,\quad A \cdot A = A\)
\(A + A B = A,\quad A (A + B) = A\)
\(\overline{A \cdot B} = \overline{A} + \overline{B}\)
\(\overline{A + B} = \overline{A} \cdot \overline{B}\)
Construct truth tables to verify expressions or gate-level circuits.
| A | B | \(A + B\) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
| A | B | \(A \oplus B\) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Cambridge assessments often require you to simplify Boolean expressions algebraically and sometimes by using Karnaugh maps (K-maps). Both are acceptable — K-maps are particularly useful to visualise minterm grouping.
Simplify: \(F = A\overline{B} + A B + \overline{A} B\).
Step-by-step (use commutativity/associativity/absorption):
\(F = A\overline{B} + AB + \overline{A}B\)
Group the \(B\) terms: \(F = A\overline{B} + B(A + \overline{A})\)
But \(A + \overline{A} = 1\), so \(B(A + \overline{A}) = B\). Thus
\(F = A\overline{B} + B\)
Use absorption: \(B + A\overline{B} = B + A\overline{B} = (B + A)(B + \overline{B}) = (B + A)\cdot 1 = A + B\)
Final: \(F = A + B\)
For two variables, the K-map is a 2×2 grid — group adjacent 1s to simplify into sum-of-products.
Translate expressions to gate-level diagrams (AND, OR, NOT, XOR, XNOR). Cambridge requires correct logic and minimal implementation where asked.
The half adder adds two bits \(A\) and \(B\), producing sum \(S\) and carry \(C\):
\(S = A \oplus B\)
\(C = A \cdot B\)
Adds \(A\), \(B\) and carry-in \(C_{in}\). Results:
\(S = A \oplus B \oplus C_{in}\)
\(C_{out} = AB + A C_{in} + B C_{in}\)
You may be asked to show how a full adder can be built from two half adders and an OR gate: combine partial sums and carries accordingly.
Simplify \(G = \overline{A}B + A\overline{B} + AB\).
Solution sketch:
Group: \(G = (\overline{A}B + A\overline{B}) + AB = A \oplus B + AB\)
Use identity \(X \oplus Y = XY' + X'Y\). Then \(A \oplus B + AB = (A \oplus B) + AB = A + B\) (you can show algebraically). Final: \(G = A + B\).
From the truth table below deduce the minimal sum-of-products expression.
| A | B | C | F |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
Hint: list minterms where \(F=1\): (0,0,1), (0,1,0), (0,1,1), (1,0,1), (1,1,1). Use K-map grouping to simplify.