Sets, Relations, & Functions
Mathematical Logic
Group Theory
Counting & Probability
Mathematical & Recurrence
Discrete Structures
Boolean Algebra
Discrete Mathematics Resources
- Discrete Mathematics - Discussion
- Discrete Mathematics - Resources
- Discrete Mathematics - Quick Guide
Selected Reading
- Who is Who
- Computer Glossary
- HR Interview Questions
- Effective Resume Writing
- Questions and Answers
- UPSC IAS Exams Notes
Simppfication Of Boolean Functions
Simppfication Using Algebraic Functions
In this approach, one Boolean expression is minimized into an equivalent expression by applying Boolean identities.
Problem 1
Minimize the following Boolean expression using Boolean identities −
$$F (A, B, C) = A B + BC + BC + AB C $$
Solution
Given,$F (A, B, C) = A B + BC + BC + AB C $
Or,$F (A, B, C) = A B + (BC + BC ) + BC+ AB C $
[By idempotent law, BC’ = BC’ + BC’]
Or,$F (A, B, C) = A B + (BC + BC) + (BC + AB C )$
Or,$F (A, B, C) = A B + B(C + C) + C (B+ AB )$
[By distributive laws]
Or,$F (A, B, C) = A B + B.1 + C (B + A)$
[ (C + C) = 1 and absorption law (B + AB )= (B + A)]
Or,$F (A, B, C) = A B + B + C (B + A)$
[ B.1 = B ]
Or,$F (A, B, C) = B(A + 1) + C (B + A)$
Or,$F (A, B, C) = B.1 + C (B + A)$
[ (A + 1) = 1 ]
Or,$F (A, B, C) = B + C (B + A)$
[ As, B.1 = B ]
Or,$F (A, B, C) = B + BC + AC $
Or,$F (A, B, C) = B(1 + C ) + AC $
Or,$F (A, B, C) = B.1 + AC $
[As, (1 + C ) = 1]
Or,$F (A, B, C) = B + AC $
[As, B.1 = B]
So,$F (A, B, C) = B + AC $is the minimized form.
Problem 2
Minimize the following Boolean expression using Boolean identities −
$$F (A, B, C) = (A + B) (A + C)$$
Solution
Given, $F (A, B, C) = (A + B) (A + C)$
Or, $F (A, B, C) = A.A + A.C + B.A + B.C$ [Applying distributive Rule]
Or, $F (A, B, C) = A + A.C + B.A + B.C$ [Applying Idempotent Law]
Or, $F (A, B, C) = A(1 + C) + B.A + B.C$ [Applying distributive Law]
Or, $F (A, B, C) = A + B.A + B.C$ [Applying dominance Law]
Or, $F (A, B, C) = (A + 1).A + B.C$ [Applying distributive Law]
Or, $F (A, B, C) = 1.A + B.C$ [Applying dominance Law]
Or, $F (A, B, C) = A + B.C$ [Applying dominance Law]
So, $F (A, B, C) = A + BC$ is the minimized form.
Karnaugh Maps
The Karnaugh map (K–map), introduced by Maurice Karnaughin in 1953, is a grid-pke representation of a truth table which is used to simppfy boolean algebra expressions. A Karnaugh map has zero and one entries at different positions. It provides grouping together Boolean expressions with common factors and epminates unwanted variables from the expression. In a K-map, crossing a vertical or horizontal cell boundary is always a change of only one variable.
Example 1
An arbitrary truth table is taken below −
A | B | A operation B |
---|---|---|
0 | 0 | w |
0 | 1 | x |
1 | 0 | y |
1 | 1 | z |
Now we will make a k-map for the above truth table −
![K-map 1](/discrete_mathematics/images/k_map1.jpg)
Example 2
Now we will make a K-map for the expression − AB+ A’B’
![K-map 2](/discrete_mathematics/images/k_map2.jpg)
Simppfication Using K-map
K-map uses some rules for the simppfication of Boolean expressions by combining together adjacent cells into single term. The rules are described below −
Rule 1 − Any cell containing a zero cannot be grouped.
![K- map Rule 1](/discrete_mathematics/images/k_map_rule1.jpg)
Wrong grouping
Rule 2 − Groups must contain 2n cells (n starting from 1).
![K- map Rule 2](/discrete_mathematics/images/k_map_rule2.jpg)
Wrong grouping
Rule 3 − Grouping must be horizontal or vertical, but must not be diagonal.
![K- map Rule3](/discrete_mathematics/images/k_map_rule3_1.jpg)
Wrong diagonal grouping
![K- map Rule 3](/discrete_mathematics/images/k_map_rule3_2.jpg)
Proper vertical grouping
![K- map Rule 3](/discrete_mathematics/images/k_map_rule3_3.jpg)
Proper horizontal grouping
Rule 4 − Groups must be covered as largely as possible.
![K- map Rule 4](/discrete_mathematics/images/k_map_rule4_1.jpg)
Insufficient grouping
![K- map Rule 4](/discrete_mathematics/images/k_map_rule4_2.jpg)
Proper grouping
Rule 5 − If 1 of any cell cannot be grouped with any other cell, it will act as a group itself.
![K- map Rule 5](/discrete_mathematics/images/k_map_rule5.jpg)
Proper grouping
Rule 6 − Groups may overlap but there should be as few groups as possible.
![K- map Rule 6](/discrete_mathematics/images/k_map_rule6.jpg)
Proper grouping
Rule 7 − The leftmost cell/cells can be grouped with the rightmost cell/cells and the topmost cell/cells can be grouped with the bottommost cell/cells.
![K- map Rule 7](/discrete_mathematics/images/k_map_rule7.jpg)
Proper grouping
Problem
Minimize the following Boolean expression using K-map −
$$F (A, B, C) = A BC + A BC + AB C + AB C$$
Solution
Each term is put into k-map and we get the following −
![K-map Problem 1](/discrete_mathematics/images/k_map_problem1.jpg)
K-map for F (A, B, C)
Now we will group the cells of 1 according to the rules stated above −
![K-map Problem 2](/discrete_mathematics/images/k_map_problem2.jpg)
K-map for F (A, B, C)
We have got two groups which are termed as $A’B$ and $AB’$. Hence, $F (A, B, C) = A’B+ AB’= A oplus B$. It is the minimized form.
Advertisements