ELL 101 - Introduction to Electrical Engineering

DIGITAL CIRCUITS
BOOLEAN ALGEBRA
(ANALYSIS OF BINARY LOGIC
FUNCTIONS)
Outline
 Rules of Combinational Logic (Laws of Boolean Algebra)

 Half & Full Adder and Subtractor circuits

 SOP (Sum of Products) and POS (Product of Sums) forms

of logical expressions

 Karnaugh Maps for simplifying logical expressions

2
 RECAP OF
VARIOUS
LOGIC GATES

3
 LOGIC NETWORKS
Logic gates can be interconnected to give a wide variety of functions.

A (A⋅C)

B F=(A⋅C)+B
C (A+B)
A

F=(A+B) ⋅ (B+C)
B

C (B+C)
4
 BOOLEAN IDENTITIES
A F=1 F=0 A F=1
A+1=1 1 A⋅ 0 = 0A A+A = 1
0 A

F=A A F=A A F=0

A A+A=A A⋅A = 0
A⋅1=A 1 A A

A F=A F=A F=A

A A=A A
A+0=A 0 A⋅ A=A A

5
 RULES OF COMBINATIONAL LOGIC
Laws of Boolean Algebra (‘+’ denotes ‘OR’, ‘AB’ denotes ‘A AND B’)
a) Commutative rules: A+B = B+A ; AB = BA

b) Associative rules: A+(B+C) = (A+B)+C ; A(BC) = (AB)C

c) Distributive rules: A+BC = (A+B)(A+C) ; A(B+C) = AB+AC

A+AB = A ; A(A+B) = A

d) de Morgan’s laws: A⋅B⋅C = A+B+C ; A⋅B⋅C = A+B+C

6
 RULES OF COMBINATIONAL LOGIC
Verification of distributive rule A+BC = (A+B)(A+C) via truth table

7
Laws of Boolean Algebra used for simplifying logical expressions
(Al = Ā denotes the complement/inverse/NOT of A)
A+0 = A ( Al )l = A
A +1 = 1 A + AB = A
A⋅ 0 = 0 A + Al B = A + B
A⋅1 = A A+ B = B + A
A+ A = A A⋅ B = B ⋅ A
A + Al = 1 A + B = A⋅ B
A⋅ A = A A⋅ B = A + B
A⋅ Al = 0 ( A + B)( A + C) = A + BC 8
 HALF ADDER CIRCUIT
 Takes two binary digits A and B as inputs. A B
 Gives out sum S and carry C bits as outputs.

1-bit
C
Half Adder
C = AB

S = Al B + ABl = A ⊕ B
S
9
 HALF ADDER CIRCUIT
A
A
Bl
SS = 𝐴𝐴̅ B + A𝐵𝐵
�
B C
C = AB

Al
B

A
SS = A⊕ B
B

C
C = AB
10
 FULL ADDER CIRCUIT
 Half Adder accepts only 2 input bits. If two n-bit binary numbers are to be
added, there can be a carry bit in various places also.
 Full Adder makes provision for a carry-in bit also i.e. total 3 input bits.
A B

(Carry-out) (Carry-in)
1-bit
Co Ci
Full Adder

S
(Sum)
11
 FULL ADDER CIRCUIT (SUM)

A
B S
Ci

S = 𝐴𝐴̅𝐵𝐵𝐶𝐶
� 𝑖𝑖 + 𝐴𝐴̅ B𝐶𝐶�𝑖𝑖 + 𝐴𝐴 𝐵𝐵
� 𝐶𝐶�𝑖𝑖 + 𝐴𝐴𝐴𝐴𝐶𝐶𝑖𝑖 � 𝐵𝐵𝐶𝐶
= 𝐴𝐴( � 𝑖𝑖 + B𝐶𝐶�𝑖𝑖 ) +𝐴𝐴(𝐵𝐵� 𝐶𝐶�𝑖𝑖 + 𝐵𝐵𝐶𝐶𝑖𝑖 )

S = 𝐴𝐴̅ (B ⊕ Ci ) + A B ⊕ Ci = A ⊕ B ⊕ Ci
12
 FULL ADDER CIRCUIT (CARRY OUT)

B
Co
Ci

