Level-3, Term-1 (‘21 Batch)

EEE-351: Digital Electronics

Analysis & Synthesis of Digital Logic Circuits
Dr. Sampad Ghosh
Professor
Department of Electrical and Electronic Engineering
Faculty of Electrical and Computer Engineering
Chittagong University of Engineering and Technology (CUET)

April 20, 2025

CHITTAGONG UNIVERSITY OF ENGINEERING & TECHNOLOGY (CUET)
KYUSHU UNIVERSITY
 Topics Reference
Analysis & synthesis of digital logic circuits
Basic logic functions
OR operation with OR gates, AND operation with
AND gates, NOR operation with NOR gates,
Describing logic circuits algebraically, Evaluating
logic circuit outputs, Implementing circuits from
Tocci
Boolean expressions, NOR gates & NAND gates

Boolean Algebra
Boolean theorems, Demorgan’s Theorems,
Universality of NAND gates & NOR gates

CHITTAGONG UNIVERSITY OF ENGINEERING & TECHNOLOGY (CUET) 2

NOR Gates and NAND Gates
 So far, discussed basic AND, OR, and NOT operations.
o Simplifying the writing of Boolean expressions
 Output of NAND and NOR gates may be found by determining the
output of an AND or OR gate, and inverting it.
o The truth tables for NOR and NAND gates show the complement of
truth tables for OR and AND gates.

CHITTAGONG UNIVERSITY OF ENGINEERING & TECHNOLOGY (CUET) 3

NOR Gates
 The NOR gate is an inverted OR gate.
o An inversion “bubble” is placed at the output of the OR gate, making the
Boolean output expression x = 𝐀 + 𝐁 = (𝐀 + 𝐁)′

CHITTAGONG UNIVERSITY OF ENGINEERING & TECHNOLOGY (CUET) 4

NAND Gates
 The NAND gate is an inverted AND gate.
o An inversion “bubble” is placed at the output of the AND gate, making
the Boolean output expression x = 𝐀. 𝐁 = (𝐀. 𝐁)′

CHITTAGONG UNIVERSITY OF ENGINEERING & TECHNOLOGY (CUET) 5

NOR Gates and NAND Gates …

Output waveform of a NOR gate Output waveform of a NAND gate

CHITTAGONG UNIVERSITY OF ENGINEERING & TECHNOLOGY (CUET) 6

NOR Gates and NAND Gates …

 Example: Logic circuit with the expression x = 𝑨𝑩. (𝑪 + 𝑫) using only

NOR and NAND gates.

CHITTAGONG UNIVERSITY OF ENGINEERING & TECHNOLOGY (CUET) 7

Exclusive-OR (XOR) Gates
 An encircled plus sign () is used to show the Exclusive–OR
operation.

AB

AB’+A’B

CHITTAGONG UNIVERSITY OF ENGINEERING & TECHNOLOGY (CUET) 8

Exclusive-NOR (XNOR) Gates
 The Exclusive–NOR gate is circuit does the opposite to the XOR
gate. The symbol is an EX-NOR gate with a small circle on the
output.
o The small circle represents inversion.

(A  B)’=(A Θ B)

AB+A’B’

CHITTAGONG UNIVERSITY OF ENGINEERING & TECHNOLOGY (CUET) 9

Boolean Theorems
 The theorems or laws helps to simplify logic expressions and logic circuits.
 Consider single variable (x is logic variable either 0 or 1.)

(3) x . x = x
(1) x . 0 = 0
Prove Theorem (3):
Theorem-1 states that if any variable
If x = 0, then 0 . 0 = 0
is ANDed with 0, the result must be 0.
If x = 1, then 1 . 1 = 1

(2) x . 1 = x
Theorem-2 is also obvious by
comparison with ordinary multiplication. (4) x . x’ = 0

CHITTAGONG UNIVERSITY OF ENGINEERING & TECHNOLOGY (CUET) 10

Boolean Theorems …

(5) x + 0 = x (7) x + x = x
Theorem-5 is straightforward, as 0 added to Theorem (7) can be proved by
anything does not affect value, either in regular checking for both values of x:
addition or in OR addition. 0+0= 0 and 1+1= 1.

