Arunkumar Khannur's Software Testing Knowledge Center
   
 

9.12 Prime Implicant Tables for obtaining Irredundant Expressions


We saw in Section 9.7.4 and 9.8 that all the prime implicants are not always required to form irredundant minimal expressions based on some cost to be minimized. We need to develop a procedure by which we could choose those prime implicants which constitute minimal expressions.

The minimal expression with reference to some cost criterion will contain a set of prime implicants so that each minterm of the function subsumes atleast one prime implicant in this set.

A tabulation which express the relationships between the prime implicants of a complete Boolean function and the minterms of a function is called the prime implicant table. Consider the function in Example in Section 9.10.3, f = Σm (2, 3, 4, 5, 7). The prime implicants were found to be-a b, a-b, a c and b c. While writing the prime implicant table, the min terms are placed along the horizontal axis and the prime implicants along the vertical axis, as shown for this example in Table 9.31.


Begin with the first minterm and place a ‘×’ mark in all rows where the minterm subsumes the prime implicant. Both the minterms -a b-c and-a b c subsume prime implicant -a b. Hence, a ‘×’ is placed undcr columns m2 and m3, corresponding to the a-b row. Similarly, both the minterms abc and ab csubsume prime implicant ab. Hence a ‘×’ is placed under columns m4 and m5 corresponding to the ab row. Minterm abc subsumes both prime implicants ac as well as bc. Hence, a ‘×’ is placed under column m7 corresponding to both ac row and be row. In the case of incomplete Boolean function min- terms corresponding to don’t care states are not placed along the horizontal axis. Only minterms for which the function equals 1 are placed along the horizontal axis in the prime implicant table.

Example
Write the prime implicant table of the function f (a, b, c, d) = Σm (0, 1, 2, 5, 10, 11, 14, 15) of Example 9.8 in Section 9.10.1.
Solution: The prime implicants obtained in Example 9.8 were abd. a bc. acd. bcd and ac The prime implicant table is shown below.


We saw in Section 9.7 that irredundant disjunctive normal forms were those with the minimal number of prime implicants. Further removal of any prime implicants would not preserve the definition of the function.

The minimal set of prime implicants without altering the function definition can be obtained from the prime implicant table. A set of prime implicants are so chosen that removing any prime implicant from this set would render one or more columns in the table without ‘X’ marks along the rows of the remaining prime implicants in the set. This means that some of the minterms would cease to imply the function.

In Table 9.31, we sec that together with -a b and a-b. by either choosing a c or b c, all the minteims would be covered.

Thus, the irredundant disjunctive normal expressions are
1. f (a, b, c) =-a b + a-b + a c and
2. f(a, b, c) =-a b + a-b + b c

The minimal form can be identified by computing the cost of (1) and (2) based on some Cost criterion.
 
 
Khannur's Book
Arunkumar Khannur, Software Testing - Techniques and Applications, Published by Pearson Publications, 2011 (ISBN:978-81-317-5836-6; Pages:341 + xxii)
Follow Khannur
         
Khannur's Company
ISQT Process & Consulting Services Pvt. Ltd., Bangalore, INDIA
Khannur's Software Testing Forum
STEP-AUTO Forum
 Contact Khannur
ISQT Process & Consulting Services Pvt. Ltd.
#732, 1st Floor, 12th Main,
3rd Block, Rajajinagar,
Bangalore - 560010, INDIA
Phone: +91 80 23012511
URL: www.isqtinternational.com
Email: khannur@isqtinternational.com
Skype: arun.isqt