‫پوهنتون تعلیم و تربیه کابل‬

‫پوهنځی‪ :‬کمپیوتر ساینس‬

‫دیپارتمنت‪ :‬تکنالوژی معلوماتی‬
DIGITAL DESIGN
6. Minterm‐Maxterm

Lecturer: Mohammad Asif Dawlatnazar

Email: [email protected]
0765910106
Kabul Education University
Computer Science Faculty

2
 What we learn
◼ Writing Boolean function in standard form
❑ Why?
❑ Standard form
❑ Minterm and Maxterm
❑ Canonical Form

3
 Truth Table Representation of Functions
a b F a b c F a b c d F
• Define value of F for 0 0 0 0 0 0 0 0 0
0 1 0 0 1 0 0 0 1
each possible 1 0 0 1 00 00 0 11 0
combination of input 1 1 0 1 1 0 0 1 1
values (a) 1 0 0 0 1 0 0
– 2‐input
2 function: 4 rows 1 0 1 0 1 0 1
1 1 0 0 1 1 0
– 3‐input function: 8 rows 1 1 1 0 1 1 1
– 4‐input function: 16 (b) 1 0 0 0
rows a 1 0 0 1
a b c F 1 0 1 0
• Q: Use truth table to 0 0 0 0
1 0 1 1
define function F(a,b,c) 0
0 1
0
0
1 a 0b0 c 1 1 0 0
that is 1 when abc is 5 or 0 1 1 0 1 1 0 1
greater in binary 1 0 0 0 1 1 1 0
1 0 1 1 1 1 1 1 1 1
1 1 0 1 (c)
1 1 1 1

4
 Converting among Representations
• Can convert from any Inputs Outputs Term
representation to any other a b F F = sum of
• Common conversions 0 0 1 a’b’
0 1 1 a’
ab
– Equation to circuit 1 0 0
– Truth table to equation 1 1 0
– Equation to truth table
• Easy ‐‐ just evaluate equation for each
F = a’b’ + a’b
input combination (row) Q: Convert to equation
• Creating intermediate columns helps a b c F
Q: Convert to truth table: F = a’b’ + a’b 0 0 0 0
0 0 1 0
Inputs Output 0 1 0 0
a b a' b' a' b F 0 1 1 0
0 0 1 0 1 1 0 0 0
0 1 0 1 1 1 0 1 1 ab’c
1 0 0 00 00 1 1 0 1 abc’
1 1 0 0 0 1 1 1 1 abc
F = ab’c + abc’ + abc
5
 Standard Representation: Truth Table

• How to determine two functions are the same?

• Use algebraic methods
• But
B t ifif we failed,
f il d does
d th t prove not equal?
that l? No.
N
• Solution: Convert to truth tables
O– lOnly
ONEONE
t th t bltable representation
truth t ti f of given same
functions: Standard representation
F = ab + a’ F = a’b’ +a’b + ab

a b F a b F
0 0 1 0 0 1
0 1 1 0 1 1 a

1 0 00 11 0 00
1 1 1 1 1 1

6
 Standard Form
- Truth tables too big for numerous inputs
- Use standard form of equation instead
- Sum Term:
a+b+c’
- Product Term:
abc’

- Standard form: a Boolean algebra statement which is

in form of only Anded sum terms or Ored product
terms

✓
✓
 7
 Why Standard Form is matter:
If a Boolean function is represented in standard form we
can represent it in two level logic diagram:

8
Minterm/Maxterm
Minterm: a Boolean algebra term that all literals are in
the term, and all are Anded.

Maxterm: a Boolean algebra term that all literals are

in the term, and all are Ored.

If f1(x,y,z) is a Boolean function then:

term Is minterm term Is maxterm
xy No X+y No
x‘yz Yes x‘+y+z Yes
x’y’z’ Yes x’+y’+z’ Yes
x+yz no xy+z’ no

9
Minterm/Maxterm

