Unit 1 of 4 · BCA Sem 1

Unit 1: Logic gates and Boolean algebra

Computer Architecture notes · PTU syllabus (UGCC2502)

7 min read7 topics16 exam questions
On this page
  1. Unit summary
  2. Digital signals and logic gates
  3. Basic logic gates
  4. NAND and NOR as universal gates
  5. Applications of logic gates
  6. Boolean algebra theorems
  7. SOP and POS forms
  8. Karnaugh maps
  9. Key terms
  10. Quick revision
  11. Important questions

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
1

Topic 1

Digital signals and logic gates

ComparisonAnalog vs digital signals
Analog
Digital

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

Key termsLogic levels
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.

2

Topic 2

Basic logic gates

AND gate

Logic circuitAND gate (Y = A · B)
ABG1Y
ABY = A·B
000
010
100
111
  • Output is 1 only when all inputs are 1 — like switches in series. Used to enable or mask a signal.

OR gate

Logic circuitOR gate (Y = A + B)
ABG1Y
ABY = A + B
000
011
101
111
  • Output is 1 when at least one input is 1 — like switches in parallel.

NOT gate (inverter)

Logic circuitNOT gate (Y = A′)
AG1Y
AY = A′
01
10
  • The only gate with a single input; the small circle (bubble) on a symbol means inversion.

NAND gate

Logic circuitNAND gate (Y = (A · B)′)
ABG1Y
ABY = (A·B)′
001
011
101
110

NOR gate

Logic circuitNOR gate (Y = (A + B)′)
ABG1Y
ABY = (A+B)′
001
010
100
110

XOR (exclusive-OR) gate

Logic circuitXOR gate (Y = A ⊕ B)
ABG1Y
ABY = A ⊕ B
000
011
101
110
  • Output is 1 when the inputs are different — A ⊕ B = A′B + AB′. Used in adders, parity checkers and comparators.

XNOR (exclusive-NOR) gate

Logic circuitXNOR gate (Y = (A ⊕ B)′)
ABG1Y
ABY = (A ⊕ B)′
001
010
100
111
  • Output is 1 when the inputs are the same — A ⊙ B = AB + A′B′; called the equality gate.
ComparisonSummary of gates
Boolean 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

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.

3

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

Logic circuitNOT from NAND (A·A)′ = A′
AN1A′
Logic circuitAND from NAND
ABN1N2A·B
Logic circuitOR from NAND (A′·B′)′ = A + B
ABN1N2N3A + B
Logic circuitXOR from four NAND gates
ABN1N2N3N4A ⊕ B

Using only NOR gates

Logic circuitNOT from NOR (A + A)′ = A′
AR1A′
Logic circuitOR from NOR
ABR1R2A + B
Logic circuitAND from NOR (A′ + B′)′ = A·B
ABR1R2R3A·B
ComparisonNAND and NOR constructions
Using only NAND
Using only NOR

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.

4

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.

ClassificationApplications of logic gates
Logic gates
  • 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

Logic circuitSeat-belt warning: buzzer ON when ignition is on and belt is not fastened
IgnitionBeltN1G1Buzzer
Logic circuitEven-parity bit generator for three data bits
D1D2D3X1X2Parity
Logic circuitEquality (comparator) of two bits
ABG1A = B

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.

5

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
IdentityA + 0 = A ; A · 1 = A
Null (domination)A + 1 = 1 ; A · 0 = 0
IdempotentA + A = A ; A · A = A
ComplementA + A′ = 1 ; A · A′ = 0
Involution(A′)′ = A
CommutativeA + B = B + A ; A · B = B · A
Associative(A + B) + C = A + (B + C) ; (AB)C = A(BC)
DistributiveA(B + C) = AB + AC ; A + BC = (A + B)(A + C)
AbsorptionA + AB = A ; A(A + B) = A
De Morgan(A + B)′ = A′B′ ; (AB)′ = A′ + B′
RedundancyA + A′B = A + B ; A(A′ + B) = AB
ConsensusAB + A′C + BC = AB + A′C

Truth-table check of De Morgan's theorems

AB(A + B)′A′B′(AB)′A′ + B′
001111
010011
100011
110000

The columns agree row by row, which proves De Morgan's theorems: (A + B)′ = A′B′ and (AB)′ = A′ + B′.

ProcessSimplifying with Boolean algebra
  1. 1

    Expand brackets and remove repeated terms

  2. 2

    Group terms with a common factor

  3. 3

    Apply complement (A + A′ = 1) and identity

  4. 4

    Apply absorption and redundancy

  5. 5

    Use De Morgan to remove long bars

  6. 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.

6

Topic 6

SOP and POS forms

