The usual GATE question does not ask you to implement a three-variable function with the obvious 8:1 multiplexer. It asks for a 4:1 MUX, then expects you to decide whether each data input should be 0, 1, the remaining variable, or its complement.
That smaller-MUX method becomes straightforward once you build one entered-variable table. Two truth-table rows that differ only in the leftover variable can behave in exactly four ways, so every data input resolves to 0, 1, that variable, or its complement.
Two ways a MUX implements a Boolean function
A multiplexer selects one data input and copies it to the output. Its select lines therefore provide a natural way to address the rows of a Boolean function's truth table.
The direct method for an n-variable function uses all n variables as select inputs. It needs a 2^n:1 MUX, and every data input is simply 0 or 1. For a three-variable function, use an 8:1 MUX, connect A, B, and C as selects, and put the truth-table output on I0 through I7.
The economical method uses only n-1 variables as select inputs. The remaining variable is allowed to appear on the data lines, either directly or complemented. As a result, any n-variable Boolean function can be implemented with a 2^(n-1):1 MUX. This is the fact behind the common GATE constraint, "use a 4:1 MUX to implement a three-variable function."
The entered-variable table procedure
Suppose the function uses A, B, and C. Choose A and B as the select variables, with A as the most significant select bit. C is the entered variable.
For each fixed value of AB, inspect the two truth-table rows obtained from C=0 and C=1. The pair of function values tells you the data input immediately:
F when C=0 | F when C=1 | Connect the data input to |
|---|---|---|
0 | 0 | 0 |
1 | 1 | 1 |
0 | 1 | C |
1 | 0 | C' |
That four-row table is the entire technique. The pattern 0,1 follows C, while 1,0 follows C'. Do not expand the function algebraically unless the question specifically asks for it.
Worked example: F(A,B,C) = sum of minterms 1, 2, 4, 7
Implement F(A,B,C) = Σm(1,2,4,7) with a 4:1 MUX. Use A as S1, the most significant select input, and B as S0. That leaves C for the data inputs.
Now group the minterms by AB:
A | B | Rows covered | F at C=0 | F at C=1 | Required input |
|---|---|---|---|---|---|
0 | 0 | m0, m1 | 0 | 1 | I0 = C |
0 | 1 | m2, m3 | 1 | 0 | I1 = C' |
1 | 0 | m4, m5 | 1 | 0 | I2 = C' |
1 | 1 | m6, m7 | 0 | 1 | I3 = C |
The reasoning row by row is worth saying aloud once:
AB=00 selects I0. Minterm 0 is absent and minterm 1 is present, so the output changes from 0 to 1 as C changes from 0 to 1. Therefore I0=C.
AB=01 selects I1. Minterm 2 is present and minterm 3 is absent, so the output changes from 1 to 0. Therefore I1=C'.
AB=10 selects I2. Minterm 4 is present and minterm 5 is absent, again giving I2=C'.
AB=11 selects I3. Minterm 6 is absent and minterm 7 is present, giving I3=C.
The final wiring is I0=C, I1=C', I2=C', I3=C, with select lines S1=A and S0=B.
Now verify all eight inputs, not only the four selected minterms. For ABC=001, I0 supplies C=1, so m1 is present. For 010, I1 supplies C'=1, so m2 is present. For 100, I2 supplies C'=1, so m4 is present. For 111, I3 supplies C=1, so m7 is present. At 000, 011, 101, and 110, the selected data expression evaluates to 0. The circuit therefore produces exactly Σm(1,2,4,7).
The direct 8:1 version and when to use it
The same function is easier to wire on an 8:1 MUX. Connect A, B, and C to the three select lines. Then set I1=I2=I4=I7=1 and I0=I3=I5=I6=0.
This version needs no entered variable because every input line represents one complete minterm address. It is useful when the question permits an 8:1 MUX or asks you to read a function from a given circuit. It is not the minimum-size solution. A constrained 4:1 question is testing whether you can compress pairs of rows into C or C'.
Decoders, encoders and adders turn up in the same question family, and combinational circuits, multiplexers, decoders and adders covers them alongside the MUX.
Building a bigger MUX from smaller MUXes
An 8:1 MUX can be built as a binary tree of 2:1 MUXes. The first level needs four units, the second needs two, and the final level needs one. The count is 4+2+1=7.
In general, a 2^n:1 MUX needs 2^n-1 units of size 2:1. You can see this either as a geometric sum or as the number of internal nodes in a full binary selection tree. Another common construction uses two 4:1 MUXes for the lower selection and one 2:1 MUX for the final choice, again producing an 8:1 MUX.
Traps that flip the wiring
Swapping the select order. If B becomes the most significant select bit, I1 and I2 no longer represent the same row pairs. Write S1 and S0 before filling the table.
Allowing only constants on data inputs. In the smaller method, C and C' are valid inputs. Excluding them defeats the purpose of the method.
Reading the minterm index backwards. With A as the most significant function variable, ABC=100 is minterm 4, not minterm 1.
Ignoring the word minimum. A three-variable function fits directly in an 8:1 MUX, but its minimum general realization uses a 4:1 MUX plus the remaining variable.
Complementing the wrong pattern. The pair 0,1 is C. The pair 1,0 is C'. Check it against C=0 before committing.
How GATE tests MUX realization
The question may ask for the minimum-size MUX and its four data inputs. It may show a wired MUX and ask which Boolean function it computes. It may also combine realization with cascade counting, such as the number of 2:1 units needed for a larger MUX.
Digital Electronics coverage is fixed for each cycle in the brochure on the official GATE portal of the organising IIT. Confirm the current syllabus there instead of assuming that an older subject list or marks distribution still applies. Use the GATE preparation category to keep the topic in the larger revision plan.
Short version and next step
For an n-variable function, start with a 2^(n-1):1 MUX. Choose n-1 high-order variables as selects, pair the two rows that differ only in the leftover variable, and map each pair to 0, 1, that variable, or its complement.
Then solve the same example once without looking at the table. Use the GATE Test Series for timed practice, followed by the Digital Electronics combinational-circuit MCQ set for another round of pattern recognition. KnowledgeGate's question bank carries about 1,500 Digital Electronics questions for this work.
