3
\$\begingroup\$

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

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

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

schematic

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.

\$\endgroup\$
3
  • \$\begingroup\$ Got me! April Fool's to you, too! \$\endgroup\$ – Joe Hass Apr 1 '14 at 10:50
  • 3
    \$\begingroup\$ 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" \$\endgroup\$ – trentcl Apr 1 '14 at 11:33
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – clabacchio Apr 1 '14 at 19:02
3
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.