Arunkumar Khannur's Software Testing Knowledge Center

9.8 Prime Implicants and Irredundant Disjunctive Expressions

Let us start with Boolean expressions that are completely specified. This section introduces some terminologies used in the development of simplification techniques.

9.8.1 Implies

Given two functions f1 and f2 the function f1 implies the function f2 if whenever f1 equals 1, f2 also equals 1. This can be alternately stated as, function f12, implies function f2 if whenever f2 equals 0, f1 also equals 0.

The first statement is illustrated with the function f1 (a, b, c) = ac + bc and f2(a, b, c) = ac + bc + ab. Tabic 9.5 shows the truth table for these functions.

Table 9.5 Truth table of f1 and f2 showing that f1 implies f2

disjunctive normal form or Sum of Product (SOP) form. It is interesting to note that the Boolean expression evaluates to 1 whenever any one of the product terms evaluates to 1. This is illustrated in Table 9.7 for the disjunctive Boolean expression.

Observe that column 7 equals 1, whenever one of the product terms in columns 4, 5 or 6 equals 1. Hence, each of the product terms implies the function in a SOP expression.s

Now, let us examine a Boolean expression in conjunctive normal form or POS form. It can be seen that in such a Boolean expression, whenever any one of the given terms evaluates to 0. the function also r:x-\ evaluate to 0. This means, that in a POS expression the function value implies each of the sum tc-r.-is. This is illustrated w ith the function f = ( a + b ) (⎯b + c ) whose truth table is shown in Table 9.8.

Notice that in the first two rows of Table 9.8. the function implies the first term (a + b). In the third row and the second last row, the function implies the second term (-b + c ).
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
 Contact Khannur
ISQT Process & Consulting Services Pvt. Ltd.
#732, 1st Floor, 12th Main,
3rd Block, Rajajinagar,
Bangalore - 560010, INDIA
Phone: +91 80 23012511
Skype: arun.isqt