Electrical engineers often use multiplexers to implement Boolean functions. What is the correct technical term for this model of computation? Is it Decision Tree model or is there another name?

  • $\begingroup$ Can you explain your question in more detail? $\endgroup$ – Yuval Filmus Dec 18 '18 at 22:33
  • $\begingroup$ You are using multiplexers ( relays if you like) to implement Boolean functions instead of logic gates. Engineers use this technique to build circuits with large truth tables because it is easy to just hardwire the values of the truth table into the input lines of the multiplexer. So what do you call this method of computation, is it relay logic, decision tree ( because the multiplexers are in the tree arrangement for any N input) ? $\endgroup$ – William Hird Dec 18 '18 at 22:42
  • $\begingroup$ You can call it a multiplexer if you wish, though truth table might be more common. It is a rather boring model of computation, since all functions have the same complexity. $\endgroup$ – Yuval Filmus Dec 18 '18 at 22:43
  • $\begingroup$ What do you mean " all the functions have the same complexity" ? $\endgroup$ – William Hird Dec 18 '18 at 22:45
  • $\begingroup$ All functions of length $n$ have the same complexity, or rather, there is no meaningful way to define a complexity measure for functions in this model. $\endgroup$ – Yuval Filmus Dec 18 '18 at 22:45

I think there is no specific name for it, just several methods, c.p. this website Note that it's quite simple to e.g. implement all 2-input logic functions with a 4 input 1 output mux, by connecting the inputs to the address/select lines, and applying the constants 0/1 to the data inputs. (This actually transforms the MUX into a Lookup table (LUT))

  • 1
    $\begingroup$ Thank you for replying , but this doesn't answer my question. Dig deeper :-) $\endgroup$ – William Hird Dec 19 '18 at 13:20
  • $\begingroup$ It absolutely answers your question. Your question is "What is the name of this thing?" and the answer given is "It doesn't have a name." I've no idea if that's the correct answer, but it's certainly an answer. $\endgroup$ – David Richerby Dec 19 '18 at 20:44
  • $\begingroup$ OK , you and Yuval are professional computer scientists, if you all don't know the answer than " with high probability" there is no answer. I withdraw the question. $\endgroup$ – William Hird Dec 19 '18 at 23:13

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.