Unit 1: Logic gates and Boolean algebra
Computer Architecture notes · PTU syllabus (UGCC2502)
On this page
Unit summary
Every digital device is built from logic gates — tiny circuits that take binary inputs (0 and 1) and produce a binary output. Boolean algebra is the mathematics that describes these gates and lets us simplify circuits so they use fewer gates, less power and less cost. This unit covers the seven basic gates with symbols and truth tables, NAND and NOR as universal gates, applications of gates, Boolean algebra theorems and simplification, SOP and POS forms, realisation with gates, and Karnaugh maps.
After this unit you can
- Draw the symbol and write the truth table and expression of every basic gate
- Build AND, OR and NOT using only NAND or only NOR gates
- Simplify Boolean expressions using theorems of Boolean algebra
- Write expressions in SOP and POS form and realise them with gates
- Simplify functions of two, three and four variables with Karnaugh maps, including don't-care conditions
PTU syllabus topics
- AND
- OR
- NOT
- NAND
- NOR
- XOR
- XNOR gates
- NAND/NOR as universal gates
- logic gate applications
- Boolean algebra theorems
- simplification of Boolean expressions
- SOP and POS forms
- realization using gates
- K-maps and K-map simplification
Topic 1
Digital signals and logic gates
Values
Continuous range
Only two levels — 0 and 1
Noise
Easily distorted
Noise-immune
Storage
Hard to store exactly
Easy to store and copy
Example
Audio from a microphone
Computer, mobile, calculator
- Logic 0
- Low voltage — about 0 V (false, OFF)
- Logic 1
- High voltage — about 3.3 V or 5 V (true, ON)
- Positive logic
- High voltage represents 1
- Bit
- One binary digit
- Logic gate
- Circuit with one or more inputs and one output whose value follows a logical rule
Truth table lists the output for every combination of the inputs; with n inputs there are 2ⁿ rows.
Example
Reading gates for A = 1, B = 0: AND gives 0 (both inputs must be 1). OR gives 1 (at least one input is 1). XOR gives 1 (the inputs differ). NAND gives 1 (the opposite of AND). NOR gives 0. NOT A gives 0.
Exam tip
NAND and NOR are universal gates: any circuit can be built from either one alone. A NAND gate with both inputs joined works as a NOT gate.
Topic 2
Basic logic gates
AND gate
| A | B | Y = A·B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
- Output is 1 only when all inputs are 1 — like switches in series. Used to enable or mask a signal.
OR gate
| A | B | Y = A + B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
- Output is 1 when at least one input is 1 — like switches in parallel.
NOT gate (inverter)
| A | Y = A′ |
|---|---|
| 0 | 1 |
| 1 | 0 |
- The only gate with a single input; the small circle (bubble) on a symbol means inversion.
NAND gate
| A | B | Y = (A·B)′ |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
NOR gate
| A | B | Y = (A+B)′ |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
XOR (exclusive-OR) gate
| A | B | Y = A ⊕ B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
- Output is 1 when the inputs are different — A ⊕ B = A′B + AB′. Used in adders, parity checkers and comparators.
XNOR (exclusive-NOR) gate
| A | B | Y = (A ⊕ B)′ |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
- Output is 1 when the inputs are the same — A ⊙ B = AB + A′B′; called the equality gate.
AND
Y = A·B
all inputs are 1
OR
Y = A + B
at least one input is 1
NOT
Y = A′
the input is 0
NAND
Y = (A·B)′
not all inputs are 1
NOR
Y = (A + B)′
all inputs are 0
XOR
Y = A ⊕ B
inputs are different
XNOR
Y = (A ⊕ B)′
inputs are the same
Exam tip
For any gate question give three things: the symbol, the Boolean expression and the truth table.
Example
Truth tables: for inputs A = 1, B = 0: AND gives 0, OR gives 1, NAND gives 1, NOR gives 0, XOR gives 1. NAND and NOR are universal gates — any circuit can be built from either alone.
Exam tip
Learn symbols, expressions and truth tables for all seven gates.
Topic 3
NAND and NOR as universal gates
NAND and NOR are called universal gates because any Boolean function — and therefore any digital circuit — can be built using only NAND gates or only NOR gates. This is cheaper in manufacturing because one type of gate can be mass-produced.
Using only NAND gates
Using only NOR gates
NOT
Join both inputs: (A·A)′ = A′
Join both inputs: (A + A)′ = A′
AND
NAND followed by NAND-inverter
NOR the inverted inputs: (A′ + B′)′ = AB
OR
NAND the inverted inputs: (A′B′)′ = A + B
NOR followed by NOR-inverter
Gates needed for AND / OR
2 / 3
3 / 2
Example
By De Morgan's law (A′·B′)′ = A + B, which is why a NAND gate with inverted inputs behaves as an OR gate.
Topic 4
Applications of logic gates
Logic gates are the building blocks of every digital circuit. By combining AND, OR and NOT gates, a designer can build circuits that make decisions, add numbers and store data.
Control and alarms
Burglar alarm (OR of sensors), car seat-belt warning (AND of ignition and unfastened belt)
Data processing
Adders (XOR and AND), comparators (XNOR), parity generators (XOR chain)
Enable and mask
AND gate passes or blocks a signal
Decision circuits
Voting machines, security locks, automatic doors
Memory and counting
Latches and flip-flops are built from NAND and NOR gates
Selection
Multiplexers, decoders, encoders
Example
Design a two-door alarm: the alarm (A) must sound if door 1 (D1) or door 2 (D2) is open and the system is armed (S). The expression is A = (D1 + D2) · S. It needs one OR gate and one AND gate. With S = 1, D1 = 0, D2 = 1, the output is (0 + 1) · 1 = 1, so the alarm sounds.
Topic 5
Boolean algebra theorems
Boolean algebra works on the values 0 and 1 with three operations: AND (·), OR (+) and NOT (′). Every law has a dual obtained by swapping AND with OR and 0 with 1. Laws of Boolean algebra
| Law and its dual | |
|---|---|
| Identity | A + 0 = A ; A · 1 = A |
| Null (domination) | A + 1 = 1 ; A · 0 = 0 |
| Idempotent | A + A = A ; A · A = A |
| Complement | A + A′ = 1 ; A · A′ = 0 |
| Involution | (A′)′ = A |
| Commutative | A + B = B + A ; A · B = B · A |
| Associative | (A + B) + C = A + (B + C) ; (AB)C = A(BC) |
| Distributive | A(B + C) = AB + AC ; A + BC = (A + B)(A + C) |
| Absorption | A + AB = A ; A(A + B) = A |
| De Morgan | (A + B)′ = A′B′ ; (AB)′ = A′ + B′ |
| Redundancy | A + A′B = A + B ; A(A′ + B) = AB |
| Consensus | AB + A′C + BC = AB + A′C |
Truth-table check of De Morgan's theorems
| A | B | (A + B)′ | A′B′ | (AB)′ | A′ + B′ |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 |
The columns agree row by row, which proves De Morgan's theorems: (A + B)′ = A′B′ and (AB)′ = A′ + B′.
- 1
Expand brackets and remove repeated terms
- 2
Group terms with a common factor
- 3
Apply complement (A + A′ = 1) and identity
- 4
Apply absorption and redundancy
- 5
Use De Morgan to remove long bars
- 6
Stop when no law reduces it further
Example
Simplify Y = AB + AB′: Y = A(B + B′) = A·1 = A.
Example
Simplify Y = A + A′B: using redundancy, Y = A + B.
Example
Simplify Y = AB + A′C + BC: by the consensus theorem the term BC is redundant, so Y = AB + A′C.
Example
Simplify Y = (A + B)(A + C): Y = A + BC (distributive law).
Example
Simplify Y = A′B′C + A′BC + AB′C + ABC: take C common — Y = C(A′B′ + A′B + AB′ + AB) = C(1) = C.
Topic 6
SOP and POS forms
- Sum of Products (SOP)
- Product terms ORed together — Y = AB + A′C
- Product of Sums (POS)
- Sum terms ANDed together — Y = (A + B)(A′ + C)
- Minterm (m)
- Product term containing every variable once, true or complemented — equals 1 for exactly one input combination
- Maxterm (M)
- Sum term containing every variable once — equals 0 for exactly one input combination
- Canonical form
- Every term contains all variables
| Row | A | B | C | Minterm | Maxterm |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | m0 = A′B′C′ | M0 = A + B + C |
| 1 | 0 | 0 | 1 | m1 = A′B′C | M1 = A + B + C′ |
| 2 | 0 | 1 | 0 | m2 = A′BC′ | M2 = A + B′ + C |
| 3 | 0 | 1 | 1 | m3 = A′BC | M3 = A + B′ + C′ |
| 4 | 1 | 0 | 0 | m4 = AB′C′ | M4 = A′ + B + C |
| 5 | 1 | 0 | 1 | m5 = AB′C | M5 = A′ + B + C′ |
| 6 | 1 | 1 | 0 | m6 = ABC′ | M6 = A′ + B′ + C |
| 7 | 1 | 1 | 1 | m7 = ABC | M7 = A′ + B′ + C′ |
- From a truth table, SOP takes the rows where Y = 1 (OR of those minterms); POS takes the rows where Y = 0 (AND of those maxterms). Y = Σm(1, 2, 3) is the same function as Y = ΠM(0, 4, 5, 6, 7).
Example
Y = 1 for rows 1, 2 and 3 of a 2-variable table (A′B, AB′, AB): Y = Σm(1, 2, 3) = A′B + AB′ + AB = A + B.
- 1Find the variable missing in a term
- 2Multiply the term by (X + X′)
- 3Expand
- 4Remove duplicate minterms
- 5Write as Σm(…)
Example
F(A, B, C) = A + BC: A = A(B + B′)(C + C′) = ABC + ABC′ + AB′C + AB′C′ and BC = BC(A + A′) = ABC + A′BC, so F = Σm(3, 4, 5, 6, 7).
Realisation using gates
Exam tip
Two-level NAND-NAND realises SOP and NOR-NOR realises POS — only one gate type is needed.
Topic 7
Karnaugh maps
A K-map is a grid representation of a truth table in which adjacent cells differ in only one variable (cell order follows Gray code 00, 01, 11, 10). Grouping adjacent 1s removes the variable that changes and gives the simplest SOP directly.
- 1
Draw the map
2ⁿ cells for n variables, Gray-code labels
- 2
Fill 1s
At the minterms of the function, 0s elsewhere
- 3
Group adjacent 1s
In groups of 1, 2, 4, 8 … as large as possible
- 4
Allow overlaps and wrap-around
Edges and corners are adjacent
- 5
Write one product term per group
Keep the variables that do not change
- 6
OR the terms
Gives the minimal SOP
- Group size
- Powers of two only — 1, 2, 4, 8, 16
- Shape
- Rectangles or squares, not diagonals
- Largest groups
- Take the biggest possible
- Overlap
- Allowed when it makes a group bigger
- Wrap-around
- Left–right and top–bottom edges are adjacent
- Every 1
- Must be in at least one group
- Prime implicant
- A group that cannot be enlarged
- Essential prime implicant
- The only group covering some 1
Two-variable map
Group of two removes one variable: Y = A + B
Three-variable map
A group of four removes two variables
Four-variable map
Don't-care conditions
- A don't-care (X) is an input combination that never occurs (or whose output does not matter); it may be treated as 1 or 0, whichever gives larger groups.
Group
Adjacent 1s
Adjacent 0s
Term
AND of variables that stay constant (complement if 0)
OR of variables that stay constant (complement if 1)
Combine
OR the product terms
AND the sum terms
Result
Minimal SOP
Minimal POS
Method
Apply laws step by step
Graphical grouping
Skill needed
Insight into which law to use
Pattern recognition
Limit
Hard for many variables
Practical up to 4–5 variables
Certainty
Minimal form not guaranteed
Minimal form guaranteed with correct groups
Example
Simplifying with a K-map: for F(A, B) with minterms 2 and 3 (A = 1 in both), grouping the two adjacent 1s gives F = A. Groups must be powers of two (1, 2, 4, 8) and as large as possible.
Exam tip
Group adjacent 1s in rectangles of 1, 2, 4 or 8, including wrap-around.
Key terms
- Logic gate
- A circuit producing a binary output from binary inputs
- Truth table
- Table of outputs for all input combinations
- Universal gate
- A gate (NAND or NOR) from which any other gate can be built
- De Morgan's theorems
- (A + B)′ = A′B′ and (AB)′ = A′ + B′
- Minterm
- A product term containing every variable once
- Maxterm
- A sum term containing every variable once
- SOP and POS
- Sum of products and product of sums forms
- K-map
- A grid used to simplify Boolean expressions by grouping adjacent cells
- Prime implicant
- A K-map group that cannot be made larger
- Don't care
- An input condition whose output may be taken as 0 or 1
Quick revision
- AND = all 1s; OR = any 1; XOR = inputs differ; XNOR = inputs same; NAND and NOR are universal.
- De Morgan: (A + B)′ = A′B′ and (AB)′ = A′ + B′.
- SOP from rows with output 1; POS from rows with output 0.
- NAND-NAND realises SOP; NOR-NOR realises POS.
- K-map: Gray code, groups of 2ⁿ, wrap-around, largest groups, X as needed.
Important exam questions
Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).
Short-answer questions
- Q1.Draw the symbol and truth table of a NAND gate.
- Q2.Why are NAND and NOR called universal gates?
- Q3.State De Morgan's theorems.
- Q4.Write the Boolean expression of an XOR gate.
- Q5.What is a minterm? What is a maxterm?
- Q6.Convert Y = Σm(1, 3) into POS form for two variables.
- Q7.Simplify A + A′B.
- Q8.What is a don't-care condition?
- Q9.State the rules for grouping cells in a K-map.
- Q10.How many cells has a four-variable K-map?
Long-answer questions
- Q1.Explain the basic logic gates with symbols, expressions and truth tables.
- Q2.Realise AND, OR and NOT using only NAND gates and using only NOR gates.
- Q3.State and prove the theorems of Boolean algebra; simplify a given expression.
- Q4.Explain SOP and POS forms and realise a given function with gates.
- Q5.Simplify F(A, B, C, D) = Σm(0, 1, 2, 5, 8, 9, 10) using a K-map and draw the circuit.
- Q6.Simplify a function with don't-care conditions using a K-map.
Stuck on this unit?
Message SBS on WhatsApp for help with Computer Architecture, or to ask about studying BCA at Synetic.
