LSD [Link]

com/c/EDULINEFORCSE
STUDENTS

MODULE 2
BOOLEAN ALGEBRA

Prepared By Mr. EBIN PM, AP, IESCE 1

POSTULATES OF BOOLEAN ALGEBRA

BOOLEAN ALGEBRA
• There are 2 types of algebras existed. One is ordinary algebra and
other is Boolean algebra.
• Logical operations are implemented only in Boolean algebra
• In Boolean algebra , A+A = A and A.A=A because, the variable A has
only a logical value. It doesn’t have any numerical significance.
• In ordinary algebra, A+A=2A and A.A=A , because variable A has a
numerical value here.
• Boolean algebra constants are 0 and 1
• Truth table is used for verification
Prepared By [Link] PM, AP, IESCE EDULINE 2

Prepared By Mr. EBIN PM, AP, IESCE 1

LSD [Link]
STUDENTS

In Boolean algebra 1+1 = 1

In binary number system 1+1 = 10
In ordinary algebra 1+1 = 2

• There is nothing like subtraction or division in Boolean algebra

• There is no negative or fractional numbers in Boolean Algebra
• Any functional relations in Boolean algebra can be proved by the
method of “Perfect Induction”

Prepared By [Link] PM, AP, IESCE EDULINE 3

POSTULATES
A set B of elements (a, b, c, …..) with an equivalence relation (=),
two binary operations(+ and . ) and unary operation (complement)
is a Boolean algebra if and only if the following postulates are
satisfied.
1) Associativity
• The + and . operations are associative
(a + b) + c = a + (b + c)
(a . b) . c = a . (b . c)

Prepared By [Link] PM, AP, IESCE EDULINE 4

Prepared By Mr. EBIN PM, AP, IESCE 2

LSD [Link]
STUDENTS

2) Commutativity
• The + and . Operations are commutative
a+b=b+a
a.b=b.a
3) Distributivity
• The two operations are distributive over each other
a + bc = (a + b)(a + c)
a(b + c) = ab + ac

Prepared By [Link] PM, AP, IESCE EDULINE 5

4) Identity Elements
An identity element denoted by 0, called zero for the + operation
and another denoted by 1 called one for the . Operation
a+0=a
a.1=a
5) Complement
a + a’ =1
a . a’ = 0

Prepared By [Link] PM, AP, IESCE EDULINE 6

Prepared By Mr. EBIN PM, AP, IESCE 3

LSD [Link]
STUDENTS

FUNDAMENTAL THEOREMS
1. Closure of identity elements - For all a Є B,
a+1=1 a.0=0
Proof Proof

Prepared By [Link] PM, AP, IESCE EDULINE 7

2. Equality Theorem – for all a, b, c Є B if

a+b=a+c
ab = ac Proof
Then b = c

Prepared By [Link] PM, AP, IESCE EDULINE 8

Prepared By Mr. EBIN PM, AP, IESCE 4

LSD [Link]
STUDENTS

3. Complementarity Theorem – for all a, b Є B,if

a + b = 1 and Proof
ab = 0 , Then
a’ = b
a = b’

Prepared By [Link] PM, AP, IESCE EDULINE 9

4. Identity elements 0 and 1 are complement to each other

Proof
Since 0 and 1 Є B
1 + 0 = 1 and 1 . 0 = 0
Then by complementarity theorem
0’ = 1
1’ = 0

Prepared By [Link] PM, AP, IESCE EDULINE 10

Prepared By Mr. EBIN PM, AP, IESCE 5

LSD [Link]
STUDENTS

LAWS OF BOOLEAN ALGEBRA

1. Involution
For all a Є B, (a’)’ = a

Prepared By [Link] PM, AP, IESCE EDULINE 11

2. Law of Idempotence
For all a Є B,
a + a = a and
a.a=a

Prepared By [Link] PM, AP, IESCE EDULINE 12

Prepared By Mr. EBIN PM, AP, IESCE 6

LSD [Link]
STUDENTS

3. Law of Absorption
For all a, b Є B
a + ab = a
a(a + b) = a

Proof

Prepared By [Link] PM, AP, IESCE EDULINE 13

DEMORGAN’S THEOREM
(a + b)’ = a’ . b’
(a . b)’ = a’ + b’
Proof

Prepared By [Link] PM, AP, IESCE EDULINE 14

Prepared By Mr. EBIN PM, AP, IESCE 7

LSD [Link]
STUDENTS

Eg: Simplify the following using Boolean theorems