�
Co = 𝐴𝐴BC i + A �
𝐵𝐵 C i + AB 𝐶𝐶 ̅ ̅ � �
i +𝐴𝐴𝐴𝐴𝐶𝐶𝑖𝑖 = BCi ( A + 𝐴𝐴) + A(B 𝐶𝐶𝑖𝑖 +𝐵𝐵 C ) i

Co = BCi + A( B ⊕ Ci )
13
 HALF SUBTRACTOR CIRCUIT
Performs subtraction of two bits, one is minuend A and other is subtrahend B
Has two inputs and two outputs. The two output bits, D and Bo represent the
difference and output borrow, respectively. A B

1-bit
Bo
Half Subtractor
�
Bo = 𝐴𝐴B

D = 𝐴𝐴̅ B + A𝐵𝐵
� = A⊕ B D 14
 HALF SUBTRACTOR CIRCUIT

A
D � + A𝐵𝐵
D = 𝐴𝐴B � = A⊕ B
B

A
�
Boo = 𝐴𝐴B
B
B

15
 FULL SUBTRACTOR CIRCUIT
Performs subtraction of two bits, taking into account borrow of the previous
adjacent lower bit also. Has three inputs A, B and Bi, denoting the minuend,
subtrahend, and previous borrow, respectively. The two outputs, D and Bo
represent the difference and output borrow.
A B

1-bit
Bo Bi
Full Subtractor

D 16
FULL SUBTRACTOR CIRCUIT (DIFFERENCE)

A
B D
Bi

