Session 3:

Optimize Boolean
Functions and 1. K-map

Introduction To 2. Combinational Circuit

.
Combinational and 3. Sequential Circuit

Sequential Circuits
 LOGIC GATE
KARNAUGH MAP

Karnaugh map it is a graphical representation of a truth table for a Boolean

function. Karnaugh maps are helpful for simplifying Boolean expressions and
minimizing the number of terms in a logic function.

2
 LOGIC GATE
KARNAUGH MAP – 2 VARIABLES

K-map to represent F(A,B) - SOP

B B B 0 1
A B minterms A
0 0 AB m0 A AB AB m0 m1
0
0 1 AB m1
1 0 AB m2 A AB AB 1 m2 m3
1 1 AB m3

3
 LOGIC GATE
KARNAUGH MAP – 2 VARIABLES

Optimize K-map rules:

❑ Make the group of 1s, which are adjacent to each other.
❑ This group should be in the power of 2. For example, in case of the 2 variables
map, we can make the group of two 1s or group of four 1s, but can not make the
group of three 1s.
❑ Ensure that during the grouping, all the 1s in the maps are covered.
❑ During grouping, even if the 2 groups overlap with each other, it’s alright.
❑ After grouping, keep the common variables (not change) in each group.

4
 LOGIC GATE
KARNAUGH MAP – 2 VARIABLES GROUPING

B 0 1 B 0 1
A A

0 1 1 0 1 1

1 1 1 1 1

B 0 1
A

0 1 1

1 1

5
 LOGIC GATE
KARNAUGH MAP – 2 VARIABLES

F(A,B) = A’.B’ + A’.B + A.B B 0 1

A
A B F
0 0 1 0 1 1
0 1 1
1 1
1 0 0
1 1 1
F(A,B) = A’ + B
Can not be
F(A,B) = A’.B + A.B’ 0 1 simplified !!!
A
A B F
0 0 0 0 1
0 1 1
1 0 1 1 1
1 1 0
F(A,B) = A’.B + A.B’ 6
 LOGIC GATE
KARNAUGH MAP – 2 VARIABLES - POS

F(A,B) = A’.B’ + A’.B B 0 1

A
A B F
0 0 1 0
0 1 1
1 0 0
1 0 0
1 1 0
F(A,B) = A’
Can not be
F(A,B) = A’.B + A.B’ 0 1 simplified !!!
A
A B F
0 0 0 0 0
0 1 1
1 0 1 1 0
1 1 0
F(A,B) = (A + B).(A’ + B’) 7
 LOGIC GATE
KARNAUGH MAP – 3 VARIABLES

K-map to represent F(A,B,C) - SOP

A B C minterms
0 0 0 m0 BC 00 01 10
11
0 0 1 m1 A
0 1 0 m2 m0 m1 m3 m2
0 (1)
0 1 1 m3
1 0 0 m4 1 m4 m5 m7 m6
(2)
1 0 1 m5
1 1 0 m6
1 1 1 m7

8
 LOGIC GATE
KARNAUGH MAP – 3 VARIABLES

Simplify below Boolean function: F(A,B,C) = σ(0,1,3,5)

BC 00 01 11 10
A
A B C F m0 m1 m3 m2
0
0 0 0 1
0 0 1 1 1 m4 m5 m7 m6
0 1 0 0
0 1 1 1 BC 00 01 11 10
A
1 0 0 0
1 1 1
1 0 1 1 0
1 1 0 0
1 1
1 1 1 0

F(A,B,C) = A’.B’ + A’.C + B’.C 9

 LOGIC GATE
KARNAUGH MAP – 3 VARIABLES - GROUPING

F(A,B,C) = σ(0,2) F(A,B,C) = σ(1,3,5,7)

BC 00 01 11 10 BC 00 01 11 10
A A
1 1 1 1
0 0
1 1 1 1

F(A,B,C) = σ(4,6) F(A,B,C) = σ(0,2,4,6)

BC 00 01 11 10
A BC 00 01 11 10
A
0 1 1
0
1 1 1
1 1 1
10
 LOGIC GATE
KARNAUGH MAP – 3 VARIABLES

Practice: simplify below Boolean function

F(A,B,C) = σ(0,1,2,4,5,6) F(A,B,C) = σ(0,1,2,3,4,6)

BC 00 01 11 10 BC 00 01 11 10
A A