1. A+A’B
A+A’B = (A+A’)(A+B)
=1. (A+B)
=A+B
2. (A+B) (A’+C)
(A+B) (A’+C) = AA’+AC+BA’+BC
= 0+AC+BA’+BC
= AC+BA’+BC

Prepared By [Link] PM, AP, IESCE EDULINE 15

BOOLEAN FUNCTIONS
Literal – A Boolean variable in the true form or in the complemented
form is called a literal.
Eg: a, a’, b, b’ are literals
• The Boolean product of two or more literals is called a product term.
• The Boolean sum of two or more literals is called a sum term.
Normal Form
There are 2 types of normal forms
1. Sum of Product (SOP)
2. Product of Sum (POS)

Prepared By [Link] PM, AP, IESCE EDULINE 16

Prepared By Mr. EBIN PM, AP, IESCE 8

LSD [Link]
STUDENTS

Sum of Product – SOP form is also called Disjunctive Normal Form

(DNF). It is in the form
f(abcd) = a’+ bc’ + cd
Product of Sum – POS form is also called Conjunctive Normal
Form (CNF). It is in the form
f(abcd) = (a + b)(b + c + d)
• A Boolean function that is neither in the DNF nor in CNF
Eg1: f1 = a’b’ + b(c + d’). Convert the function in normal form?
f1= a’b’ + bc + bd’
Eg2: f2 = (a’+ b)(a + cd). Convert the function in normal form?
f1=(a’+ b)(a + d)(a + c)
Prepared By [Link] PM, AP, IESCE EDULINE 17

CANONICAL FORM
• When each of the terms of a Boolean function expressed either in
SOP or POS form has all the variables in it, it is said to be expressed
in canonical form.
• Canonical form cannot have the same term more than once.
• Canonical SOP is called Disjunctive Canonical Form (DCF)
• Canonical POS is called Conjunctive Canonical Form (CCF)
Eg 1: Express the function f1= ab’c + bc’+ ac in canonical form?
f1 = ab’c + bc’.1 + ac.1
= ab’c + bc’(a + a’) + ac(b + b’)
= ab’c + bc’a + bc’a’ + acb
Prepared By [Link] PM, AP, IESCE EDULINE 18

Prepared By Mr. EBIN PM, AP, IESCE 9

LSD [Link]
STUDENTS

Eg 2: Express the function f2= (a + b)(b + c’) in canonical form?

(a + b)(b + c’)
= (a + b + c.c’) (b + c’+ a.a’)
=(a + b + c)(a + b +c’) (b + c’+ a)(b + c’+ a’)
=(a + b + c)(a + b + c’)(b + c’ + a’)

Prepared By [Link] PM, AP, IESCE EDULINE 19

Eg 3: Express the function f3= a +a’(b + c’) in canonical form?

a + a’(b + c’)
= a + a’b + a’c’
= a(b + b’)(c + c’) + a’b(c + c’) + a’c’(b + b’)
=(ab + ab’)(c + c’) + a’bc + a’bc’ + a’c’b + a’c’b’
= abc + abc’ + ab’c + ab’c’ + a’bc + a’bc’ + a’c’b + a’b’c’
= abc + abc’ + ab’c + ab’c’ + a’bc + a’bc’ + a’b’c’

Prepared By [Link] PM, AP, IESCE EDULINE 20

Prepared By Mr. EBIN PM, AP, IESCE 10

LSD [Link]
STUDENTS

FUNDAMENTAL PRODUCT (MINTERM)

• The number of all possible minterms of n variables is 𝟐𝐧
• 0 is written for a complemented variable (a’ = 0)
• 1 is written for the uncomplemented variable (a = 1)
• Each minterm is designated as mᵢ , the subscript i is the decimal
value of the binary number.
Minterm Binary Symbolic Minterm Binary Symbolic
number Representation number Representation
a’b’c’ 000 m₀ ab’c 101 m₅
a’b’c 001 m₁ abc’ 110 m₆
a’bc’ 010 m₂ abc 111 m₇
a’bc 011 m₃
ab’c’ 100 m₄
Prepared By [Link] PM, AP, IESCE EDULINE 21

FUNDAMENTAL SUM (MAXTERM)

• The number of all possible maxterms of n variables is 𝟐𝐧
• 0 is written for a uncomplemented variable (a = 0)
• 1 is written for the complemented variable (a’ = 1)
• Each maxterm is designated as Mᵢ , the subscript i is the decimal
value of the binary number.
Maxterm Binary Symbolic Maxterm Binary Symbolic
number Representation number Representation
a+b+c 000 M₀ a’+b+c’ 101 M₅
a+b+c’ 001 M₁ a’+b’+c 110 M₆
a+b’+c 010 M₂ a’+b’+c’ 111 M₇
a+b’+c’ 011 M₃
a’+b+c 100 M₄
Prepared By [Link] PM, AP, IESCE EDULINE 22