Key termsStandard 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
RowABCMintermMaxterm
0000m0 = A′B′C′M0 = A + B + C
1001m1 = A′B′CM1 = A + B + C′
2010m2 = A′BC′M2 = A + B′ + C
3011m3 = A′BCM3 = A + B′ + C′
4100m4 = AB′C′M4 = A′ + B + C
5101m5 = AB′CM5 = A′ + B + C′
6110m6 = ABC′M6 = A′ + B′ + C
7111m7 = ABCM7 = 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.

ProcessConverting a non-canonical SOP to canonical form
  1. 1Find the variable missing in a term
  2. 2Multiply the term by (X + X′)
  3. 3Expand
  4. 4Remove duplicate minterms
  5. 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

Logic circuitSOP realisation of Y = AB + A′C (AND-OR)
ABCN1A1A2O1Y
Logic circuitNAND-NAND realisation of Y = AB + A′C
ABCN1G1G2G3Y
Logic circuitPOS realisation of Y = (A + B)(A′ + C) (OR-AND)
ABCN1O1O2A1Y

Exam tip

Two-level NAND-NAND realises SOP and NOR-NOR realises POS — only one gate type is needed.

7

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.

ProcessSimplifying with a K-map
  1. 1

    Draw the map

    2ⁿ cells for n variables, Gray-code labels

  2. 2

    Fill 1s

    At the minterms of the function, 0s elsewhere

  3. 3

    Group adjacent 1s

    In groups of 1, 2, 4, 8 … as large as possible

  4. 4

    Allow overlaps and wrap-around

    Edges and corners are adjacent

  5. 5

    Write one product term per group

    Keep the variables that do not change

  6. 6

    OR the terms

    Gives the minimal SOP

Key termsRules for grouping
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

Karnaugh mapY = Σm(1, 2, 3) = A + B
AB010100112131A (m2, m3)B (m1, m3)

Group of two removes one variable: Y = A + B

Three-variable map

Karnaugh mapY = Σm(1, 3, 5, 7) → Y = C
ABC00011110010011312040517160C (group of 4: m1, m3, m5, m7)

A group of four removes two variables

Karnaugh mapF = Σm(0, 1, 4, 5, 6) → F = B′ + AC′
ABC00011110010111302041517061B′ (m0, m1, m4, m5)AC′ (m4, m6)
Karnaugh mapWrap-around: F = Σm(0, 2, 4, 6) → F = C′
ABC00011110010110302141507061C′ (columns 00 and 10 are adjacent)

Four-variable map

Karnaugh mapF = Σm(0, 2, 8, 10) → F = B′D′ (four corners)
ABCD000111100001111001103021405070601201301501408190110101B′D′ (corners)
Karnaugh mapF = Σm(0, 2, 5, 7, 8, 10, 13, 15) → F = B′D′ + BD
ABCD000111100001111001103021405171601201311511408190110101B′D′ (corners)BD (middle block)
Karnaugh mapF = Σm(0, 1, 2, 5, 8, 9, 10) → F = B′D′ + B′C′ + A′C′D
ABCD000111100001111001113021405170601201301501408191110101B′D′ (corners)B′C′ (m0, m1, m8, m9)A′C′D (m1, m5)

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.
Karnaugh mapF = Σm(1, 3, 7, 11, 15) + d(0, 2, 5) → F = A′B′ + CD
ABCD00011110000111100X11312X405X71601201301511408090111100A′B′ (m0, m1, m2, m3 — uses X at 0, 2)CD (m3, m7, m11, m15)
ComparisonK-map for SOP vs POS
SOP (group 1s)
POS (group 0s)

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

ComparisonAlgebra vs K-map simplification
Boolean algebra
Karnaugh map

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

  1. Q1.Draw the symbol and truth table of a NAND gate.
  2. Q2.Why are NAND and NOR called universal gates?
  3. Q3.State De Morgan's theorems.
  4. Q4.Write the Boolean expression of an XOR gate.
  5. Q5.What is a minterm? What is a maxterm?
  6. Q6.Convert Y = Σm(1, 3) into POS form for two variables.
  7. Q7.Simplify A + A′B.
  8. Q8.What is a don't-care condition?
  9. Q9.State the rules for grouping cells in a K-map.
  10. Q10.How many cells has a four-variable K-map?

Long-answer questions

  1. Q1.Explain the basic logic gates with symbols, expressions and truth tables.
  2. Q2.Realise AND, OR and NOT using only NAND gates and using only NOR gates.
  3. Q3.State and prove the theorems of Boolean algebra; simplify a given expression.
  4. Q4.Explain SOP and POS forms and realise a given function with gates.
  5. Q5.Simplify F(A, B, C, D) = Σm(0, 1, 2, 5, 8, 9, 10) using a K-map and draw the circuit.
  6. 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.

WhatsApp us