DSN5101
Computer Architecture and
Organization
Section A (Digital Logic Design)
Lecture 1
Introduction to Digital Logic and
Boolean Algebra
TOPIC COVERAGE IN THE
LECTURE (1(A))
□ Introductory Digital Concepts
■ Analog Vs Digital Quantities
■ Analog Vs Digital Electronic Systems – Examples
■ Advantages and Limitations of Digital Systems
■ Logic levels – Positive and Negative Logic
2
TOPIC COVERAGE IN THE
LECTURE (1(B))
□ Logic Gates - NOT, AND, OR, NAND, NOR, XOR,
XNOR
■ Standard Logic Symbols
■ Truth Tables
■ Logic expression
■ Logical operation
■ Timing Diagram
■ Application examples
□ IC Gates
■ DIP, Pin configurations
3
TOPIC COVERAGE IN THE
LECTURE (1(C))
□ Boolean Algebra
■ Laws and Rules of Boolean Algebra
■ Demorgan’s theorems
□ Boolean Analysis of Logic circuits
■ Evaluation of logic circuit output
■ Constructing a truth table for a logic circuit
□ Simplification using Boolean Algebra
4
Introduction to Digital Logic
and Boolean Algebra
– Part 1 of 3
Introductory Digital Concepts
- Digital Vs Analog Systems
Analog Quantities
An analog quantity is one having continuous values.
Examples: Temperature, Pressure, Level, Position, Volume, Voltage, Current
Graph of an Analog Quantity – Temperature Vs Time
6
Digital Quantities
A digital quantity is one having a discrete set of values.
Examples: Digital Watch reading – (Time of the day in minutes/seconds)
Number of coins
Human population of a city (it changes with the time)
People travel from/to the city
Sampled-value representation of Temperature Vs Time
7
Analog Electronic System
– An Example
□ Analog system
■ A combination of devices that
manipulate values represented
in an analog form
- Here the variable is
allowed to take any value
in a specified range.
■ An example: A basic audio
public address system.
Sound through a microphone
causes voltage changes in
proportion to the amplitude of
the sound waves.
8
Digital System
- Examples
□ Digital system
■ A combination of devices that
manipulate values
represented in digital form.
Examples:
■ Digital Computer
■ Handheld Calculator
■ Digital Watch
■ Telephone system
Analog Watch and Digital Watch
■ Digital audio and video
equipment
9
Advantages of Digital over Analog
□ Data Processing and Transmission – more efficient and reliable
□ Data Storage – more compact storage and greater accuracy and
clarity in reproduction
□ Ease of design – In switching circuits, only the range in which
the voltage or current fall is important not the exact values
□ Accuracy and precision are easier to maintain – In analog
systems, voltage and current signals are affected by
temperature, humidity but in digital systems, info. does not
degrade
□ Easy Programmable operation
□ Less affected by noise - since exact value is not important in
digital systems
□ Ease of fabrication on IC chips – analog devices cannot be
economically integrated.
10
Limitations of Digital Techniques
■ The real world is analog
■ The analog nature of the world requires a
time consuming conversion process:
■ Convert analog inputs to digital
■ Process (operate on) the digital information
■ Convert the digital output back to analog
11
Digital and Analog electronics together
- Examples
Example 1: The audio CD is a typical
hybrid (combination) system.
•Analog sound is converted into
analog voltage.
• Analog voltage is changed into
digital through an ADC in the
recorder.
• Digital information is stored on
the CD .
• At playback the digital
information is changed into
analog by a DAC in the CD
player.
• The analog voltage is amplified
and used to drive a speaker
that produces the original
analog sound.
12
Digital and Analog electronics together
-Examples
Example 2: Temperature Control System
13
Introduction to Digital Logic
and Boolean Algebra
– Part 2 of 3
Logic Gates
- NOT, AND, OR, NAND, NOR, XOR, XNOR
TOPIC COVERAGE
- PART 2 of 3
□ Logic Gates - NOT, AND, OR, NAND, NOR, XOR,
XNOR
■ Standard Logic Symbols
■ Truth Tables
■ Logic expression
■ Logical operation
■ Timing Diagram
■ Application examples
□ IC Gates
■ DIP, Pin configurations
15
Logic Gates - Introduction
□ Logic gates are the building blocks of computers.
□ Most of the functions in a computer are implemented
with logic gates used on a very large scale.
□ For example, a Microprocessor, which is the main part of
the computer, is made of up of hundreds of thousands of
logic gates
16
The Inverter (NOT gate)
17
The Inverter (NOT gate)
- Symbol, Truth Table, Boolean Expression,
Logical Operation, Timing Diagram
Basic Logical Function:
NOT gate can have only one input and
performs logical inversion or
complementation.
Logical operation:
The output of an inverter is always
the complement (opposite) of the
input.
Truth table Boolean expression
0 = LOW Pulsed waveforms/
1 = HIGH
Timing Diagram
18
The Inverter (NOT gate)
- Problem
The output of the INVERTER is connected to the input of a
second INVERTER. Determine the output of the second
INVERTER for the input A
19
The Inverter
- An example application
A group of inverters can be used to form the 1’s complement of
a binary number
Binary number
1 0 0 0 1 1 0 1
0 1 1 1 0 0 1 0
1’s complement
20
The AND Gate
21
The AND Gate
- Symbol, Truth Table, Boolean Expression,
Logical operation, Timing Diagram
Basic Logical Function:
An AND gate can have two or more
inputs and performs logical
multiplication.
Logical Operation:
The output of an AND gate is HIGH
only when all inputs are HIGH.
Boolean expression
Truth table
(2-input AND gate)
0 = LOW Timing Diagram
1 = HIGH
22
The AND gate (3-inputs)
3-Input AND Gate
23
The AND gate (4-inputs)
□ The total number of possible
combinations of binary inputs to
a gate is determined by the
following formula:
N = 2n
where N is the number of
possible input combinations and
n is the number of input
variables.
For two input variables:
N = 22 = 4 combinations
For three input variables:
N = 23 = 8 combinations
4-Input AND Gate For four input variables:
N = 24 = 16 combinations
24
The AND gate
- Problem 1
If two waveforms, A and B are applied to AND gate inputs as shown in
figure below, what is the resulting output waveform?
25
The AND gate
- Problem 2
If two waveforms, A and B are applied to AND gate inputs as shown in
figure below, what is the resulting output waveform?
26
The AND gate
- An example application
□ A common application of the AND gate is to enable (to allow) the passage of a
signal (pulse waveform) from one point to another at certain times and to inhibit
(prevent) the passage at other times.
□ Example : A seat belt Alarm system
An AND gate is used to detect when the ignition switch is ON and the seat belt is unbuckled.
If the ignition switch is on, a HIGH is produced on input A of the AND gate.
If the seat belt is not properly buckled, a HIGH is produced on input B.
Also, when the ignition switch is turned on, a timer is started that produces a HIGH on input C for 30s.
If all three conditions exist- that is, if the ignition is on and the seat belt is unbuckled and timer is running-
the output of AND gate is HIGH and audible alarm is energized to remind the driver.
27
The AND gate
- An example application
The AND operation is used in computer programming as a
selective mask.
If you want to retain certain bits of a binary number but
reset the other bits to 0, you could set a mask with 1’s in
the position of the retained bits.
Example: If the binary number 10100011 is ANDed with the
mask 00001111, what is the result?
Ans: 00000011
28
The OR Gate
29
The OR Gate
- Symbol, Truth Table, Boolean Expression,
Logical operation, Timing Diagram
Basic Logical Function:
The OR gate can have two or more
inputs and performs logical addition.
Logical Operation:
The output of an OR gate is LOW only
when all inputs are LOW.
Boolean expression
Truth table
(2-input OR gate)
0 = LOW
1 = HIGH Timing Diagram
30
The OR gate (3-inputs)
Note:
Boolean addition differs
from binary addition in
the cases where two or
more 1s are added.
There is no carry in
Boolean addition.
3-Input OR Gate
31
The OR gate (4-inputs)
4-Input OR Gate
32
The OR gate
- Problem 1
If two waveforms, A and B are applied to OR gate inputs as shown in
figure below, what is the resulting output waveform?
33
The OR gate
- Problem 2
If two waveforms, A and B are applied to OR gate inputs as shown in
figure below, what is the resulting output waveform?
34
The OR gate
- An example application
The OR operation can be used in computer programming to
set certain bits of a binary number to 1.
Example: What will be the result if you OR an ASCII upper case
letter with the binary number 0100000?
Ans: The resulting letter will be ASCII lower case.
35
The NAND Gate
36
The NAND Gate
- Symbol, Truth Table, Boolean Expression,
Logical operation, Timing Diagram
Basic Logical Function:
The NAND gate can have two or more
inputs and performs inverse of logical
multiplication.
Logical Operation:
The output of a NAND gate is LOW
only when all inputs are HIGH
Boolean expression
Truth table
(2-input NAND Gate)
0 = LOW
1 = HIGH
Timing Diagram
37
The NAND gate (3-inputs)
3-Input NAND Gate
38
The NAND gate (4-inputs)
4-Input NAND Gate
39
The NAND gate
- Problem
If two waveforms, A and B are applied to NAND gate inputs as shown in
figure below, what is the resulting output waveform?
40
The NAND Gate
- Negative-OR Equivalent operation
□ A NAND gate produces HIGH output, when one or more
inputs are LOW.
□ From this view point, a NAND gate can be used for an
OR operation that requires one or more LOW inputs to
produce a HIGH output. This aspect of NAND operation is
referred to as negative-OR
Standard symbols representing the two equivalent operations of a NAND gate
41
The NOR Gate
42
The NOR Gate
- Symbol, Truth Table, Boolean Expression,
Logical operation, Timing Diagram
Basic Logical Function:
The NOR gate can have two or more
inputs and performs inverse of logical
addition.
Logical Operation:
The output of a NOR gate is HIGH only
when all inputs are LOW
Boolean expression
Truth table
(2-input NOR Gate)
0 = LOW
1 = HIGH
Timing Diagram
43
The NOR gate (3-inputs)
3-Input NOR Gate
44
The NOR gate (4-inputs)
4-Input NOR Gate
45
The NOR gate
- Problem
If two waveforms, A and B are applied to NOR gate inputs as shown in
figure below, what is the resulting output waveform?
46
The NOR Gate
- Negative-AND Equivalent operation
□ A NOR gate produces HIGH output, when all inputs are
LOW.
□ From this view point, a NOR gate can be used for an
AND operation that requires all LOW inputs to produce a
HIGH output. This aspect of NOR operation is referred to
as negative-AND
Standard symbols representing the two equivalent operations of a NOR gate
47
The XOR Gate
48
The XOR (Exclusive-OR) Gate
- Symbol, Truth Table, Boolean Expression,
Logical operation, Timing Diagram
Basic Logical Function:
The XOR gate can have two or more
inputs and performs ODD function
(output is equal to 1 if the input
variables have an odd number of 1’s).
Logical Operation:
The output of XOR gate is HIGH
whenever the two inputs are different
(2-input XOR gate)
Boolean expression
Truth table
(2-input XOR gate)
0 = LOW
1 = HIGH
Timing Diagram
49
The XOR gate (2-inputs)
- using AND-OR-NOT Gates
50
The XOR gate (3-inputs)
51
The XOR gate
- Problem
If two waveforms, A and B are applied to XOR gate inputs as shown in
figure below, what is the resulting output waveform?
A
B
X
If the A and B waveforms are both inverted for the above waveforms,
how is the output affected?
Ans: There is no change in the output.
52
The XNOR Gate
53
The XNOR (Exclusive-NOR) Gate
- Symbol, Truth Table, Boolean Expression,
Logical operation, Timing Diagram
Basic Logical Function:
The XNOR gate can have two or more
inputs and performs EVEN function
(output is equal to 1 if the input
variables have an even number of 1’s).
Logical Operation:
The output of XNOR gate is HIGH
whenever the two inputs are identical
(2-input XNOR gate - can be called as
equivalence gate)
Boolean expression
Truth table
(2-input XNOR Gate)
0 = LOW
1 = HIGH Timing Diagram
54
The XNOR gate (3-inputs)
A B C X
0 0 0 1
0 0 1 0
0 1 0 0
3-input even function 0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 0
Truth Table
55
The XNOR gate
- Problem
If two waveforms, A and B are applied to XNOR gate inputs as
shown in figure below, what is the resulting output waveform?
A
B
X
If the A waveform is inverted but B remains the same, how is the
output affected?
Ans: The output will be inverted
56
Basic Logic Gates
(Summary)
57
Integrated Circuit (IC) Packages
DIP and surface mount chips
Pin 1
Dual in-line package Small outline IC (SOIC)
Dual-In-line Package Chip
Cutaway view of a DIP (Dual-In-line Package) chip:
The TTL series, available as DIPs, are popular for laboratory
experiments with logic.
Pin configuration diagrams
- Common fixed-function IC gates
60
Introduction to Digital Logic
and Boolean Algebra
– Part 3 of 3
Boolean Algebra
- Laws, Rules and Theorems
- Analysis of Logic Circuits
- Simplification
TOPIC COVERAGE
- PART 3 of 3
□ Boolean Algebra
■ Laws and Rules of Boolean Algebra
■ Demorgan’s theorems
□ Boolean Analysis of Logic circuits
■ Evaluation of logic circuit output
■ Constructing a truth table for a logic circuit
□ Simplification using Boolean Algebra
62
BOOLEAN ALGEBRA
– Rules, Laws, and Theorems
63
Boolean Algebra
□ Boolean algebra is the mathematics of digital systems
developed by George Boole in 1854.
□ A basic knowledge of Boolean algebra is necessary to
the study and analysis of logic circuits.
□ Variable, complement and literal are terms used in
Boolean algebra.
■ A variable is a symbol used to represent logical quantity.
Any single variable can have a 1 or a 0 value.
■ The complement or inverse of a variable is indicated by
bar or prime symbol
■ A literal is a variable or its complement.
64
Laws of Boolean Algebra
□ Commutative Law
□ Associative Law
□ Distributive Law
65
Laws of Boolean Algebra
□ Commutative Law of Addition: A+B=B+A
□ Commutative Law of Multiplication: A . B = B .A
66
Laws of Boolean Algebra
□ Associative Law of Addition: A + (B + C) = (A + B) + C
□ Associative Law of Multiplication: A . (B . C) = (A . B) . C
67
Laws of Boolean Algebra
□ Distributive Law:
A(B + C) = AB + AC
68
Rules of Boolean Algebra
69
Rules of Boolean Algebra
□ Rule 1
□ Rule 2
OR Truth Table
70
Rules of Boolean Algebra
□ Rule 3
□ Rule 4
AND Truth
Table
71
Rules of Boolean Algebra
□ Rule 5
□ Rule 6
OR Truth Table
72
Rules of Boolean Algebra
□ Rule 7
□ Rule 8
AND Truth
Table
73
Rules of Boolean Algebra
□ Rule 9
74
Rules of Boolean Algebra
□ Rule 10: A + AB = A
AND Truth OR Truth Table
Table
75
Rules of Boolean Algebra
□ Rule 11:
AND Truth OR Truth Table
Table
76
Rules of Boolean Algebra
□ Rule 12: (A + B)(A + C) = A + BC
AND Truth OR Truth Table
Table
77
De Morgan’s Theorems
De Morgan’s first theorem:
The complement of a product of variables is equal to the sum
of the complements of the variables.
Stated in another way,
The complement of two or more variables ANDed is equivalent to
the OR of the complements of the individual variables.
The formula for expressing this theorem for two variables is:
78
De Morgan’s Theorems
De Morgan’s second theorem:
The complement of a sum of variables is equal to the product
of the complements of the variables.
Stated in another way,
The complement of two or more variables Ored is equivalent to
the AND of the complements of the individual variables
The formula for expressing this theorem for two variables is:
79
De Morgan’s Theorem
□ De Morgan’s theorems provide mathematical verification of the
equivalency of the NAND and negative-OR gates and equivalency of
the NOR and negative- AND gates.
□ These theorems are extremely useful in simplifying expressions in
which a product or sum of variables is inverted
Gate equivalencies
and
corresponding
truth tables
80
BOOLEAN ANALYSIS OF LOGIC
CIRCUITS
81
Boolean Analysis of Logic Circuits
The purpose of this section is to
□ Determine the boolean expression for a combination of
gates.
□ Evaluate the logic operation of a circuit from the boolean
expression.
□ Arrive at the simplified boolean algebra expression with
the given logic.
Determination of the boolean expression is done one
gate at a time starting at the inputs and simplification is
done using Boolean laws and rules
82
Example 1 : Problem
Solution: One gate at a time starting with the inputs
X= AB+(C+D)
X= AB + C+ D
83
Example 2 : Problem
Solution:
X = (AB)(CD)
X = ABCD
84
Example 3 : Problem
Solution:
X = ABCD +A
X = A + BCD
85
Example 4 : Problem
Solution:
X=AB
C
86
Example 5 : Problem
Solution:
87
Example 5 : Problem
Solution (continued):
88
Example 5 : Problem
Solution (continued):
Simplification:
X = (A +AB) +(B(C+D))
X =(A + B) + (B(C + D))
X = (A + B) + (B C + B D)
X = A + B + BC + BD
X=A+B+C+B D
X=A+B+C+D
89
Example 5 : Problem
The circuits
are different
but the
outputs are the
same
90
Example 6 : Problem
Solution:
(A + B)(CD) = A + B + CD
= A + B + CD
91
Example 6 : Problem
X and Y are
the same
92
SIMPLIFICATION USING
BOOLEAN ALGEBRA TECHNIQUES
93
Problem 1
Simplify: A’B + A’ B’ C’ D’ + A B C D’
Problem 2
Simplify: F = A’ B C + A B’ C + A B C’ + A B C
F=BC+AC+AB
Problem 3
Simplify:
W = [M + N’P + (R + ST)’][M + N’P + R + ST]
Assume X = M + N’P Y = R + ST
W = (X + Y’)(X + Y)
W = XX + XY + Y’X + Y’Y
W = X·1 + XY + XY’ + 0
W = X + X(Y + Y’) = X + X·1 = X
W = M + N’P
Problem 4
Express the complement f’(w,x,y,z) of the following
expression in a simplified form.
f(w,x,y,z) = wx(y’z + yz’)
f’(w,x,y,z) = w’ + x’ + (y’z +yz’)’
= w’ + x’ + (y’z)’(yz’)’
= w’ + x’ + (y + z’)(y’ + z)
= w’ + x’ + yy’ + yz + z’y’ + z’z
= w’ + x’ + 0 + yz + z’y’ + 0
= w’ + x’ + yz + y’z’
Simplification using Boolean Algebra
– More Problems
□ Using Boolean Algebra Techniques, simplify the
following expressions :
1. AB+A(B+C)+B(B+C)
2. [AB’(C+BD)+A’B’]C
3. A’BC+AB’C’+A’B’C’+AB’C+ABC
4. (AB+AC)’+A’B’C
98
References
Slides adopted from the books
❑ Thomas L.Floyd, “Digital Fundamentals,”11th Edition, Prentice Hall,
2014 (ISBN10:0132737965/ISBN13:9780132737968)
□ M.Morris Mano and Michael D. Ciletti, " Digital Design,"
5th Edition, Pearson Education International, 2013
(ISBN: 9780132774208)
□ Ronald J.Tocci, Neal S.Widmer, and Gregory L.Moss, "Digital
Systems- Principles and Application"- 11th Edition, Pearson Education
International, 2011 (ISBN: 9780135103821)
99