(6) x + 1 = 1 (8) x + x’ = 1
Theorem-6 states that if any variable is
Theorem (8) can be proved similarly.
ORed with 1, the is always 1.
Check values: 0+1= 1 and 1+1= 1

CHITTAGONG UNIVERSITY OF ENGINEERING & TECHNOLOGY (CUET) 11

Boolean Theorems …
 Multivariable Theorems (14) x + xy = x
(15a) x + x’y = x + y
Commutative laws
(15b) x’ + xy = x’ + y
(9) x + y = y + x
(10) x . y = y . x Theorems (14) and (15) do not have
counterparts in ordinary algebra. Each
Associative laws can be proved by trying all possible

(11) x + (y + z) = (x + y) + z = x + y + z cases for x and y.

(12) x(yz) = (xy)z = xyz

Proof of Theorem (14)

Distributive law
(13a) x(y + z) = xy + xz
(13b) (w + x)(y + z) = wy + wz + xy + xz

CHITTAGONG UNIVERSITY OF ENGINEERING & TECHNOLOGY (CUET) 12

Boolean Theorems …
 Example: Simplify x = ACD + A’BCD

Solutions:

x = CD (A + A’B)
= CD (A + B) [(15a) x + x’y = x + y]

= ACD + BCD

Why we need simplification?

CHITTAGONG UNIVERSITY OF ENGINEERING & TECHNOLOGY (CUET) 13

Algebraic Simplification
 Justification for simplifying Boolean expressions:
 Reduces the cost associated with realizing the expression using logic
gates.
 Reduces the area (i.e. silicon) required to fabricate the switching
function.
 Reduces the power consumption of the circuit.

 In general, there is no easy way to determine when a Boolean expression

has been simplified to a minimum number of terms or minimum number of
literals.
o No unique solution

CHITTAGONG UNIVERSITY OF ENGINEERING & TECHNOLOGY (CUET) 14

DeMorgan’s Theorems
 DeMorgan’s theorems are extremely useful in simplifying expressions
in which a product or sum of variables is inverted.

(16) (𝐱 + 𝐲) = 𝐱ഥ . 𝐲ഥ
Theorem (16) says inverting the OR sum of two variables is the same as inverting each
variable individually, then ANDing the inverted variables.

(17) (𝐱 . 𝐲) = 𝐱ഥ + 𝐲ഥ
Theorem (17) says inverting the AND product of two variables is the same as inverting each
variable individually and then ORing them.

 Each of DeMorgan’s theorems can readily be proven by checking for all

possible combinations of x and y.

CHITTAGONG UNIVERSITY OF ENGINEERING & TECHNOLOGY (CUET) 15

Proving DeMorgan’s Theorems

(17) (𝐱 . 𝐲) = 𝐱ഥ + 𝐲ഥ (16) (𝐱 + 𝐲) = 𝐱ഥ . 𝐲ഥ

Try it yourself

CHITTAGONG UNIVERSITY OF ENGINEERING & TECHNOLOGY (CUET) 16

DeMorgan’s Theorems …
 Equivalent circuits implied by Theorem (16).

(16) (𝐱 + 𝐲) = 𝐱ഥ . 𝐲ഥ

The alternative symbol for the NOR function

CHITTAGONG UNIVERSITY OF ENGINEERING & TECHNOLOGY (CUET) 17

DeMorgan’s Theorems …
 Equivalent circuits implied by Theorem (17).
(17) (𝐱 . 𝐲) = 𝐱ഥ + 𝐲ഥ

The alternative symbol for the NAND function

CHITTAGONG UNIVERSITY OF ENGINEERING & TECHNOLOGY (CUET) 18

Example-1
 Simplify the functions T1 and T2 to a minimum number of literals.

A B C T1 T2 T1 = A’B’C’+ A’B’C+ A’BC’ T2 = (T1)’

0 0 0 1 0 = A’B’(C’+C)+ A’BC’ = (A’B’+A’C’)’ (X+Y)’=X’Y’

0 0 1 1 0 = A’B’+A’BC’ X+X’=1 = (A’B’)’(A’C’)’ (XY)’=X’+Y’
0 1 0 1 0
= A’(B’+BC’) = [(A’)’+(B’)’][(A’)’+(C’)’]
0 1 1 0 1
1 0 0 0 1 = A’(B’+B)(B’+C’) X+YZ=(X+Y)(X+Z) = [A+B][A+C]
1 0 1 0 1
= A’(B’+C’)= A’B’+A’C’ = A+BC X+YZ=(X+Y)(X+Z)
1 1 0 0 1
1 1 1 0 1

T2 = A’BC+AB’C’+AB’C+ABC’+ABC Can you draw the circuit diagram?

Try to simplify

CHITTAGONG UNIVERSITY OF ENGINEERING & TECHNOLOGY (CUET) 19

Example-1 ….
 circuit diagram.
T1 = A’B’+A’C’ T2 = A+BC

T1
B

T2

CHITTAGONG UNIVERSITY OF ENGINEERING & TECHNOLOGY (CUET) 20

Example-2
 Given the following Boolean function:
02 Marks
T1 = xy’z + x’y’z + w’xy + wx’y + wxy
(a) Obtain the truth table of the function.
(b) Draw the logic diagram using the original Boolean expression.
(c) Simplify the function to a minimum number of literals using Boolean algebra.
(d) Obtain the truth table of the function from the simplified expression and show
that it is the same as the one in part (a).
(e) Draw the logic diagram from the simplified expression and compare the total
number of gates with the diagram of part (b).

CHITTAGONG UNIVERSITY OF ENGINEERING & TECHNOLOGY (CUET) 21

Example-2: Solution
T1 = xy’z + x’y’z + w’xy + wx’y + wxy (a) w x y z T1
= xy’z(w+w’)+ x’y’z(w+w’)+ w’xy(z+z’)+ wx’y(z+z’)+ wxy(z+z’) X+X’=1 0 0 0 0 0
= wxy’z+w’xy’z + wx’y’z+w’x’y’z + w’xyz+w’xyz’ + wx’yz+ wx’yz’ + 0 0 0 1 1

wxyz+ wxyz’ 0 0 1 0 0
0 0 1 1 0
w
0 1 0 0 0
0 1 0 1 1
0 1 1 0 1
x
0 1 1 1 1
T1
1 0 0 0 0
1 0 0 1 1
y 1 0 1 0 1
1 0 1 1 1
1 1 0 0 0

z 1 1 0 1 1
1 1 1 0 1

(b) 1 1 1 1 1

CHITTAGONG UNIVERSITY OF ENGINEERING & TECHNOLOGY (CUET) 22

Example-2 : Solution …
(c) T1 = xy’z + x’y’z + w’xy + wx’y + wxy (d) w x y z T1s

= y’z (x+x’) + xy (w’+w) + wx’y X+X’=1 0 0 0 0 0

= y’z + xy + wx’y 0 0 0 1 1

0 0 1 0 0
= y’z + y (x + wx’)
0 0 1 1 0
=y’z + y (x+w)(x+x’) X+YZ=(X+Y)(X+Z)
0 1 0 0 0
= y’z + y (w + x) = y’z + wy + xy 0 1 0 1 1

w 0 1 1 0 1
0 1 1 1 1
T1 1 0 0 0 0
x 1 0 0 1 1
1 0 1 0 1
1 0 1 1 1
y Before simplification, total number of
1 1 0 0 0
gates = 11
1 1 0 1 1
z After simplification, total number of 1 1 1 0 1
(e) gates = 05 1 1 1 1 1

CHITTAGONG UNIVERSITY OF ENGINEERING & TECHNOLOGY (CUET) 23

Summary
 Evaluating logic circuit outputs and truth table construction
 Boolean expression and Algebra
 Implementation of circuits from Boolean Expressions
 AND, OR, NOT, NOR, NAND, Ex-OR and Ex-NOR gates
 Boolean expression simplification by Boolean Algebra
 Circuits implementation

CHITTAGONG UNIVERSITY OF ENGINEERING & TECHNOLOGY (CUET) 24

 CT-1
27/04/2025 (Sunday) @8:30am
Syllabus: Class-3,4,5

CHITTAGONG UNIVERSITY OF ENGINEERING & TECHNOLOGY (CUET) 25