Courses / Computer Science XI (HSSC-I) – FBISE Complete SLO-Based Course
1.2 Boolean Algebra, Identities, Duality and Karnaugh Maps
Unit 1 – Computer Systems · 90 min read · 11 MCQs to check yourself
De Morgan's laws and simplifying Boolean expressions
1. Boolean functions and expressions
Boolean algebra (George Boole, 1854) is algebra where variables can only be 0 or 1 and the operations are AND (·), OR (+) and NOT (').
- A Boolean variable holds 0 or 1 (A, B, X …).
- A Boolean expression combines variables with operators, e.g. AB + C.
- A Boolean function gives an output for every input combination, e.g. F(A,B,C) = AB + C. Every function can be shown three ways: expression, truth table and logic circuit.
- A literal is a variable or its complement (A or A'). A minterm is an AND term that contains every variable once, e.g. ABC (= row 101 = m₅).
- Sum of products (SOP): an OR of AND terms, e.g. AB + AC. To write the SOP from a truth table, take each row where F = 1 and AND its literals (0 → complemented).
2. Boolean identities (laws)
| Law | AND form | OR form |
|---|---|---|
| Identity | A · 1 = A | A + 0 = A |
| Null (dominance) | A · 0 = 0 | A + 1 = 1 |
| Idempotent | A · A = A | A + A = A |
| Complement | A · A = 0 | A + A = 1 |
| Double complement | A = A | – |
| Commutative | AB = BA | A + B = B + A |
| Associative | (AB)C = A(BC) | (A+B)+C = A+(B+C) |
| Distributive | A(B + C) = AB + AC | A + BC = (A+B)(A+C) |
| Absorption | A(A + B) = A | A + AB = A |
| De Morgan | AB = A + B | A + B = A B |
De Morgan in words: "break the bar, change the sign". NAND = OR of inverted inputs; NOR = AND of inverted inputs.
Proof by truth table (De Morgan, first law):
| A | B | AB | (AB)' | 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 columns (AB)' and A' + B' are identical in every row, so the law is proved. |
3. Duality
The dual of an expression is found by swapping AND ↔ OR and 0 ↔ 1, leaving the variables (and their bars) unchanged. Principle of duality: if an identity is true, its dual is also true. That is why every law above comes in a pair.
| Expression | Dual |
|---|---|
| A + 0 = A | A · 1 = A |
| A + A = 1 | A · A = 0 |
| A(B + C) | A + BC |
| AB + AC + 1 | (A + B)(A + C) · 0 |
4. Simplifying with algebra
Example 1 (model paper, Section B): F = XYZ + XYZ + XZ F = XZ(Y + Y) + XZ = XZ · 1 + XZ = Z(X + X) = Z The whole circuit reduces to a single wire from Z!
Example 2: F = AB + AB = A(B + B) = A · 1 = A
Example 3 (absorption): F = A + AB = A(1 + B) = A · 1 = A
5. Karnaugh maps (K-maps)
A K-map is a grid with one cell per row of the truth table, arranged in Gray code order (00, 01, 11, 10) so that neighbouring cells differ by only one variable. Grouping neighbouring 1s removes the variable that changes.
Rules for grouping:
- Groups contain only 1s, and their size must be a power of 2: 1, 2, 4, 8.
- Groups are rectangles (no diagonals); make each group as large as possible.
- Use as few groups as possible; groups may overlap.
- The map wraps around: the left and right edges are neighbours (so are the four corners).
- In each group, keep the variables that do not change; a variable that is 0 throughout appears complemented.
| Group size (3-variable map) | Variables left in the term |
|---|---|
| 1 cell | 3 |
| 2 cells | 2 |
| 4 cells | 1 |
| 8 cells | F = 1 |
2-variable K-map
3-variable K-map – model paper question
Simplify F = A B C + ABC + AB C + ABC + ABC + ABC and draw the circuit.
Step 1 – minterms: 000 = m0, 010 = m2, 100 = m4, 101 = m5, 110 = m6, 111 = m7. Step 2 – fill the map: rows A = 0 / A = 1, columns BC = 00, 01, 11, 10. Step 3 – group: the whole A = 1 row (m4, m5, m7, m6) is a group of four → A. The four cells with C = 0 (m0, m2, m4, m6 – the left and right columns, which wrap around) form another group of four → C'. Step 4 – answer: F = A + C
6. Check a simplification in Python
from itertools import product
same = True
for a, b, c in product((0, 1), repeat=3):
na, nb, nc = 1 - a, 1 - b, 1 - c
original = (na&nb&nc) | (na&b&nc) | (a&nb&nc) | (a&nb&c) | (a&b&nc) | (a&b&c)
simple = a | nc
same = same and original == simple
print("F = A + C' is correct:", same)
Output:
F = A + C' is correct: True
3-variable Karnaugh map tutorial
Practical (PBA) tasks
- Prove both De Morgan's laws using truth tables and a Python program.
- Simplify F = AB + AB + AB with a K-map (answer: A + B) and test the original and the simplified circuits in a simulator.
- Build a half adder (Sum = A XOR B, Carry = AB) and check its truth table.
Short and long questions
1. Convert the Boolean expression F = XYZ + XY'Z + X'Z to a logic circuit.
Model answer
Inputs X, Y, Z. Use NOT gates to make Y' and X'. Three AND gates make the terms: AND1(X, Y, Z), AND2(X, Y', Z), AND3(X', Z). One 3-input OR gate combines the three AND outputs to give F. (Simplification: F = XZ(Y + Y') + X'Z = XZ + X'Z = Z – so the circuit is equivalent to a single wire from Z.)
2. State De Morgan's laws and prove one using a truth table.
Model answer
Law 1: (AB)' = A' + B'. Law 2: (A + B)' = A'B'. Proof of law 2:
| A | B | A+B | (A+B)' | A' | B' | A'B' |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| The columns (A+B)' and A'B' are identical, so the law holds. |
3. What is duality in Boolean algebra? Write the dual of (a) A + 0 = A (b) A(B + C) (c) A + A' = 1.
Model answer
The dual of an expression is obtained by interchanging AND (·) with OR (+) and 0 with 1, keeping variables unchanged. The principle of duality says that if an identity is true, its dual is also true. (a) A · 1 = A (b) A + BC (c) A · A' = 0
4. Why are NAND and NOR called universal gates? Show how a NOT gate is made from a NAND gate.
Model answer
Because every other logic gate (NOT, AND, OR, XOR …) and therefore any circuit can be built using only NAND gates or only NOR gates. Manufacturers can produce one type of gate cheaply in bulk. NOT from NAND: connect both inputs of the NAND gate to A. Output = (A · A)' = A'.
5. Simplify the Boolean function F using a Karnaugh map and construct a logic circuit for the simplified expression: F = A'B'C' + A'BC' + AB'C' + AB'C + ABC' + ABC (3 + 3)
Model answer
Minterms: A'B'C' = 000 = m0, A'BC' = 010 = m2, AB'C' = 100 = m4, AB'C = 101 = m5, ABC' = 110 = m6, ABC = 111 = m7. So F = Σm(0, 2, 4, 5, 6, 7). K-map (rows A, columns BC in Gray order):
| A \ BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
| Groups: (1) the complete A = 1 row – four cells (m4, m5, m7, m6) → A. (2) the four cells where C = 0 – columns 00 and 10 in both rows (m0, m2, m4, m6), adjacent by wrap-around → C'. | ||||
| Simplified expression: F = A + C' | ||||
| Circuit: input C goes through a NOT gate to give C'; A and C' go into a 2-input OR gate whose output is F. (2 gates instead of 6 three-input ANDs and a 6-input OR.) |
6. Define logic gates. Explain AND, OR, NOT, NAND, NOR and XOR gates with symbols, Boolean expressions and truth tables.
Model answer
A logic gate is an electronic circuit with one or more binary inputs and one output whose value is decided by a logical rule.
| Gate | Expression | Rule | Output for AB = 00, 01, 10, 11 |
|---|---|---|---|
| AND | F = A·B | 1 only if all inputs are 1 | 0, 0, 0, 1 |
| OR | F = A + B | 1 if any input is 1 | 0, 1, 1, 1 |
| NOT | F = A' | inverts the single input | A = 0 → 1, A = 1 → 0 |
| NAND | F = (AB)' | NOT of AND | 1, 1, 1, 0 |
| NOR | F = (A + B)' | NOT of OR | 1, 0, 0, 0 |
| XOR | F = A ⊕ B = A'B + AB' | 1 if inputs differ | 0, 1, 1, 0 |
| Symbols: AND – D-shape; OR – curved shield; NOT – triangle with a bubble; NAND and NOR – AND/OR shapes with an output bubble; XOR – OR shape with an extra curved line at the input. | |||
| NAND and NOR are universal gates. Uses: AND in seat-belt alarms, OR in burglar alarms, XOR in adders and staircase switches. |
7. Simplify F = A'B + AB + AB' using Boolean algebra and a K-map, and draw both the original and simplified circuits.
Model answer
Algebra: F = A'B + AB + AB' = B(A' + A) + AB' = B + AB' = (B + A)(B + B') = A + B (distributive law A + BC = (A+B)(A+C)). K-map (2 variables): 1s in cells 01, 11, 10. Group the column B = 1 (cells 01 and 11) → B; group the row A = 1 (cells 10 and 11) → A. F = A + B. Original circuit: NOT gates for A' and B'; three 2-input AND gates (A'B, AB, AB'); one 3-input OR gate. Simplified circuit: a single 2-input OR gate with inputs A and B. The function is simply OR.
This lesson ends with a quiz of 11 MCQs. Open the lesson on PrepOasis to take it and save your progress.
Previous: 1.1 Digital Logic, Logic Gates and Truth Tables · Next: 1.3 Systems Design: SDLC and Software Development Methodologies
All lessons in Computer Science XI (HSSC-I) – FBISE Complete SLO-Based Course