Prepared By Mr. EBIN PM, AP, IESCE 11

LSD [Link]
STUDENTS

 ∑ indicate that the terms are minterms and the function is a

summation.
∏ indicate that the terms are maxterms and the function is a
product.
The complement of mᵢ is Mᵢ and vice versa. That is,
mᵢ’ = Mᵢ
Mᵢ’ = mᵢ

f1 = a’b’c’ + a’b’c + abc f2 = (a+b+c) (a’+b’+c)(a’+b’+c’)

= m₀+m₁+m₇ = M₀M₆M₇
= ∑(0, 1, 7) = ∏(0, 6, 7)
Prepared By [Link] PM, AP, IESCE EDULINE 23

Examples
1. Reduce x(x’+yz) 3. prove that ab’(c + bd) + a’b’= b’c + a’b’
x(x’ + yz) ab’(c + bd) + a’b’
= xx’ + xyz = ab’c + ab’bd + a’b’
= xyz = ab’c + a’b’
2. Reduce x(x’y + x’z) = b’(ac + a’)
x(x’y + x’z) = b’(a’ + c)(a’ + a)
= xx’y + xx’z = a’b’ + b’c
=0

Prepared By [Link] PM, AP, IESCE EDULINE 24

Prepared By Mr. EBIN PM, AP, IESCE 12

LSD [Link]
STUDENTS

Disjunctive & Conjunctive Canonical Forms (DCF & CCF)

• DCF is same as sum of minterms (canonical SOP)
• CCF is same as product of maxterms (canonical POS)
• If a Boolean function is expressed in the DCF, it can also be
expressed in the CCF
• Eg1: Express the function f1=a’bc+ab’c’+abc in the other type of
canonical form?
a’bc + ab’c’+abc
= 011 100 111 So, fᵢ = m₃+m₄+m₇ (minterms)
Then Maxterms are fⱼ= M₀.M₁.M₂.M₅.M₆

Prepared By [Link] PM, AP, IESCE EDULINE 25

Eg 2: Express the function f2=a’b’c’d’+a’bc’d+a’bcd’ in the other type

of canonical form?
a’b’c’d’ + a’bc’d + a’bcd’
= 0000 0101 0110 So, fᵢ = m₀+m₅+m₆ (minterms)
Then Maxterms are
fⱼ= M₁.M₂.M₃.M₄.M₇.M₈.M₉.M₁₀.M₁₁.M₁₂.M₁₃.M₁₄.M₁₅
A Boolean function expressed as a sum of minterms or as a
product of maxterms can be converted in to the other form as
given by
∑mᵢ = ∏Mⱼ & ∏Mᵢ = ∑mⱼ
 Where, the subset i and j are two partitions of the entire set of 2
subscripts of either m’s or M’s
Prepared By [Link] PM, AP, IESCE EDULINE 26

Prepared By Mr. EBIN PM, AP, IESCE 13

LSD [Link]
STUDENTS

Q: Expand A’+B’ to minterms and maxterms?

A’+B’
= A’.1 + B’.1
= A’(B + B’) + B’(A + A’)
= A’B + A’B’ + B’A + B’A’
= A’B + A’B’ + AB’
= 01 + 00 + 10
= m₁ + m₀ + m₂
= ∑(0, 1, 2)
Corresponding maxterms is M₃
= ∏(3)
Prepared By [Link] PM, AP, IESCE EDULINE 27

DUAL & COMPLEMENT

DUAL
To obtain the dual of an expression
1. Change the ORs to ANDs , ANDs to ORs
2. Change the 0s to 1s, 1s to 0s
3. Do not complement the variables

Eg: A’B + A’BC’ + A’BCD + A’BC’D’E

DUAL = (A’+B).(A’+B+C’).(A’+B+C+D).(A’+B+C’+D’+E)

Prepared By [Link] PM, AP, IESCE EDULINE 28

Prepared By Mr. EBIN PM, AP, IESCE 14

LSD [Link]
STUDENTS

COMPLEMENT
To obtain the complement of an expression
1. Change the ANDs to ORs , ORs to ANDs
2. Change the 0s to 1s , 1s to 0s
3. Complement each variable

Eg: AB + A(B+C) + B’(B+D)

COMPLEMENT = (A’+B’).(A’+B’.C).(B+B’.D’)

Prepared By [Link] PM, AP, IESCE EDULINE 29