D = 𝐴𝐴� 𝐵𝐵 � 𝐵𝐵
� B + 𝐴𝐴B � + A𝐵𝐵� 𝐵𝐵� + ABB
i i i i
� 𝐵𝐵
D = 𝐴𝐴( � B + B𝐵𝐵
� ) + A( 𝐵𝐵
� 𝐵𝐵
� + BB )
i i i i
� ⊕ B ) + A(𝐵𝐵 ⊕ 𝐵𝐵)
D = 𝐴𝐴(B
i i

D = A ⊕ B ⊕ Bi
17
FULL SUBTRACTOR CIRCUIT (OUTPUT BORROW)
A

B
Bo
Bi

B = 𝐴𝐴̅𝐵𝐵B � 𝐵𝐵
� + 𝐴𝐴B �
� + 𝐴𝐴BB + ABB
o i i i i
� 𝐵𝐵B
B = 𝐴𝐴( � � ) + BB ( A +𝐴𝐴)̅
+ B𝐵𝐵
O i i i
� ⊕ B ) + BB
B = 𝐴𝐴(B
o i i 18
 SUM OF PRODUCTS (SOP) FORM
 Two or more “product” (AND-gated) terms are “summed” (OR-
gated) to form a Boolean expression.

 Examples: AB + ABC, ABC + CDE + BCD, AB + BCD + E, etc.

 In an SOP expression, a single overbar (denoting inversion) cannot

extend over more than one variable e.g. there can be terms like ABC,
but terms like ABC are not allowed.

 In a “standard” SOP expression, each product term contains all the

input variables e.g. for 3 inputs, AB + ABC is not in standard form,
whereas ABC + ABC is in standard form. 23
 PRODUCT OF SUMS (POS) FORM
 Two or more “sum” (OR-gated) terms are taken “product” (AND-
gated) to form a Boolean expression.

 Examples: (A+B)(A+B+C), (A+B+C)(B+C+D)(C+D)E, etc.

 In an POS expression, a single overbar (denoting inversion) cannot

extend over more than one variable e.g. there can be terms like
A+B+C, but terms like A + B + C are not allowed.

 In a “standard” POS expression, each product term contains all the

input variables e.g. for 3 inputs, (A+B)(A+B+C) is not in standard
form, whereas (A+B+C)(A+B+C) is in standard form. 24
 Canonical Forms of Boolean Expressions
 The various possible standard product (AND) terms are called “minterms”,
while the standard sum (OR) terms are called “maxterms”.
 N input variables (bits) can be combined to form 2N minterms or 2N maxterms,
designated by their decimal equivalents (bits are assigned values such that each
minterm yields value 1 while each maxterm yields value 0)
X Y Z minterm designation maxterm designatio
n
0 0 0 𝑋𝑋� 𝑌𝑌� 𝑍𝑍̅ 𝑚𝑚𝑜𝑜 𝑋𝑋 + 𝑌𝑌 + 𝑍𝑍 𝑀𝑀𝑜𝑜
Note that each maxterm
0 0 1 𝑋𝑋� 𝑌𝑌𝑍𝑍
� 𝑚𝑚1 𝑋𝑋 + 𝑌𝑌 + 𝑍𝑍̅ 𝑀𝑀1
is the complement
0 1 0 � 𝑍𝑍̅
𝑋𝑋𝑌𝑌 𝑚𝑚2 𝑋𝑋 + 𝑌𝑌� + 𝑍𝑍 𝑀𝑀2
(inverse) of the
0 1 1 �
𝑋𝑋𝑌𝑌𝑌𝑌 𝑚𝑚3 𝑋𝑋 + 𝑌𝑌� + 𝑍𝑍̅ 𝑀𝑀3
corresponding minterm
1 0 0 𝑋𝑋𝑌𝑌� 𝑍𝑍̅ 𝑋𝑋� + 𝑌𝑌 + 𝑍𝑍
i.e. mi = Mi’
𝑚𝑚4 𝑀𝑀4
1 0 1 �
𝑋𝑋𝑌𝑌𝑍𝑍 𝑚𝑚5 𝑋𝑋� + 𝑌𝑌 + 𝑍𝑍̅ 𝑀𝑀5
1 1 0 𝑋𝑋� 𝑌𝑌𝑍𝑍
� 𝑚𝑚6 𝑋𝑋� + 𝑌𝑌� + 𝑍𝑍 𝑀𝑀6
(from de Morgan’s laws)
1 1 1 𝑋𝑋𝑌𝑌𝑍𝑍 𝑚𝑚7 𝑋𝑋� + 𝑌𝑌� + 𝑍𝑍̅ 𝑀𝑀7 21
 Canonical Forms of Boolean Expressions
Example: We can write the expression for function F using the truth table below
X Y Z F
0 0 0 0
F = XYZ + XY Z + XYZ (SOP form using minterms:
collect all the terms which
0 0 1 1 F = m1 + m4 + m7 give F = 1)
0 1 0 0
0 1 1 0
1 0 0 1 (
F = (X + Y + Z ) X + Y + Z )(X + Y + Z )(X + Y + Z )(X + Y + Z )
1 0 1 0
F = M 0 M 2 M 3M 5 M 6
1 1 0 0
1 1 1 1 (POS form using maxterms: collect all the terms which give F = 0)

Any Boolean function can be expressed as a sum of minterms (SOP

form) or product of maxterms (POS form).
29
 KARNAUGH MAP (K-MAP)
 Karnaugh maps are a powerful, widely used, tabular method of logic
simplification that are used to find the simplest SOP or POS form.

 Karnaugh maps (or just K-maps) allow expressions with up to four

variables to be handled in a straightforward manner, and can be used with
expressions of up to six Boolean variables.

 Each cell in the Karnaugh map corresponds to one line in the truth table.

23
 KARNAUGH MAP (K-MAP)
Steps to simplify a logic expression using a Karnaugh map are:
1. Draw the empty Karnaugh map.
2. Fill in 1’s and 0’s into the corresponding cells. (using the original
logic expression or it’s truth table.)
3. Identify and draw loops on the Karnaugh map to group together
adjacent 1’s (for SOP form) or adjacent 0’s (for POS form).
4. Create the expression for each group and combine to give the
simplified logic expression.
24
 KARNAUGH MAP (K-MAP)
1. Creating an empty Karnaugh map
 The number of inputs N defines the number of cells (2N) in the
Karnaugh map to be drawn.
 e.g. for two variables, A and B, there are four possible input states i.e.
00, 01, 11 and 10. Hence, the K-map will have 4 cells, each cell
corresponding to one particular input state.
 The small numbers in the top left corner of each cell show the decimal
equivalent of the binary input code for that cell. Notice that the cells are
arranged such that only 1-bit changes when we go to an adjacent cell.
 Each cell thus corresponds to one particular minterm mi or maxterm Mi,
where i is the decimal equivalent denoting the cell.
25
 Two-variable K-map Three-variable K-map Four-variable K-map
F = f(A,B) F = f(A,B,C) F = f(A,B,C,D)
A
A CB 0 1 BA
DC 00 01 11 10
B 0 1 0 1
00 0 1 3 2
0 1 00
0 2 3
01 4 5 7 6
01
2 3 6 7
1 11 12 13 15 14
11
4 5
10 8 9 11 10
Truth table for two variables 10
BA
C 00 01 11 10
0 1 3 2

0
4 5 7 6

1
 KARNAUGH MAP
2. Filling in the Karnaugh map
 Each cell of the Karnaugh map is filled with either a 1 or a 0
signifying the output for the input corresponding to that cell.

 The original binary function which needs to be simplified may be

provided in any one of the following forms:
• by specifying the binary/decimal numbers that correspond to an
output of 1 (i.e. sum of minterms) or output of 0 (i.e. product of
maxterms);
• a general logical/Boolean expression;
• a truth table.
37
 K-MAP FILLING EXAMPLE
Q. Map the following standard SOP expression on a Karnaugh map:
ABCD + ABC D + ABCD + ABCD + ABCD + ABCD + ABC D
CD
AB 00 01 11 10
Given expression is a sum of minterms:
00 1 1
F = ∑(0011, 0100, 1101, 1111, 1100,
0001, 1010) 01 1
= ∑m(3, 4, 13, 15, 12, 1, 10)
11 1 1 1
Fill in 1’s into the cells corresponding
to the above inputs 10 1
(rest of the cells have output 0)
 K-MAP FILLING EXAMPLE
Q. Map the following SOP expression on a Karnaugh map: A + AB + ABC
The SOP expression is not in standard form because each product term does not have three variables.
The first term is missing two variables, the second term is missing one variable, and the third term is standard.
First expand the terms numerically as follows, C
AB
(
A = A(B + B)(C + C) = AB + AB )( )
C + C = ABC + ABC + ABC + ABC
0 1

The second term is expand as, 00 1 1

AB = AB(C + C) = ABC + ABC
01 1 1
The standard SOP expression is given as,
ABC + ABC + ABC + ABC + ABC + ABC + ABC 11 1

F = ∑(011, 010, 001, 000, 101, 100, 110)

10 1 1
= ∑m(3, 2, 1, 0, 5, 4, 6)
 K-MAP FILLING EXAMPLE
Q. Map the following standard POS expression on a Karnaugh map:
(A + B + C + D)( A + B + C + D )(A + B + C + D )(A + B + C + D )(A + B + C + D )
CD
AB 00 01 11 10

Given expression is a product of maxterms:

00 0 0

F = ∏(1100, 1011, 0010, 1111, 0011)

01
= ∏M(12, 13, 2, 15, 3)
11 0 0
Fill in 0’s into the cells corresponding to the
above inputs 10 0
(rest of the cells have output 1)
 K-MAP FILLING EXAMPLE
Q. Map the following standard POS expression on a Karnaugh map:
( A + B + C )( A + B + C )(A + B + C )(A + B + C )
C
AB 0 1

Given expression is a product of maxterms: 00 0

F = ∏(000, 010, 110, 101)

01 0
= ∏M(0, 2, 6, 5)
11 0
Fill in 0’s into the cells corresponding to the
above inputs
10 0
(rest of the cells have output 1)
 KARNAUGH MAP
3. Creating groups in Karnaugh maps
When all the output values are entered, all of the 1’s (or all of the 0’s,
depending on if SOP or POS form is finally required, respectively) must
be grouped together according to the following rules:

• Each group must contain 2n adjacent cells, where n is an +ve integer.

• Each group should be made as large as possible, while satisfying the
constraint of having cells numbering to a power of 2.
• The larger the groups formed, the simpler the final function.

32
 KARNAUGH MAP
3. Creating groups in Karnaugh maps
• Each cell with output 1 (or each cell with output 0; for SOP or POS) must
be included in at least one group.
• The groups may overlap, so one cell may be included in several groups,
but any group that has all its elements included in other groups can be
ignored.
• There may be several correct minimal forms for a given logic function,
dependent upon the particular groupings that are chosen.
• Once the groups have been assigned, a logic expression can be created.
For each group, write down the common inputs (AND/product terms if
using 1s; OR/sum terms if using 0s) that describe that specific group and
combine accordingly (SOP or POS). 44
 KARNAUGH MAP
"Don't Care" Conditions
 Sometimes a situation arises in which some input variable
combinations are not allowed. For example, in a particular coding
scheme with 4 input bits called “BCD”, there are six invalid
combinations: 1010, 1011, 1100, 1101, 1110, and 1111.

 Since these unallowed states will never occur in for that particular
application, they can be treated as "don't care" terms with respect
to their effect on the output. That is, for these "don't care" terms
either a 1 or a 0 may be assigned to the output: it really does not
matter since they will never occur.
34
 KARNAUGH MAP
"Don't Care" Conditions

 The "don't care" terms can be used to our advantage on the

Karnaugh map to further simplify the Boolean expression for a
particular application.
 For each "don't care" term, an X is placed in the cell. When
grouping the 1s, some of the Xs can be treated as 1s to make a
larger grouping, while others can be treated as 0s if they cannot be
used (and vice-versa if we are grouping 0s).
 The larger a group, the simpler the resulting term will be.
35
"Don't Care" Conditions
CD
AB 00 01 11 10
Without "don't cares"
 Example: SOP form 00

Inputs Output 2 1 ⇒ ABC

ABCD Y 01 1
0000 0 2 ⇒ ABCD
0001 0 11 X X X X
0010 0
0011 0
0100 0
10 1 1 X X
Y = ABC + ABCD
0101 0 1
0110 0 CD
0111 1 AB 00 01 11 10
1000 1 With "don't cares"
00
1001 1
1010 X 2
1⇒ A
01 1
1011
1100
X
X 1 2 ⇒ BCD
11 X X X X
1101 X
1110 X
10
1111 X
1 1 X X
Y = A + BCD 36
"Don't Care" Conditions AB
CD
00 01 11
2
10 Without "don't cares"
 Example: POS form 00 0 0 0 0
1⇒ A+ C
Inputs Output 3 2 ⇒ A+ B
ABCD Y
0000 0
01 0 0 0 23 ⇒ A + C + D
0001 0 1
11 X X X X
0010
0011
0
0
(
Y = ( A + C )( A + B ) A + C + D )
10 X X
0100 0
0101 0
0110 0 CD 2
0111 1 AB 00 01 11 10 With "don't cares"
1000 1
00 0 0 0 0 1⇒ A + C
1001 1
1010 X 3 2 ⇒ A+ B
01 0 0 0
1011 X
3⇒C + D
1100 X 1
11 X X X X
1101 X
1110
1111
X
X
10 X X (
Y = ( A + C )( A + B ) C + D )
37
 SOLVED EXAMPLES
Q. Using Boolean algebra techniques, simplify this expression:
F = AB + A(B + C) + B(B + C)

Soln: F = AB + A(B + C) + B(B + C) = AB + AB + AC + BB + BC

= AB + AC + B + BC = AC + BA + B.1 + BC = AC + B.(A + 1 + C)
= AC + B.1 = AC + B
A

B B+AC
AB+A(B+C)+B(B+C)

B
C A
C
19
 SOLVED EXAMPLES
Q. Minimize the following Boolean function using algebraic manipulation:
Dll +ABC
F=ABCllD +ABCl D+AB
l
D+ABlClC
l l
D+ABCD+AB
D+ABCD+AB l l
CD+ABCD
CD+ABCD l l
+AB+AB
l
CDlCD
l l

Soln: F = ABCl (D+Dl )+ABlCl D+ACD(B+Bl )+ACDl (B+Bl )

F = ABCl + ABlCl D + ACD + ACDl
F = ABCl + ABlCl D + AC(D + Dl )
F = ABCl + ABlCl D + AC
F = A(C+BCl ) + ABlClD
F = A(C + B) + ABlClD
F = AC + AB + ABlCl D
F = AC + A(B + BlCl D)
F = AC + A(B + Cl D) = AC + AB + ACl D = A(C + ClD) + AB
F = A(C + D) + AB = AC + AD + AB 20
 SOLVED EXAMPLES
Q. Apply de Morgan's theorems to the following expressions:
(a) F = A + BC + D(E + F ) (b) F = AB + CD + EF

Soln:
(a) F = A + BC + D(E + F ) (b) F = AB + CD + EF

F =  A + BC 



D(E + F ) 

( )
 = A + BC  D + (E + F ) 




( )(CD)(EF )
F = AB

(
F = A + BC )(D+ E + F ) F = (A+ B)(C+ D )(E+ F )

( )(
F = A+ B C+ D )(E + F )
40
 SOLVED EXAMPLES
Q. Draw the circuit to implement the function F = A⋅ B + A⋅C
Simplify this function and hence redraw the reduced circuit.

A A⋅ B
Soln: F = A⋅ B + A⋅C

( )(A⋅C )
F = A⋅ B
B
A⋅ B + A⋅C

F = A⋅ B ⋅ A⋅C C
A⋅C
F = A⋅ B ⋅C
A
A⋅ B ⋅C
B
C
41
 SOLVED EXAMPLES
Q. Convert the following Boolean expression into standard SOP form: ABC + AB + ABCD

The domain of this SOP expression A, B, C, D. Take one term at a time.

The first term, ABC, is missing variable D or D, so multiply the first term by (D+D) as follows:
ABC = ABC(D + D) = ABCD + ABC D
The second term, AB, is missing variables C or C and D or D, so first multiply the second term by (C+C)
as follows:
AB = AB(C + C) = ABC + ABC
The two resulting terms are missing variable D or D, so multiply both terms by (D+D) as follows:
ABC(D + D) + ABC(D + D) = ABCD + ABC D + ABCD + ABCD
The third term, ABCD, is already in standard form.
The complete standard SOP form of the original expression is as follows:
ABC + AB + ABCD = ABC(D + D) = ABCD + ABC D + ABCD + ABC D + ABCD + ABCD + ABCD
25
 SOLVED EXAMPLES
Q. Convert the following Boolean expression into standard POS form: (A + B + C )(B + C + D )(A + B + C + D )
The domain of this POS expression A, B, C, D. Take one term at a time.
The first term, A + B + C, is missing variable D or D, so add DD as follows:

(
A + B + C = A + B + C + DD = A + B + C + D )(A + B + C + D ) Note, A + BC = ( A + B )( A + C )

The second term, B + C + D, is missing variables A or A and D or D, so AA as follows:

( )( ) (
B + C + D = B + C + D + AA = B + C + D + A B + C + D + A = A + B + C + D )(A+ B + C + D )
The third term, A + B + C + D, is already in standard form.
The complete standard POS form of the original expression is as follows:

(A + B + C )(B + C + D )(A + B + C + D )=
(A + B + C + D)( A + B + C + D )(A + B + C + D )(A + B + C + D )(A+ B + C + D ) 43
 SOLVED EXAMPLES
Q. Express the Boolean function F = A + BC as a sum of minterms (SOP).
F = A + BC
First term missing B and C variables,
(
A = A(B + B)(C + C) = AB + AB )(C + C )= ABC + ABC + ABC + ABC
Second term missing variable A,
BC=BC( A + A) = ABC + ABC
F = ABC + ABC + ABC + ABC + ABC + ABC = ABC + ABC + ABC + ABC + ABC
F = m7 + m6 + m5 + m4 + m1 In short notation
F ( A, B,C) = ∑(1, 4,5,6, 7)
F ( A, B,C) = ∑ (0, 2,3) 30
 SOLVED EXAMPLES
Q. Express F = XY + XZ as a product of maxterms (POS form).

F = XY + XZ
(
F = XY + X )(XY + Z ) = (X + X )(Y + X )(X + Z )(Y + Z )
F = (Y + X )( X + Z )(Y + Z ) (∴X + X = 1)
)
F = (X + Y + Z Z )(X + YY + Z )(X X + Y + Z ) (∴ X X = 0)

