4.13M

Category: $mathematics$ mathematics

Digital Logic Design

1.

Digital Logic Design
Lecture – 3:
Combining Logic Gates
Konakbayev Olzhas, senior-lecturer,

2.

Lecture base
Digital Electronics: Principles & Applications, 9th edition by Roger
Tokheim & Patrick E. Hoppe:
• Chapter 4
2

Topics to cover
• Constructing Circuits from Boolean Expressions
• Minterm and Maxterm Boolean Expressions
• Boolean Expression from a Truth Table
• Truth Tables and Boolean Expressions
• Simplifying Boolean Expressions
• Karnaugh Maps
• Using NAND Logic
• Using DeMorgan’s Theorem
3

4.

Circuits from Boolean Expressions
1a
• AND-OR pattern of gates from a Sum-of-Products
Boolean expression.
A B A C B C Y
4

5.

Circuits from Boolean Expressions
2
• OR-AND pattern of gates from a Product-of-Sums
Boolean expression.
(A B) (A B C) Y
5

6.

Circuits from Boolean Expressions
3
• Step 1: Identify pattern of operation
6

7.

Circuits from Boolean Expressions
4
• Step 2: Add the first OR gate with inputs
7

8.

Circuits from Boolean Expressions
5
• Step 3: Add the second OR gate with inputs
8

9.

Minterm and Maxterm Boolean Expressions
1
• Maxterm Boolean Expression
C+B+A C+B+A C+B+A =Y
(Product-of-Sum Expression)
9

10.

Minterm and Maxterm Boolean Expressions
2
• Minterm Boolean Expression
C B A C B A C B A Y
(Sum-of-Product Expression)
10

11.

Boolean Expression from a Truth Table
• Step 1: Write an AND
expression for each
instance Y = 1.
• Step 2: OR the
expressions together
to form a Boolean
expression.
11

12.

Truth Tables and Boolean Expressions
Let’s look at an example.
12

13.

Simplifying Boolean Expressions
1
• Original Boolean Expression
13

14.

Simplifying Boolean Expressions
2
• Reduced Boolean Expression
14

15.

Single-variable Boolean Theorems
1
• The first Boolean theorem states that X ANDed with
0 is 0.
X 0 0
15

16.

Single-variable Boolean Theorems
2
• The second Boolean theorem states that X ANDed
with 1 is X.
X 1 X
16

17.

Single-variable Boolean Theorems
3
• The third Boolean theorem states that X ANDed with
X is X.
X X X
17

18.

Single-variable Boolean Theorems
4
• The fourth Boolean theorem states that X ANDed
with ഥ
X is 0.
X X 0
X
18

19.

Single-variable Boolean Theorems
5
The fifth Boolean theorem states that X ORed with 0 is X.
X+0=0
19

20.

Single-variable Boolean Theorems
6
• The sixth Boolean theorem states that X ORed with 1
is 1.
X+1=1
20

21.

Single-variable Boolean Theorems
7
• The seventh Boolean theorem states that X ORed
with X is X.
X+X=X
21

22.

Single-variable Boolean Theorems
8
• The eighth Boolean theorem states that X ORed with
ഥ
X is 1
X X 1
22

23.

Single-Variable Boolean Theorems
9
23

24.

Multivariable Boolean Theorems
1
The ninth Boolean theorem states that X ORed with Y is
equal to Y ORed with X.
X+Y=Y+X
24

25.

Multivariable Boolean Theorems
2
• The tenth Boolean theorem states that X ANDed with
Y is equal to Y ANDed with X.
X Y Y X
25

26.

Multivariable Boolean Theorems
3
• The eleventh Boolean theorem demonstrates when
ORing multiple inputs, the order of operation does
not matter.
X Y Z X Y Z X Y Z
26

27.

Multivariable Boolean Theorems
4
• The twelfth Boolean theorem demonstrates when
ANDing multiple inputs, the order of operation does
not matter.
X Y Z X Y Z X Y Z
27

28.

Multivariable Boolean Theorems
5
• The thirteenth Boolean theorem is sometimes called
the distributive theorem.
X Y Z X Y X Z
28

29.

Multivariable Boolean Theorems
6
• The fourteenth Boolean theorem states X ORed with
X ANDed with Y is equal to X.
X X Y X
29

30.

Multivariable Boolean Theorems
7
• The fifteenth Boolean theorem states X ORed with ഥ
X
ANDed with Y is equal to X ORed with Y.
X X Y X Y
Access the text alternative for slide images.
30
30

31.

Multivariable Boolean Theorems
8
31

32.

Multivariable Boolean Theorems
9
32

33.

Boolean Reduction with Two Variables
1
33

34.

Boolean Reduction with Two Variables
2
• Let’s check our answer.
34

35.

Boolean Reduction with Three Variables
1
35

36.

Boolean Reduction with Three Variables
2
• Let’s check our answer.
36

37.

Karnaugh Maps
• The columns and rows of the two and three input
Karnaugh maps must be laid out in this manner.
37

38.

Karnaugh Maps with Three Variables
1
Step 1: Write the minterm for each input
combination that produces a 1 on the
output.
38

39.

Karnaugh Maps with Three Variables
2
Step 2: Write the Sum of Product expression
using the minterms.
39

40.

Karnaugh Maps with Three Variables
3
Step 3: Fill in the 1’s for each minterm in
The Sum of Product expression
40

41.

Karnaugh Maps with Three Variables
4
Step 4: Loop adjacent 1’s in groups of
two, four, or eight.
41

42.

Karnaugh Maps with Three Variables
5
Step 5: Simplify by dropping terms that
contain a term and its complement within a
loop.
Step 6: OR the remaining terms together to
form a simplified Boolean expression.
42

43.

Karnaugh Maps with Three Variables
6
43

44.

Boolean Reduction with Three Variables
• Let’s check our answer.
44

45.

Karnaugh Maps with Four Variables
1
45

46.

Karnaugh Maps with Four Variables
2
46

47.

Other Looping Possibilities
1
• Consider the Karnaugh map as a vertical cylinder.
47

48.

Other Looping Possibilities
2
• Consider the Karnaugh map as a horizontal cylinder.
48

49.

Other Looping Possibilities
3
• Consider the Karnaugh map as a ball
49

50.

Using NAND Logic
1
• Start with a minterm (sum-of-products) Boolean
expression.
• Draw the AND-OR logic diagram using AND, OR, and
NOT symbols.
• Substitute NAND symbols for each AND and OR
symbol, keeping all connections the same.
• Substitute NAND symbols with all inputs tied
together for each inverter.
• Test the logic circuit containing all NAND gates to
determine if generates the proper truth table.
50