Minterms and Maxterms

Minterms and Maxterms

n binary variables can be combined to form 2ⁿ terms (AND terms),

called Minterms or standard products. x’y’(00),x’y(01),xy’(10),xy(11)

In a similar fashion, n binary variables can be combined to form 2ⁿ terms (OR terms), called Maxterms or standard sums.

Boolean Functions expressed in Sum of MinTerms or Product of MaxTerms are said to be in Canonical Form

* Note that each maxterm is the complement of its corresponding minterm and vice versa.

1

Minterms and Maxterms (continued)

Each Minterm is obtained from an AND term. Variable primed if corresponding bit 0, vice versa Each Maxterm is obtained from an OR term. Variable primed if corresponding bit 1, vice versa

x	y	z	Minterms		Maxterms
0	0	0	x’y’z’	mo	x+y+z	Mo
0	0	1	x’y’z	m1	x+y+z’	M1
0	1	0	x’yz’	m2	x+y’+z	M2
0	1	1	x’yz	m3	x+y’+z’	M3
1	0	0	xy’z’	m4	x’+y+z	M4
1	0	1	xy’z	m5	x’+y+z’	M5
1	1	0	xyz’	m6	x’+y’+z	M6
1	1	1	xyz	m7	x’+y’+z’	M7

2

Sum of Minterms S

^§ Given the truth table, express F₁ in sum of minterms

x	y	z		F1	F2
0	0	0		0	1
0	0	1			0
				1
0	1	0		0	1
0	1	1		0	1
1	0	0		1	0
1	0	1		0	0
1	1	0		0	0
1	1	1		1	0

F₁ (x, y, z) = å(1,4,7) = m₁ + m₄ + m₇

= (x' y' z) + (xy' z' ) + (xyz)

^§ Find F_{2                                                                                                                                                                                                                                                         3}

Product of Maxterms P

^§ Given the truth table, express F₁ in Product of Maxterms

	x	y	z			F1	F2
	0	0	0			0	1
0		0	1		1		0
0		1	0				1
						0