IMPORTANT QUESTIONS
1. Find the SOP form of (A+C) (AB’+AC) (A’C’+B’) ?

(A+C) (AB’+AC) (A’C’+B’) simply multiply

= (AAB’+AAC+CAB’+CAC) (A’C’+B’)
= (AAB’A’C’+AACA’C’+CAB’A’C’+CACA’C’+AAB’B’+AACB’+CAB’B’+CACB’)
= AB’ + ACB’ + ACB’ + ACB’
= AB’ + AB’C

Prepared By [Link] PM, AP, IESCE EDULINE 30

Prepared By Mr. EBIN PM, AP, IESCE 15

LSD [Link]
STUDENTS

2. For the function f=AB’D+A’BC+BC’D’. Obtain this f in SOP form?

f = AB’D + A’BC + BC’D’
= AB’D(C+C’) + A’BC(D+D’) + BC’D’(A+A’)
= AB’DC + AB’DC’ + A’BCD + A’BCD’ + BC’D’A + BC’D’A’
3. Express the Boolean function f=xy+x’z in a product of maxterms
form?
f = xy + x’z
= xy(z+z’) + x’z(y+y’)
= xyz + xyz’ + x’zy + x’zy’
= m₇+m₆+m₃+m₂
= M₀.M₁.M₄.M₅ = ∏(0, 1, 4, 5)
Prepared By [Link] PM, AP, IESCE EDULINE 31

4. Find the minterms of A+B ?

A+B
= A(B+B’) + B(A+A’)
= AB + AB’ + BA + BA’
= AB + AB’ + BA’
= m₃+m₂+m₁
= ∑(1, 2, 3)

Prepared By [Link] PM, AP, IESCE EDULINE 32

Prepared By Mr. EBIN PM, AP, IESCE 16

LSD [Link]
STUDENTS

5. Convert f=A’B’C’+A’B’C+A’BC’+AB’C’+ABC’+ABC into POS form?

f = A’B’C’+A’B’C+A’BC’+AB’C’+ABC’+ABC
= ∑(0, 1, 2, 4, 6, 7)
= ∏(3, 5)
= (A+B’+C’) (A’+B+C’)
= 0 1 1 1 0 1
3 5

Prepared By [Link] PM, AP, IESCE EDULINE 33

THE KARNAUGH MAP (K-MAP)

• The K-map is a very convenient way of representing a switching
function.
• A two variable K-map will have 2 =4 cells
• A three variable K-map will have 2 =8 cells
• A four variable K-map will have 2 =16 cells
2 variable K-map 3 variable K-map

Prepared By [Link] PM, AP, IESCE EDULINE 34

Prepared By Mr. EBIN PM, AP, IESCE 17

LSD [Link]
STUDENTS

4 variable K-map

• We can group the elements in to pairs, quads and octect

• In a pair, one variable is reduced.
• In a quad, two variables can be eliminated
• In an octect, three variables can be eliminated
Prepared By [Link] PM, AP, IESCE EDULINE 35

Eg: Reduce the expression AB+AB’C+A’BC’+BC’ using K-map?

bc
a b’c’ b’c bc bc’

a’ 1
0 1 3 2
a 1 1 1
4 5 7 6

Ans: ac + bc’

Prepared By [Link] PM, AP, IESCE EDULINE 36

Prepared By Mr. EBIN PM, AP, IESCE 18

LSD [Link]
STUDENTS

Eg: Convert A+B’C’ to minterms using K-map?

bc
a b’c’ b’c bc bc’

a’ 1
0 1 3 2
a 1 1 1 1
4 5 7 6

minterms = ∑(0, 4, 5, 6, 7)
= A’B’C’ + AB’C’ + AB’C + ABC’ + ABC

Prepared By [Link] PM, AP, IESCE EDULINE 37

Eg: Reduce AB+AC+C+AD+AB’C+ABC using K-map?

CD
AB C’D’ C’D CD CD’

A’B’ 1 1
0 1 3 2 Ans: A+C
A’B 1 1
4 5 7 6

AB 1 1 1 1
12 13 15 14

AB’ 1 1 1 1
8 9 11 10

Prepared By [Link] PM, AP, IESCE EDULINE 38

Prepared By Mr. EBIN PM, AP, IESCE 19

LSD [Link]
STUDENTS

Eg: Reduce ∑(5, 6, 7, 9, 10, 11, 13, 14, 15) using K-map?
CD
AB C’D’ C’D CD CD’

A’B’
0 1 3 2 Ans: BD+DA+CB+CA
A’B 1 1 1
4 5 7 6

AB 1 1 1
12 13 15 14

