1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Design a logic gate for each different output

  1. Nov 25, 2012 #1
    1. The problem statement, all variables and given/known data

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

    2. Relevant equations


    3. 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?
    Last edited by a moderator: May 6, 2017
  2. jcsd
  3. Nov 25, 2012 #2
    oh wow sorry about the size of that image!-Fixed
    Last edited: Nov 25, 2012
  4. Nov 25, 2012 #3
    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,
  5. Nov 26, 2012 #4
    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.
  6. Nov 26, 2012 #5
    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

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

    didn't seem like it could do much for me?
  7. Nov 26, 2012 #6
    what I got was this as my statement...

  8. Nov 26, 2012 #7
    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.
  9. Nov 26, 2012 #8
    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:

    [itex]\begin{matrix} a/bc & 00 & 01 & 11 &10 \\ 0 & 0 & 1 & 0 &1 \\ 1 & 1 & 0 & 0 & 0 \end{matrix}[/itex]
  10. Nov 26, 2012 #9
    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.
  11. Nov 26, 2012 #10
    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?

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

    which gives me [itex]\bar{Q_1}=\bar{A}\cdot\bar{B}\cdot\bar{C}+A\cdot B\cdot C[/itex]
    Last edited: Nov 26, 2012
  12. Nov 26, 2012 #11
    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 [Broken]http://media.newschoolers.com/uploads/images/17/00/58/56/28/585628.png [Broken]

    PS. thank you for putting the time in to help me!
    Last edited by a moderator: May 6, 2017
  13. Nov 26, 2012 #12


    User Avatar

    Staff: Mentor

    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?
  14. Nov 26, 2012 #13


    User Avatar

    Staff: Mentor

    http://physicsforums.bernhardtmediall.netdna-cdn.com/images/icons/icon2.gif [Broken] 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!
    Last edited by a moderator: May 6, 2017
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook