Minimization refers to the process in which we simplify the algebraic expressions of any given boolean function. This process is very important as it helps in the reduction of the overall cost and complexity of an associated circuit.
In this article, we will take a look at the Minimization of Boolean Functions according to the GATE Syllabus for CSE (Computer Science Engineering). Read ahead to learn more.
Table of Contents
Minimization of Boolean Functions
We can express every Boolean function in the form of a product of maxterms or a sum of minterms. We have discussed this in the Representation of Boolean Functions. Now since the total number of literals present in such expressions is usually pretty high (also the complexity of the gates of digital logic implementing a Boolean function is related directly to the algebraic expression’s complexity from which the function would be implemented), it is preferable that we simplify the given algebraic expression to its most simplified form.
This process in which we simplify the given algebraic expression present in a boolean expression is known as minimization. This minimization is very crucial since it helps us in the reduction of cost and the overall complexity of an associated circuit.
For instance, the function F = x’y’z +x’yz + xy’ can be minimized to F = x’y + xy’. Here are the circuits that are associated with the expressions given above –
It is very clear from the image given above that the minimized version of any expression requires comparatively lesser numbers of logic gates. It also substantially reduces the overall complexity of the circuit. Hence, minimization is very important to discover the most economical form of equivalent representation of a given boolean function. We can perform minimization using the K-Map method or Algebraic Manipulation. Every method has its own pros and cons.
Minimization using Algebraic Manipulation
Out of all the methods that we use for the process of minimization, this method is the simplest. It is the most suitable for any medium-sized expression that involves 4 or 5 variables in total. Remember that algebraic manipulation is basically a manual method. And thus, it is very much prone to blunders and human error.
Here are the Common Laws that we use in the process of algebraic manipulation:
A + A’ = 1
A + A’B = A +B
A + AB = A
Example 1 – Let us minimize the boolean function given as follows using the method of algebraic manipulation-
F = ABC’D’ + ABC’D + AB’C’D + ABCD + AB’CD + ABCD’ + AB’CD’
Solution – The properties used here refer to the 3 most common laws mentioned above.
F = ABC’ (D’ + D) + AB’C’D + ACD (B + B’) + ACD’ (B + B’)
= ABC’ + AB’C’D + ACD + ACD’ Using Property- 1
= ABC’ + AB’C’D + AC (D + D’)
= ABC’ + AB’C’D + AC Using Property-1
= A (BC’ + C) + AB’C’D
= A (B +C) + AB’C’D Using Property-2
= AB + AC + AB’C’D
= AB + AC + AC’D Using Property-2
= AB + AC + AD Using Property-2
Minimization Using K-Map
The method of algebraic manipulation, as we witnessed above, is pretty long, cumbersome, and tedious to follow for every expression. Instead, we can use the K-Map method, which is much faster. It can be used to solve the Boolean Functions up to five variables. You can learn more about K-Map by visiting here.
Example 2 – Let us consider the same expression that we have used in example-1 and then minimize it using the K-Map method instead of the algebraic manipulation method.
Solution – A K-Map of 4 variables of the expression is given here:
The figure given above highlights the prime implicants here in red, green, and blue.
The blue one extends to 4 squares, and it gives us – AC
The red one extends to 4 squares, and it gives us – AD
The green one extends to the whole third row, and it gives us – AB
Thus, the minimized Boolean expression would be – AB + AC + AD
Practice Problems on Minimization of Boolean Functions
1. Simplify the expression: P’(P + QR) + (PC + Q’R).
a) (PQ’R + QR’)
b) (P’Q + R’)
c) (P + QR)
d) PC
Answer – (b) (P’Q + R’)
2. Find the simplified term A’ (M’ + A’) (M + M’A)?
a) MA’
b) M’A
c) M + A
d) M’A’
Answer – (a) MA’
3. Simplify the expression: FT’ + F’ + T’F’.
a) F’ + T
b) FT’
c) (FT)’
d) T’ + F
Answer – (c) (FT)’
4. What would be the simplification value of the following expression: AV(A + V’) + A(V + V’)?
a) A
b) A + V’
c) (1 + A)
d) AV + A’V’
Answer – (d) AV + A’V’
5. Minimize the Boolean expression given below using the Boolean identities:
F(J, K, L) = (J + KL’) (JK’ +L)
a) J + K + L’
b) JL’ + K
c) K + JL
d) J (K’ + L)
Answer – (d) J (K’ + L)
FAQs
How many ways are there to simplify the Boolean functions?
There are two methods that help us in the reduction of a given Boolean Function. These are the algebraic manipulation method, which is longer, and the K-map method, which is shorter.
What do we mean by minimization of boolean functions?
Minimization refers to the process in which we simplify the algebraic expressions of any given boolean function. This process is very important as it helps in the reduction of the overall cost and complexity of an associated circuit.
Why do we simplify Boolean expressions?
There are numerous benefits as to why we must simplify Boolean functions before implementing them in any hardware. For starters, a reduced number of gates would ultimately decrease the considerable cost of the hardware, reduce the heat that the chip generates, and, most importantly, would greatly increase the speed.
Keep learning and stay tuned to get the latest updates on GATE Exam along with GATE Eligibility Criteria, GATE 2023, GATE Admit Card, GATE Syllabus, GATE Previous Year Question Paper, and more.
Also Explore,
- Combinational Circuits
- Boolean Algebra
- Laws of Boolean Algebra
- Introduction of K-Map (Karnaugh Map)
- Various Implicants in K-Map
- Representation of Boolean Functions
- Combinational and sequential circuits
- Flip-Flop Types, Conversion and Applications
- The Base of Number System
- Conversion to Base 10
- Number System Notes
- Decimal to Binary Conversion
- Decimal to Hexadecimal Conversion
- Decimal to Octal Conversion
Comments