AB’ 1 1 1
8 9 11 10

Prepared By [Link] PM, AP, IESCE EDULINE 39

Eg: Reduce AB’C+B+BD’+ABD’+A’C using K-map?

CD
AB C’D’ C’D CD CD’

A’B’ 1 1
0 1 3 2 Ans: C + BC’
A’B 1 1 1 1
4 5 7 6

AB 1 1 1 1
12 13 15 14

AB’ 1 1
8 9 11 10

Prepared By [Link] PM, AP, IESCE EDULINE 40

Prepared By Mr. EBIN PM, AP, IESCE 20

LSD [Link]
STUDENTS

Eg: Reduce the expression (a+b)(a+b’+c)(a+c’) using K-map?

b+c
a b+c b+c’ b’+c’ b’+c

a 0 0 0 0
0 1 3 2
a’
4 5 7 6

Ans: a

Prepared By [Link] PM, AP, IESCE EDULINE 41

Eg: Reduce A(B+C’)(A+B’)(B+C+D’) using K-map?

C+D
A+B C+D C+D’ C’+D’ C’+D

A+B 0 0 0 0
0 1 3 2 Ans: A(A’+B)
A+B’ 0 0 0 0
4 5 7 6

A’+B’
12 13 15 14

A’+B 0 0 0 0
8 9 11 10

Prepared By [Link] PM, AP, IESCE EDULINE 42

Prepared By Mr. EBIN PM, AP, IESCE 21

LSD [Link]
STUDENTS

DON’T CARE CONDITIONS

Eg: Reduce ∑(0,1,4,5,6,7,9,11,15) + d(10,14) using K-map?
CD
AB C’D’ C’D CD CD’

A’B’ 1 1
0 1 3 2
Ans: A’C’+A’B+BC+AC+AB’D
A’B 1 1 1 1
4 5 7 6

AB 1 X
12 13 15 14

AB’ 1 1 X
8 9 11 10

Prepared By [Link] PM, AP, IESCE EDULINE 43

DON’T CARE CONDITIONS

Eg: Reduce ∏(3,6,8,11,13,14).d (1,5,7,10) using K-map?
C+D
A+B C+D C+D’ C’+D’ C’+D

A+B X 0
0 1 3 2
Ans: (A+D’). (B’+C’+D) .
A+B’ X X 0 (A’+B+C’).(B’+C+D’).
4 5 7 6

0 (A’+B+D)
A’+B’ 0
12 13 15 14

A’+B 0 0 X
8 9 11 10

Prepared By [Link] PM, AP, IESCE EDULINE 44

Prepared By Mr. EBIN PM, AP, IESCE 22

LSD [Link]
STUDENTS

5 variable K-map - Here , number of minterms=2 =32

Eg: f(A,B,C,D,E) = ∑(0,2,3,10,11,12,13,16,17,18,19,20,21,26,27)

A’=0 A =1
DE DE
BC D’E’ D’E DE DE’ BC D’E’ D’E DE DE’

B’C’ 1 1 1 B’C’
1 1 1 1
0 1 3 2 16 17 19 18
B’C B’C 1 1
4 5 7 6 20 21 23 22
BC 1 1 BC
12 13 15 14 28 29 31 30
BC’ 1 1 BC’ 1 1
8 9 11 10 24 25 27 26
Ans: C’D+AB’C’D’E’+AB’C’D’+A’BCD’+AB’CD’
Prepared By [Link] PM, AP, IESCE EDULINE 45

LOGIC GATES
• Logic Gates are the basic building blocks of any digital system.
• It is an electronic circuit having one or more than one input and only
one out put.
• The relationship between the input and the output is based on a
certain logic.
• Based on this, logic gates are named as
AND gate
OR gate
NOT gate

Prepared By [Link] PM, AP, IESCE EDULINE 46

Prepared By Mr. EBIN PM, AP, IESCE 23

LSD [Link]
STUDENTS

Elementary (Basic) Logic Gates

Prepared By [Link] PM, AP, IESCE EDULINE 47

NAND GATE
• NAND means Not AND. Ie, AND gate is NOTed
• NAND gate is equivalent to bubbled OR gate
• Bubbled OR gate is also called negative OR gate
• Bubbled NAND gate is equivalent to OR gate

(NAND gate) (NAND as an inverter)

Prepared By [Link] PM, AP, IESCE EDULINE 48

Prepared By Mr. EBIN PM, AP, IESCE 24

LSD [Link]
STUDENTS

NOR GATE
• NOR means Not OR. Ie, OR output is NOTed
• NOR gate is equivalent to bubbled AND gate
• Bubbled AND gate is also called negative AND gate
• Bubbled NOR gate is equivalent to AND gate

