# Boole Truth Table Conversion question.

• Jul 25th 2012, 11:42 AM
nikosliapis
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?

• Jul 25th 2012, 01:13 PM
emakarov
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.
• Jul 25th 2012, 09:38 PM
nikosliapis
Re: Boole Truth Table Conversion question.
Wow.
I trully got my answer and more...
Thank you very much.