GATE CS Mastery
Cheat sheets

GATE CS 2015 Set 2 · Digital Logic

Question 47

NATPrinted as CS Q.372 marksNo negative markingMedium (estimate)

Question

The number of min-terms after minimizing the following Boolean expression is _____.

[D′+AB′+A′C+AC′D+A′C′D]′[D' + AB' + A'C + AC'D + A'C'D]'
Official answer and solution
Official answer
1
From
Official GATE 2015 answer key

Solution

Simplify the Boolean expression using standard algebraic minimization theorems.

Let E=D′+AB′+A′C+AC′D+A′C′DE = D' + AB' + A'C + AC'D + A'C'D.
We minimize EE before taking its complement.

  1. Combine the last two terms:
AC′D+A′C′D=(A+A′)C′D=C′D.AC'D + A'C'D = (A + A')C'D = C'D.
  1. Combine D′D' and C′DC'D using rule X+X′Y=X+YX + X'Y = X + Y:
D′+C′D=D′+C′.D' + C'D = D' + C'.
  1. Combine C′C' with A′CA'C:
C′+A′C=C′+A′.C' + A'C = C' + A'.
  1. Now the expression is:
E=D′+C′+A′+AB′.E = D' + C' + A' + AB'.

Combine A′A' with AB′AB':

A′+AB′=A′+B′.A' + AB' = A' + B'.

Thus:

E=A′+B′+C′+D′.E = A' + B' + C' + D'.

By De Morgan's laws, E=(ABCD)′E = (ABCD)'.

Now compute the complement E′E':

E′=[(ABCD)′]′=ABCD.E' = [(ABCD)']' = ABCD.

The minimized expression is the single minterm ABCD=m15ABCD = m_{15}.
The number of minterms is 1.

Final answer

1

Common trap

Counting the minterms of the uncomplemented expression (which has 15 minterms) instead of taking the outer complement.

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

Source

Paper
GATE 2015 Computer Science and Information Technology (CS) Session 2
Question
47 of 65, printed as CS Q.37
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.