68 votes 68 votes Suppose only one multiplexer and one inverter are allowed to be used to implement any Boolean function of $n$ variables. What is the minimum size of the multiplexer needed? $2^n$ line to $1$ line $2^{n+1}$ line to $1$line $2^{n-1}$ line to $1$line $2^{n-2}$ line to $1$line Digital Logic gatecse-2007 digital-logic normal multiplexer + – Kathleen asked Sep 21, 2014 • edited Jun 19, 2018 by Pooja Khatri Kathleen 31.6k views answer comment Share Follow See all 10 Comments See all 10 10 Comments reply Show 7 previous comments Asim Siddiqui 4 commented Oct 25, 2018 i edited by Asim Siddiqui 4 Oct 25, 2018 reply Follow Share https://gateoverflow.in/2751/gate1996-2-22 https://gateoverflow.in/2182/gate2010-9 https://gateoverflow.in/1923/gate2014-1-45 i think these three questions are very much related to this question (especially the last one). 6 votes 6 votes Prashant bhardwaj commented Jul 17, 2022 reply Follow Share actually for this , we can generalize if you have n variable function then , one 2^n x 1 MUX is enough without additional hardware(not gate , nor gate , and gate ……….) 2. one 2^n-1 x 1 MUX + 1 inverter is enough 3. one 2^n-2 x 1 MUX + additional hardware 6 votes 6 votes Atharva007 commented Aug 21, 2022 reply Follow Share any one wants in depth explanation of this question, you can refer this video lecture. https://youtu.be/4487X-8FXsI Hope this helps. 2 votes 2 votes Please log in or register to add a comment.
–2 votes –2 votes Simple logic is...you can not get A' and B' (or any 2 variables ) from single not gate...................to use 2^(n-2)line to 1 mux BhaRgav MoRadiya answered Jan 24, 2016 BhaRgav MoRadiya comment Share Follow See all 0 reply Please log in or register to add a comment.
