GATE 2018 CS – Question 59
Consider the minterm list form of a Boolean function $F$ given below.
$$F(P,Q,R,S)=\sum m(0,2,5,7,9,11)+d(3,8,10,12,14)$$
Here, $m$ denotes a minterm and $d$ denotes a don't care term. The number of essential prime implicants of the function $F$ is ________.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 3
Explanation
$F(P,Q,R,S)=\sum m(0,2,5,7,9,11)+d(3,8,10,12,14)$. Treat the don't-cares as 1 when forming groups, but we only need to cover the real minterms $0,2,5,7,9,11$.
**Prime implicants** (largest groups, with don't-cares):
- $\overline Q\,\overline S$: cells $0,2,8,10$
- $P\overline Q$: cells $8,9,10,11$
- $\overline Q R$: cells $2,3,10,11$
- $\overline P\,Q\,S$: cells $5,7$ (cells $13,15$ are not in $F$, so the group cannot grow)
**Essential prime implicants** (the only prime implicant covering some minterm):
- Minterm 0 is covered only by $\overline Q\,\overline S$. Essential.
- Minterm 5 (and 7) is covered only by $\overline P\,Q\,S$. Essential.
- Minterm 9 is covered only by $P\overline Q$. Essential.
- $\overline Q R$ covers only minterms 2 and 11, both already covered by essential implicants, so it is not essential.
Number of essential prime implicants $=\mathbf{3}$.