GATE CS 2025 Set 2 | Question 43

MSQ · 2 marks

Given the following Karnaugh Map for a Boolean function \(F(w, x, y, z)\):

Four-variable Karnaugh map with wx labelling the rows and yz labelling the columns; the individual rows and columns carry no labels. The rows read, from top to bottom: 1 0 0 1, 0 1 1 0, 0 1 1 0, 1 0 0 1.

Which one or more of the following Boolean expression(s) represent(s) \(F\)?

  1. Option A: \(\overline{w}\,\overline{x}\,\overline{y}\,\overline{z} + w\overline{x}\,\overline{y}\,\overline{z} + \overline{w}\,\overline{x}y\overline{z} + w\overline{x}y\overline{z} + xz\) (correct)
  2. Option B: \(\overline{w}\,\overline{x}\,\overline{y}\,\overline{z} + \overline{w}\,\overline{x}y\overline{z} + w\overline{x}yz + xz\)
  3. Option C: \(\overline{w}\,\overline{x}\,\overline{y}\,\overline{z} + w\overline{x}\,\overline{y}\,\overline{z} + w\overline{x}\,\overline{y}z + xz\)
  4. Option D: \(\overline{x}\,\overline{z} + xz\) (correct)

Answer

(A), (D)

Explanation

Read the map with the usual Gray-code order (00, 01, 11, 10) for \(wx\) and \(yz\). The four corner 1s are the cells with \(x = 0, z = 0\), and the central block of four 1s has \(x = 1, z = 1\). So \(F = \overline{x}\,\overline{z} + xz\), which is option D.

  • A: its four 4-literal terms are exactly the four corner cells, and \(\overline{x}\,\overline{z}(\overline{w}\,\overline{y} + w\overline{y} + \overline{w}y + wy) = \overline{x}\,\overline{z}\), so A equals D.
  • B: \(w\overline{x}yz\) has \(x = 0, z = 1\), a 0 cell, and two corner cells are missing.
  • C: \(w\overline{x}\,\overline{y}z\) is also a 0 cell, and two corner cells are missing.

Answer: A, D