# GATE2004-59

3.4k views

Which are the essential prime implicants of the following Boolean function?

$f(a, b, c)= a' c+ ac'+b' c$

1. $a' c$ and $ac'$
2. $a' c$ and $b' c$
3. $a' c$ only.
4. $ac'$ and $bc'$

retagged

$f(a,b,c) = a'c+ac'+b'c$

We can write these product of sum terms into canonical product of sum form.

$f(a,b,c) = \underbrace{a'b'c}_{001}+\underbrace{a'bc}_{011}+\underbrace{ab'c'}_{100}+\underbrace{abc'}_{110}+\underbrace{ab'c}_{101}+\underbrace{a'b'c}_{001}$

$f(a,b,c) = \sum(1,3,4,5,6)$

Now, we can draw the k-map for these minterms.

• Prime implicant of $f$ is an implicant that is minimal - that is, the removal of any literal from product term results in a non-implicant for $f$.
• Essential prime implicant is an prime implicant that cover an output of the function that no combination of other prime implicants is able to cover.

Prime implicants are$:a'c,b'c,ab',ac'$

Essential prime implicants are$:a'c,ac'\:\text{(green color)}$.

References:

selected by
1
Perfect explanation.
0

No. of Implicants = No. of Minterms = 5

Please, correct me if i am wrong.

1

@ayushsomani

It is not true.

1

@ayushsomani

Number of implicants $=$ number of minterms $+$ number of subcubes of size $2$

Number of implicants $= 5 + 4 = 9$

PS: Number of implicants $=$  number of subcubes of size $2^{0} \:+$  number of subcubes of size $2^{1} +$  number of subcubes of size $2^{2} +$ number of subcubes of size $2^{3}$

0

If prime implicant is the group of one's, then what is the difference between prime implicant & implicant

0

@MRINMOY_HALDER

see this

From the above comment

$\implies$ All prime implicant is also implicant but the reverse is not true.

0
In this example, they are saying y = AB + ABC + BC

all 3 are implicants, Can an implicants be subset of other implicant ??

If ABC is an implicant then it's the subset of both AB & BC, but implicant should not be subset of another, right??
0
The last line is valid for prime implicant not for implicant.

Using K map $f = ac' + a'c$

edited
1
yes you are right, b'c is selective prime implicant.
3

Just to see it visually ;)

Clearly $A\bar{C}$ and $\bar{A}C$ cover cells that are not covered by any others.

0

Essential prime implicant: A prime implicant that includes one or more distinguished one cells. Essential prime implicants are important because a minimal sum contains all essential prime implicants.

Reference:

1
Someone please edit the answer. f is not a$\overline{c}$ + $\overline{a}$c

f = a$\overline{c}$ + $\overline{a}$c + $\overline{b}$c

or

f = a$\overline{c}$ + $\overline{a}$c + a$\overline{b}$

EPIs are a$\overline{c}$ , $\overline{a}$c
1

## Related questions

1
11.6k views
A 4-bit carry look ahead adder, which adds two 4-bit numbers, is designed using AND, OR, NOT, NAND, NOR gates only. Assuming that all the inputs are available in both complemented and uncomplemented forms and the delay of each gate is one time unit, what is the ... Assume that the carry network has been implemented using two-level AND-OR logic. 4 time units 6 time units 10 time units 12 time units
Consider the partial implementation of a 2-bit counter using T flip-flops following the sequence 0-2-3-1-0, as shown below. To complete the circuit, the input X should be $Q_2^c$ $Q_2 + Q_1$ $\left(Q_1 + Q_2\right)^c$ $Q_1 \oplus Q_2$
Consider a multiplexer with $X$ and $Y$ as data inputs and $Z$ the as the control input. $Z=0$ selects input $X$, and $Z=1$ selects input $Y$. What are the connections required to realize the 2-variable Boolean function $f=T+R$, without using any additional hardware? $\text{R to X, 1 to Y, T to Z}$ $\text{T to X, R to Y, T to Z}$ $\text{T to X, R to Y, 0 to Z}$ $\text{R to X, 0 to Y, T to Z}$
A circuit outputs a digit in the form of $4$ bits. $0$ is represented by $0000$, $1$ by $0001$, …, $9$ by $1001$. A combinational circuit is to be designed which takes these $4$ bits as input and outputs $1$ if the digit $\geq$ $5$, and $0$ otherwise. If only AND, OR and NOT gates may be used, what is the minimum number of gates required? $2$ $3$ $4$ $5$