GATE EE 2014 Set 2 — Question 60

The given Boolean function is in Sum of Products (SOP) form:
$F(A,B,C,D) = \sum m(0,1,3,7,11)$The question asks for the minimized expression, and the options are in Product of Sums (POS) form. To find the minimized POS expression for a function F, we first find the minimized SOP expression for its complement, F', and then apply De Morgan's theorem.The minterms of the function are {0, 1, 3, 7, 11}. For a 4-variable function, the maxterms (which are the minterms of F') are all the other indices from 0 to 15.
Maxterms of F = Minterms of F' = {2, 4, 5, 6, 8, 9, 10, 12, 13, 14, 15}.We will now use a K-map to find the minimal SOP for F'.The 4-variable K-map for F' (grouping the 1s which correspond to the maxterms of F) is:Now, we find the essential prime implicants (EPIs) by grouping the 1s:The set of EPIs is {$C\bar{D}, B\bar{C}, A\bar{C}, AB$}. Let's check if these EPIs cover all the minterms of F'.

• $C\bar{D}$ covers {2, 6, 10, 14}
• $B\bar{C}$ covers {4, 5, 12, 13}
• $A\bar{C}$ covers {8, 9, 12, 13}
• $AB$ covers {12, 13, 14, 15}

The union of these sets is {2, 4, 5, 6, 8, 9, 10, 12, 13, 14, 15}, which covers all the minterms of F'. Therefore, the minimal SOP expression for F' is the sum of these EPIs:
$F' = C\bar{D} + B\bar{C} + A\bar{C} + AB$To find the minimal POS expression for F, we take the complement of F' and apply De Morgan's theorem:
$F = (F')' = (C\bar{D} + B\bar{C} + A\bar{C} + AB)'$
$F = (C\bar{D})' \cdot (B\bar{C})' \cdot (A\bar{C})' \cdot (AB)'$
$F = (\bar{C} + D) \cdot (\bar{B} + C) \cdot (\bar{A} + C) \cdot (\bar{A} + \bar{B})$Rearranging the terms to match the options:
$F = (\bar{B} + C)(\bar{A} + C)(\bar{A} + \bar{B})(\bar{C} + D)$This matches option (A).