10
11
Canonical form
• Canonical form is some kind of standard
form which all terms are in form of
Minterm or Maxterm. So we have two
canonical form for each Boolean algerbra
function:
- SoP: sum of products (som of Minterms)

- PoS: product of Sum (product of Maxtemrs)

12
 How to write Boolean function in
canonical form
◼ There are two ways:
❑ Using truth table
❑ Using Boolean algebra

13
 How to write Boolean function in
canonical form
◼ Using truth table:
◼ To write in form of SOP we write function as sum of
minterms which are 1.
◼ To write in form of POS we write function as product of
maxterms which are 0
◼ Example 1:
◼ Example 2:

14
 Example1:
◼

15
 Example2:
◼

16
How to write Boolean
function in canonical form
◼

17
 How to write Boolean function in canonical form

◼ Using Boolean algebra:

◼ To write in form of PoS: Write the function in form of OR
terms (if not) using distribution law, then looking for missing
variables in each term and or with the missing variable and
its complement:
◼ Example:
◼ F(x,y,z)= xy + x’z
= (xy + x’) (xy + z)
= (x + x’) (y + x’) (x + z) ( y + z)
= (y + x’) (x + z) ( y + z)
= (y + x’ + zz’) (x + z + yy’) ( y + z + xx’)
= (y + x’ + z) (y + x’ + z’) (x + z + y) (x + z + y’)( y + z + x)( y + z +x’)
= (x’ + y + z) (x’ + y + z’) (x + y + z) (x + y’+ z)
= M4 . M5 . M0 . M2 = Π (0,2,4,5)
18
 Converting between SoP and PoS
◼ If a Boolean function is in form of SoP we can
simply write it in form of PoS using these steps:
◼ Convert Σ to Π
◼ Write the missing number
◼ Example:
◼ SoP:

◼ PoS:

19
 summarize
◼ We need to write Boolean functions in standard form:
◼ Canonical form is a kind of standard form
◼ In canonical form we can use SoP or PoS form
◼ In SoP we use Minterms
◼ In PoS we use Maxterms
◼ We can convert SoP to PoS

20
 homework

1-

2-

3-

21
DIGITAL DESIGN
7. KMap‐Logic Minimization
Lecturer: Mohammad Asif Dawlatnazar
Email: [email protected]
0765910106
Kabul Education University
Computer Science Faculty

22
 Minimization using K-map
◼ As we said there are two ways of minimization:
❑ Boolean algebra: simplification of Boolean function using
Boolean algebra rules.
❑ K-map: graphical way to simplify functions using Minterms or
Maxterms.
❑ If we use minterms the minimization is in form SOP
❑ If we use Maxterms the mimimization is in form of POS

23
 K-map
◼

24
Minimizing the function
using SOP form

25
 2 variable k-map-draw map
◼ If function has 2variables we can use
4squeres k-map
◼ To draw a 2 variable k-map:
❑ Draw a square
❑ Divide it two four squares
❑ Label it by input variables
❑ Label each column and row by 0 and 1
❑ Label small squares using minterms or input
variables y 1
x 0
m0 m1
0
X’y’ X’y

m2 m3
1 Xy’ Xy
26
 2 variable k-map-fill by function
◼ To fill by the function
❑ Convert function to sop
❑ equation form or Boolean algebra form
❑ For each minterm in function label
corresponding square by 1
❑ Label other squers by 0

0 0
0 1
 2 variable k-map-fill by function
X Y f

F(x,y)=xy+xy’+x’y 0 0 0 m0

0 1 1 m1

1 0 1 m2

1 1 1 m3

0 1
1 1
 2 variable k-map-minimization
◼ To minimize the function
❑ Group the 1’s in map using adjacent rules
❑ There are groups of 1 or 2 or 4 adjacent variables
❑ For each group write the algebraic term
❑ The minimized function is sum of groups

1 1 0 1 0 0
1 1 1 1 0 1

G1=? G2=x G1=y G1=xy

 3 variable k-map-draw map
