Digital Electronics

EE2304
Lecture 02
04/09/2023

Faculty of Engineering- SEUSL 1

Outline
• Logic Gates
• Boolean Algebra
• Simplifying Logic Circuits
• Karnaugh Maps
• Combinational Logic Circuits

Faculty of Engineering- SEUSL

2
Logic Gates
• Logic gates are building blocks from which all other logic circuits and digital
systems are constructed.
• Logic gates can be constructed from diodes, transistors, and resistors
connected so that the circuit output is the result of a basic logic operation
(OR, AND, NOT) performed on the inputs.
• Voltage‐operated logic circuits respond to two separate voltage levels that
represent a binary variable equal to logic 1 or logic 0.
• Different logic gates and the more complex circuits formed from
combinations of logic gates can be described and analyzed using Boolean
algebra.
• A truth table is a means for describing how a logic circuit’s output depends
on the logic levels present at the circuit’s inputs.

Faculty of Engineering- SEUSL

3
OR Operation / OR Gate
• "x equals A OR B"

Truth table circuit symbol for a

defining the two-input OR gate
OR operation;

x will be 1 when A or B or both are 1

In digital circuitry, an OR gate is a circuit that has two or more inputs and whose output is
equal to the OR combination of the inputs.

Faculty of Engineering- SEUSL

4
Example – 3 Input OR Gate

Symbol and truth table for a three-input OR gate.

Faculty of Engineering- SEUSL

5
Example - Application

In many industrial control systems, it is required to activate an

output function whenever any one of several inputs is activated.

Faculty of Engineering- SEUSL

6
Example – Timing Diagram

The OR gate output is determined by realizing that it will be

HIGH whenever any of the two inputs is at a HIGH level.
Faculty of Engineering- SEUSL
7
AND Operation / AND Gate
• "x equals A AND B“

Truth table for the

AND gate symbol
AND operation;

x will be 1 only when A and B are both 1

AND gate is a circuit that operates so that its output is HIGH only when all its inputs are HIGH

Faculty of Engineering- SEUSL

8
Example – Timing Diagram

Faculty of Engineering- SEUSL

9
NOT Operation / NOT Gate
• "x equals the inverse of A” or
• “x equals NOT A"

Truth table Sample waveforms

Symbol for the INVERTER (NOT circuit)

NOT circuit always has only a single input

Faculty of Engineering- SEUSL

10
Example

Faculty of Engineering- SEUSL

11
Example- Answers

Faculty of Engineering- SEUSL

12
NOR Gate
Operates like an OR gate followed by an INVERTER.

NOR symbol

Equivalent circuit

Truth table

Faculty of Engineering- SEUSL

13
Example

Faculty of Engineering- SEUSL

14
NAND Gate
• NAND operates like an AND gate followed by an INVERTER.

NAND symbol

Equivalent circuit

Truth table

Faculty of Engineering- SEUSL

15
Example

Faculty of Engineering- SEUSL

16
XOR Gate (Exclusive-OR)

Has two inputs only and produces one output.

The outputs go HIGH if inputs are different from each other.

Faculty of Engineering- SEUSL

17
XNOR Gate (Exclusive-NOR gate)

Exclusive-NOR gate always has two inputs only and produces one output.

Faculty of Engineering- SEUSL

18
Boolean Algebra
• Boolean algebra is a relatively simple mathematical tool that allows us to
describe the relationship between a logic circuit's output(s) and its inputs as
an algebraic equation (a Boolean expression).
• Boolean algebra can be used to simplify a circuit‘s Boolean expression so that
the circuit can be rebuilt using fewer logic gates and/or fewer connections.
• There are only three basic Boolean operations(the logic operations
implemented by logic gates) :
• OR, AND, and NOT

Faculty of Engineering- SEUSL

19
Boolean Variables
• Used to represent the voltage level present on a wire or at the
input/output terminals of a circuit.
• Boolean constants and variables are allowed to have only two possible
values, 0 or 1.
• Ex:
• Boolean value of 0 might be assigned to any voltage in the range from 0 to 0.8 V.
• Boolean value of 1 might be assigned to any voltage in the range 2 to 5 V.

Faculty of Engineering- SEUSL

20
 Boolean Algebra Theorems

NOT operator is represented by the “ - “

symbol and has the highest precedence.

OR operator is represented by the ‘+’

symbol and has the lowest precedence.

AND operator is represented by ‘.’ symbol

and is in the middle.

Single-variable theorems.
Faculty of Engineering- SEUSL
21
Boolean Algebra Theorems
Multi-variable theorems.

Faculty of Engineering- SEUSL

22
Boolean Algebra Theorems
DeMorgan’s theorem

Faculty of Engineering- SEUSL

23
Examples

Faculty of Engineering- SEUSL

24
Examples

Faculty of Engineering- SEUSL

25
Example
• Determine the output expression for the below circuit and simplify
it using DeMorgan’s theorems

Faculty of Engineering- SEUSL

26
Solution

Faculty of Engineering- SEUSL

27
Implementing Circuits from Boolean
Expressions
• F = x’y’z + x’yz + xy’

Faculty of Engineering- SEUSL

28
Simplified Implementation

Each circuit implements the same identical function, but the one with fewer gates and
fewer inputs to gates is preferable because it requires fewer wires and components.
In general, there are many equivalent representations of a logic function. Finding the most
economic representation of the logic is an important design task.

