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 it lets us simplify circuits so they use fewer gates, cost less and run faster.
This unit covers the seven basic gates, why NAND and NOR are called universal gates, the laws of Boolean algebra, SOP and POS forms, and simplification using Karnaugh maps.
After this unit you can
- Draw the symbol and write the truth table of every basic gate
- Build AND, OR and NOT using only NAND or only NOR gates
- Simplify Boolean expressions using the laws of Boolean algebra
- Write expressions in SOP and POS form and simplify them with K-maps
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
Basic: AND, OR, NOT
The building blocks of every circuit
Universal: NAND, NOR
Either one alone can build any circuit
Exclusive: XOR, XNOR
Output depends on whether inputs differ
Simplification
Boolean theorems and K-maps reduce gate count
Topic 1
Logic gates
A logic gate is an electronic circuit with one or more binary inputs and one binary output. The output depends only on the current inputs.
| Gate | Expression | Output is 1 when… |
|---|---|---|
| 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 (it inverts) |
| NAND | Y = (A·B)' | not all inputs are 1 |
| NOR | Y = (A + B)' | all inputs are 0 |
| XOR | Y = A ⊕ B = A'B + AB' | the inputs are different |
| XNOR | Y = (A ⊕ B)' = AB + A'B' | the inputs are the same |
AND
0
1
OR
1
1
NAND
1
0
NOR
0
0
XOR
1
0
XNOR
0
1
Exam tip
For any gate question, give three things: the symbol, the Boolean expression and the truth table.
Topic 2
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 simplifies manufacturing, since one type of gate can be mass-produced.
| To build | Using only NAND | Using only NOR |
|---|---|---|
| NOT | Join both inputs: (A·A)' = A' | Join both inputs: (A + A)' = A' |
| AND | NAND followed by a NAND-inverter | Invert each input, then NOR: (A' + B')' = AB |
| OR | Invert each input, then NAND: (A'·B')' = A + B | NOR followed by a NOR-inverter |
Example
Using De Morgan's law, (A'·B')' = A + B, which is why a NAND gate with inverted inputs behaves as an OR gate.
Topic 3
Boolean algebra theorems
Boolean algebra works on the values 0 and 1 with three operations: AND (·), OR (+) and NOT ('). Its laws let us reduce a long expression to a shorter equivalent one.
- Identity
- A + 0 = A ; A·1 = A
- Null
- A + 1 = 1 ; A·0 = 0
- Idempotent
- A + A = A ; A·A = A
- Complement
- A + A' = 1 ; A·A' = 0
- Absorption
- A + AB = A ; A(A + B) = A
- De Morgan
- (A + B)' = A'B' ; (AB)' = A' + B'
Example
Simplify Y = AB + AB'. Y = A(B + B') = A·1 = A.
Example
Simplify Y = A + A'B. Using A + A'B = (A + A')(A + B) = 1·(A + B), so Y = A + B.
Topic 4
SOP and POS forms
- Sum of Products (SOP): product terms ORed together, e.g. Y = AB + A'C. Each product term in which every variable appears is a minterm.
- Product of Sums (POS): sum terms ANDed together, e.g. Y = (A + B)(A' + C). Each full sum term is a maxterm.
- From a truth table, SOP is written from the rows where Y = 1; POS from the rows where Y = 0.
Example
If Y = 1 for rows 1, 2 and 3 of a 2-variable table (A'B, AB', AB), then Y = Σm(1, 2, 3) = A'B + AB' + AB, which simplifies to A + B.
SOP expressions are realised with an AND-OR circuit (or NAND-NAND); POS with an OR-AND circuit (or NOR-NOR).
Topic 5
Karnaugh maps
A K-map is a grid representation of a truth table in which adjacent cells differ by only one variable (Gray code order: 00, 01, 11, 10). Grouping adjacent 1s removes the variable that changes, giving the simplest SOP.
- 1
Draw the map
2ⁿ cells for n variables
- 2
Fill the 1s
From the minterms
- 3
Group the 1s
In 1, 2, 4, 8 … cells, as large as possible
- 4
Allow overlaps and wrap-around
Edges are adjacent
- 5
Write one term per group
Keep only variables that don't change
- 6
OR the terms together
Example
Y = Σm(0, 1, 2, 3) for two variables fills the whole map, so Y = 1. For three variables, Y = Σm(1, 3, 5, 7) forms a group of four where C = 1 throughout, so Y = C.
Exam tip
Groups must be rectangles of size 1, 2, 4 or 8. Always draw the map with Gray code labels and circle every group.
Key terms
- Logic gate
- A circuit producing a binary output from binary inputs
- Universal gate
- A gate (NAND or NOR) from which any other gate can be built
- Minterm
- A product term containing every variable once
- Maxterm
- A sum term containing every variable once
- K-map
- A grid used to simplify Boolean expressions by grouping adjacent 1s
Quick revision
- AND = all 1s; OR = any 1; XOR = inputs differ; XNOR = inputs same.
- NAND and NOR are universal gates.
- De Morgan: (A + B)' = A'B' and (AB)' = A' + B'.
- SOP from rows with output 1; POS from rows with output 0.
- K-map groups: 1, 2, 4, 8 adjacent cells, edges wrap around.
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.Why are NAND and NOR called universal gates?
- Q2.Write the truth table of an XOR gate.
- Q3.State De Morgan's theorems.
- Q4.Differentiate between SOP and POS forms.
- Q5.What is a minterm? Give an example.
- Q6.Simplify A + AB.
Long-answer questions
- Q1.Explain all the basic logic gates with symbols, expressions and truth tables.
- Q2.Show how AND, OR and NOT gates can be realised using only NAND gates and only NOR gates.
- Q3.State and prove the laws of Boolean algebra used for simplification, with examples.
- Q4.Simplify F(A, B, C, D) = Σm(0, 2, 5, 7, 8, 10, 13, 15) using a K-map and draw the circuit.
Stuck on this unit?
Message SBS on WhatsApp for help with Computer Architecture, or to ask about studying BCA at Synetic.