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 Boolean functions of three arguments and 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 were an injection), then there would also be 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 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.

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.