0 0
1 1

F(A,B,C)= F(A,B,C)=

11
 LOGIC GATE
KARNAUGH MAP – 3 VARIABLES

When the SOP Boolean functions is not enough (lack of variables to form a minterm).
For example: BC 00 01 11 10
F(A,B,C) = A’ + A.B’ + A.B.C’ A
m0 m1 m3 m2
A B C F 0
0 0 0 1
0 0 1 1
1 m4 m5 m7 m6

0 1 0 1
BC 00 01 11 10
0 1 1 1 A
1 0 0 1 1 1 1 1
1 0 1 1
0
1 1 0 1 1 1 1 1
1 1 1 0

F(A,B,C)= 12
 LOGIC GATE
KARNAUGH MAP – 3 VARIABLES

When the SOP Boolean functions is not enough (lack of variables to form a minterm).
For example: BC 00 01 11 10
F(A,B,C) = A’ + A.B’ + A.B.C’ A
m0 m1 m3 m2
A B C minterms 0
0 0 0 1
0 0 1 1
1 m4 m5 m7 m6

0 1 0 1
BC 00 01 11 10
0 1 1 1 A
1 0 0 1 1 1 1 1
1 0 1 1
0
1 1 0 1 1 1 1 1
1 1 1

F(A,B,C)= A’ + B’ + C’ 13
 LOGIC GATE
HOMEWORK

Homework:
❑ Prove that the
F(A,B,C) = A’ + A.B’ + A.B.C’ = A’ + B’ + C’

14
 LOGIC GATE
KARNAUGH MAP – 4 VARIABLES

K-map to represent F(A,B,C,D) - SOP

A B C D minterms
0 0 0 0 m0
0 0 0 1 m1
CD 00 01 11 10
0 0 1 0 m2
AB
0 0 1 1 m3
00 m0 m1 m3 m2
0 1 0 0 m4 (1)
0 1 0 1 m5
0 1 1 0 m6 01 m4 m5 m7 m6
(2)
0 1 1 1 m7
1 0 0 0 m8
1 0 0 1 m9 11 m12 m13 m15 m14
1 0 1 0 m10
(4)
1 0 1 1 m11
10 m8 m9 m11 m10
1 1 0 0 m12
(3)
1 1 0 1 m13
1 1 1 0 m14
1 1 1 1 m15
15
 LOGIC GATE
KARNAUGH MAP – 4 VARIABLES - GROUPING

Grouping of 4 and 8, as long as the 1s are adjacent

CD 00 01 11 10 CD 00 01 11 10
AB AB
00 1 1 1 1 00 1 1 1 1

01 1 1 01 1 1

11 1 1 11 1 1

10 1 1 10 1 1 1 1

16
 LOGIC GATE
KARNAUGH MAP – 4 VARIABLES

F(A,B,C,D) = σ(0,2,5,9,15)
CD 00 01 11 10 CD 00 01 11 10
AB AB
m0 m1 m3 m2 00 1 1
00

01 m4 m5 m7 m6 01 1

11 m12 m13 m15 m14 11

10 m8 m9 m11 m10 10 1 1

17
 LOGIC GATE
KARNAUGH MAP – 4 VARIABLES

F(A,B,C,D) = σ(0,2,5,9,15)
CD 00 01 11 10 CD 00 01 11 10
AB AB
m0 m1 m3 m2 00 1 1
00

01 m4 m5 m7 m6 01 1

11 m12 m13 m15 m14 11

10 m8 m9 m11 m10 10 1 1

F(A,B,C,D) = A’.B’.D’+A’.B.C’.D+A.B’.C’.D+A.B’.C’.D
18
 LOGIC GATE
KARNAUGH MAP – 4 VARIABLES

F(A,B,C,D) = σ(4,5,6,7,9,13,14,15)
CD 00 01 11 10 CD 00 01
AB 11 10
AB
00 m0 m1 m3 m2
00

01 m4 m5 m7 m6 01 1 1 1 1

11 m12 m13 m15 m14 11 1 1 1

10 m8 m9 m11 m10 10 1

19
 LOGIC GATE
KARNAUGH MAP – 4 VARIABLES

F(A,B,C,D) = σ(4,5,6,7,9,13,14,15)
CD 00 01 11 10 CD 00 01
AB 11 10
AB
00 m0 m1 m3 m2
00