(NOR gate) (NOR as an inverter)

Prepared By [Link] PM, AP, IESCE EDULINE 49

X-OR GATE
• It is called anti-coincidence gate or inequality detector
• It is an odd function
• Fan –in of XOR is 2
• A + B = A’B + AB’
Logic Symbol

XOR as an inverter
Prepared By [Link] PM, AP, IESCE EDULINE 50

Prepared By Mr. EBIN PM, AP, IESCE 25

LSD [Link]
STUDENTS

X-NOR GATE
• Combination of X-OR and NOT gate
• It is also called Coincidence gate
• It can be used as an equality detector
• Its output is 1 only when its input are equal
• A . B = AB + A’B’
Logic Symbol

X-NOR as an inverter
Prepared By [Link] PM, AP, IESCE EDULINE 51

FUNCTIONALLY COMPLETE SETS

• A set of operations is called a functionally complete set if and only if
any Boolean function can be expressed by operations belonging to
the set only
• It can be seen that the NAND and NOR operations alone form a
functionally complete set
• It is there fore possible to implement any switching function using
only one type of gate , either NAND or NOR.
• Hence these two operations are known as universal operations

Prepared By [Link] PM, AP, IESCE EDULINE 52

Prepared By Mr. EBIN PM, AP, IESCE 26

LSD [Link]
STUDENTS

NAND REALIZATION
Implementation of Basic Gates using NAND only

Prepared By [Link] PM, AP, IESCE EDULINE 53

NOR REALIZATION
Implementation of Basic Gates using NOR only

Prepared By [Link] PM, AP, IESCE EDULINE 54

Prepared By Mr. EBIN PM, AP, IESCE 27

LSD [Link]
STUDENTS

BINARY NUMBERS
Simple way to write Binary numbers:
Decimal Binary Number 7 0111
Number 8 1000
0 0000 9 1001
1 0001 10 1010
2 0010 11 1011
3 0011 12 1100
4 0100 13 1101
5 0101 14 1110
6 0110 15 1111
Prepared By [Link] PM, AP, IESCE EDULINE 55

TABULAR MINIMIZATION PROCEDURE

• Tabular minimization method is used to solve more than 6 variable
functions
• Commonly used tabular method is Quine-Mc Cluskey (QM)method
Eg1: simplify using QM method f(a b c d)=∑m(0,1,2,3,4,6,8,9,10,11)
• Weight of a cube is said to be in terms of one’s present in the
minterm.
• For example, 1100 has weight 2.
• First we create a table T₀, which contains only zero cubes. Then we
construct T₁ which contains only one cubes and so on.

Prepared By [Link] PM, AP, IESCE EDULINE 56

Prepared By Mr. EBIN PM, AP, IESCE 28

LSD [Link]
STUDENTS

T₀ ∑m(0,1,2,3,4,6,8,9,10,11)
x1 x2 x3 x4

0 0 0 0 0 Weight =0

1 0 0 0 1
2 0 0 1 0
Weight =1
4 0 1 0 0

8 1 0 0 0
3 0 0 1 1

6 0 1 1 0 Weight =2
9 1 0 0 1
10 1 0 1 0
Weight =3
11 1 0 1 1

Prepared By [Link] PM, AP, IESCE EDULINE 57

T₁
x1 x2 x3 x4 (8,10) 1 0 2 0
(0,1) 0 0 0 2
(3,11) 2 0 1 1
(0,2) 0 0 2 0
(9,11) 1 0 2 1
(0,4) 0 2 0 0
(10,11) 1 0 1 2
(0,8) 2 0 0 0

(1,3) 0 0 2 1

(1,9) 2 0 0 1
(2,3) 0 0 1 2
(2,6) 0 2 1 0
(2,10) 2 0 1 0
(4,6) 0 1 2 0
(8,9) 1 0 0 2
Prepared By [Link] PM, AP, IESCE EDULINE 58

Prepared By Mr. EBIN PM, AP, IESCE 29

LSD [Link]
STUDENTS

T₂ T₃
x1 x2 x3 x4 x1 x2 x3 x4
(0,1,2,3) 0 0 2 2

(0,1,8,9) 0 0 2 (0,1,2,3,8 0 2 2 B
2 2
,9,10,11)
(0,2,4,6) 0 2 2 0 A

(0,2,8,10) 2 0 2 0

(1,3,9,11) 2 0 2 1

(2,3,10,11) 2 0 1 2
Prime cubes = A , B
(8,10,9,11) 1 0 2 2