0		1	1			0	1
1		0	0		1		0
1		0	1		1		0
1		1	0		1		0
1		1	1		1		0
F1(x, y, z) = Õ(0,2,3) = M 0				× M 2	× M3
= (x + y + z)(x + y'+z)(x + y'+z')

^§ Find F₂                                                                                                                                                                                                                                                         ⁴

Sum of Min Terms

Express the Boolean function F = x + y' z in a sum of minterms.

AIM: Convert it to 3 variable AND Terms and take their SUM

x = x( y + y' ) = xy + xy'

xy = xy(z + z' ) = xyz + xyz' xy' = xy' (z + z' ) = xy' z + xy' z' y' z = y' z(x + x' ) = xy' z + x' y' z

Adding all terms and excluding recurring terms:

F (x, y, z) = x' y' z + xy' z'+xy' z + xyz'+xyz

F (x, y, z) = m₁ + m₄ + m₅ + m₆ + m₇  = å(1,4,5,6,7)

5

Product of Max Terms

Express the Boolean function F = xy + x' z in a Product of Maxterms.

AIM: Convert it to 3 variable OR Terms and take their Product

Tip: Postulate 4b (Distributed)

F = xy + x' z = (xy + x' )(xy + z) (xy + x' ) = (x + x' )( y + x' )

(xy + z) = (x + z)( y + z)

F =1.( y + x' )(x + z)( y + z)					All Term missing one variable  X+X’=1
x'+ y + zz' = (x'+ y + z)(x'+ y + z' )
x + z + yy' = (x + z + y)(x + z + y' )
y + z + xx' = ( y + z + x)( y + z + x' )
Remove any recurring terms
F = (x + y + z)(x + y'+z)(x'+ y					+ z)(x'+ y + z' )
M0M2M4M5	= F(x,y,z)=Π(0,2,4,5)					6

Using Truth Table

•         Find Sum of Minterms and Product of MaxTerms of F= xy+x’z

(Same as before)

–  Truth Table

Find Sum of Minterms & Product of Maxterms from truth table

– F(x,y,z)= ∑(1,3,6,7)

– F(x,y,z)= П (0,2,4,5)

7

Conversion between Canonical Forms

•       Complement of a function expressed as sum of minterms equals sum of minterms missing from the original function

•       F(A,B,C,D) = ∑(1,4,5,6,7)= m₁+m₄+m₅₊ m₆+m₇

•       Complement is F’(A,B,C,D)= ∑(0,2,3) = m₀+m₂+m₃

•       Complement of F’ is F that is different

F = (m₀+m₂+m₃)’ = = m’₀. m’₂ . m’_{3 =} = M₀.M₂.M₃₌ П(0,2,3)

8

Standard Form to represent Boolean Function

•        Sum of Minterms and Product of Maxterm may not be most efficient way to draw a circuit as all variables must be used.

•        Standard Functions have one two or three terms and Two Levels. (AIM: Minimum Gates)

•        SUM OF PRODUCT

– F= y’ + xy+ x’yz’

– Sum denotes OR of these terms

– Two Levels

•        PRODUCT OF SUM

– F= x(y’+z)(x+’y+z’)

– Product denotes AND of these terms

– Two Levels

9

SUM OF PRODUCT

SUM OF PRODUCT F= y’ + xy+ x’yz’

Sum denotes OR of these terms Draw the circuit (2 Level)

x’ y z’

y’

x y

 F

10

PRODUCT of SUM

PRODUCT OF SUM F= x(y’+z)(x’y+z’)

Product denotes AND of these terms Draw the circuit (2 Level)

x’ y z’

x

y’

z

 F

11

Non Standard Boolean Function

•        Boolean Expression in non standard form F=AB+C(D+E)

.

– Neither SOP or POS

– Implemented in 3 levels

A
B	F
C
D
E

– Convert to Standard Form by distributive law

– F=AB+C(D+E) = AB+CD+CE

– Draw 2 Level Standard Sum of Product Circuit

12

Truth Table and Boolean Expression for 16 functions of two variables

•         F0=0 Constant 0 or Null

•          F1= x.y^è AND (x and y)

•          F2 = xy’^è x but not y

•         F3 = x

•          F4 = x’y^è y but not x

•         F5 = y

•          F6 = xy’ + x’y ^èExclusive OR ( x or y but not both

•          F7= x+y ^èOR (x or y)

•          F8 = (x+y)’ ^è NOR (Not OR)

•          F9 = xy + x’y’^è Equivalence (x equals y)

•          F10 = y’ ^èNot y

•          F11 = x+y’^è If y then x

•         F12 = x’ (Not x)

•         F13 = x’ + y If x then y

•          F14 = (xy)’ ^è NAND

•         F15 = 1 Binary constant 1

13

NOR Logic gate

2-input NOR logic gate:

F = ( X + Y )'

x	F
y

X	Y	F
0	0	1
0	1	0
1	0	0
1	1	0

14

NAND Logic gate

2-input NAND logic gate:

F = ( X .Y )'

x	F
y

X	Y	F
0	0	1
0	1	1
1	0	1
1	1	0

15

Exclusive OR Logic gate

2-input exclusive-OR (XOR) logic gate:

F = X ÅY

x	F
y

X	Y	F
0	0	0
0	1	1
1	0	1
1	1	0

16

Exclusive NOR Logic gate

2-input exclusive-NOR logic gate:

F = ( X ÅY )'

x	F
y

X	Y	F
0	0	1
0	1	0
1	0	0
1	1	1

17

More Digital Logic Gates

• AND                        F=xy

• OR                                  F=x+y

• Inverter F=x’

• Buffer                        F=x

• NAND F=(xy)’

• NOR                                   F=(x+y)’

• Exclusive OR- XOR

• Exclusive NOR

18

Multiple Input GATES

3-input exclusive-OR (XOR) logic gate:

F = X ÅY Å Z

x	F
y
z

Implemented by 3 Input Gates

x

y  F

z

Implemented by 2 Input Gates

X	Y	Z	F
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

19

Implementation of Boolean Functions

^§ Using only OR and NOT gates, draw a schematic for the

following function: F = xy + x' y'+ y' z

(F ' )'= ((xy + x' y'+ y' z)')'

= [( xy)'.(x' y' )'.(y' z)']'

= [( x'+ y' ).(x + y).( y + z' )]'

= (x'+ y' )'+(x + y)'+( y + z' )'

x

y

F

^z                                     20

Implementation of Boolean Functions

^§ Using ONLY NAND gates, draw a schematic for the following function: F = (a.b)+(b.c)

a

b

F

c