Boole Truth Table Conversion question.

Hello Everybody, this is my first post.

I have a "strange" question on Boole's truth tables, So i better start with an example.

Lets say that i have three Digital Inputs X, Y and Z and 1 digital Output Q

Also i have a Boole's expression that determines the Output : Q = X+Y+Z (Where * => logical AND and + => Logical OR)

The Truth table representing this expression is:

X | Y | Z | Q |

0 | 0 | 0 | 0 |

0 | 0 | 1 | 1 |

0 | 1 | 0 | 1 |

0 | 1 | 1 | 1 |

1 | 0 | 0 | 1 |

1 | 0 | 1 | 1 |

1 | 1 | 0 | 1 |

1 | 1 | 1 | 1 |

The problem is to "Brake" this Truth table into 2 other truth tables with 2 inputs each. We are able to use "virtual" inputs representing with lower case letters a, b, c, ...

Well in a simple example like that the solution is obvious:

The first truth table would be :

Y | Z | a |

0 | 0 | 0 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 1 |

And the second truth table would be:

a | X | Q |

0 | 0 | 0 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 1 |

Now my question is, if i have a complex expression which produces a complex truth table, lets say:

X | Y | Z | Q |

0 | 0 | 0 | 0 |

0 | 0 | 1 | 1 |

0 | 1 | 0 | 0 |

0 | 1 | 1 | 0 |

1 | 0 | 0 | 1 |

1 | 0 | 1 | 1 |

1 | 1 | 0 | 1 |

1 | 1 | 1 | 0 |

Is it possible to "Brake" this truth table into 2 other truth tables with 2 inputs each?

And if Yes, How it can be generalized to "Break" multiple input truth tables to others with 2 inputs each?

Thanks in advance.

Re: Boole Truth Table Conversion question.

The proper place for questions about Boolean functions is the Discrete Math subforum.

What you would like to do is to represent a Boolean function f(x, y, z) as a composition of two functions g(x, h(y, z)). Counting the number of all possible compositions, we can see that this is not always possible. Indeed, there are $\displaystyle 2^{2^3}=2^8$ Boolean functions of three arguments and $\displaystyle 2^{2^2}=2^4$ functions of two arguments. If each pair (g, h) of two-argument functions produced a distinct three-argument function (in other words, if the mapping $\displaystyle (g, h)\mapsto g(x,h(y,z))$ were an injection), then there would also be $\displaystyle 2^4\cdot 2^4=2^8$ compositions. However, some compositions of distinct pairs (g, h) produce the same function, e.g., when g(x, y) = x: then h does not matter. Thus, there are fewer than $\displaystyle 2^8$ compositions of the form g(x, h(y, z)).

Representing a Boolean function as a composition of two or more functions is called Boolean decompositions, and apparently it is (or was) an active research area. This paper claims that "almost all n-variable functions are undecomposable when n is large." It also has a criterion of decomposition. Let's say we want to represent f(x, y, z) as g(x, h(y, z)). One has to write the Boolean table for f as a 2 x 4 table. Its columns are marked by all possible values of the arguments of the internal function h (here this is y and z), and its rows are marked by the remaining variables (here x). The cells of the table are, of course, the values of f for the corresponding x, y and z. For your second function, the table is the following.

$\displaystyle \begin{array}{c|c|c|c|c}_{\textstyle x}\char`\\^{\textstyle yz} & 00 & 01 & 10 & 11\\\hline0 & 0 & 1 & 0 & 0\\\hline1 & 1 & 1 & 1 & 0\end{array}$

Theorem 2.1 in the paper says that f is decomposable iff there are at most two distinct columns in the table. Here, however, there are three: 01, 11 and 00. Therefore, the function is undecomposable.

Re: Boole Truth Table Conversion question.

Wow.

I trully got my answer and more...

Thank you very much.