F = (X + Y + Z )(X + Y + Z )( X + Y + Z )( X + Y + Z )( X + Y + Z )( X + Y + Z ) (∴X + YY = (X + Y )(X + Y ))

F = (X + Y + Z )(X + Y + Z )( X + Y + Z )( X + Y + Z ) (∴ XX = X )
F = M 4M 5M 0M 2
F ( X ,Y , Z ) = Π(0, 2, 4,5)
F ( X ,Y , Z ) = Π(1,3,6, 7)
45
 SOLVED EXAMPLES
Q. Simplify F = ABC + ABC + ABC
into simpler SOP form using K-map C C
C
AB 0 1

AB 00

AB 01 1 AB
F = AB + BC
BC 11 1 1
AB

AB 10
 SOLVED EXAMPLES
Q. Simplify F = ∑ m(1,2,3,6)
into simpler SOP form using K-map C C C
AB 0 1 Group
1
AB 00
Group 1 ⇒ AC 1

Group 2 ⇒ BC AB 01 1 1

Group 2 11 1
AB
F = AC + BC
AB 10
 SOLVED EXAMPLES
Q. Simplify F = ∑ m(2,3, 4,5, 7,8,10,13,15)
Group
into simpler SOP form using K-map CD CD CD CD
CD 3

AB 00 01 11 10
Group
AB 00 1
1 ⇒ BD 1