Prepared By [Link] PM, AP, IESCE EDULINE 59

Prime cube table

Prime Cubes 0 1 2 3 4 6 8 9 10 11

A(0,2,4,6) X X X X

B(0,1,2,3,8,9,10,11) X X X X X X X X

Essential Prime cubes = A, B

= 0220 + 2022
= A’D’ + B’

Prepared By [Link] PM, AP, IESCE EDULINE 60

Prepared By Mr. EBIN PM, AP, IESCE 30

LSD [Link]
STUDENTS

T₀
x1 x2 x3 x4

8 1 0 0 0 Weight =1
Eg 2: f=∑(6,7,8,9)+d(10,11,12,
6 0 1 1 0
13,14,15)
9 1 0 0 1
Weight =2
10 1 0 1 0

12 1 1 0 0
7 0 1 1 1

11 1 0 1 1 Weight =3
13 1 1 0 1
14 1 1 1 0
Weight =4
15 1 1 1 1

Prepared By [Link] PM, AP, IESCE EDULINE 61

T₁
x1 x2 x3 x4 (7,15) 2 1 1 1
(8,9) 1 0 0 2
(11,15) 1 2 1 1
(8,10) 1 0 2 0
(13,15) 1 1 2 1
(8,12) 1 2 0 0
(14,15) 1 1 1 2

(6,7) 0 1 1 2
(6,14) 2 1 1 0

(9,11) 1 0 2 1
(9,13) 1 2 0 1
(10,11) 1 0 1 2
(10,14) 1 2 1 0
(12,13) 1 1 0 2
(12,14) 1 1 2 0
Prepared By [Link] PM, AP, IESCE EDULINE 62

Prepared By Mr. EBIN PM, AP, IESCE 31

LSD [Link]
STUDENTS

T₂ T₃
x1 x2 x3 x4 x1 x2 x3 x4
(8,9,10,11) 1 0 2 2

(8,9,12,13) 2 0 2 (8,9,10,11,12 2 2 2 B
1 1
,13,14,15)
(8,10,12,14) 1 2 2 0

(6,7,14,15) 2 1 1 2 A

(9,11,13,15) 1 2 2 1
Prime cubes = A , B
(10,11,14,15) 1 2 1 2
(12,13,14,15) 1 1 2 2

Prepared By [Link] PM, AP, IESCE EDULINE 63

Prime cube table

Prime Cubes 6 7 8 9

A(6,7,14,15) X X

B(8,9,10,11,12,13,14,15) X X

• For creating prime cube table, we will not consider Don’t care
terms
Essential Prime cubes = A, B
= 2112 + 1222
= BC + A

Prepared By [Link] PM, AP, IESCE EDULINE 64

Prepared By Mr. EBIN PM, AP, IESCE 32

LSD [Link]
STUDENTS

T₀ Eg 3: f=∑(2,6,13,14,15,18,26,30)
x1 x2 x3 x4 x5

2 0 0 0 1 0 Weight =1

6 0 0 1 1 0
Weight =2
18 1 0 0 1 0

13 0 1 1 0 1
Weight =3
14 0 1 1 1 0
26 1 1 0 1 0

15 0 1 1 1 1

30 1 1 1 1 0 Weight =4

Prepared By [Link] PM, AP, IESCE EDULINE 65

T₁
x1 x2 x3 x4 x5

(2,6) 0 0 2 1 0 A

(2,18) 2 0 0 1 0 B

(6,14) 0 2 1 1 0 C

(18,26) 1 2 0 1 0 D

(13,15) 0 1 1 2 1 E
(14,15) 0 1 1 1 2 F

(14,30) 2 1 1 1 0 G

(26,30) 1 1 2 1 0 H

Prepared By [Link] PM, AP, IESCE EDULINE 66

Prepared By Mr. EBIN PM, AP, IESCE 33

LSD [Link]
STUDENTS

Prime cube table

Prime Cube 2 6 13 14 15 18 26 30
A(2,6) X X
B(2,18) X X
C(6,14) X X
D(18,26) X X
E(13,15) X X
F(14,15) X X
G(14,30) X X
H(26,30) X X

Essential prime cube= E

Prepared By [Link] PM, AP, IESCE EDULINE 67

Selective Prime cube table

Prime Cube 2 6 14 18 26 30
A(2,6) X X
B(2,18) X X
C(6,14) X X
D(18,26) X X
E(13,15)
F(14,15) X
G(14,30) X X
H(26,30) X X

• Here, we cannot apply the dominance relation. This type of

