Design a logic gate for each different output

[richyw]

Homework Statement

http://media.newschoolers.com/uploads/images/17/00/58/56/03/585603.png

Homework Equations

None

The Attempt at a Solution

I have tried just messing around with them, and I have tried to turn this table into a "boolean" expression. I have no idea how I would begin to solve a question like this. I have never even turned a truth table with one output into an expression. Sorry, really really lost here. This prof has not explained to us how to answer this type of question!

Is there some systematic way I should approach this?

 

[richyw]

oh wow sorry about the size of that image!-Fixed

 

[richyw]

alright so I think the question might mean design a separate circuit for each outcome? even this seems to be tough. I do not think I am able to reduce the boolean expressions I am getting,

 

[aralbrec]

The simplest way to do this is by drawing up a Karnaugh map (K-map) but I think you haven't gotten that far yet. K-maps give you a graphical way to find the simplest logic equation to implement a logic equation.

Instead we can do this symbolically.

The truth table tells you when you want to generate a 1 (true) for a given set of inputs. According to your truth table, Q0 must be 1 when A=0, B=0 and C=1. A logic equation for that is Q0 = /A and /B and C. You can certainly draw a circuit for that with AND and NOT gates. But that's not all; Q0 must also be 1 when A=0, B=1 and C=0. So Q0=/A and /B and C *OR* Q0=/A and B and /C. You can write this in one equation Q0 = (/A and /B and C) or (/A and B and /C) which you can again implement with AND, OR and NOT gates.

You're still not done as you have other cases where Q0 must be 1 but I think you can see how to generate a logic equation and gates to implement that logic equation from the above. The next step will be to simplify the final logic equation to use the least number of gates possible. K-Maps help you to do it graphically but without having been taught that tool yet, you can also do it symbolically knowing the rules of boolean logic you know already.

For Q1 there are a lot of 1s. The simplest logic equation would result by trying to generate the 0s in the truth table. Generate the 0s as 1s and then take the NOT of that to make zeroes.

 

[richyw]

I have attempted to draw k-maps. I wonder if maybe I am doing them wrong? I have been able to make a circuit that works, but am sure I need to reduce it.

This is what my k-map looked like for the first one

$\begin{matrix} a/bc & 00 & 01 & 11 &10 \\ 0 & 1 & 0 & 0 &1 \\ 1 & 0 & 0 & 0 & 0 \end{matrix}$

didn't seem like it could do much for me?

 

[richyw]

what I got was this as my statement...

$$A\cdot\bar{B}\cdot\bar{C}+B\cdot\bar{A}\cdot\bar{C}+C\cdot\bar{B}\cdot\bar{A}$$

 

[aralbrec]

This is what my k-map looked like for the first one

$\begin{matrix} a/bc & 00 & 01 & 11 &10 \\ 0 & 1 & 0 & 0 &1 \\ 1 & 0 & 0 & 0 & 0 \end{matrix}$

didn't seem like it could do much for me?

The K-Map is not right. For example, you are saying Q0=1 when A=0, B=0, C=0 which is not what the truth table says.

But you are right -- the K-Map will not do much for you in this case. That is because the 1s are sparse. There are few AND terms and there isn't much in common between them so there isn't much possibility for simplification.

The situation with Q1 will be different.

 

[richyw]

alright, yeah I see that that table I posted is wrong. my one on paper is correct (I think). So in this case, is there nothing I can do to make it simpler?

edited table:

$\begin{matrix} a/bc & 00 & 01 & 11 &10 \\ 0 & 0 & 1 & 0 &1 \\ 1 & 1 & 0 & 0 & 0 \end{matrix}$

 

[aralbrec]

alright, yeah I see that that table I posted is wrong. my one on paper is correct (I think). So in this case, is there nothing I can do to make it simpler?

edited table:

$\begin{matrix} a/bc & 00 & 01 & 11 &10 \\ 0 & 0 & 1 & 0 &1 \\ 1 & 1 & 0 & 0 & 0 \end{matrix}$

No, this is a very sparse KMap which leaves few options for simplification. The 01/10 pattern on the left side of the KMap is indicative of XOR but you do not have an XOR gate available so you cannot use that to simplify the result.

 

[richyw]

ok so then for the second one. I have tried your suggestion to switch the zeros and ones and I find my k-map is even more sparse?

$\begin{matrix} a/bc & 00 & 01 & 11 &10 \\ 0 & 1 & 0 & 0 &0 \\ 1 & 0 & 0 & 1 & 0 \end{matrix}$

which gives me $\bar{Q_1}=\bar{A}\cdot\bar{B}\cdot\bar{C}+A\cdot B\cdot C$

 

[richyw]

and these are my two answers (the first one I originally had like this, the second one I needed that tip about the zeros). Do these look like the best answers then?

http://media.newschoolers.com/uploads/images/17/00/58/56/29/585629.png http://media.newschoolers.com/uploads/images/17/00/58/56/28/585628.png

PS. thank you for putting the time into help me!

 

[NascentOxygen]

There is nothing preventing you from fabricating an EXCLUSIVE-OR using the gates you have at your disposal. Q0 is very close to being EXCLUSIVE-OR together with ¬(EXCLUSIVE-OR).

For Q1, you can see that for all but one case, Q1=A+B+C (this function needing a pair of 2-input OR gates)
The exception to this being the case when A=B=C=1 (that needs a pair of 2-input AND gates)
add to this some logic to block A+B+C when A=B=C=1 (2 gates)

Looks like you'd be able to share 3 of these gates (in the arrangement needed to generate Q1) with the arrangement to produce Q0.

Will answers which use fewer gates be marked more favourably?

 

[NascentOxygen]

and these are my two answers (the first one I originally had like this, the second one I needed that tip about the zeros). Do these look like the best answers then?

http://physicsforums.bernhardtmediall.netdna-cdn.com/images/icons/icon2.gif If you need ¬B in a number of places, you should use only one inverter and run connectors to every place where ¬B is needed, not generate it anew for each input! You are using too many inverters!