# Is demultiplexer universal gate?

I want to prove that demultiplexer is universal gate. Can we build any logic gates using demultiplexer? Can we build AND, NOT, OR gate?

• Seems overly complex way to put it. NAND is the universal gate, and ROM. – C. Towne Springer Apr 1 '14 at 7:59

Technically, yes. This is how you get the NOR function:

simulate this circuit – Schematic created using CircuitLab

And if you can get NOR or NAND you can get any other gate. Though, since it takes two deMUXes to get a NOR, I don't know if it strictly is universal.

• Got me! April Fool's to you, too! – Joe Hass Apr 1 '14 at 10:50
• In formal logic, you can't simply tie an input to 1 -- that's a function. This answer is adequate for someone building circuits, but doesn't match the textbook definition of "universal" – trentcl Apr 1 '14 at 11:33
• @trentcl I have never seen the term "universal gate" in a formal context. Admittedly, I was going to answer no because, as you pointed out, the A input is not negated. But, from a practical point of view, you can infact obtain any gate out of a combination of deMUXes. – clabacchio Apr 1 '14 at 19:02

Formally, the demultiplexer is not universal (functionally complete) because it is falsity-preserving -- that is, if you set all the inputs to 0, you can't get a 1 out of any combination of demuxes.

(Note that a demux actually calculates two functions, and would therefore be considered two "gates" in abstract logic: the AND gate and a does-not-imply gate. Both these gates have the falsity-preserving characteristic, so the set containing both of them is not universal either.)

You can make a universal set by including the constant 1 -- this is easy to do in real electronics, where you may just tie an input to +Vcc. In other words, the set consisting of {AND, does-not-imply, 1} is universal.