CODEWITHSUNDEEP
pythonpython-3.xbooleantruthtable
Aleksander
Aleksander

Reputation: 2815

Making truthtables in python

I'm having some trouble doing some homework related to making truthtables in Python. I've tried going to Office Hours, but they don't know anything so I gotta ask you guys.

Here's the question:

--

In this problem, you will implement functions for printing truth tables for formulas with variables. You may use the following helper function, which prints a tab-delimited list of values.

def prints(values):
    print("\t".join([str(value) for value in values]))

The above function can be used as follows

prints([True, False, True])
True   False  True

You may also use the following helper function, which returns a list of the argument names of a function:

def variables(f):
    return list(f.__code__.co_varnames)

The above function can be used as follows:

def h(x,y,z): return (y or x) and (not(z) <= x)

variables(h)
['x', 'y', 'z']

A: Implement a function truthtableXY(f) that takes as its input a single function f (i.e., a Python function corresponding to a formula such as those you defined in Problem #2 above). You may assume f takes two boolean arguments x and y. The function should print a truth table for f.

def f(x,y): return x and y

truthtableXY(f)
y      x      formula
True   True   True
True   False  False
False  True   False
False  False  False

B: Implement a recursive function truthtable(f) that takes as its first argument a single function f (i.e., a Python function corresponding to a formula). The function f may take any non-zero quantity of arguments. The function should print a truth table for f.

def h(x,y,z): return (y or x) and (not(z) <= x)

truthtable(h)
x       y       z       formula
True    True    True    False
True    True    False   False
True    False   True    False
True    False   False   False
False   True    True    True
False   True    False   False
False   False   True    False
False   False   False   False

Your truthtable() function should employ the recursive backtracking approach, and can be organized as follows:

C: Implement a function rows(f) that takes as its first argument a single function f (i.e., a Python function corresponding to a formula). The function should return the number of rows in the truth table for f.

def h(x,y,z): return (y or x) and (not(z) <= x)

rows(h)
8

--

I managed to do A, and got this answer:

def truthtableXY(f):
    prints(['y', 'x', 'formula'])
    for x in [True, False]:
        for y in [True, False]:
            prints([x, y, f(x,y)])

which works. But I simply cannot work out how to do the others.

Anyone out there who knows/ can work out the answer?

Here's the original website with the homework btw: http://cs-people.bu.edu/lapets/131/m.php?#2.4 (question 3)

Thanks in advance guys! :)

Upvotes: 4

Views: 5518

Answers (3)

jonrsharpe
jonrsharpe

Reputation: 122024

For B, you want:

def truthtable(f, values=None):
    if values is None:
        prints(variables(f) + ["formula"])
        values = []
    # print values 
    if len(values) == len(variables(f)):
        prints(values + [f(*values)])
    else:
        for b in [True, False]:
            truthtable(f, values + [b])

How this meets your spec:

  • The function should have a second parameter values with a default value of [], which will be the list of values the function builds up and eventually passes to f; - not quite, "mutable default parameter" is a bad move in Python, but I have values and make it an empty list on the first call to truthtable

  • If the list values is empty, the function should print a row containing all the variable names (one column header per variable); - done at the same time as initialising value

  • If the list values is the same length as the list of variables of f, the function should print a row of values containing all the values in values, as well as the result of applying f to that list of values (use the *-operator to apply f to the list of arguments); - the second if block

  • If the list values is shorter than the list of variables of f, the function should make recursive calls to truthtable(), with approprate changes to the arguments of truthtable(). - the for loop at the end.

For more explanation on the last part; you need to build up combinations of True and False to pass as arguments to f, so you recursively call (i.e. call a function from within itself) truthtable first with True, then with False, each time adding to the list until you have the right number of arguments. Uncomment print values to watch this happen in the interpreter.

Upvotes: 3

poke
poke

Reputation: 387667

First of all, instead of using that variables function, we define our own using the inspect module. That way, we don’t have to access internal implementation-specific properties:

import inspect
def variables (f):
    return inspect.getargspec(f).args

For the truthtable, we need some combinatorics, so we use the itertools module:

from itertools import product, repeat
def truthtable (f):
    vars = variables(f)

    # print the header
    prints(vars + ['formula'])

    # get all combinations
    for args in product(*repeat((True, False), len(vars))):
        result = f(*args)
        prints(args + (result,))

Used, we get these results:

>>> truthtable(f)
x   y   formula
True    True    True
True    False   False
False   True    False
False   False   False
>>> truthtable(h)
x   y   z   formula
True    True    True    False
True    True    False   False
True    False   True    False
True    False   False   False
False   True    True    True
False   True    False   False
False   False   True    False
False   False   False   False

I’ll leave the implementation of a recursive function to you. It’s your homework after all, and the instructions actually explain rather well what you need to do.

As for the last task, this is simple combinatorics. For each variable, we have two possible values. For each variable we add to a set of combinations, we have to combine all those combinations once with True and once with False so we get twice as much. And for the case with only a single variable, we have just two possibilites. So for n variables, we have 2 ** n possible combinations.

Okay, let’s go through the instructions one-by-one to get this recursive solution working:

The function should have a second parameter values with a default value of [], which will be the list of values the function builds up and eventually passes to f

Okay, so our function will look like this:

def truthtable (f, values=[]):
    # …

But instead of that, we will actually make the default value None and explicitely set it to an empty list inside of the function. You may hit your instructor for this, because this is a very common error.

def truthtable (f, values=None):
    if values is None:
        values = []
    # …

If the list values is empty, the function should print a row containing all the variable names (one column header per variable)

Okay, that’s just calling prints(variables(f)), so that part looks like this:

if values == []:
    prints(variables(f))

If the list values is the same length as the list of variables of f, the function should print a row of values containing all the values in values, as well as the result of applying f to that list of values (use the *-operator to apply f to the list of arguments)

Again, this is also straight-forward:

if len(values) == len(variables(f)):
    result = f(*values)
    prints(values + [result])

If the list values is shorter than the list of variables of f, the function should make recursive calls to truthtable(), with approprate changes to the arguments of truthtable().

So here is where the recursion happens, so let’s think about this. We start with an empty list of values, and we want to get to a point where we have as many values as variables. So obviously we want to add values to the values list when calling the function recursively. Now which values do we want to add? The only two values we know: True and False. So the calls look like this:

truthtable(f, values + [True])
truthtable(f, values + [False])

And now we put all that together:

def truthtable (f, values=None):
    if values is None:
        values = []

    if values == []:
        prints(variables(f))

    if len(values) == len(variables(f)):
        result = f(*values)
        prints(values + [result])
    else:
        truthtable(f, values + [True])
        truthtable(f, values + [False])

And that’s it. Now, my remark from the beginning, about the mutable default value of values is not exactly true for this function as we never modify the list directly but just create a new list by concatting it with other lists; so we could revert that again. But I’ll leave it in anyways because you should always keep this in mind or you will run into problems sooner or later.

Upvotes: 3

Noctua
Noctua

Reputation: 5208

Well, the C part is trivial, that's just 2 ** len(variables(h)). For the B-part, I suggest using an enumerator for all possible assignments to the variables. With assignment, I mean an array of booleans of the same length as the array of variables, so you get a boolean for each variable.

Then you can make use of the following trick in Python:

>>> def f(x, y, z): return (y or x) and (not(z) <= x)
>>> assignment = [True, False, True]
>>> f(*assignment)
False

This is a trick of calling a function with the parameters as in the list.

You can see that now, you can just enumerate the assignments, and check the value of the function for each assignment.

To enumerate the assignments, you could also use the fact that the boolean values are just the bits of an integer counter. If you really want it backtracking, use:

def enumerate_bools(length):
    if length == 0:
        yield []
        return
    for rest in enumerate_bools(length - 1):
        yield [False] + rest
        yield [True]  + rest

Upvotes: 2

Related Questions