HCMC University of Technology and Education
Faculty of Electrical & Electronic Engineering
Lecture:
DIGITAL SYSTEMS
Chapter 2:
Simplifying Logic circuits using theorems
Assoc. Prof. Nguyen Thanh Hai, PhD
1
HCMC University of Technology and Education
Faculty of Electrical & Electronic Engineering
Simplifying Logic circuits using theorems
Example: Simplify the expression y=ABD+ABD
Solution: According to theorem (13), we have y=AB(D+D)
Using theorem (8) and (2), we have y=AB 1
=AB
Review questions: Simplify the following expressions
1) y=AC+ABC 2) y=ABCD+ABCD 3) y=AD+ABD
When we need to design a logic circuit based on user’s
requirements (inputs and output states), an expression is
produced, however, the expression can be complex, so we need
to simplify it using theorems, as described in example.
2
Assoc. Prof. Nguyen Thanh Hai, PhD
HCMC University of Technology and Education
Faculty of Electrical & Electronic Engineering
Simplifying Logic circuits using theorems
Similarity to Boolean theorems, we can use DeMorgan’s theorems
for simplifying expressions
Example: Simplify the expression z=(A+C) (B+D)
Solution: According to theorem (17), we have z=(A+C) (B+D)
Using theorem (16), we have z=(A C) (B D)
Review questions:
1. Use DeMorgan’s theorems to convert the expression z=(A+B) C
to one that has only single-variable inversions.
z=(A+B) C A+B+C=A B+C=A B+C
2. Repeat question 1 for the expression y=RST+Q
y=RST+Q RST Q=(R+S+T) Q (R+S+T) Q
3
Assoc. Prof. Nguyen Thanh Hai, PhD
HCMC University of Technology and Education
Faculty of Electrical & Electronic Engineering
Simplifying Logic circuits using theorems
Review questions:
1. Use DeMorgan’s theorems to convert the expression z=(A+B) C
to one that has only single-variable inversions.
z=(A+B) C A+B+C=A B+C=A B+C
2. Repeat question 1 for the expression y=RST+Q
y=RST+Q RST Q=(R+S+T) Q (R+S+T) Q
3. Implement a circuit having the output expression
using only a NOR gate and an INVERTER. z=ABC
z=ABC=(A+B) C=(A+B)+C (A+B)+C
4. Use DeMorgan’s theorems to convert y=A+B+CD to an
expression containing only single-variable inversions.
y=A+B+CD A B CD A B (C+D)=A B (C+D) 4
Assoc. Prof. Nguyen Thanh Hai, PhD
HCMC University of Technology and Education
Faculty of Electrical & Electronic Engineering
Simplifying Logic circuits using theorems
Review Questions: Simplify the minimum expressions
1. Expression 1: Y=ABC( A D)
2. Expression 2: Y=AC+BC +ABC
3. Expression 3: Y=[D+(A+B)C.E
5
Assoc. Prof. Nguyen Thanh Hai, PhD
HCMC University of Technology and Education
Faculty of Electrical & Electronic Engineering
Simplifying Logic circuits using theorems
Simplify the minimum expression: Y=ABC( A D)
Using Demorgan’s theorem, the Sum converted to the Product,
we have
Y ABC ( A.D)
Multiplying together, and A. A A , we have
Y ABC D
Thus, in this simplified expression, we just use one NAND gate
with 4 inputs and two NOT gates
6
Assoc. Prof. Nguyen Thanh Hai, PhD
HCMC University of Technology and Education
Faculty of Electrical & Electronic Engineering
Simplifying Logic circuits using theorems
Algebraic Simplification
Example
Simplify the logic circuit shown in the following figure
A z=ABC+AB(AC)
z=ABC+AB (AC) A(C+B) 7
Assoc. Prof. Nguyen Thanh Hai, PhD
HCMC University of Technology and Education
Faculty of Electrical & Electronic Engineering
Simplifying Logic circuits using theorems
Algebraic Simplification
Example 4.2
Simplify the expression z=ABC+ABC+ACB (*)
Solution
Method 1: z=A(B+C)
Method 2: add an extra term ABC
And from Eq. (*) z=A(B+C)
8
Assoc. Prof. Nguyen Thanh Hai, PhD
HCMC University of Technology and Education
Faculty of Electrical & Electronic Engineering
Simplifying Logic circuits using theorems
Example:
Design a logic circuit that has three inputs, A, B and C, and whose
output will be HIGH only when a majority of the input is HIGH
Truth table
Input Output
1. Truth table
A B C Y
0 0 0 0 2. AND for each case
0 0 1 0 3. Sum-of-product expression
0 1 0 0 4. Simplify the expression
0 1 1 1 ABC
5. Implement the circuit
1 0 0 0
AB C
1 0 1 1
1 1 0 1 ABC
1 1 1 1 ABC
9
Assoc. Prof. Nguyen Thanh Hai, PhD
HCMC University of Technology and Education
Faculty of Electrical & Electronic Engineering
Simplifying Logic circuits using theorems
Review questions
1. Write one sum-of-products expression for a logic circuit
with four inputs (ABCD) and an output (Y), which Y will be
HIGH, only when the input A is LOW at the same time that
exactly two other inputs are LOW.
2. Implement the expression of question 1 using all four-input
NAND gates. How many are required?
10
Assoc. Prof. Nguyen Thanh Hai, PhD
HCMC University of Technology and Education
Faculty of Electrical & Electronic Engineering
Simplifying Logic circuits using theorems
11
Assoc. Prof. Nguyen Thanh Hai, PhD
HCMC University of Technology and Education
Faculty of Electrical & Electronic Engineering
Simplifying Logic circuits using theorems
Example: There is the following expression:
Y CA (C B).(C A)
a. Draw the circuit of the above expression.
b. Write its truth table.
Y CA (C B)
12
Assoc. Prof. Nguyen Thanh Hai, PhD
HCMC University of Technology and Education
Faculty of Electrical & Electronic Engineering
Simplifying Logic circuits using theorems
Design of Integrated Circuits
Design steps:
1. Based on requirements, one will determine input variables and
the corresponding output functions.
2. Draw the truth table for the relation between inputs and outputs.
3. Write the output function (its output can be SOP or POS)
4. Simplify the function.
5. Draw the simplified circuit. 13
Assoc. Prof. Nguyen Thanh Hai, PhD
HCMC University of Technology and Education
Faculty of Electrical & Electronic Engineering
Simplifying Logic circuits using theorems
Example:
The requirement is that the output of an integrated circuit
is high if and only if its two inputs are high.
a.Design the circuit with 3 inputs and 1 output.
b.Simplify the circuit having the least total gates
c.Re-design the circuit using NAND gates with three
inputs only.
14
Assoc. Prof. Nguyen Thanh Hai, PhD
HCMC University of Technology and Education
Faculty of Electrical & Electronic Engineering
Simplifying Logic circuits using theorems
Given an integrated circuit, in which there are 2 inputs
(A,B), a control input C and one output Y.
a. Design this circuit when the input C is low, data of A
will go through to Y; when the input C is high, data of
B will go through Y.
b. Simplify the circuit having the least total gates
c. Re-design the circuit using NOR gates with two inputs
only.
15
Assoc. Prof. Nguyen Thanh Hai, PhD
HCMC University of Technology and Education
Faculty of Electrical & Electronic Engineering
Simplifying Logic circuits using theorems
Review questions
1. Design a logic circuit with three inputs A, B, C and an
output that goes LOW only when A is HIGH while B and C
are different.
2. Which logic gates produce a 1 output in the disable
state?
3. Which logic gates pass the inverse of the input signal
when they are enabled.
16
Assoc. Prof. Nguyen Thanh Hai, PhD
HCMC University of Technology and Education
Faculty of Electrical & Electronic Engineering
Simplifying Logic circuits using theorems
The End
17
Assoc. Prof. Nguyen Thanh Hai, PhD