◼ If function has 3 variables we can use 8squeres k-map
◼ To draw a 3 variable k-map:
❑ Draw a rectangle
❑ Divide it two 8 squares
❑ Label it by input variables
❑ Label each row by 0 and 1
❑ Label each column by 00 01 11 10 (gray code)
❑ Label small squares using minterms or input variables

yz
x 00 01 11 10

0 m0 m1 m3 m2
x’y’z’ x’y’z x’y z x’y z’

m4 m5 m7 m6
1 x y’z’
30
x y’z xyz x y z’
 3 variable k-map-fill by function
◼ To fill by the function
❑ Convert function to sop if not
❑ equation form or Boolean algebra form
❑ For each minterm in function label
corresponding square by 1
❑ Lable other squers by 0

0 0 1 1

1 1 0 0
3 variable k-map-fill by function

1 0 0 1

1 1 0 1
 3 variable k-map-minimization
◼ To minimize the function
❑ Group the 1’s in map using adjacent rules
❑ There are groups of 1 or 2 or 4 or 8 adjacent
variables
❑ For each group write the algebraic term
❑ The minimized function is sum of groups

G2=xy’ G1=z’
F(x,yz)=G1+G2=z’+xy’
3variable K-map
◼ Adjacency rules:

34
 Example2

A B C F
0 0 0 0 m0
◼ Answer:
0 0 1 1 m1
0 1 0 1 m2
0 1 1 1 m3
1 0 0 0 m4
1 0 1 1 m5
1 1 0 0 m6
1 1 1 1 m7

35
 4 variable K-map
◼ Labeling

36
 4 variable K-map
◼ Adjacency rules:
◼ 1 variable group
◼ 2
◼ 4
◼ 8
◼ 16

37
 4 variable K-map
◼ Adjacency rules:
◼ 4
◼ 8
◼ 16

38
 4 variable K-map
◼ Adjacency rules:
◼ 8
◼ 16

39
 4 variable K-map
◼ Adjacency rules:
◼ 16

40
 4 variable K-map
◼ Minimization
◼ Example1:

1 1 1
G3=w’z’

1 1 1
G2=xz’
1 1 1

1 1

G1=y’

41
 4 variable K-map
◼ Minimization
◼ Example2:

1 1 1
G3=A’CD’
1
G2=B’C’

1 1 1

G1=B’D’

42
 4 variable K-map
◼ Minimization
◼ Example3:
Minimization in form of
POS

44
 K-map minimization in form of POS
◼ To minimize a K-map in form of POS we should
consider squares with 0 value and grouping them.
◼ for each group write the product term
◼ Complement each group using DeMorgan rules
◼ The minimized function in POS form is result of
producing complemented groups

45
 K-map minimization in form of POS
◼ Example:

G1=CD

1 1 0 1

G3=B D’ 0 0
1 0

G2=A B 0 0 0 0

1 1 0 1

46
 K-map minimization in form of POS
◼ Example:

G3=A+B+D
0 0

0
G1=C+D

0 0

47
 Karnaugh ‫نگاشت‬
◼ Converting the SOP to POS by K_Map
 Karnaugh ‫نگاشت‬
◼ Converting the SOP to POS by K_Map
Don’t care conditions

50
 What is Don’t care condition?
◼ The logical sum of the minterms associated with a
Boolean function specifies the conditions under which
the function is equal to 1. The function is equal to 0 for
the rest of the minterms.
◼ In practice, in some applications the function is not
specified for certain combinations of the variables.
◼ Functions that have unspecified outputs for some input
combinations are called incompletely specified
functions
◼ In most applications, we simply don’t care what value is
assumed by the function for the unspecified minterms.
To distinguish the don’t-care condition from 1’s and 0’s,
an X is used.

51
 Don’t care condition
◼ Example:

G1=CD

X 1 1 X G1=w’x’ Solution1
G2=yz
X 1

52
 Don’t care condition
◼ Example:
Solution2
G1=CD

X 1 1 X G1=w’z

G2=yz
X 1

53
‫کارخانگی‬

‫‪54‬‬
END

55