AB
2 ⇒ ABC 01 1 1 1
Group 2
3 ⇒ BCD Group
AB 11 1 1 1
4 ⇒ ABD Group
AB 10 4
1 1

Group
F = BD + ABC + BCD + ABD Group 4
3
 SOLVED EXAMPLES
Q. Simplify F = ∑ m(0,5,7,8,10,12,14,15)
Group
5
into simpler SOP form using K-map CD CD CD CD CD
AB 00 01 11 10
Group Group
AB 00 1
1 ⇒ ABD 1

2 ⇒ ABC AB 01
1 1
Group
3 ⇒ ACD 2

4 ⇒ ACD AB 11 1 1 1
Group 4
4 ⇒ BCD AB 10 1 1

Group Group
F = ABD + ABC + ACD + ACD + BCD 5 3
 SOLVED EXAMPLES
Q. Use a Karnaugh map to find the minimum SOP expression of the
function: f ( A, B,C, D) = ∑ m(0, 2,5, 7,8,10,13,15)
Group
CD CD CD CD CD 2
AB 00 01 11 10
AB
00 1 1
Group
Group Group 2 AB 01
1
1 1
1 ⇒ BD
AB 11 1 1 Group
2 ⇒ BD 2
AB 10 1 1

Minimum SOP: F = BD + BD Group

