
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 tcr.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:9788131758366; Pages:341 + xxii) 
Follow Khannur 

Khannur's Company 

ISQT Process & Consulting Services Pvt. Ltd., Bangalore, INDIA

Khannur's Software Testing Forum 

STEPAUTO 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 
