Boolean interpretation and recursion function

Question

1.) I want to confirm that I indeed need four boolean variables to answer the question below e.g. p,q,x,y

2.) I need to write a recursive function to parse and interpret this.

Boolean statement:

(T| (F& (T|F))) where | = or, & = and

I think this can be restated correctly below with variables:

X Or ( Y And (P Or Q))

Assuming I am ok so far, I am thinking I can use the Truth table Truth Table to build my recursion function in some way. By some way, break the problem into a termination condition and a reduction step where the function calls itself with a smaller number each time.

How can I build a recursive function in python?

https://www.youtube.com/watch?v=wMNrSM5RFMc <- Python Recursion Explained in depth

Any clarification would be greatly appreciated!

Do `T` and `F` stand for `True` and `False`, or are those variables? In the latter case, I'd say you need two variables (and can be simplified to `T|F`, and in the first case, zero variables (evaluates to `T`). — tobias_k, Jan 29 '18 at 14:58
If you want to bulid a recursive formula to test/create the entire truth table, you should use a list of "open" variables. In each recursive call, you set one of those variables to either true or false and recurse with the rest of the variables, until none are left. — tobias_k, Jan 29 '18 at 15:02
The Boolean expression `(T| (F& (T|F)))` evaluates to `T`. It is not clear what you need a recursive function here for. — goodvibration, Jan 29 '18 at 15:04
Thank you for the quick feedback. I am asking the question writer to clarify on whether T= True and F = False or if T & F are variables that can take on True/False themselves. Thanks again for helping me think about this one. — whalekayo, Jan 29 '18 at 15:33
@tobias_k - I can confirm T and F stand for True and False. Given this is the case, is a recursive function even possible? — whalekayo, Jan 29 '18 at 16:52

Adirio · Accepted Answer · 2018-01-30T15:00:45.163

The statement you proposed ((T| (F& (T|F))) where | = or, & = and) can be simplified to: T or (F and (T or F))

Now, as @tobias_k said, T and F could be variable names or just abreviations of True and False.

Variable names:

T or (F and (T or F)) == T or F

Abreaviations of True and False:

True or (False and (True or False))
True or (False and True)
True or False
True

You considered them to be 4 different variables: X, Y, P and Q. X or (Y and (P or Q)) is a valid Python expression that will evaluate to True or False depending on the X, Y, P and Q values. There is no recursion to apply. Even if you wanted to get the full truth table you would not need any recursion.

The following function accepts as arguments a dict whose keys are used as column names and whose values are functions that will be called with all the imputs and must return a boolean value, and a second argument with the names of the input variables.

import itertools

def truth_table(f, field_names):
    outputs = list(f.keys())
    cols = list(field_names) + outputs
    format = ""
    separator = ""
    for width in (len(name) + 2 if len(name) > 5 else 7 for name in cols):
        format += "{!s:^" + str(width) + "}|"
        separator += ("-" * width) + "+"
    format = format[:-1]
    separator = separator[:-1]
    print(format.format(*cols))
    print(separator)
    for case in itertools.product((False, True), repeat=len(field_names)):
        row = list(case)
        for output in outputs:
            row.append(f[output](*case))
        print(format.format(*row))

You would then call it:

truth_table(
    {
        "P or Q": lambda x, y, p, q: p or q,
        "Y and (P or Q)": lambda x, y, p, q: y and (p or q),
        "X or (Y and (P or Q))": lambda x, y, p, q: x or (y and (p or q)),
    },
    ("X", "Y", "P", "Q")
)

Which will output:

   X   |   Y   |   P   |   Q   | P or Q | Y and (P or Q) | X or (Y and (P or Q))
-------+-------+-------+-------+--------+----------------+-----------------------
 False | False | False | False | False  |     False      |         False
 False | False | False | True  |  True  |     False      |         False
 False | False | True  | False |  True  |     False      |         False
 False | False | True  | True  |  True  |     False      |         False
 False | True  | False | False | False  |     False      |         False
 False | True  | False | True  |  True  |      True      |         True
 False | True  | True  | False |  True  |      True      |         True
 False | True  | True  | True  |  True  |      True      |         True
 True  | False | False | False | False  |     False      |         True
 True  | False | False | True  |  True  |     False      |         True
 True  | False | True  | False |  True  |     False      |         True
 True  | False | True  | True  |  True  |     False      |         True
 True  | True  | False | False | False  |     False      |         True
 True  | True  | False | True  |  True  |      True      |         True
 True  | True  | True  | False |  True  |      True      |         True
 True  | True  | True  | True  |  True  |      True      |         True

If anyone is interested in the inner workings of the functions just leave a comment — Adirio, Jan 29 '18 at 16:32
Nice, but I'd use `itertools.product([True, False], repeat=len(field_names))` instead, and calling the variable `permutations` is somewhat misleading IMHO. — tobias_k, Jan 29 '18 at 16:36
@tobias_k What name would you suggest instead of `permutation`. Edited with the `repeat` keyword param, but the order and tuple type kept as they are desirable. — Adirio, Jan 30 '18 at 07:26
To be honest, I'm not sure what one element in the `product` is called, but a permutation is something entirely different. How about just "values" or "assignment"? — tobias_k, Jan 30 '18 at 12:22
`case`? Also swapped `result` to `row` as it was holding both inputs and results. — Adirio, Jan 30 '18 at 15:01

Boolean interpretation and recursion function

1 Answers1