calculator of karnaugh map simplification 4 variables rules method simplify boolean expression using k-map how to solve in k map ?
Simplification of Boolean Expression
To reduce the requirement of hardware, it is necessary to simplify the boolean expression. boolean expression can be simplified using
1. Algebric simplification
2. Karnaugh map method.
3. Quine MC Cluskey method.
Algebric Method
In algebric method, boolean theorems are used to simplify the expression.
For example
Y (A, B, C) = (A + B) (A + B + D) D
= (A + B) (AD + BD + DD)
= (A + B) (AD + BD) [DD = 0]
= (AAD + ABD + BAD + BBD)
= ABD + ABD + BD [AA = 0 and BB = B]
= ABD + (1 + A) BD [1 + A = 1]
= ABD + BD
= BD (1 + A) [ 1 + A = 1]
= BD
Karnaugh Map Simplification
K-map is a graphica tachnique to simplify boolean expression, it provides a systematic method for simplifying and manipulating boolean expressions.
K-map contains cells. two variable maps contain four cells. three variable map contain eight cells, four-variable maps contains 16 cells and n-variable map contains 2n calls.
Representation of K-map
The logic function can be represented by input and output conditions or boolean functions. each cell assigned a cell number, the cell number is calculated from columns and rows.
Representation of Truth Tabl K-map
The truth table defines, how the inputs are related. the representation of truth table in the output state of a digital system in cells of k-map corresponding to input conditions.
For example the truth table of three variable digital systems is given as
Its k-map representation is shown below.
Representation of SOP on K-map
Boolean expression in SOP may or may not be in a standard form. firstly the expression is converted into standard SOP and then 1’s are marked in each cell corresponding to the midterm and remaining cells are filled with 0’s.
For example Let us take a boolean expression
Y (A, B, C) = AB + BC + ABC
The standard SOP form will be
Y (A, B, C) = AB (C + C) + (A + A) BC + ABC
Y (A, B, C) = ABC + ABC + ABC + ABC + ABC
Y (A, B, C) = ABC + ABC + ABC + ABC
AB (111) = M7 ABC (110) = M6
ABC (010) = M2 ABC (001) = 1
The boolean expression can also be represented as Y (A, B, C) = M (1, 2, 6, 7)
Representation of POS on K-map
Firstly converted POS form into standard POS form and then 0’s are entered in each cell corresponding to the maxterms of expression and then remaining cells are filled with 1’s.
For example Let us take a boolean expression
Y (A, B, C) = (A + B) (B + C) (A + B + C)
= (A + B + CC) (AA + B + C) (A + BC)
Y (A, B, C) = (A + B + C) (A + B + C) (A + B + C) (A + B + C) (A + B + C)
A + B + C (000) = M0 A + B + C (010) = M2
A + B + C (001) = M1 A + B + C = (110) = M6
The boolean expression can be written as
Y (A, B, C) = M (0, 1, 2, 6)
The k-map representation of the above expression is shown.
Grouping the Adjacent cell
Two cells are said to be adjacent if
1. These are vertically above each other or are in the top and bottom cells of a column.
2. These are horizontally side by side or in the left and right most cells of a row.
in combining adjacent cells these differ in one variable only because of the use of gray code.
Types of Combination for Simplification
The following terms can be defined with respect to k-map simplification :
pair Group of two adjacent minterms. A pair eliminates one variable in output expression.
For example let Y = ABCD + ABCD. Its k-map representation is
After solving with the help of K-map we get
Y = BCD
Quad
Group of four adjacent minterms. A quad eliminates two variables in output expression. it can appear in various ways as shown below.
Octet Group of eight adjacent minterms. an octet eliminates three variables in output expression. it can appear in the given ways-
Redundant Group A redundant group is a group in which all the elements in this group are covered by some other groups.
Consider the example shown, here m5 m7 m13 m15 form a quad (G1). However, all elements of this group are covered by the adjacent groups. hence, G1 Becomes a redundant group and
Example 13. Simplify the boolean function
F (w, x, y, z) = [0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 14]
Sol. the k-map representation is shown in figure.
Don’t Care Condition
In some logic circuits, certain input conditions never occur therefore the corresponding output never appears.
The outputs corresponding to these inputs are indicated by ‘X’ [Cross] and called as don’t care condition.
The Boolean function can be specified in one of the following ways :
1. In terms of minterms and don’t care conditions
Y (A, B, C, D) = M(0, 1, 2, 4, 8, 10) + d (5, 7)
2. In terms of maxterms and don’t care conditions
Y (A, B, C, D) = IIM (0, 4, 5, 14, 15). d(1, 2, 7)
Example 14. Simplify the following Boolean Expression.
F (A, B, C, D) = (1, 3, 7, 11, 15).
Which has the don’t care conditions
d (A, B, C, D) = (0, 2, 5).
Sol. K-map representation of the given function is shown
F = (A, B, C, D) = CD + AD
Example 15. Y = IIM (4, 5, 6, 7, 8, 12) + d (1, 2, 3, 9, 11, 14)
Sol. The K-map representation of given function is
Quine-Mc Cluskey Method
As number of variables becomes more than six, it becomes difficult to form the group and simplify the boolean expression. for reducing this problem another method is used for simplifying the boolean expression. this method is known as Quine -Mc Cluskey method. it is also known as tabular method.
The steps used to simplify the boolean function using Quine-Mc Cluskey method are
1. List all the given minterms in their binary equivalent.
2. Arrange the minterms according to the number of 1’s.
3. Compare each binary number with every term in the adjacent next higher category. if they differ by one position put a check mark and write in the next column.
4. Repeat Step 3 for the resultant column and continue these cycles until no further elimination of variables takes place.
5. List the primary implicants.
6. Select the minimum number of primes that must cover all the minterms.
For example Consider the example :
Y = M (0, 2, 3, 6, 7, 8, 10, 12, 13)
1. The given minterms in binary equivalent are
0-0000 2-0010 3-0011 6-0110 10-1010 7-0111 8-1000 12-1100 13-1101
2. Arrangement of minterms according to number of 1’s.
3. Compare each binary number with every term in the adjacent next higher category and if they differ by one position put a check mark.
Logic Gates
The graphic symbols and truth tables of eight gates are shown below :
4. List the prime implicants. the group of minterms in the above table without check marks are known as prime implicants and is given by
Prime implicants Binary representation
8, 12 1-00
12, 13 110
0, 2, 8, 10 – 0-0
2, 3, 6, 7 0-1-
5. Select the minimum number of primes that must cover all the minterms. the prime implicants selection chart is shown below.
It is clear from selection chart that it is sufficient to select the prime implicants (2, 3, 6, 7) and (0, 2, 8, 10) and (12, 13).
It is not necessary to select the prime implicants (8,12) because 8 is present in (0,2, 8, 10) and 12 is present in (12, 13) and hence,
Y (A, B, C, D) = (110-) + (-0 -0) + (0 – 1 -)
Y (A, B, C, D) = ABC + BD + AC
Multilevel NAND Circuits
The general procedure for converting a multilevel AND-OR diagram into an all NAND diagram using mixed notation is as follows
1. Convert all AND gate to NAND gates with AND invert graphic symbols.
2. Convert all OR gates to NAND gates with invert OR graphic symbol.
3. Check all the bubbles in the diagram. for every bubble that is not compensated by another small circle along the same line, insert an inverter (a one input NAND gate) or complement the input lateral.
For example Cosider the multilevel Boolean function
F = (AB’ + A’B) (C + D’)
Step 1. Draw logic diagram using AND, OR and NOT
Step 2. AND gates are replaced by NAND gate and OR gates are replaced by invert OR gates.
Step 3. Replacing
NOR Implementation
The NOR operation is the dual of the NAND operation. Therefore, all the procedures and rules for NOR logic are the duals of the corresponding procedures and rules developed for NAND logic. the following steps are followed to implement multilevel NOR implementation.
1. Draw logic diagram using AND-OR gate for the given Boolean function.
2. Replace AND gate by invert AND gate and OR gate is replaced by NOR gate.
3. Check all bubbles in the diagram. for every bubble that is not compensated by another bubble along the same line insert an inverter equivalent NOR gate. the invert AND gate is replaced by NOR gate.
For example Consider the multilevel Boolean function.
F = A(BC + D) + AB
step 1. Draw logic diagram using AND, OR and NOT only.
Step 2. OR gates are replaced by NOR gate and AND gate is replaced by invert AND gate.
Example 16. If the X and Y logic inputs are available and theri complements X and not available, then what will be the minimum number of two input NAND required to implement X Y.
So, minimum four NAND gates are required to implement XOR gate.
Intro Exercise – 1
1. A number expressed in binary 2’s complement as 11011. it’s decimal equivalent value is
(a) 4
(b) 5
(c) -4
(d) -5
2. Given (125)R = (203)5. the value of radix R will be
(a) 16
(b) 10
(c) 8
(d) 6
3. The minimum number of NOR gates required to implement A (A + B) (A + B + C) is equal to
(a) 0
(b) 3
(c) 4
(d) 7
4. Consider the Boolean expression
Z = ABCD + ABCD + ABCD :
The simplified form of Z is
(a) C + D
(b) BC
(c) CD
(d) BC
5. Consider the following signed binary number A = 01101101 and B = 10110110 Where B is the 1’S complement and MSB is the sign bit. in list I operation is given and in list II resultant binary number is given and find the correct answer using the codes given below the lists.
List I List II
P. A + B 1. 00100100
Q. A – B 2. 01001001
R. B – A 3. 11001001
S. – A – B 4. 00100011
5. 11011011
6.1011011
7. 00100100
8. 01001000
Codes
P Q R S
(a) 3 6 8 7
(b) 1 6 2 5
(c) 3 4 2 5
(d) 1 4 8 7
6. Consider the signed binary number A = 00101110 and B = 11010011, where B is in 2’s complement and MSB is the sign bit in list I, operation is given and in list ii, resultant binary number is given and find the correct answer using the codes given below the lists.
List I List II
P. A + B 1. 10100101
Q. A – B 2. 00000010
R. B – A 3. 01011011
S. – A – B 4. 10100101
5. 11111111
6. 00000001
7. 11110101
8. 11011011
Codes
P Q R S
(a) 5 7 4 2
(b) 5 3 4 2
(c) 6 3 4 5
(d) 6 7 1 5
7. In the network of figure, Y can be written as
(a) X0 X1X3X5 + X2X4X5….XN-1 + ….XN-1XN
(b) X0X1X3X5 + X2X3X4…..XN + …..XN-1XN
(c) X0X1X3X5 ….XN-1 + X2X3X5 …..XN + XN-1 XN-2 + XN
(d) X0X1X3X5…..XN + X2X3X5……XN + …..+ XN-1 XN
8. In the figure shown the input condition, needed to produce X = 1, is
(a) A = 1, B = 1, C = 1,
(b) A = 1, B = 1, C = 0
(c) A = 1, B = 0, C = 0
(d) A = 0, B = 1, C = 1
9. What is dual of A + [B + (AC)] + D ?
(a) A + [B(A + C)] +D
(b) A [B + AC]+ D
(c) A + [B (A + C)] D
(d) A. [B (A + C)] D
10. Consider the following gate network :
Which one of the following gates is redundant ?
(a) Gate No. 1
(b) Gate No. 2
(c) Gate No. 3
(d) Gate No. 4
11. Which one of the following is a coincidence logic circuit?
12. The gates G1 and G2 in the figure have propagation delays of 10 ns and 20 ns respectively. if the input VI makes an abrupt change from logic 0 to 1 at time t = t0, then the output waveform V0 is
13. A boolean function F of two variables X and Y is defined as follows
F (0,0) = F(0,1) = F(1,1) = 1, F(1,0) = 0
Assuming components of X and Y are not available, a minimum cost solution for realizing F using only two input NOR gates and 2 input OR gates (each having unit cost) would have a total cost of
(a) 1 unit
(b) 4 unit
(c) 3 unit
(d) 2 unit
14. The boolean expression for the truth table shown is
(a) B (A + C) (A + C)
(b) B (A + C) (A + C)
(c) B (A + C) (A + C)
(d) B (A + C) (A + C)
15. A new binary coded pentary (BCP) number system is proposed in which every digit of a base-5 number is represented by its corresponding 3 bit binary code. for example, the base-5 number 24 will be represented by its BCP code 010100. in this numbering system, the BCP code 100010011001 corresponds to the following number in base -5 system.
(a) 423
(b) 1324
(c) 2201
(d) 4231
16. With 2’s complement representation, the range of values that can be represented on the data bus of on 8 bit microprocessor is given by
(a) – 128 to + 127
(b) – 128 to + 128
(c) – 127 to + 128
(d) – 125 to + 256
17. The number of distinct Boolean expression of 4 variable is
(a) 16
(b)256
(c) 1024
(d) 65536
18. The range of signed decimal numbers that can be represented by 6 bit 1’s complement number is
(a) – 64 to + 63
(b) – 32 to + 31
(c) – 63 to + 64
(d) – 31 to + 31
19. The point p in the folowing figure is stuck at 1. the output will be
(a) ABC
(b) A
(c) ABC
(d) A
20. The simplified boolean expression from the karnaugh map given in the figure is
(a) AC + AD + AB
(b) AC + AD + ABC
(c) AB + CD + AD
(d) AC + ACD + ABC + BCD
Answers with Solutions
1. (d) 2’s complement number MSB is 1 so, equivalent decimal number
= – (2’s complement of 11011)
= – (00101) = – 5
2. (d)
(125)R = (203)5
1 x R2 + x R1 + 5 x R0 = 2 x (5)2 + 0 x (5)1 + 3 x (5)0
R2 + 2R + 5 = 50 + 3
R2 + 2R – 48 = 0
R = 6, – 8
So, the value of radix R is 6.
3. (a)
Given function F = A (A + B) (A + B + C)
Simplifiy this
F = (A + AB) (A + B + C)
= (A + AB + AC + AB + AB + ABC)
= A + AB + AC + ABC
= A + AB + AC (1 + B)
= A (1 + B) + AC (1 + B ) = 1]
= A + AC
= A (1 + C)
= A
So, there is no NOR gate is required to implement the above boolean function.
4. (a)
Given Boolean expression
Z = ABCD + ABCD + ABCD
Z = ACD + BCD
5. ( b)
A = 01101101 and B = 10110110
(i) A + B
0 1 1 0 1 1 0 1 A
+ 1 0 1 1 0 1 1 0 B
1 0 0 1 0 0 0 1 1
1
0 0 1 0 0 1 0 0
(ii) A – B = A + B
(iii) B – A = A + B
(iv) – A – B = A + B
6. (c)
A = 00101110 and B = 11010011
(i) A + B
(ii) A – B = A + B
(iii) B – A = A + B
(iv) – A – B = A + B
7. (d)
Output of gate 1 is X0X1
Output of gate 2 is X0X1 + X2
Output of gate 3 is (X0X1 + X2) X3 = X0X1X3 + X2 X3
Output of gate 4 is X0X1X3 + X2 X3 + X4
Output of gate 5 is X0X1X3X5 + X2X3X5 + X4X5
So, output of gate n would be
X0X1X3X5…….XN + X2X3X5………XN + X4X5X7……XN + XN-1 XN
8. (d)
output of the circuit
X = (A * B). (B * C). C
For X = 1 C = 1
B . C = 1 = For this B = 1, C = 1
and A . B = 1 = For this A = 0, B = 1
Thus for X = 1
A = 0, B = 1, C = 1
9. (d) Given function = A + [B + AC] + D
Dual can be obtained by replacing AND – OR and OR – AND
So, dual of function = A . [B. (A + C)] .D
10. (b)
output of the given gate network can be written as
F = W + WZ + Z x Y
= W (1 +Z) + Z + Y
= W + Z xY
So, gate 2 is redundant.
11. (a)
X – NOR logic is called coincidence logic.
12 (b)
13 (d)
F = x + y
Since the complements are not available.
Therefore 2 units are required.
14. (a)
f = ABC + ABC = B (AC + AC) = B (A + C) (A + C)
SOP of XOR = POS of NOR
15. (d)
Given, BCD code
16. (a)
For an n -bit number the maximum negative number which can be represented in 2’s complement form is -2n-1 and maximum positive number 2n-1- 1. so, the range of 2’s complement representation
– 2n-1 to 2n-1 – 1
For n = 8 bit range will be
= – 28-1 to 28-1 – 1 = – 128 to 127
17. (d)
Number of boolean expression = 22n
For n = 4
number of boolean expression = 224 = 216 = 65536
18. (d)
The maximum positive number that can be represented by 1’s complement number is + 2n-1 – 1 and maximum negative number is – (2n-1 – 1). so, range
+ 26-1 – 1 to – (26-1 -1)
+ 31 to – 31
19. (d)
The point P is stuck 1 means the input of gate 5 is high, the output of gate 5 will be low, this low output make the output of gate 7 high. because of high and A input of gate 8, it will pass A which become A after passing gate 9. so, the output will be A.
20 (b)
Y = AC + AD + ABC