1
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented May 25, 2013 at 7:09
  • $\begingroup$ How is SoP related to Universal Boolean Function ? Can you be more clear ? $\endgroup$
    – sashank
    Commented May 25, 2013 at 11:55

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .