Hi!
Would like to receive help please.
I was asked to create a function: F=NOT(a AND b AND NOT(c)) = NOT(a) OR NOT(b) OR c
Firstly, MUX 2:1, and '1' and '0' (easy - 2 MUX 2:1, one with i0=1, i1=c, s=b, second with i0=1, i2=output mux 1, s=a).
Problem is, when they asked to implement this function without '1' and '0', only MUX 2:1 with a,b,c
I managed to reach close multiple times, with 2MUX, but its futile...

If anybody has any tips, it will be welcomed...

MOD NOTE: Moved to Homework Help from Digital Design.

 

If asked to do it using nothing but 2-input NAND gates (or 2-input NOR gates) could you do it (adhering to the constraint that only the three signals are used as input)?

If so, then the problem reduces to being able to implement a 2-input NAND function (or 2-input NOR function) using only 2:1 Muxes without using '0' or '1' as inputs.

If you can do this, you are done. If you can show that this cannot be done, you may or may not have shown that the problem has not solution. You will only have shown that a 2:1 Mux is not a universal gate in the strictest sense. While this implies that you can't implement arbitrary logic functions with it, it doesn't say that you can't implement this particular logic function with it (again, under the constraint of not using any constant inputs).

Here's a point to ponder -- is there any way to get any kind of inversion using a 2:1 Mux without using any constant inputs?

 

If asked to do it using nothing but 2-input NAND gates (or 2-input NOR gates) could you do it (adhering to the constraint that only the three signals are used as input)?

If so, then the problem reduces to being able to implement a 2-input NAND function (or 2-input NOR function) using only 2:1 Muxes without using '0' or '1' as inputs.

If you can do this, you are done. If you can show that this cannot be done, you may or may not have shown that the problem has not solution. You will only have shown that a 2:1 Mux is not a universal gate in the strictest sense. While this implies that you can't implement arbitrary logic functions with it, it doesn't say that you can't implement this particular logic function with it (again, under the constraint of not using any constant inputs).

Here's a point to ponder -- is there any way to get any kind of inversion using a 2:1 Mux without using any constant inputs?

Hi, about your last part.
That is exactly my problem, I thought of trying to create inversion using MUX, but I don't think it is possible without '1' or '0'. I tried this, with this, it will take 3 MUX 2:1 (I managed to get close with 2 MUX 2:1, but because of negativity I couldn't solve exactly).

I also tried creating '1' or '0', but also not possible here.

About the NAND or NOR part, there is difference, though MUX is built on NANDs, still, implementation by NAND is not the same as using MUX, since MUX is a "built in".

 

Hi, about your last part.
That is exactly my problem, I thought of trying to create inversion using MUX, but I don't think it is possible without '1' or '0'. I tried this, with this, it will take 3 MUX 2:1 (I managed to get close with 2 MUX 2:1, but because of negativity I couldn't solve exactly).

I don't understand what you mean by "I tried this, with this, it will take 3 MUX 2:1". It doesn't matter how many parts it takes, as long as it can be done at all. Are you saying that, using three 2:1 muxes, you got something that worked? If so, show what you got.

I also tried creating '1' or '0', but also not possible here.

Why isn't it possible? You need to be able to articulate a convincing explanation for why it is not possible. Otherwise, all you have done is establish that you didn't happen to figure out how to do it, not that it can't be done.

About the NAND or NOR part, there is difference, though MUX is built on NANDs, still, implementation by NAND is not the same as using MUX, since MUX is a "built in".

It doesn't matter how the MUX is implemented -- it is a black box that has a defined interface that you get to use, as is, as a building block. In actuality, most real 2:1 multiplexers are not implemented with NAND gates, but with smaller and faster circuit topologies.

But, if you can implement your desired function with nothing but NAND gates, and if you can figure out how to implement a NAND gate using MUXes, no matter how many muxes it might take, then all you have to do is replace each NAND gate in your function implementation with its MUX-based implementation.

The thread title indicates that this is an interview question. Good interview questions should push you a bit and force you to think about the problem and not just regurgitate memorized things. A good interviewer doesn't want to just see the solution (indeed, a solution might not exist), they want to see how you approached tackling the problem.

 

I don't understand what you mean by "I tried this, with this, it will take 3 MUX 2:1". It doesn't matter how many parts it takes, as long as it can be done at all. Are you saying that, using three 2:1 muxes, you got something that worked? If so, show what you got.



Why isn't it possible? You need to be able to articulate a convincing explanation for why it is not possible. Otherwise, all you have done is establish that you didn't happen to figure out how to do it, not that it can't be done.



It doesn't matter how the MUX is implemented -- it is a black box that has a defined interface that you get to use, as is, as a building block. In actuality, most real 2:1 multiplexers are not implemented with NAND gates, but with smaller and faster circuit topologies.

But, if you can implement your desired function with nothing but NAND gates, and if you can figure out how to implement a NAND gate using MUXes, no matter how many muxes it might take, then all you have to do is replace each NAND gate in your function implementation with its MUX-based implementation.

The thread title indicates that this is an interview question. Good interview questions should push you a bit and force you to think about the problem and not just regurgitate memorized things. A good interviewer doesn't want to just see the solution (indeed, a solution might not exist), they want to see how you approached tackling the problem.

Well, if I interpret the boolean function as NAND, so we can:
!(ab!c) = NAND(ab, !c) = NAND (NAND (NAND(a,b), NAND(a,b)), NAND(c,c)) )
Regarding interperating NAND as using MUX, i need to think about it, because I dont have '1' or '0'

 

Okay, I am pretty sure I can't implement NAND2 by using MUX without the inverter or '0' or '1'. By using a,b,c I can't do any NAND of them... I don't have proof, ( I don't know how to prove such thing) :\
I know I am supposed to think, but after tiring 3 hours, its beating me and I just give up :\

 

Okay, I am pretty sure I can't implement NAND2 by using MUX without the inverter or '0' or '1'. By using a,b,c I can't do any NAND of them... I don't have proof, ( I don't know how to prove such thing) :\
I know I am supposed to think, but after tiring 3 hours, its beating me and I just give up :\

One of the nice things about Boolean proofs is that you can do them by brute-force exhaustive enumeration of all possible conditions. When you only have a few possibilities, this is very straight-forward.

What are all of the possible two-input functions that can be implemented using a 2:1 MUX?

You have two signals, call them x and y.

You have to map those two signals onto the three inputs of the MUZ, call them d0, d1, and sel.

How many ways are there to do this?

You can also do it by contradiction.

You assume that you can implement a NAND2 using some combination of MUXes. That means that when both inputs are '0', the output has to be '1'. But, in order for the output of a MUX to be '1', what must be true of its inputs?

 

One of the nice things about Boolean proofs is that you can do them by brute-force exhaustive enumeration of all possible conditions. When you only have a few possibilities, this is very straight-forward.

What are all of the possible two-input functions that can be implemented using a 2:1 MUX?

You have two signals, call them x and y.

You have to map those two signals onto the three inputs of the MUZ, call them d0, d1, and sel.

How many ways are there to do this?

You can also do it by contradiction.

You assume that you can implement a NAND2 using some combination of MUXes. That means that when both inputs are '0', the output has to be '1'. But, in order for the output of a MUX to be '1', what must be true of its inputs?

Hi, we have 3 signals - a,b,c, not 2.
About how many way there are to input with 2 signals, its 2 * 2 * 2 = 8 (if you count without 0/1 from a,b,, just general signals)
About the NAND, yea, we need '0' in one of the inputs to be output '1', since NAND will receive '1' nonetheless of its other inputs if one of them is '0'.
But how is it proof that we cant? we need to prove that we basically can't do '0'

 

Hi, we have 3 signals - a,b,c, not 2.
About how many way there are to input with 2 signals, its 2 * 2 * 2 = 8 (if you count without 0/1 from a,b,, just general signals)
About the NAND, yea, we need '0' in one of the inputs to be output '1', since NAND will receive '1' nonetheless of its other inputs if one of them is '0'.
But how is it proof that we cant? we need to prove that we basically can't do '0'

can I make a bold statement, if this is an interview question your sitting,
a. the interviewer is looking mainly how you would go about solving this
b. an interviewer is probably looking for a sketch of the problem and your working.
c. id have to say, on what I'm seeing you have unfortunatly st this time failed selection to the next stage.

 

Hi, we have 3 signals - a,b,c, not 2.

If you want to try to do an exhaustive proof that you can't implement your 3-input function given an unlimited number of MUX chips, then you have to work your way through all possible connections of an arbitrary number of MUX parts. You would do this starting with one part and showing all of the functions that can be implemented with the various ways of connecting the three signals. But then, for each of those, you would need to consider all of the possible ways that you could add a second MUX and determine the functions that correspond to each of those. Then, for each of those, do the same while adding a third. And so on. But it doesn't go on forever. There are only a finite number of functions that are possible, so each circuit you evaluate will map to one of them. What will happen is that they will eventually you'll have a map that shows which functions you can implement given a circuit that implements one function by adding an additional MUX to the circuit. If the function you want is not represented on that map, then you can't implement it this way.

But don't go down that path. It's viable, but it's almost certainly not going to be pleasant and it's going to be very easy to make a mistake along the way by overlooking one or more possibly ways to connect the next MUX.

This is why I suggested that you first show that it can be implemented using nothing but NAND2 parts and then determine whether or not you can implement a NAND2 using nothing but MUXes.

About how many way there are to input with 2 signals, its 2 * 2 * 2 = 8 (if you count without 0/1 from a,b,, just general signals)

Yep. Just eight. And each one has either two or four rows in its truth table. Should only take a few minutes to do them all, in which case you will find that there are only four functions that you can implement. From there, it's pretty easy to show that adding additional MUXes doesn't change anything.

About the NAND, yea, we need '0' in one of the inputs to be output '1', since NAND will receive '1' nonetheless of its other inputs if one of them is '0'.
But how is it proof that we cant? we need to prove that we basically can't do '0'

I actually laid out the proof for you in prose.

It uses proof by contradiction.

You assume that a NAND2 can be implemented using some combination of 2:1 MUXes.
This means that the output must be a '1' when both inputs are a '0'. (You can also proceed working with the fact that the output must be a '0' when both inputs are a '1').
But the only way that the output of a MUX can be a '1' is for one of its data inputs to be a '1'.
But if all of the inputs are '0', then none of the inputs can be a '1'.
Hence, we have a contradiction and therefore the assumption must be invalid.

 

If you want to try to do an exhaustive proof that you can't implement your 3-input function given an unlimited number of MUX chips, then you have to work your way through all possible connections of an arbitrary number of MUX parts. You would do this starting with one part and showing all of the functions that can be implemented with the various ways of connecting the three signals. But then, for each of those, you would need to consider all of the possible ways that you could add a second MUX and determine the functions that correspond to each of those. Then, for each of those, do the same while adding a third. And so on. But it doesn't go on forever. There are only a finite number of functions that are possible, so each circuit you evaluate will map to one of them. What will happen is that they will eventually you'll have a map that shows which functions you can implement given a circuit that implements one function by adding an additional MUX to the circuit. If the function you want is not represented on that map, then you can't implement it this way.

But don't go down that path. It's viable, but it's almost certainly not going to be pleasant and it's going to be very easy to make a mistake along the way by overlooking one or more possibly ways to connect the next MUX.

This is why I suggested that you first show that it can be implemented using nothing but NAND2 parts and then determine whether or not you can implement a NAND2 using nothing but MUXes.



Yep. Just eight. And each one has either two or four rows in its truth table. Should only take a few minutes to do them all, in which case you will find that there are only four functions that you can implement. From there, it's pretty easy to show that adding additional MUXes doesn't change anything.



I actually laid out the proof for you in prose.

It uses proof by contradiction.

You assume that a NAND2 can be implemented using some combination of 2:1 MUXes.
This means that the output must be a '1' when both inputs are a '0'. (You can also proceed working with the fact that the output must be a '0' when both inputs are a '1').
But the only way that the output of a MUX can be a '1' is for one of its data inputs to be a '1'.
But if all of the inputs are '0', then none of the inputs can be a '1'.
Hence, we have a contradiction and therefore the assumption must be invalid.

Ohhh, I see now that proof by contradiction.
Thanks!