function is called Cyclic function. For solving cyclic functions, we
use branching method.
Prepared By [Link] PM, AP, IESCE EDULINE 68

Prepared By Mr. EBIN PM, AP, IESCE 34

LSD [Link]
STUDENTS

• In the above table, F(14,15) gets deleted, being dominated by both

G and C
• In branching method, we select say A, so that we delete A(2,6) and
(2,6) minterms from the above table.

D and G are selected

= E + {A + D + G}
Prepared By [Link] PM, AP, IESCE EDULINE 69

• Another solution, when we select B, we delete B(2,18) and (2,18)

minterms from the table

C and H are selected

= E + {B + C + H}

Prepared By [Link] PM, AP, IESCE EDULINE 70

Prepared By Mr. EBIN PM, AP, IESCE 35

LSD [Link]
STUDENTS

T₀ Eg 4: f=∑(0,1,3,5,7-10,13,14,15,17,21,25,29)
x1 x2 x3 x4 x5
7 0 0 1 1 1
0 0 0 0 1 0 Weight =0 0
13 1 1 0 1
Weight =3
1 0 0 0 0 1 14 0 1 1 1 0
Weight =1
8 0 1 0 0 0
21 1 0 1 0 1
3 0 0 0 1 1 1 1 0 0 1
25
5 0 0 1 0 1
15 0 1 1 1 1
9 0 1 0 0 1 Weight =4
Weight =2
29 1 1 1 0 1
10 0 1 0 1 0

17 1 0 0 0 1

Prepared By [Link] PM, AP, IESCE EDULINE 71

T₁ x1 x2 x3 x4 x5 (9,25) 2 1 0 0 1
(10,14) 0 1 2 1 0 B
(0,1) 0 0 0 0 2 (17,21) 1 0 2 0 1
(0,8) 0 2 0 0 0 (17,25) 1 2 0 0 1
(1,3) 0 0 0 2 1 (7,15) 0 2 1 1 1
(1,5) 0 0 2 0 1
(13,15) 0 1 1 2 1
(1,9) 0 2 0 0 1
(13,29) 2 1 1 0 1
(1,17) 2 0 0 0 1
(14,15) 0 1 1 1 2 C
(8,9) 0 1 0 0 2
(8,10) 0 1 0 2 0 A (21,29) 1 2 1 0 1
(3,7) 0 0 2 1 1 (25,29) 1 1 2 0 1
(5,7) 0 0 1 2 1
(5,13) 0 2 1 0 1
(5,21) 2 0 1 0 1
(9,13) 0 1 2 0 1
Prepared By [Link] PM, AP, IESCE EDULINE 72

Prepared By Mr. EBIN PM, AP, IESCE 36

LSD [Link]
STUDENTS

T₂ x1 x2 x3 x4 x5

(0,1,8,9) 0 2 0 0 2 D
(1,3,5,7) 0 0 2 2 1 E
(1,5,9,13) 0 2 2 0 1
(1,5,17,21) 2 0 2 0 1
(1,9,17,25) 2 2 0 0 1

(5,7,13,15) 0 2 1 2 1 F

(5,13,21,29) 2 2 1 0 1

(9,13,25,29) 2 1 2 0 1

(17,21,25,29) 1 2 2 0 1

Prepared By [Link] PM, AP, IESCE EDULINE 73

T₃
x1 x2 x3 x4 x5

(1,5,9,13,17,21,25,29) 2 2 2 0 1 G

Prime cubes = A, B, C, D, E, F, G
• Next we create prime cube table.

Prepared By [Link] PM, AP, IESCE EDULINE 74

Prepared By Mr. EBIN PM, AP, IESCE 37

LSD [Link]
STUDENTS

Prime cube table

Prime Cube 0 1 3 5 7 8 9 10 13 14 15 17 21 25 29
A(8,10) x x
B(10,14) x x
C(14,15) x x
D(0,1,8,9) x x x x
E(1,3,5,7) x x x x
F(5,7,13,15) x x x x
G(1,5,9,13,17,21,25,29) x x x x x x x x

Essential prime cube= D,E,G

Prepared By [Link] PM, AP, IESCE EDULINE 75

Selective Prime cube table

Prime Cube 10 14 15
A(8,10) x
B(10,14) x x
C(14,15) x x
F(5,7,13,15) x

Now we apply row domination

Selective prime cube= B, F
Final solution = D+ E+ G + {B + F}
= 02002+00221+22201+01210+02121
= A’C’D’ + A’B’E + D’E + A’BDE’ +A’CE

Prepared By [Link] PM, AP, IESCE EDULINE 76

Prepared By Mr. EBIN PM, AP, IESCE 38