Results 1 to 3 of 3

Math Help - Boole Truth Table Conversion question.

  1. #1
    Newbie
    Joined
    Jul 2012
    From
    Greece
    Posts
    3

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    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 2^{2^3}=2^8 Boolean functions of three arguments and 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 (g, h)\mapsto g(x,h(y,z)) were an injection), then there would also be 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 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.

    \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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2012
    From
    Greece
    Posts
    3

    Re: Boole Truth Table Conversion question.

    Wow.
    I trully got my answer and more...
    Thank you very much.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Truth Table
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 23rd 2011, 12:14 PM
  2. Please help with truth table?
    Posted in the Geometry Forum
    Replies: 2
    Last Post: May 26th 2010, 09:16 AM
  3. Truth table
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 20th 2010, 05:25 AM
  4. Truth Table
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 5th 2009, 10:24 AM
  5. Truth Table Question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 3rd 2008, 11:30 AM

Search Tags


/mathhelpforum @mathhelpforum