2
 SOLVED EXAMPLES
Q. Use a Karnaugh map to minimize the following standard POS expression:
F = ( A + B + C)( A + B + C)( A + B + C)( A + B + C)( A + B + C)
C C C
AB 0 1 Group
1
Group A+B 00
0
1⇒ A 0

(
2 ⇒ B+C ) A+B 01
0 0

A+B
11 0
Group 2

(
F = A B+C ) A+B 10
 SOLVED EXAMPLES
Q. Use K-maps to convert the following standard POS expression into:
a) a minimum POS expression, b) a standard SOP expression, and
c) a minimum SOP expression.
F = ( A + B + C + D)( A + B + C + D)( A + B + C + D)( A + B + C + D)( A + B + C + D)( A + B + C + D)
Group 3
a) CD C+D C+D C+D C+D
AB 00 01 11 10 Group
Group 1
(
1⇒ A+ B + C ) A+B 00 0 0 0

2 ⇒ (B + C + D) A+B 01 0

3 ⇒ (B + C + D) A+B 11 0
Group 2
10
( )(B + C + D )(B + C + D )
0
Minimum POS:
SOP: F = A + B + C A+B
Group
3
b) The remaining cells are filled with 1s. CD CD CD CD CD
AB 00 01 11 10
Sum all the minterms corresponding to
these cells with output 1 to get the AB 00 1 0 0 0
standard SOP expression as:
AB 01 1
0 1 1
F = ∑(0000, 0101, 0111, 0110, 1101,
1111, 1110, 1000, 1011, 1010) AB 11
0 1 1 1

F = ABCD + ABCD + ABCD + ABCD +

AB 10 1 0 1
ABCD + ABCD + ABCD + ABCD 1
+ ABCD + ABCD

52
c)
Group
4
Group CD CD CD CD CD
AB 00 01 11 10
1 ⇒ BD
AB
2 ⇒ BC 00 1 Group
Group 1 2
3 ⇒ AC
AB 01 1 1 1
4 ⇒ BCD
AB
11 1 1 1
Group
3
Minimum SOP: F = BD + BC + AC + BCD
AB 10 1 1 1

Group
4 53
 References
 E. Hughes, J. Hiley, K. Brown, and I. M. Smith,
“Electrical and Electronic Technology,” Pearson
Education Limited, England, 2008.

 A. Anand Kumar, “Fundamentals of Digital Circuits,”

PHI Learning Private Limited, Delhi 2009.

55