# A Combinational circuit Problem

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?

My Solution: After analyzing the patterns of the 4 bits ABCD

$\\0000\\ 0001\\ 0010\\ 0011\\ 0100\\ 0101\\ 0110\\ 0111\\ 1000\\ 1001\\$

I've come up with this Combinational Circuit

But it took me 5 gates realzize the given output. I was wondering, can we realize the given output with less number of gates ($<$ 5 gates)

• If the triangle is an inverter, you should draw a 'bubble'. Did you try a Karnaugh table ? I get /(/A * (/B + /C./D)) – TEMLIB Jan 27 '15 at 21:31

You can solve this problem on your own by writing a program to enumerate all circuits with fewer than 5 gates, and for each one, test whether it has the right truth table. The running time should be minimal, as there aren't that many circuits with fewer than 5 gates.

• By using K-Map I got this function A+BD+BC. Now what steps should I follow to make Combinational Circuit, Is there any article I can read. I've trouble implementing combinational circuit from a boolean function. – Atinesh Jan 28 '15 at 12:01
• @Atinesh, did you read my answer? My answer tells you what steps you can take. – D.W. Jan 28 '15 at 18:30