Making truthtables in python

Question 1

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.

Question 2

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.

Question 3

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