Answer would be (B) "3 Gate will be needed to design the o/p see below

The Gateway to Computer Science Excellence

+15 votes

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$

+3

@prateek

Your solution is wrong. We cannot take 3 IP OR as by default we have to take only 2 IP ones. Also terms beyond 9 will be don't cares.

Your solution is wrong. We cannot take 3 IP OR as by default we have to take only 2 IP ones. Also terms beyond 9 will be don't cares.

+1

Prateek's answer is right, Since min no. of gates have been asked so we can assume 3-i/p gate is available and for the don't care part , he has taken 1s in place of don't care.

or A + BC + BD => A + B(C + D) only 2 i/p gates are required.

or A + BC + BD => A + B(C + D) only 2 i/p gates are required.

+37 votes

Best answer

Answer should be **(B).** As according to question, truth table will be like:

$A B C D$ $f$

$0 0 0 0$ $0$

$0 0 0 1$ $0$

$0 0 1 0$ $0$

$0 0 1 1$ $0$

$0 1 0 0$ $0$

$0 1 0 1$ $1$

$0 1 1 0$ $1$

$0 1 1 1$ $1$

$1 0 0 0$ 1

$1 0 0 1$ 1

$1 0 1 0$ do not care

$1 0 1 1$ do not care

$1 1 0 0$ do not care

$1 1 0 1$ do not care

$1 1 1 0$ do not care

$1 1 1 1$ do not care

Using this truth table we get $3$ sub cube which are combined with following minterms $A (8,9,10,11,12,13,14,15)$, $BD( 5,13,7,15)$ and $BC(6,7,14,15)$

So, $f = A+ BD +BC= A+ B(C+D)$

So, minimum gate required $2$ OR gate and $1$ AND gate $= 3$ minimum gate..

0

flash12 **Don't care (X) **refers to the set of input for which the output of the function does not matter or a set of inputs that is known to never occur. Now, that being said, technically it leaves a function non-deterministic as we do not know what output the function will give on these set of inputs. However, when a circuit is realized it can only be deterministic; meaning you're in a way forced to define the output for the function even at those positions for which the input is known not to occur.

Now, we do something clever, in order to minimize our circuitry we assume the values of these don't cares in such a way that the overall expression for the function has minimum literals and minterms and thus a smaller circuit.

Coming back to the question, if you closely look, you'll see that the octet formed for deriving term **A** in the answers just takes all those don't cares to be 1. This does not mean you have changed the function. The function is known to never take those values and we can thus play with them for our benefit. Just draw K-Map and you'll see.

Please note, this a very intuitive yet useful way of thinking about don't cares. I suggest that you read more about them from standard text

+9

10-15 is taken as don't care because the question says that if the "**digit"** >=5. From 10 to 15 they are not a digit number. So we don't care about them.

+3 votes

We should get output 1 for values>=5

Making truth table for problem

A B C D Op

0 0 0 0 0

0 0 0 1 0

0 0 1 0 0

0 0 1 1 0

0 1 0 0 0

0 1 0 1 1

0 1 1 0 1

0 1 1 1 1

1 0 0 0 1

1 0 0 1 1

1 0 1 0 X

1 0 1 1 X

1 1 0 0 X

1 1 0 1 X

1 1 1 0 X

1 1 1 1 X

Putting this in kmap and solving

49

Here crucial point is that we need to make pair of 8 elements using don’t cares also…so final expression is

A+BD+BC

A+B(C+D)

Hence we’ll use two OR gate and one AND gate so total 3 gates.

Ans (B) part.

Making truth table for problem

A B C D Op

0 0 0 0 0

0 0 0 1 0

0 0 1 0 0

0 0 1 1 0

0 1 0 0 0

0 1 0 1 1

0 1 1 0 1

0 1 1 1 1

1 0 0 0 1

1 0 0 1 1

1 0 1 0 X

1 0 1 1 X

1 1 0 0 X

1 1 0 1 X

1 1 1 0 X

1 1 1 1 X

Putting this in kmap and solving

49

Here crucial point is that we need to make pair of 8 elements using don’t cares also…so final expression is

A+BD+BC

A+B(C+D)

Hence we’ll use two OR gate and one AND gate so total 3 gates.

Ans (B) part.

+2 votes

We should get output 1 for values>=5

Making truth table for problem

A | B | C | D | Op |

0 | 0 | 0 | 0 | 0 |

0 | 0 | 0 | 1 | 0 |

0 | 0 | 1 | 0 | 0 |

0 | 0 | 1 | 1 | 0 |

0 | 1 | 0 | 0 | 0 |

0 | 1 | 0 | 1 | 1 |

0 | 1 | 1 | 0 | 1 |

0 | 1 | 1 | 1 | 1 |

1 | 0 | 0 | 0 | 1 |

1 | 0 | 0 | 1 | 1 |

1 | 0 | 1 | 0 | X |

1 | 0 | 1 | 1 | X |

1 | 1 | 0 | 0 | X |

1 | 1 | 0 | 1 | X |

1 | 1 | 1 | 0 | X |

1 | 1 | 1 | 1 | X |

Putting this in kmap and solving

Here crucial point is that we need to make pair of 8 elements using don’t cares also…so final expression is

A+BD+BC

- A+B(C+D)

Hence we’ll use two OR gate and one AND gate so total 3 gates.

Ans (B) part.

52,215 questions

60,006 answers

201,215 comments

94,685 users