# Simplifying a MUX's truth table

I found this truth table for a 4-to-1 MUX:

(circuit for context)

I know (I think?) that if I were to make a truth table with 2^6 variables and simplified it I'd get the same SOP as I'd get with this one. My question, how was the big truth table simplified with don't-cares to become like the one in the example? What was the thinking behind it?

• @Tyler Not quite... what about when A=0 ? – SilenceOnTheWire Dec 5 '19 at 1:03

The Select signals dictate which input is reflected on the output of the multiplexer. The don't cares show that the output is not affected by those inputs. If you were to increase the number of inputs for the multiplexer, you have to scale your number of Select signals accordingly. The SOP would be dictated based on what input you want on the output, based on your Select signals.

The diagram seems to be a bit misleading, it would make more sense to me if the output showed:

• Output Q = A, when inputs b = 0 and a = 0
• Output Q = B, when inputs b = 0 and a = 1
• Output Q = C, when inputs b = 1 and a = 0
• Output Q = D, when inputs b = 1 and a = 1

My question, how was the big truth table simplified with don't-cares to become like the one in the example? What was the thinking behind it?

I don't think the authors started out with a "big truth table." I think they started out thinking very directly. First off, they developed $$\a\$$ and $$\\overline{a}\$$ and $$\b\$$ and $$\\overline{b}\$$ so they could form up all four permutations as inputs to each of four NAND gates. Only one of the four NAND gates would be enabled to pass along their remaining input, which are $$\A\$$, $$\B\$$, $$\C\$$, and $$\D\$$. Since these are NAND gates, their output of the only enabled NAND will be the inverted sense of its input. The rest, being disabled, will have "1" as their output. Only the enabled gate will have the inverted sense of its input at the NAND gate output.

So they figured they'd invert the outputs of these NANDs, so that the logic sense remained the same as the input, and then feed that into a simple OR gate to get the output.

Yet, the final gate is shown as another NAND. But as I said, it really should be seen as a simple OR gate with inverted inputs. It's output is the OR of all of its inputs, after inversion. For all the disabled prior NAND gates, the inverted input to the inverted-input OR gate is "0" and therefore don't play a part in the output. But for the only enabled prior NAND, it's output is the inverted sense of its input. But the inverted input OR gate inverts that back, so it simply passes along the original sense of the selected input to the output.

I think the designers saw this in their mind's eye (except this stupid editor doesn't provide 4-input OR gates, so I had to fabricate one):

simulate this circuit – Schematic created using CircuitLab

It's not complicated. And I think they didn't care if anyone wanted to write up a full table and attempt to solve it, letting others worry about that if they wanted to do so. They just knew how to write it out to get the job done without anything more than a straight-forward "do it this very obvious way" approach.