# Implement the boolean function using only a multiplexer

Discussion in 'Homework Help' started by popeyes, Feb 25, 2013.

1. ### popeyes Thread Starter New Member

Feb 25, 2013
6
0
Given logic signal a,b and c, along with their complements

Using only a mux to perform the function below:

It doesn't say any restriction on multiplexer, but assuming the simpler the better. It kind drive me nuts....I guess 2to1 mux will not work anyway, right?

2. ### WBahn Moderator

Mar 31, 2012
18,079
4,917
If the restriction is that you can use "only a mux" ('a' mux, as in 'one' mux), then no, you can't use a 2:1 mux, in general, for a function of three variables. There are SOME functions of three variable in which you can, but not in general.

In general, a 2^N:1 mux can implement ANY function of (N+1) variables or less and some functions of more than (N+1) variables

3. ### panic mode Senior Member

Oct 10, 2011
1,328
305
if you are using 2:1 mux, you will need 3 levels or seven units.
if you are using 8:1 mux, you can use just one.

4. ### WBahn Moderator

Mar 31, 2012
18,079
4,917
Using 2:1 muxes you only need two levels with three muxes and possibly an inverter.

Using 4:1 muxes you only need one mux and possibly an inverter.

5. ### popeyes Thread Starter New Member

Feb 25, 2013
6
0
Just curious about how to do it in 4:1 mux....

6. ### thatoneguy AAC Fanatic!

Feb 19, 2009
6,357
718
Have you diagrammed the truth table?

Column 1 Column 2 Column 3 Column 4 Column 5
A B C Out
x x x x x
x x x x
x x x x
x x x x
x x x x
x x x x
x x x x
x x x x

Here's a blank 8:1 mux
I0-I7 are Mux Inputs, S2-S0 are selectors

Column 1 Column 2 Column 3 Column 4 Column 5 Column 6 Column 7 Column 8 Column 9 Column 10 Column 11 Column 12
S2 S1 S0 I0 I1 I2 I3 I4 I5 I6 I7 Out
0 0 0 x x
0 0 1 x x
0 1 0 x x
0 1 1 x x
1 0 0 x x
1 0 1 x x
1 1 0 x x
1 1 1 x x

Quote the post, fill in the Truth Table (swap numbers for each 'x'), post results, then fill in MUX entries.

Last edited: Feb 27, 2013
absf likes this.
7. ### panic mode Senior Member

Oct 10, 2011
1,328
305
just do the truth table and see what comes out. if i'm not mistaken (it's late and i'm tired) this should be it:

File size:
5.5 KB
Views:
98
8. ### WBahn Moderator

Mar 31, 2012
18,079
4,917
Come on, panic mode, you have been around long enough to know better than to just post solutions!

9. ### WBahn Moderator

Mar 31, 2012
18,079
4,917
Think about how you would implement a 2-input function using just a 2:1 mux. You have two inputs, A and B. Use one of them to select which channel of the mux to use. So let's use A for that. You now need to bring a signal into input D0 of the mux that is the correct signal given A=0 and, likewise, you need to bring in the signal into input D1 of the mux that is the correct signal given A=1. In either case, the signal can only depend on B and there are only four possibilities:

 B 0 1 B B' 0 0 1 0 1 1 0 1 1 0

Use the one you need.

It can help to write the truth table for your 2-input function this way

 B A=0 A=1 0 1 1 1 1 0

So we tie the D0 input HI and apply B' to D1. The result is a 2-input NAND gate.

10. ### thatoneguy AAC Fanatic!

Feb 19, 2009
6,357
718
Since Panic Mode just posted the answer, I'll fill this in. I did the truth table quick, so unsure if it is correct, but you get the idea.

Function:
A'C+A'B+AB'C'

Column 1 Column 2 Column 3 Column 4
A B C Out
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 0

Here's a blank 8:1 mux
I0-I7 are Mux Inputs, S2-S0 are selectors

Column 1 Column 2 Column 3 Column 4 Column 5 Column 6 Column 7 Column 8 Column 9 Column 10 Column 11 Column 12
S2 S1 S0 I0 I1 I2 I3 I4 I5 I6 I7 Out
0 0 0 0 0
0 0 1 1 1
0 1 0 1 1
0 1 1 1 1
1 0 0 1 1
1 0 1 0 0
1 1 0 0 0
1 1 1 0 0

--ETA: DOH!, I messed it up, but somebody can fix it, I don't want to re-do that table.

11. ### WBahn Moderator

Mar 31, 2012
18,079
4,917
As you say, since panic mode has posted the solution, we can go further.

It would be nice if we had a simple way to get the mux inputs by just Boolean manipulation. Well, we can. First, expand things into SOP form:

A'(B + C) + (A' + B + C)'
A'B + A'C + AB'C'

Now choose all but one of the variables to be your select lines.

If A and B are the select lines, then we need something of the form:

A'B'(?) + A'B(?) + AB'(?) + AB(?)

This is the function for a 4:1 MUX. Each ? will be replaced with 0, 1, C, or C'

So expanding our function, we get

A'B + A'C + AB'C'
A'B + A'(B+B')C + AB'C'
A'B + A'BC + A'B'C + AB'C'
A'B(1+C) + A'B'C + AB'C'
A'B + A'B'C + AB'C'
A'B(1) + A'B'(C) + AB'(C') + AB(0)

So I get

A'B'(C) + A'B(1) + AB'(C') + AB(0)

Now panic mode used CB as the two channel selects, so for that choice it would be

C'B'() + CB'() + C'B() + CB()

A'B + A'C + AB'C'
A'B(C+C') + A'(B+B')C + AB'C'
A'BC + A'BC' + A'B'C + B'C + AB'C'
AB'C' + A'BC' + (1+A')B'C + A'BC
AB'C' + A'BC' + B'C + A'BC

Reordering the factors in each term to match the pattern:

C'B'(A) + C'B(A') + CB'(1) + CB(A')

Which is not quite the solution panic mode had.

Where we differ is CB'A, where his solution has that outputing a 0 and mine has it outputting a 1.

Looking back at the original expression

A'(B + C) + (A' + B + C)'

It appears that panic mode is correct and mine has an error. Looking back, the error is pretty obvious and, upon fixing it, you can eliminate the two lines that follow it. But I'm going to leave finding it as an exercise for the reader (at least for now).