PGEE sample paper

Question

Choose the digital building blocks from the following list using which we can realize any boolean function.

(A) 2-to-1 Multiplexer

(B) 4-to-1 Multiplexer

(C) 8-to-1 Multiplexer

(D) 16-to-1 Multiplexer

(E) None of the above

Comments

MUX is functionally complete and can realize any boolean function given that we have required size of MUX to implement that function. Nx1 MUX can implement a boolean function having logN variables.

2x1 MUX can be used to form bigger MUXs and thus to implement any boolean function. 4x1 can't implement a function having only one variable. Thus only A is correct.

---

Thanks.. was confused between A and A/B/C/D

---

I think ,all A,B,C, and D are correct .. we can get 2:1 MUX which is already functionally complete using 4:1 ,8:1 ,16:1 MUXs but it should be considered as partially functionally complete device.

https://gateoverflow.in/212829/digital-logic

---

yes..I think so too

---

How will we implement one variable function with such kind of 4x1 MUX?!

---

Hey wait! Now I think none of these should be the answer, because even a 2:1 Mux needs a o and 1 as an input to act as not, which means it is only partially complete.

@Akhilesh Just how you convert a 2:1Mux to have a single variable..... once you've got 2:1 from 4:1, what can possibly go wrong in getting a single variable?

---

@Warlock I agree about 4x1 part but MUX are functionally complete. See page 10 in the below link:

http://www.eng.auburn.edu/~strouce/class/elec2200/elec2200-8.pdf

---

It is functionally complete but they are talking about building blocks. NAND NOR are also functionally complete but only AND, OR and NOT are considered as the building blocks

---

@akhilesh  ,  in the given link,  it is written that "MUX is functionally complete ".. this statement does not imply only 2:1 MUX is functionally complete..

---

"In logic, a functionally complete set of logical connectives or Boolean operators is one which can be used to express all possible truth tables by combining members of the set into a Boolean expression."

Look into the bold words. 0 and 1 are not members of the set. In the case of 2:1 MUX, F(A,B), A and B are members of the set. 

Refer this as well, https://www.geeksforgeeks.org/digital-logic-functionality-completeness/

---

@gauravkc

https://en.wikipedia.org/wiki/Functional_completeness#Characterization_of_functional_completeness

http://www.exploreroots.com/dc29.html

http://nptel.ac.in/courses/122104013/node32.html

@ankit

I agree with you. I do not have any additional points to add into my reasoning of why only option A is correct. All four can also be correct.

---

@warlock

That g4g link talks only about functionally complete "set".

---

Take some pain to see the problems below. They have given an example of a partially compete function.

---

I did. I read that link during preparation. But here in the given question they are asking about digital building blocks. And a function comes out of building block(s) itself to be either functionally complete or not.

---

yes MUX are efficient

and $2\times 1$ MUX more efficient

right?

Because if we use $4\times 1$ MUX to implement a simple AND gate, then 2 among 4 MUX lines need to be grounded

---

building block means block diagram

---

Yeah and building blocks are supposed to make work easy so that they can be produced in large quantity to implement things.

---

I think the main characteristic is they should be basic. Nobody should be able to build them. A 2x1 mux has to be made the way it should be. Hence 2x1 only must be the answer :/

---

I agree with the basic part but any MUX itself is made up of AND-OR logic gates. So we need AND-OR for MUX. Nevertheless, in the exam I would certainly pick only A.

---

@Gaurav ,I agree multiplexers are considered as digital building block but why did you  consider only 2:1 MUX as a digital building block,  why not 4:1,8:1,16:1.. 2:1 mux is functionally complete because it is giving a set which is already functionally complete.. We can do this thing by 4:1  8:1,16:1 MUX also.. We can build 2:1 mux using set {or, not} ...and we can also build 4:1,8:1,16:1 MUX using set {or, not}..  Please correct me where I m wrong..

---

Yes, all are functionally complete. But 2:1 mux is like a basic one. 4:1, 8:1 .. all others can be constructed using 2:1. Similar to as I said, NAND, NOR are functionally complete but they are not called the building blocks. The three basic gates remain the same, AND, OR and NOT.

I'm not sure but that's what I am thinking about this problem. Corrections are welcomed :)

---

But in question,  they  have not asked about basic building block...yes all other muxs can be constructed using 2:1 mux but 2:1 MUX is also constructed using other muxs..

---

Yes. But it's like disabling some functionalities to get what you want. You reduce the scope of work a 16:1 can do to make it work equal to 2:1. It is not construction. However, to convert a 2:1 mux to 16:1. you make use of multiple 2:1 to get what you want which indeed gives a sense of construction. :)

---

Can anyone give a sure answer
@joshi_nitish @Ashwin Kulkarni

---

according to question, we are neither constructing anything nor reducing the scope of any device. we are just checking ,can we build all the circuits or can we realize all the boolean functions  using MUXs.. Since all the MUXs can generate set {not,or} which is already functionally complete. So, all the multiplexers should be considered as functionally complete..

---

@ankit
draw OR  gate with 4*1 MUX

---

....

---

yes, here I₃ and I₄ actually no use rt?

that is why for efficient use we take a) as option

but surely this question will not come in GATE like standard exam

---

@ankitgupta.1729

How to construct 2*1 mux using bigger multiplexers

---

@anchitjindal07

https://gateoverflow.in/212829/digital-logic

---

@Shaik Masthan  your go on this? I had selected a,b,c,d last year but as they don't publish the result not sure about answer.

---

@tusharp now can you tell us please , your ans (a,b,c,b) was right or wrong?

Answer 1

using 2x1 mux we can derive the set   <AND,OR,NOT> . and it is functionally complete. so we can derive  any boolean function.