Boolean Algebra & Logic Gates
10h
Class hours
6
Topics
0%
0/36 done
Why This Unit Matters
The mathematical foundation of digital circuits — master Boolean algebra, logic gates, and K-map minimisation for elegant circuit design.
Why This Unit Matters
Unit 2 is the language of digital design. Logic gates are the physical building blocks of every circuit — from a simple adder to an entire CPU. Boolean algebra lets you describe, simplify, and optimize those circuits mathematically. K-maps and Quine-McCluskey give you systematic tools to find the minimal gate implementation of any truth table. TU BCA exams consistently test K-map minimization, Boolean simplification, and universal gate realization in every paper from 2019–2025.
Unit Overview in Simple Words
Logic Gates
AND, OR, NOT, NAND, NOR, XOR, XNOR — the physical switches that compute.
Boolean Algebra
Math rules for 0s and 1s — simplify circuits without building them.
K-Map
Visual grid method to find the simplest sum-of-products expression.
Quine-McCluskey
Tabular algorithm — like K-map but works for any number of variables.
Learning Outcomes
Teaching Hours
10 hours
Topics
6 main topics
Exam Weight
~30% of paper
Must Know
K-Map + Boolean simplification
Logic Gates
2.1 Basic Logic Gates: AND, OR, NOT
Logic gates are the fundamental building blocks of all digital circuits. They implement Boolean operations on one or more binary inputs to produce a single binary output. The three primary gates are AND, OR, and NOT — every other gate is derived from these.
Click to toggle inputs
Interactive Truth Table
LIVE
| A | B | Y = A·B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Output is HIGH (1) only when ALL inputs are HIGH. Acts like multiplication — any 0 input forces output to 0.
Click to toggle inputs
Interactive Truth Table
LIVE
| A | B | Y = A+B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Output is HIGH if ANY input is HIGH. Acts like addition — any 1 input forces output to 1.
Click to toggle inputs
Interactive Truth Table
LIVE
| A | Y = Ā |
|---|---|
| 0 | 1 |
| 1 | 0 |
Inverts the input. Single input, single output. Also called a complementor or inverter.
🎯 Exam Focus
2.2 Universal Logic Gates: NAND and NOR
NAND and NOR are called universal gates because any Boolean function — and therefore any digital circuit — can be implemented using only NAND gates or only NOR gates. This is extremely important for IC manufacturing: only one type of gate needs to be fabricated.
Click to toggle inputs
Interactive Truth Table
LIVE
| A | B | Y = (AB)̄ |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
NOT of AND. Output is LOW only when ALL inputs are HIGH. The bubble on the AND symbol represents inversion.
Click to toggle inputs
Interactive Truth Table
LIVE
| A | B | Y = (A+B)̄ |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
NOT of OR. Output is HIGH only when ALL inputs are LOW. The bubble on the OR symbol represents inversion.
Why NAND/NOR Are Universal
If you can build NOT, AND, and OR from a single gate type, you can build any circuit. Here's how:
Using only NAND gates:
NOT A: Connect both NAND inputs to A → output = (AA)̄ = Ā
A AND B: NAND(A,B) → NOT → gives A·B
A OR B: NOT A → NAND with NOT B → gives A+B (De Morgan)
Using only NOR gates:
NOT A: Connect both NOR inputs to A → output = (A+A)̄ = Ā
A OR B: NOR(A,B) → NOT → gives A+B
A AND B: NOT A → NOR with NOT B → gives A·B (De Morgan)
NAND Gate Realizations — All Basic Gates
Connect both inputs of a NAND gate to the same signal A. Output = (A·A)̄ = Ā
One NAND gate → NOT. This is the key trick.
🎯 Exam Focus
2.3 Extended Gates: XOR and XNOR
Click to toggle inputs
Interactive Truth Table
LIVE
| A | B | Y = A⊕B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Output is HIGH when inputs are DIFFERENT. Output is LOW when inputs are the SAME. Think: 'odd number of 1s at input.'
Click to toggle inputs
Interactive Truth Table
LIVE
| A | B | Y = A⊙B |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Complement of XOR. Output is HIGH when inputs are EQUAL (same). Used in comparator circuits.
All 7 Gates — Quick Reference
| Gate | Expression | 00 | 01 | 10 | 11 | Rule |
|---|---|---|---|---|---|---|
| AND | A·B | 0 | 0 | 0 | 1 | All inputs must be 1 |
| OR | A+B | 0 | 1 | 1 | 1 | Any input can be 1 |
| NOT | Ā | 1 | - | - | 0 | Inverts input (1 input) |
| NAND | (AB)̄ | 1 | 1 | 1 | 0 | NOT of AND |
| NOR | (A+B)̄ | 1 | 0 | 0 | 0 | NOT of OR |
| XOR | A⊕B | 0 | 1 | 1 | 0 | Inputs must differ |
| XNOR | A⊙B | 1 | 0 | 0 | 1 | Inputs must be equal |
Columns 00/01/10/11 show Y for AB = 00, 01, 10, 11 respectively. NOT has only one input.
💡 Remember
Boolean Algebra
2.4 Boolean Algebra
Boolean algebra is the mathematical framework for digital logic, developed by George Boole in 1854 and applied to digital circuits by Claude Shannon in 1938. Variables can only take two values: 0 (FALSE) or 1 (TRUE). The three fundamental operations are AND (·), OR (+), and NOT (‾).
2.4.1 Postulates and Theorems
Boolean Laws — All 16 Identities
Identity & Null Laws
Idempotent & Complement
Commutative & Associative
Distributive & Absorption
De Morgan's Theorems
The most important theorems in Boolean algebra — asked every year.
(A · B)̄ = Ā + B̄
NOT of AND = OR of NOTs
In words: The complement of a product equals the sum of the complements. A NAND gate is equivalent to an OR gate with inverted inputs.
Verify for A=1, B=0:
(1·0)̄ = 0̄ = 1
Ā+B̄ = 0+1 = 1 ✓
(A + B)̄ = Ā · B̄
NOT of OR = AND of NOTs
In words: The complement of a sum equals the product of the complements. A NOR gate is equivalent to an AND gate with inverted inputs.
Verify for A=1, B=0:
(1+0)̄ = 1̄ = 0
Ā·B̄ = 0·1 = 0 ✓
💡 Remember
2.4.2 Canonical Forms: SOP and POS
Any Boolean function can be expressed in two standard forms: Sum of Products (SOP) — OR of AND terms, or Product of Sums (POS) — AND of OR terms. The "canonical" forms use minterms and maxterms (one term per row of truth table).
Minterm (Sum of Products)
Minterm mᵢ: AND of all variables (complemented if input is 0, uncomplemented if 1). Output = 1 for exactly one input combination.
SOP: Sum (OR) of all minterms where f = 1.
Notation: F(A,B,C) = Σm(0,2,4,6) — OR of minterms 0,2,4,6
Example: F = Σm(1,3,5,7) for A,B,C:
F = ĀB̄C + ĀBC + AB̄C + ABC
= C(Ā+A) = C ← simplified
Maxterm (Product of Sums)
Maxterm Mᵢ: OR of all variables (uncomplemented if input is 0, complemented if 1). Output = 0 for exactly one input combination.
POS: Product (AND) of all maxterms where f = 0.
Notation: F(A,B,C) = ΠM(1,3,5,7) — AND of maxterms 1,3,5,7
Example: F = ΠM(0,2,4,6) for A,B,C:
F = (A+B+C)(A+B̄+C)(Ā+B+C)(Ā+B̄+C)
= C ← simplified (same function!)
3-Variable Minterms and Maxterms
| A | B | C | Minterm | Symbol | Maxterm | Symbol |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | ĀB̄C̄ | m0 | (A+B+C) | M0 |
| 0 | 0 | 1 | ĀB̄C | m1 | (A+B+C̄) | M1 |
| 0 | 1 | 0 | ĀBC̄ | m2 | (A+B̄+C) | M2 |
| 0 | 1 | 1 | ĀBC | m3 | (A+B̄+C̄) | M3 |
| 1 | 0 | 0 | AB̄C̄ | m4 | (Ā+B+C) | M4 |
| 1 | 0 | 1 | AB̄C | m5 | (Ā+B+C̄) | M5 |
| 1 | 1 | 0 | ABC̄ | m6 | (Ā+B̄+C) | M6 |
| 1 | 1 | 1 | ABC | m7 | (Ā+B̄+C̄) | M7 |
SOP ↔ POS Relationship
SOP uses minterms (rows where F=1)
F = Σm(where output = 1)
F̄ = Σm(where output = 0)
POS uses maxterms (rows where F=0)
F = ΠM(where output = 0)
F̄ = ΠM(where output = 1)
💡 Remember
🎯 Exam Focus
2.4.3 Algebraic Simplification
Algebraic simplification reduces a Boolean expression to its simplest form using the laws and theorems. Each step must cite which law/theorem was applied. Click through the steps below:
Example 1: Two-variable simplification
Simplify: F = AB + AB̄
F = AB + AB̄
Original expression
Example 2: Three-variable simplification
Simplify: F = ABC + ABC̄ + AB̄C
F = ABC + ABC̄ + AB̄C
Original expression
Example 3: Using De Morgan's theorem
Simplify: F = (AB̄ + C̄)̄
F = (AB̄ + C̄)̄
Original expression — complement of a sum
Example 4: Four-variable with absorption
Simplify: F = A + AB + ABC + ABCD
F = A + AB + ABC + ABCD
Original expression
⚠️ Common Mistake
Mistake 2: Confusing Absorption 1 (A+AB=A) with Absorption 3 (A+ĀB=A+B). In law 1, the second term has NO complement on A. In law 3, the second term has A complemented.
Karnaugh Map (K-Map)
2.5 Karnaugh Map (K-Map)
The Karnaugh Map (developed by Maurice Karnaugh, 1953) is a visual method to simplify Boolean expressions. It uses a grid where adjacent cells differ by exactly one bit (Gray code ordering), allowing groups of 1s to be combined to eliminate variables.
K-Map Grouping Rules
Groups must be powers of 2
1, 2, 4, 8, 16 cells only — never 3, 5, 6, 7 etc.
Make groups as large as possible
Larger group = fewer variables in final term
Groups can overlap
A cell can belong to more than one group
Wrap around (toroidal)
Left edge adjacent to right edge; top to bottom — they are logically adjacent
Don't cares (×) can be 0 or 1
Include × in a group if it makes the group larger — but only if it helps
Every minterm (1) must be covered
No minterm can be left ungrouped
Group Size → Variables Eliminated
| Group Size | Variables in resulting term | Result |
|---|---|---|
| 1 cell (group of 1) | 4 (for 4-var) | All 4 variables remain — not simplified |
| 2 cells (group of 2) | 3 | One variable eliminated |
| 4 cells (group of 4) | 2 | Two variables eliminated |
| 8 cells (group of 8) | 1 | Three variables eliminated |
| 16 cells (all) | 0 | F = 1 (all 1s) |
Interactive K-Map
Click cells to set minterms and see the resulting SOP expression.
Canonical Sum of Products (SOP)
Minterm Notation ∑m:
Algebraic Form:
2-Variable K-Map
F(A,B) = Σm(1,3) — group of 2
Minterms: Σm(1,3)
| A\B | B=0 | B=1 |
|---|---|---|
| A=0 | 00 | 11 |
| A=1 | 02 | 13 |
3-Variable K-Map
F(A,B,C) = Σm(1,3,5,7) — group of 4
Minterms: Σm(1,3,5,7)
| A\BC | BC=00 | BC=01 | BC=11 | BC=10 |
|---|---|---|---|---|
| A=0 | 00 | 11 | 13 | 02 |
| A=1 | 04 | 15 | 17 | 06 |
F(A,B,C) = Σm(0,1,4,5) — wrap-around group of 4
Minterms: Σm(0,1,4,5)
| A\BC | BC=00 | BC=01 | BC=11 | BC=10 |
|---|---|---|---|---|
| A=0 | 10 | 11 | 03 | 02 |
| A=1 | 14 | 15 | 07 | 06 |
F(A,B,C) = Σm(0,2,4,5,6,7) — multiple groups
Minterms: Σm(0,2,4,5,6,7)
| A\BC | BC=00 | BC=01 | BC=11 | BC=10 |
|---|---|---|---|---|
| A=0 | 10 | 01 | 03 | 12 |
| A=1 | 14 | 15 | 17 | 16 |
4-Variable K-Map
F(A,B,C,D) = Σm(0,1,2,3,4,5,6,7) — group of 8
Minterms: Σm(0,1,2,3,4,5,6,7)
| AB\CD | CD=00 | CD=01 | CD=11 | CD=10 |
|---|---|---|---|---|
| AB=00 | 10 | 11 | 13 | 12 |
| AB=01 | 14 | 15 | 17 | 16 |
| AB=11 | 012 | 013 | 015 | 014 |
| AB=10 | 08 | 09 | 011 | 010 |
F(A,B,C,D) = Σm(0,1,4,5,10,11,14,15) — complex
Minterms: Σm(0,1,4,5,10,11,14,15)
| AB\CD | CD=00 | CD=01 | CD=11 | CD=10 |
|---|---|---|---|---|
| AB=00 | 10 | 11 | 03 | 02 |
| AB=01 | 14 | 15 | 07 | 06 |
| AB=11 | 012 | 013 | 115 | 114 |
| AB=10 | 08 | 09 | 111 | 110 |
F(A,B,C,D) = Σm(0,2,3,4,6,7,8,10) — multiple groups
Minterms: Σm(0,2,3,4,6,7,8,10)
| AB\CD | CD=00 | CD=01 | CD=11 | CD=10 |
|---|---|---|---|---|
| AB=00 | 10 | 01 | 13 | 12 |
| AB=01 | 14 | 05 | 17 | 16 |
| AB=11 | 012 | 013 | 015 | 014 |
| AB=10 | 18 | 09 | 011 | 110 |
Don't-Care Conditions
Don't-care conditions (×) are input combinations that either cannot occur (e.g., invalid BCD inputs 1010–1111) or whose output doesn't matter. In K-maps, don't-cares can be treated as 0 or 1 — whichever makes the groups larger. They must never remain as isolated 1s; only include them as part of a group.
F(A,B,C,D) = Σm(1,3,7,11,15) + d(0,2,5) — with don't cares
Minterms: Σm(1,3,7,11,15) + don't cares: d(0,2,5)
| AB\CD | CD=00 | CD=01 | CD=11 | CD=10 |
|---|---|---|---|---|
| AB=00 | ×0 | 11 | 13 | ×2 |
| AB=01 | 04 | ×5 | 17 | 06 |
| AB=11 | 012 | 013 | 115 | 014 |
| AB=10 | 08 | 09 | 111 | 010 |
🎯 Exam Focus
POS Minimization from K-Map
Algorithm: POS from K-Map
- Group the 0s (instead of 1s)
- For each group, write a Sum (OR) term
- In each Sum term: variable is uncomplemented if it contributes a 0, complemented if it contributes a 1 (opposite of SOP)
- AND all Sum terms together → this is the POS
💡 Remember
5-Variable K-Map
A 5-variable K-map uses two 4-variable K-maps placed side by side: one for E=0 (minterms 0–15) and one for E=1 (minterms 16–31). Cells in the same position on both maps are adjacent.
Layout Structure
Left map: E=0 (minterms 0–15)
Same 4×4 K-map using variables A,B,C,D
Right map: E=1 (minterms 16–31)
Same layout, minterm index = 16 + corresponding left-map index
A group can span across both maps (E varies) — this eliminates E from the term. Otherwise, treat each map independently and combine with OR.
How to Extract a Simplified Term from a Group
SOP (grouping 1s):
• Variable included if it's the same in all cells
• Include uncomplemented if it's always 1
• Include complemented if it's always 0
• Omit if it changes (both 0 and 1 appear)
POS (grouping 0s):
• Variable included if it's the same in all cells
• Include uncomplemented if it's always 0
• Include complemented if it's always 1
• Omit if it changes
⚠️ Common Mistake
Mistake 2: Forgetting wrap-around adjacency. The top row is adjacent to the bottom row, and the left column is adjacent to the right column. Many students miss corner groups.
Mistake 3: Using the wrong variable assignment rule for POS. In POS, variables are uncomplemented when the variable is 0 in the group — the opposite of SOP.
Quine-McCluskey Method
2.6 Quine-McCluskey Tabular Method
The Quine-McCluskey (QM) method is a systematic tabular approach to Boolean minimization, developed by Willard Van Orman Quine (1952) and Edward J. McCluskey (1956). Unlike K-maps (limited to 4–5 variables visually), QM works for any number of variables and can be computerized.
QM Algorithm — 4 Steps
Group minterms by number of 1s in binary
Write all minterms in binary. Sort them into groups by how many 1s they contain (0 ones, 1 one, 2 ones, etc.).
Combine adjacent groups to find prime implicants
Compare minterms in adjacent groups (groups that differ by 1 count of 1s). If two minterms differ by exactly one bit, combine them — replace that bit position with a dash (−). Repeat until no more combinations possible.
Mark uncombined terms as prime implicants
Any term that was NOT combined with any other term is a prime implicant (PI). These are marked with ★.
Build prime implicant chart, select essential PIs
Create a chart with minterms as columns and PIs as rows. Mark which PIs cover which minterms. A PI is essential if it is the only PI covering a minterm. Select all essential PIs, then cover remaining minterms with fewest additional PIs.
💡 Remember
Worked Example
Problem:
F(A,B,C,D) = Σm(0,1,2,5,6,7,8,9,10,14)
Minimize using Quine-McCluskey method.
Setup: Convert minterms to binary (4-bit)
| Minterm | A | B | C | D | Count of 1s |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 |
| 2 | 0 | 0 | 1 | 0 | 1 |
| 5 | 0 | 1 | 0 | 1 | 2 |
| 6 | 0 | 1 | 1 | 0 | 2 |
| 7 | 0 | 1 | 1 | 1 | 3 |
| 8 | 1 | 0 | 0 | 0 | 1 |
| 9 | 1 | 0 | 0 | 1 | 2 |
| 10 | 1 | 0 | 1 | 0 | 2 |
| 14 | 1 | 1 | 1 | 0 | 3 |
K-Map vs Quine-McCluskey — Comparison
| Feature | K-Map | Quine-McCluskey |
|---|---|---|
| Variables | Up to 5 (visual limit) | Any number (can be automated) |
| Method | Visual grouping on grid | Systematic tabular comparison |
| Speed | Fast for ≤4 variables | Slower by hand, fast on computer |
| Error-prone | Easy to miss wrap-around groups | Mechanical — less chance of error |
| Don't cares | Easily handled visually | Include in initial groups, omit from PI chart |
| Usage | Exam standard for ≤4 variables | Exam for 5+ variables or when K-map isn't available |
🎯 Exam Focus
Practice & Self-Assessment
Active Recall Questions
Answer from memory first — then reveal.
What are the truth tables for NAND and NOR gates? Why are they called universal gates?
State De Morgan's theorems and verify with an example.
What is the difference between SOP and POS forms? Give an example.
What are the K-map grouping rules? How many variables does a group of 4 cover?
Simplify F = AB + AB̄C + A + ABC using Boolean algebra.
Exam-Style Questions
TU BCA exam format — attempt before revealing solution.
Q1. Realize the AND gate using only NAND gates. [4 marks]
4 marksQ2. Find the minimal SOP expression using K-map for F(A,B,C,D) = Σm(0,1,2,5,8,9,10). [6 marks]
6 marksQ3. Convert F = (Ā+B̄)(A+B) to SOP and simplify. [5 marks]
5 marksQ4. Explain the Quine-McCluskey method. Solve F(A,B,C) = Σm(0,1,3,5,7). [8 marks]
8 marksQ5. Prove the absorption law A + AB = A and A(A+B) = A. [4 marks]
4 marksMini-Test
8 MCQs covering all of Unit 2. Submit for instant scoring.
1. The output of a NAND gate is 0 when:
2. De Morgan's theorem states that (A+B)̄ equals:
3. In K-map grouping, a group of 4 cells in a 4-variable map gives a term with:
4. The canonical SOP form uses:
5. Which property allows A+AB to be simplified to A?
6. For F(A,B,C) = Σm(0,2,4,6), the simplified expression is:
7. XOR gate output is HIGH when:
8. In Quine-McCluskey method, two minterms can be combined when they:
How to Remember Unit 2
How to Remember Unit 2
Unit 2 has lots of rules and symbols to memorize. These shortcuts make recall effortless.
Gate Truth Table Patterns
The "Only One" Pattern
The relationship: NAND is inverse of AND. NOR is inverse of OR. So if you know AND/OR, just flip the output column for NAND/NOR.
De Morgan's — The 2-Step Trick
To complement any Boolean expression:
Step 1: Complement each variable
A → Ā, B → B̄, Ā → A (double complement cancels)
Step 2: Swap · and +
AND (·) becomes OR (+), and OR (+) becomes AND (·)
Complement vars, swap AND↔OR
Two-level: complement each factor
De Morgan generalizes to n variables
K-Map Memory Tricks
Gray Code Order: 00-01-11-10
K-maps use Gray code column order: 00, 01, 11, 10 — NOT binary order. Adjacent cells differ by exactly 1 bit.
Group Size Rule: Always 2ⁿ
Valid group sizes: 1, 2, 4, 8, 16. Never 3, 5, 6, 7. If you have 3 cells, you can't group them — you need to overlap two groups of 2.
Wrap-Around: K-Map is a Torus
Think of the K-map as a donut shape. Top edge touches bottom edge. Left edge touches right edge. Corners are all adjacent to each other!
How to Read a Group: 'Same stays, different goes'
For each variable, check if it's always 0, always 1, or varies in the group. If it's always the same value → keep it in the term. If it varies → drop it.
Boolean Laws — Quick-Fire Recall
Always true
A+0=A
A·1=A
A+1=1
A·0=0
Self-interaction
A+A=A
A·A=A
A+Ā=1
A·Ā=0
Absorption
A+AB=A
A(A+B)=A
A+ĀB=A+B
Universal Gates — Memory Anchor
NAND realization: "1-2-3 rule"
1
NOT
1 NAND gate (tie inputs)
2
AND
2 NAND gates (NAND → NOT)
3
OR
3 NAND gates (NOT A → NAND ← NOT B)
NOR follows the same counts but with a different circuit topology (De Morgan's dual).
Quick Revision Summary
Before the Exam: Unit 2 Checklist