Boolean Algebra & Minimization
Boolean algebra is a branch of mathematical logic or algebra in which value of the variables is binary, i.e. it can be either 0 or 1, also denoted as false and true respectively. Boolean algebra is used to simplify and analyze digital logical circuits. Boolean algebra was introduced by George Boole in 1854.
Any digital circuit can be implemented and represented using Boolean functions, but the issue is literals used in original Boolean function is usually high, and if that function is implemented using logic gates so it will increase the complexity and cost of the system. Boolean functions are directly related to algebraic expression's complexity through which we were implementing the function.
To decrease the complexity, we need to have simplified version of algebraic Boolean expression. So, the process of minimizing and simplifying a algebraic expression is known as minimization. Minimization is important to cut down cost and complexity of the circuit.
Ways of representing the functions:
- Canonical Expressions
- POS form
- SOP form
- Simplified Expressions
Before moving towards actual expression, let us understand the basic terms
- It is the product term which contains all the variables in the given function, and for that combination, the function output must be 1.
- It isrepresented by m.
- A minterm is also called a canonical product term.
- A minterm is a product term, but a product term may or may not be a minterm.
- The SOP Expression is written in the form of minterms.
- Each sum term is known as maximum term that contains all of the variables used in the function.
- It is a sum term, containing all the variables in the given function either complementary or un-complementary form, for that combination, function output must be 0.
- A maxterm is a sum term of all variables in which each variable is either in complemented form or in un-complemented form.
- A maxterm is also called a canonical sum term.
- A maxterm is a sum term, but a sum term may or may not be a maxterm.
Canonical SOP Expression
- SOP stands for sum of product terms.
- To obtain the SOP expression, Refer to the combination of truth table whose value is 1
- If a variable x is 1, represent it as x
- if variable x is 0, represent it as x'.
- In this manner, obtain All the minterm for the given function.
- Add all the minterms to get the SOP expression for the given function.
Canonical POS Expression
- POS stands for product of sum terms.
- To obtain the POS expression, Refer to those combination of truth table whose value is 0.
- If a variable X is 1, represent it as x'.
- if a variable X is 0, represent it as x,
- Represent all the variables as sum terms
- In this manner obtain all the maxterm of the given function
- Finally multiply all the product terms obtained to get the POS expression.
The following are examples of product term, minterm, sum term, and maxterm for a function of three variables a, b, and c:
- product terms: a, ac, b’c, abc, a’bc, a’b’c’, …
- minterms: ab’c, abc, a’b’c, a’b’c’, …
- sum terms: a, (a+b), (b+c), (a’+b), (a’+b’), …
- maxterms: (a+b+c), (a+b’+c), (a’+b’+c’), …
Representations of Minterm and Maxterm
Note: With' n' variables maximum possible minimum and maximum terms = 2n
With' n' variables maximum possible logic expression =
SOP (Sum of Product): A sum of product expression is two or more AND functions or functions together.
- SOP expression is used when output becomes logic 1.
- three minterms are there in the expression
POS (Product of Sum): It is the AND function of two or more OR function.
- POS expression is used when output is logic '0'.
- Three maxterms are there in the expression
Example: Sum of Product and Product Of Sum Equivalences for function F and Its Inverse Function F’.
Duality Theorem: Duality Theorem used to change positive logic into negative logic and vice-versa, we make use of dual function.
- Change each AND sign by OR sign and vice versa (↔ +)
- Complement any 0 or l appearing in expression.
- Keep variable as it is.
Minimization of Boolean Expressions
The following two approaches can be used for simplification of a Boolean expression:
- Algebraic method (using Boolean algebra rules)
- Karnaugh map method
Minimization using boolean algebra properties
All the properties are used to minimized the obtained expression, but it is not always possible to minimize the expression completely just by using the boolean algebra properties. there are the chances that expression cant be reduced further but it is not in minimal form, using boolean algebra properties. Such form of expression is known as Irreducible form/ irredundant expression.
But there are some other way to reduce an expression completely, by using K- map.
Representation of K-map
With n-variable Karnaugh-map, there are 2n cells.
- 2 –variable K Map:
- 3 –variable K Map:
- 4 –variable K Map:
Note: Once the you fill Karnaugh map with 1s, 0s and Xs as specified the remaining task is to group adjacent terms of the same state (generally 1) in groups of 2^n, where n= any rational number i.e. 1, 2, 4, 8, 16, and so on. The bigger the group of similar adjacent terms the simpler the final expression. It is also possible for groups to overlap. This happens to achieve a larger group size, hence we get more simplified final expression.
Minimization Procedure of Boolean Expression using K-map
- Construct a K-map.
- Find all groups of horizontal or vertical adjacent cells that contain 1.
- Each group must be either rectangular or square with 1, 2, 4, 8, or 16 cells.
- Each group should be as large as possible.
- Each cell with 1 on the K-map must be covered at least once. The same
- cell can be included in several groups if necessary.
- Select the least number of groups so as to cover all the 1’s.
- Adjacency applies to both vertical and horizontal borders.
- Translate each group into a product term. (Any variable whose value changes from cell to cell drops out from the term)
- Sum all the product terms.
Note: Don't care conditions can be used to provide more simplified version of a Boolean Expression.
EXAMPLE: Simplify the following equation using a K-map (Karnaugh-map):
SOLUTION: Draw the K-map and minimise.
- It should be a prime implicant.
- It should cover atleast one minterm which is not covered by any one of the prime implicant.
You can go with the detailed champion study plan for GATE CS 2021 from the following link:
Candidates can also practice 110+ Mock tests for exams like GATE, ISRO, DRDO, BARC, NIELIT, etc. with the Test Series, check the following link to avail it:
Get unlimited access to 21+ structured Live Courses all 112+ mock tests with the Online Classroom Program subscription for GATE CS & PSU Exams: