MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

A Boolean function U($z_1$, $z_2$ ..... , $z_m$) is universal for given n > 1 if it realizes all Boolean functions f($x_l$ ..... $x_n$) by substituting for each $z_i$ with a variable of the set {0, 1, $x_1$ ..... $x_n$,$x^1_1$ ...$x^1_n$}.

Less formally , a universal boolean function can realize any given boolean function .

Now the question is how do we translate given function or express a given boolean function in terms of Universal Boolean Function ? is there an well defined way ?

Preparata, Franco P., and David E. Muller. "Generation of near-optimal universal Boolean functions." Journal of Computer and System Sciences 4.2 (1970): 93-102.

share|cite|improve this question
There is sum of products form, for a start. Or did you have something else in mind? Gerhard "Ask Me About System Design" Paseman, 2013.05.25 – Gerhard Paseman May 25 '13 at 7:09
How is SoP related to Universal Boolean Function ? Can you be more clear ? – sashank May 25 '13 at 11:55

Here is my take on the question.

An early theorem in propositional logic (or digital logic, or gate based circuit design) is that any Boolean function has a representation in disjunctive normal form. A somewhat cumbersome example is XOR(x,y,z) = xyz + xy'z' + x'y'z + x'yz', where I use + for an OR gate and concatenation (instead of explicit multiplication $\cdot$) for AND and ' for NOT. If I have a collection of a large (but fixed) number of NOT gates, followed by an array of four AND gates, each with six inputs, and an OR gate with four inputs, I can wire those together in a configuration that, once I assign signals to the inputs appropriately, allows me to represent any of the 256 three input Boolean functions. This configuration is a gate based realization of a Universal Boolean function for n=3.

A bit of personal history: I was involved in a project decades ago which allowed digital logic designers to use software to help design and simulate circuits created with PLDs. These Programmable Logic Devices were modifiable gate arrays, and often served as physical realizations of approximations to Universal Boolean Functions. I have not seen the Preparata and Muller paper above, but I would bet a small amount of cash that the paper inspired the use of gate arrays in chip and circuit design in the folllowing decades.

Gerhard "Practical Uses Of Clone Theory" Paseman, 2013.05.25

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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