GATE2025_CS1_Q42

Consider the following four variable Boolean function in sum-of-product form F(b₃, b₂, b₁, b₀) = Σ(0, 2, 4, 8, 10, 11, 12).

where the value of the function is computed by considering b₃b₂b₁b₀ as a 4-bit binary number, where b₃ denotes the most significant bit and b₀ denotes the least significant bit. Note that there are no don't care terms. Which ONE of the following options is the CORRECT minimized Boolean expression for F?

✅ Final Answer:

The correct answer is option (A): b₁b₀ + b₂b₀ + b₁b₂b₃

🔹 Short Answer:

To find the minimal expression, we use a 4-variable Karnaugh map (K-map). By plotting the minterms (0, 2, 4, 8, 10, 11, 12) and grouping the 1s, we identify three essential prime implicants. These groups correspond to the terms b₁b₀, b₂b₀, and b₁b₂b₃. The sum of these terms gives the minimal Sum-of-Products (SOP) expression.

🔸 Long Answer:

The standard method to minimize a Boolean function in SOP form is by using a Karnaugh map (K-map). This visual method helps in easily identifying groups of adjacent minterms, which leads to a simplified Boolean expression.

Step 1: Set up the 4-Variable K-Map

The function is F(b₃, b₂, b₁, b₀) = Σ(0, 2, 4, 8, 10, 11, 12). We will create a 4x4 K-map with variables b₃b₂ for the rows and b₁b₀ for the columns. We then place a '1' in the cells corresponding to each minterm.

Step 2: Group the 1s to Form Prime Implicants

We look for the largest possible groups of 1s (in powers of 2: 8, 4, 2, 1).

• Group 1 (Red Quad): The column of 1s in cells 0, 4, 8, and 12.
  • b₃b₂ changes from 00 → 01 → 11 → 10. Both b₃ and b₂ are eliminated.
  • b₁b₀ is constant at 00.
  • This gives the term b₁b₀.
• Group 2 (Blue Quad): The corner 1s in cells 0, 2, 8, and 10.
  • b₃b₂ changes from 00 → 10. b₃ changes, but b₂ is constant at 0.
  • b₁b₀ changes from 00 → 10. b₁ changes, but b₀ is constant at 0.
  • This gives the term b₂b₀.
• Group 3 (Green Pair): The pair of 1s in cells 10 and 11.
  • b₃b₂ is constant at 10.
  • b₁b₀ changes from 11 → 10. b₀ changes, but b₁ is constant at 1.
  • This gives the term b₃b₂b₁.

Step 3: Identify Essential Prime Implicants (EPIs)

An EPI is a prime implicant that covers at least one minterm that no other prime implicant can cover.

• Minterm 4 is only covered by the red group (b₁b₀). So, it's an EPI.
• Minterm 2 is only covered by the blue group (b₂b₀). So, it's an EPI.
• Minterm 11 is only covered by the green group (b₃b₂b₁). So, it's an EPI.

Since all three prime implicants are essential, the minimal expression is the sum of these three terms.

Step 4: Form the Final Expression

Summing the EPIs gives the minimal SOP expression:

F = b₁b₀ + b₂b₀ + b₁b₂b₃

This matches option (A) exactly.

Bibliography:
- Mano, M. M., & Ciletti, M. D. (2017). Digital Design. Pearson.
- Wakerly, J. F. (2017). Digital Design: Principles and Practices. Pearson.

Ask your doubts in comment form our GURUJEE will reply ASAP, click notify me button so that you get notified on reply.