01 m4 m5 m7 m6 01 1 1 1 1

11 m12 m13 m15 m14 11 1 1 1

10 m8 m9 m11 m10 10 1

F(A,B,C,D) = A’.B + BC + A.C’.D

20
 LOGIC GATE
KARNAUGH MAP – 4 VARIABLES

Practice: simplify below F(A,B,C,D) = σ(4,5,6,7,9,13,14,15)

CD 00 01 11 10 CD 00 01
AB 11 10
AB
00 m0 m1 m3 m2
00

01 m4 m5 m7 m6 01

11 m12 m13 m15 m14 11

10 m8 m9 m11 m10 10

F(A,B,C,D) =
21
 LOGIC GATE
KARNAUGH MAP – 4 VARIABLES

Practice: simplify below F(A,B,C,D) = σ(0,1,5,6,7,8,9,13,15)

CD 00 01 11 10 CD 00 01
AB 11 10
AB
00 m0 m1 m3 m2
00

01 m4 m5 m7 m6 01

11 m12 m13 m15 m14 11

10 m8 m9 m11 m10 10

F(A,B,C,D) =
22
 LOGIC GATE
KARNAUGH MAP – 4 VARIABLES

Practice: simplify below F(A,B,C,D) = σ(0,1,4,5,7,8,9,11,12,13,15)

CD 00 01 11 10 CD 00 01
AB 11 10
AB
00 m0 m1 m3 m2
00

01 m4 m5 m7 m6 01

11 m12 m13 m15 m14 11

10 m8 m9 m11 m10 10

F(A,B,C,D) =
23
 LOGIC GATE
SUMMARY

SUMMARY:
❑ Transistor acts as a switch to turn ON or turn OFF a circuit.
Transistor N-type typical usage Transistor P-type typical usage
S is connected to GND (Logic 0) D is connected to VDD (Logic 1)
G = 1 => switch is ON => Transistor is conducting G = 1 => switch is OFF => Transistor is NOT conducting
G = 0 => switch is OFF => Transistor is NOT conducting G = 0 => switch is ON => Transistor is conducting

❑ NOT, NOR, NAND are basic gates and can be used to express any other elements.
❑ Boolean algebra is used for designing and analyzing digital circuits and algorithms.
❑ There are 2 type of Boolean function: SOP & POS.
❑ Karnaugh map is a very effective way to simplify Boolean functions.

24
 LOGIC GATE
HOMEWORK

Homework:
❑ A circuit has 4 inputs A,B,C,D and 1 output Y. Design a combinational logic for
Y to set Y to 1 whenever 2 or more inputs are equal to 1. Otherwise, Y is 0.
❑ *Investigate 5 variable K-map and do the same requirement as above
homework

25
 COMBINATIONAL CIRCUIT
Below is some characteristics of combinational circuit:
❑ No feedback: do not have feedback paths, meaning there are no elements that store information
about previous inputs or outputs.
❑ Instantaneous Output: The output is a function only of the current input values, and there is no
concept of time or sequence.
❑ Truth Table: The behavior of a combinational circuit is fully described by a truth table, which lists all
possible combinations of input values and their corresponding output values.
❑ Logic Gates: Combinational circuits are constructed using basic logic gates such as AND, OR, NOT, XOR,
and others.

26
 SEQUENTIAL CIRCUIT
Below is some characteristics of combinational circuit:
❑ Memory Elements: Sequential circuits include memory elements (such as flip-flops or latches) that store
information about the past states of the circuit.
❑ Feedback Paths: Sequential circuits have feedback paths that allow the output to influence the input, creating a
loop that enables the circuit to maintain and update its state.
❑ Clock Signal: The clock signal determines when the circuit should update its state, ensuring that changes happen
at specific intervals.
❑ State Transition: The behavior of a sequential circuit is often described using a state diagram, which illustrates
how the circuit transitions from one state to another based on input and clock signals.
❑ Finite State Machines: Sequential circuits are often implemented as finite state machines, where the circuit can
exist in a finite number of states, and transitions between states are governed by specified conditions.

27
 SUMMARY

SUMMARY:
❑ Karnaugh map is a very effective way to simplify Boolean functions.
❑ Combinational logic has no feedback path, the output changes immediately based
on input.
❑ Sequential logic has feedback path to store the current state.

28