GATE CS 2017 Set 2 Q.28 (CS Q.28): Boolean Algebra and Logic Minimization

Given $f(w,x,y,z) = \sum m(0,1,2,3,7,8,10) + \sum d(5,6,11,15)$ , where $d$ represents the don’t-care condition in Karnaugh maps. Which of the following is a minimum product-of-sums (POS) form of $f(w,x,y,z)$ ?

$f = (\bar{w} + \bar{z})(\bar{x} + z)$

$f = (\bar{w} + z)(x + z)$

$f = (w + z)(\bar{x} + z)$

$f = (w + \bar{z})(\bar{x} + z)$

Official answer and solution

Official answer: A
From: Official GATE 2017 answer key

Solution

Identify the maxterms (0-entries) and don't-cares of the Boolean function $f$ , then group them on a Karnaugh map to find the minimal Product-of-Sums (POS) expression.

Given minterms $m(0, 1, 2, 3, 7, 8, 10)$ and don't-cares $d(5, 6, 11, 15)$ .
The 0-entries (maxterms) of $f$ are the remaining indices from 0 to 15:

M = \{4, 9, 12, 13, 14\}

Don't-cares available for grouping are $D = \{5, 6, 11, 15\}$ .

Group the 0-entries and don't-cares in the 4-variable K-map:

Quad 1: Maxterms $\{4, 12\}$ combined with $\{6, 14\}$ form the 4-cell group $\{4, 6, 12, 14\}$ , where $x = 1$ and $z = 0$ . In maxterm (sum) form, this gives:

(\bar{x} + z)

Quad 2: Maxterms $\{9, 13\}$ combined with don't-cares $\{11, 15\}$ form the 4-cell group $\{9, 11, 13, 15\}$ , where $w = 1$ and $z = 1$ . In maxterm (sum) form, this gives:

(\bar{w} + \bar{z})

All 0-entries $\{4, 9, 12, 13, 14\}$ are fully covered by these two prime implicants without covering any 1-minterms.

Taking the product of these sum terms gives the minimal POS expression:

f = (\bar{w} + \bar{z})(\bar{x} + z)

This matches option A.

Final answer

Common trap

Forming Sum-of-Products (SOP) instead of Product-of-Sums (POS), or grouping 1s instead of 0s.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2017 Computer Science and Information Technology (CS) Session 2
Question: 28 of 65, printed as CS Q.28
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source