# translating a given boolean function to universal boolean function

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.

-
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

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.