Faculty of Engineering- SEUSL

29
Implementation Example
• In a certain manufacturing process, a conveyor belt will shut down whenever specific
conditions occur. These conditions are monitored and reflected by the states of four logic
signals as follows:
• signal A will be HIGH whenever the conveyor belt speed is too fast;
• signal B will be HIGH whenever the collection bin at the end of the belt is full;
• signal C will be HIGH when the belt tension is too high;
• signal D will be HIGH when the manual override is off.
A logic circuit is needed to generate a signal x that will go HIGH whenever conditions A and B
exist simultaneously or whenever conditions C and D exist simultaneously.

Faculty of Engineering- SEUSL

30
Solution
x = AB + CD

Faculty of Engineering- SEUSL

31
Simplifying Logic Circuits
• Boolean expression must be reduced to as simple a form as possible before
realization because every logic operation in the expression represents a
corresponding element of hardware.
• Realization of a digital circuit with minimal expressions – results in reduction
of cost and complexity and the corresponding increase in reliability.

Faculty of Engineering- SEUSL

32
Example
• Both circuits perform the same logic

Faculty of Engineering- SEUSL

33
Simplifying Logic Circuits
• Available Options are :
• Boolean simplification (1- 3 Variables – Still Tedious Work)
• Mapping Technique -Karnaugh map (3-6 Variable)
• CAD (computer automated design) ( 6-8 Variables - PALASM, ABEL, CUPL,
Verilog, and VHDL)

Faculty of Engineering- SEUSL

34
Representation of Boolean Functions
• Sum of Products (SOP) form:
• A logic function that is expressed as an OR of several product terms is considered to be in "sum-of-products" or SOP form.
• Also called as Disjunctive Normal Form(DNF)
• f(A,B,C) = A’B + B’C
• Minterms:
• Product terms that consist of all the variables of a function either in complimented or uncomplimented form are called
"canonical product terms", "fundamental product terms" or "minterms".
• Ex: The term ABC’ is a minterm in a three-variable logic function, but will be a non-minterm in a four-variable logic function

• Products of Sums(POS) form:

• Also called Conjunctive Normal Form (CNF)
• f(A,B,C) = (A’+B’)(B+C)
• .Maxterms :
• Sum terms that contain all the variables of a Boolean function are called "canonical sum terms", "fundamental sum terms" or
"maxterms".

Faculty of Engineering- SEUSL

35
Representation of Boolean Functions
The sum of the minterms whose value is equal to 1 is the
standard SOP form / canonical SOP form of the function

Consider a function of three variables

f(A,B,C) = m0 + m3 + m5 + m6

This is equivalent to
f(A,B,C) = A’B’C’+A’BC+AB’C+ABC’
Minterms and Maxterms of 3 variables
Another way of representing canonical SOP
f(A,B,C) = Sum(0,3,5,6)

Faculty of Engineering- SEUSL

36
Karnaugh Map (K-Map)
• Graphical tool
• to simplify a logic equation.
• or to convert a truth table to its corresponding logic circuit in a simple,
orderly process.
• Karnaugh maps reduce logic functions more quickly and easily
compared to Boolean algebra.
• Simplify means, reducing the number of gates and inputs.
• Extremely useful in minimizing functions of 3,4,5 or 6 variables.
• Karnaugh maps are the graphical equivalent of a truth table

Faculty of Engineering- SEUSL

37
Basics of K-Map
• We look for commonality of Boolean variables among cells.
• The Karnaugh map is organized so that we may see that
commonality

Faculty of Engineering- SEUSL

38
 2 Variable Example

The truth table contains two 1s. the K- map must have both of them.
1. Locate the first 1 in the 2nd row of the truth table.
2. Note the truth table AB address locate the cell in the K-map having the same address
3. Place a 1 in that cell
4. Repeat the process for the 1 in the last line of the truth table.

The presence of a minterm indicates that the output of the logic circuit assumes 1 for the
combination of input variables.

The sum of Minterms will give an equivalent Boolean expression.

Faculty of Engineering- SEUSL
39
2 Variable Example

Faculty of Engineering- SEUSL

40
2 Variable Example

Faculty of Engineering- SEUSL

41
Faculty of Engineering- SEUSL
42
3 Variable K-Map

the basic property possessed by adjacent squares: Any two adjacent

squares in the map differ by only one variable,

Faculty of Engineering- SEUSL

43
3 Variable Example
• Simplify the Boolean function
• F (x, y, z) =Sum (2, 3, 4, 5)
• Solution
• squares for minterms are 010, 011, 100, and 101
• next step is to find possible adjacent squares
These are indicated in the map by two
shaded rectangles, each enclosing two 1’s

F (x, y, z) = (2, 3, 4, 5) = xy’ + x’y

Faculty of Engineering- SEUSL

44
3 Variable Example

Faculty of Engineering- SEUSL

45
Solution

Faculty of Engineering- SEUSL

46
3 Variable Example

Faculty of Engineering- SEUSL

47
Adjacency
• In certain cases, two squares in the map are considered to be adjacent even
though they do not touch each other.
• Here m0 is adjacent to m2 and m4 is adjacent to m6 because their minterms
differ by one variable.

Faculty of Engineering- SEUSL

48
3 Variable K Map Example

Faculty of Engineering- SEUSL

49