Programming Forums - Truth Table --> Logical Expressions

Programming Forums (http://www.programmingforums.org/forumindex.php)

- Project Ideas (http://www.programmingforums.org/forum50.html)

- - Truth Table --> Logical Expressions (http://www.programmingforums.org/showthread.php?t=10141)

Truth Table --> Logical Expressions

I'd like to convert the following truth table in to a logical expression:

INPUT                   OUTPUT

[0, 0, 0, 0, 0, 0, 0] [1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0]

[0, 0, 0, 0, 0, 0, 1] [1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 1, 0] [1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1]

[0, 0, 0, 0, 0, 1, 1] [1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1]

[0, 0, 0, 0, 1, 0, 0] [1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1]

[0, 0, 0, 0, 1, 0, 1] [1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1]

[0, 0, 0, 0, 1, 1, 0] [1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1]

[0, 0, 0, 0, 1, 1, 1] [1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0]

[0, 0, 0, 1, 0, 0, 0] [1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1]

[0, 0, 0, 1, 0, 0, 1] [1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1]

[0, 0, 0, 1, 0, 1, 0] [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0]

[0, 0, 0, 1, 0, 1, 1] [0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0]

[0, 0, 0, 1, 1, 0, 0] [0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1]

[0, 0, 0, 1, 1, 0, 1] [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1]

[0, 0, 0, 1, 1, 1, 0] [0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1]

[0, 0, 0, 1, 1, 1, 1] [0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1]

[0, 0, 1, 0, 0, 0, 0] [0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1]

[0, 0, 1, 0, 0, 0, 1] [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0]

[0, 0, 1, 0, 0, 1, 0] [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1]

[0, 0, 1, 0, 0, 1, 1] [0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1]

[0, 0, 1, 0, 1, 0, 0] [1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0]

[0, 0, 1, 0, 1, 0, 1] [1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0]

[0, 0, 1, 0, 1, 1, 0] [1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1]

[0, 0, 1, 0, 1, 1, 1] [1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1]

[0, 0, 1, 1, 0, 0, 0] [1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1]

[0, 0, 1, 1, 0, 0, 1] [1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1]

[0, 0, 1, 1, 0, 1, 0] [1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1]

[0, 0, 1, 1, 0, 1, 1] [1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0]

[0, 0, 1, 1, 1, 0, 0] [1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1]

[0, 0, 1, 1, 1, 0, 1] [1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1]

[0, 0, 1, 1, 1, 1, 0] [1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0]

[0, 0, 1, 1, 1, 1, 1] [1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0]

[0, 1, 0, 0, 0, 0, 0] [1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1]

[0, 1, 0, 0, 0, 0, 1] [1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1]

[0, 1, 0, 0, 0, 1, 0] [1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1]

[0, 1, 0, 0, 0, 1, 1] [1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1]

[0, 1, 0, 0, 1, 0, 0] [1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1]

[0, 1, 0, 0, 1, 0, 1] [1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0]

[0, 1, 0, 0, 1, 1, 0] [1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]

[0, 1, 0, 0, 1, 1, 1] [1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1]

[0, 1, 0, 1, 0, 0, 0] [0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0]

[0, 1, 0, 1, 0, 0, 1] [0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0]

[0, 1, 0, 1, 0, 1, 0] [0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1]

[0, 1, 0, 1, 0, 1, 1] [0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1]

[0, 1, 0, 1, 1, 0, 0] [0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1]

[0, 1, 0, 1, 1, 0, 1] [0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1]

[0, 1, 0, 1, 1, 1, 0] [0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1]

[0, 1, 0, 1, 1, 1, 1] [0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0]

[0, 1, 1, 0, 0, 0, 0] [0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

[0, 1, 1, 0, 0, 0, 1] [0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1]

[0, 1, 1, 0, 0, 1, 0] [1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0]

[0, 1, 1, 0, 0, 1, 1] [1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0]

[0, 1, 1, 0, 1, 0, 0] [1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1]

[0, 1, 1, 0, 1, 0, 1] [1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1]

[0, 1, 1, 0, 1, 1, 0] [1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1]

[0, 1, 1, 0, 1, 1, 1] [1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1]

[0, 1, 1, 1, 0, 0, 0] [1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1]

[0, 1, 1, 1, 0, 0, 1] [1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0]

[0, 1, 1, 1, 0, 1, 0] [1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

[0, 1, 1, 1, 0, 1, 1] [1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1]

[0, 1, 1, 1, 1, 0, 0] [1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0]

[0, 1, 1, 1, 1, 0, 1] [1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0]

[0, 1, 1, 1, 1, 1, 0] [1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1]

[0, 1, 1, 1, 1, 1, 1] [1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1]

[1, 0, 0, 0, 0, 0, 0] [1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1]

[1, 0, 0, 0, 0, 0, 1] [1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1]

[1, 0, 0, 0, 0, 1, 0] [1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1]

[1, 0, 0, 0, 0, 1, 1] [1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0]

[1, 0, 0, 0, 1, 0, 0] [1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

[1, 0, 0, 0, 1, 0, 1] [1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1]

[1, 0, 0, 0, 1, 1, 0] [1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0]

[1, 0, 0, 0, 1, 1, 1] [1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0]

[1, 0, 0, 1, 0, 0, 0] [1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1]

[1, 0, 0, 1, 0, 0, 1] [1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1]

[1, 0, 0, 1, 0, 1, 0] [1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1]

[1, 0, 0, 1, 0, 1, 1] [1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1]

[1, 0, 0, 1, 1, 0, 0] [1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1]

[1, 0, 0, 1, 1, 0, 1] [1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0]

[1, 0, 0, 1, 1, 1, 0] [1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1]

[1, 0, 0, 1, 1, 1, 1] [1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1]

[1, 0, 1, 0, 0, 0, 0] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0]

[1, 0, 1, 0, 0, 0, 1] [1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0]

[1, 0, 1, 0, 0, 1, 0] [1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1]

[1, 0, 1, 0, 0, 1, 1] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1]

[1, 0, 1, 0, 1, 0, 0] [1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1]

[1, 0, 1, 0, 1, 0, 1] [1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1]

[1, 0, 1, 0, 1, 1, 0] [1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1]

[1, 0, 1, 0, 1, 1, 1] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0]

[1, 0, 1, 1, 0, 0, 0] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

[1, 0, 1, 1, 0, 0, 1] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1]

[1, 0, 1, 1, 0, 1, 0] [1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0]

[1, 0, 1, 1, 0, 1, 1] [1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0]

[1, 0, 1, 1, 1, 0, 0] [1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1]

[1, 0, 1, 1, 1, 0, 1] [1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1]

[1, 0, 1, 1, 1, 1, 0] [1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1]

[1, 0, 1, 1, 1, 1, 1] [1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1]

[1, 1, 0, 0, 0, 0, 0] [1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1]

[1, 1, 0, 0, 0, 0, 1] [1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0]

[1, 1, 0, 0, 0, 1, 0] [1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

[1, 1, 0, 0, 0, 1, 1] [1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1]

The program would output fourteen logical expressions (one for each column in the output). Is there a program that can do this for me? If not, how would you assume is the best way to do it? It doesn't have to be perfectly optimized logic, but that would surely help.

An example of what the program could do:

INPUT  OUTPUT

[0, 0]  [1]

[0, 1]  [0]

[1, 0]  [0]

[1, 1]  [0]

Then the program would output: A2 = A1 nor B1

A way to look at it is one expression for each column in the output. So all that has to be made sure is that the seven inputs in my first example, can achieve all the results in _X_ column of the output with a certain logical expression. Then this is repeated for all the columns in the output table.

Could just be something to do with what i just smoked and maybe im in way over my head here; But where's there any f****** in what you posted?

Quote:

Originally Posted by john Wesley

Could just be something to do with what i just smoked and maybe im in way over my head here; But where's there any f****** in what you posted?

What the hell are you talking about?

IMO, you need to seriously back off the details, and give us a LOT more overview.

You show a VERY over-detailed input/output table, and then immediately jump into a different input/output, with A1, B1, but no clue as to exactly WHAT A1 or B1, IS?

Yes, I can hypothesize what you may have meant, but if you want help, you're going to have to be a LOT more descriptive, here.

Give us a SMALL example, step by step. In addition to helping us understand your problem, it may well help you further understand it, as well.

We don't need sixy lines of input/output, but we need more lines of descriptive, step by step, notation.

Adak

I assume if you don't know enough to understand my issue and proposed solution, then you don't know enough to help me. I explained to a reasonable extent what needs to be accomplished, and I'm asking you what you think should be done "step by step".

I've developed a good chunk of framework for this program, let me know if you think I'm doing anything wrong. This is in Python.

What it does is starts with the smallest number of columns in the input side to try to minimilize the inputs that the logical expression uses. If this column does not satisfy enough unique inputs to outputs, then it proceeds to the next combination of column(s). When it finds a combination that does not have more then one output for the same input, validate() returns true and outputs the corresponding column of bits.

If you run this program, you can see that for the "or" truth table, that the smallest number of columns possible to achieve a "validated" possibility of succeeding a logical expression, is both columns combined. This can be used to limit the possibilities, and also catch any obvious methods straight off the bat.

IN SHORT... it tells you what input columns could (and should) be used to determine the "_output'th" output column, in order from smallest to greatest number of bits.

Feel free to add and/or modify accordingly.

class keep_index:

    """custom integer that can be called for its index value,

    easiest way to attach a static value to a dynamic value"""

    def __init__(self, value, index):

        self.value = str(value)

        self.index = index

        

    def __call__(self):

        return self.index

    

    def __repr__(self):

        return self.value



    def __lt__(self, other):

        return self.value < other



    def __le__(self, other):

        return self.value <= other



    def __eq__(self, other):

        return self.value == other



    def __ne__(self, other):

        return self.value != other



    def __gt__(self, other):

        return self.value > other



    def __ge__(self, other):

        return self.value >= other        



def index_table(table):

    """add the index of each item in the table"""

    ntable = []

    for row in table:

        ntable += [[[]]]

        for i, item in enumerate(row[0]):

            ntable[-1][-1].append(keep_index(item, i))

        ntable[-1].append(row[1])

    return ntable



def comb_list(seq, k):

    """    Algorithm by Gilward Kukel

    http://www.programmingforums.org/forum/showthread.php?t=4343



    returns a list of all k-combinations

    of the elements of sequence seq"""

    

    n=len(seq)

    if not 0<=k<=n:

        raise Exception,"0<=k<=len(seq) is not true"

    v=[]   #list of combinations

    #x: number of taken elements

    #y: number of rejected elements

    #we want to take k elements and reject n-k elements

    def f(x,y,a):

        if x==k:

            #we have taken enough elements, reject all remaining elements

            v.append(a)

            return

        if y==n-k:

            #we have rejected enough elements, take all remaining elements

            a.extend(seq[x+y:])

            v.append(a)

            return

        if (x<k):

            #take element seq[x+y]

            h=a+[seq[x+y]]

            f(x+1,y,h)

        if (y<n-k):

            #don't take element seq[x+y]

            f(x,y+1,a)            

    f(0,0,[])

    return v



def fetch(table, b):

    """fetch a column from the table"""

    '''

    [

    [[(0, 0), (0, 1)], [(0, 0), (2, 2)], [(0, 1), (2, 2)]],

    [[(0, 0), (1, 1)], [(0, 0), (2, 2)], [(1, 1), (2, 2)]],

    [[(1, 0), (0, 1)], [(1, 0), (2, 2)], [(0, 1), (2, 2)]],

    [[(1, 0), (1, 1)], [(1, 0), (2, 2)], [(1, 1), (2, 2)]]

    ]

    '''

    t = []

    for row in table:

        t.append([])

        for item in row[b]:

            t[-1].append(item)

    

    return t



def validate(col, out):

    """find out if a logical expression is possible for this

    column(s) (if there are two results for the same input)"""

    '''

    [[0, 0], [0, 1], [1, 0], [1, 1]], [0, 1, 1, 1]

    '''

    for find, flp in enumerate(col):

        for sind, slp in enumerate(col):

            if flp == slp and find != sind:

                if out[find] != out[sind]:

                    return False

    return True



def main(table):

    INPUTS  = len(table[0][0])

    OUTPUTS = len(table[0][1])

    ntable = index_table(table)



    # figure out each output column one by one

    for _output in range(OUTPUTS):



        # grab the output column from the table

        out = [row[1][_output] for row in ntable]



        # we can't go past "INPUT" number of columns in the expression

        for _input in range(1, INPUTS+1):

            

            choices = []

            

            for row in ntable:

                # get all combination of elements inside a

                # row that is _input'th elements long

                choices += [comb_list(row[0], _input)]



            for choice in range(len(choices[0])):

                # fetch the column of each combination

                columns = fetch(choices, choice)



                # validate it with the "vertical line test"

                if validate(columns, out):

                    print columns



if __name__ == '__main__':

    table = [[[0, 0], [0]],

             [[0, 1], [1]],

             [[1, 0], [1]],

             [[1, 1], [1]]]

    main(table)

Okay. I have an example of what the program would do for my original truth table.

Y = OR(A, NOR(OR(AND(NOT(C), AND(B, D)), AND(OR(NOR(E, F), AND(AND(NOT(E), F), NOT(B))), AND(C, NOT(D)))), AND((AND(AND(NOT(C), D), OR(E, F))), NOT(B))))

That's what it would output for the first logical expression. As each number in the first output column can be satisfied by these conditions.

I figured it out in my head, and I couldn't even start explaining how I did it. It would be very tough to program this I think. I would think someone has already though.

If you'd like to test that equation, it is wrtten in Python using these functions...

def AND(x, y):

    return (x and y)

def NAND(x, y):

    return not AND(x, y)

def OR(x, y):

    return (x or y)

def NOR(x, y):

    return not OR(x, y)

def XOR(x, y):

    return (x or y) and (not (x and y))

def XNOR(x, y):

    return not XOR(x, y)

def NOT(x):

    return not x

Quote:

Originally Posted by jayme

What the hell are you talking about?

"Where is there any logic in this mans post" was firstly my query; The fact that I was so irresponsable to miss out the most important word of my question is really quite embarrasing. I apologize for this mistake.

You not only missed a word, you missed seeing that there's logic involved, somehow. Perhaps your definition of logic is limited.

Perhaps my definition of logic is limited or maybe its my lack of knowledge of algebra IF im correct in thinking this is part of what it entails?