Python: Need help writing a function that outputs a truth table based on a given expression, below is the assignment I'm working on and source code. I need help with the truth_table function and it's very important that it is done recursively, any advice is greatly appreciated

Assignment:

Your first python programming assignment is about propositional logic. The basic task will be to write a function that computes the truth table of a statement in propositional logic along with several functions that reason about those tables.

Lets start with the task of computing the truth table of a proposition, and describe it informally first. We want to be able to do something like:

>>> tt = truth_table(expression)

where expression is a string that contains a valid Python logical expression, and the return value is a list where each element is a row in the table, e.g.:

>>> truth_table('a and b') [[True, True, True], [True, False, False], [False, True, False], [False, False, False]]

More formally, if the expression has n variables, each element in the returned list is itself a list of length n+1, where the first n values represent an assignment to the variables, and the last element is the value of the logical expression (in Python, a list that contains other lists is called a list-of-lists, and is analogous to 2-d arrays in Java). To make things simple, we impose the restriction that variable names be lower-case letters, i.e. a through z. In the template code we provide a function that recognizes all the variable names present in a given logical expression and returns a list of them in sorted order (see details below). In the list returned by truth_table the order of the values in a given row of the table should correspond to the sorted order of the variables. For example, in the example give above

>>> truth_table('a and b') [[True, True, True], [True, False, False], [False, True, False], [False, False, False]]

the row [True, False, False] in the truth table corresponds to a=True, b=False and a result of False. The expressions can be more complicated than a and b, e.g. (a and b) or (c and not d).

You already know that in Python you can easily evaluate logical expressions, i.e. propositions:

>>> a = True >>> b = False >>> a and (not a or b)

But, at this point you may ask how you can evaluate arbitrary expressions without even knowing the names of the variables ahead of time. Turns out its quite simple in Python using the exec and eval builtins:

>>> exec('a=True') >>> exec('b=True') >>> expression = 'a and (not a or b)' >>> eval(expression)

We are providing you with template code that contains some black magic that enriches Pythons Boolean operators (and, or, not) with two additional operators: |iff| and |implies| that correspond to the bi-conditional (<>) and implication (>) operators, respectively. Using the template code youll be able to evaluate expressions such as:

>>> eval('a |implies| b') >>> eval('a |iff| b')

This was the hard part. Next, well ask you to write three additional functions that determine the following properties of a proposition:

• count_satisfying(expression): receives a Boolean expression in exactly the same format as truth_table and returns the number of assignments of the variables for which the result is True. So for example, count_satisfying('a and 'b) should return 1.
• is_tautology(expression): receives a Boolean expression in exactly the same format as truth_table and returns a Boolean value that indicates whether the expression is a tautology or not. For example, is_tautology('a and 'b) should return False.
• are_equivalent(expression1, expression2): receives two Boolean expressions as input and returns a Boolean value that indicates if the two expressions are logically equivalent. For example, are_equivalent('not a or b', 'a |implies| b') should return True. Note that if two expressions do not have the same variables, they are not considered equivalent. For example, 'not a or b' is not logically equivalent to 'x |implies| y'.

Do not modify the following functions provided in the template code:

• extract_variables(expression): receives as input an expression as a string, and outputs the variables that participate in it as a sorted list. You will need to use the extract_variables function to extract the list of variables from an expression.
• implies(p, q), iff(p, q): implement the operators |implies| and |iff|.

Instructions:

• Download the template and tester files contained in this tar file.
• Implement the four functions specified above and provided as stubs in PA1.py; you can add functions of your own as needed.
• Do not modify the functions whose implementations are provided.
• The file Tester.py provides you with diagnostics that will indicate that your functions returns values of the correct type. Remember: this file is only for your reference. It gives you an idea of how we will be testing your code. You should test your code with more expressions. To run it, type python Tester.py in the command line.

If your implementation is correct, then you will see the following output:

Truth table for the expression: a and b [[True, True, True], [True, False, False], [False, True, False], [False, False, False]]

Number of satisfying values in the expression a and b is: 1

The expression a and b is NOT a tautology!

Truth table for expression 1: not a or b [[True, True, True], [True, False, False], [False, True, True], [False, False, True]]

Truth table for expression 2: a |implies| b [[True, True, True], [True, False, False], [False, True, True], [False, False, True]]

The expressions not a or b and a |implies| b are equivalent!

Tips: You can use the following recursive algorithm to create all combinations of variables for the truth table:

• Base case: For a single variable, the list of all combinations is [ [True], [False] ]
• Recursive case: each element in the list (which is itself a list), is replaced with two lists, one with True appended to it, and one with False appended to it.

Another approach is to use bit strings of length n (i.e. binary numbers) to enumerate all combinations.

Submission instructions:

Submit your assignment using the checkin system. Submit your source code as a single file named PA1.py.

Code

# NOTE: # You must use small single letters for your variable names, for eg. a, b, c # You may use parenthesis to group your expressions such as 'a and (b or c)'

# Implement the following four functions: # truth_table, count_satisfying, is_tautology and are_equivalent

# Submission: # Submit this file using the checkin system on the course web page.

######## Do not modify the following block of code ######## # ********************** BEGIN *******************************

from functools import partial import re

class Infix(object): def __init__(self, func): self.func = func def __or__(self, other): return self.func(other) def __ror__(self, other): return Infix(partial(self.func, other)) def __call__(self, v1, v2): return self.func(v1, v2)

@Infix def implies(p, q) : return not p or q

@Infix def iff(p, q) : return (p |implies| q) and (q |implies| p)

# You must use this function to extract variables # This function takes an expression as input and returns a sorted list of variables # Do NOT modify this function def extract_variables(expression): sorted_variable_set = sorted(set(re.findall(r'\b[a-z]\b', expression))) return sorted_variable_set

# *********************** END ***************************

############## IMPLEMENT THE FOLLOWING FUNCTIONS ############## ############## Do not modify function definitions ##############

# This function calculates a truth table for a given expression # input: expression # output: truth table as a list of lists # You must use extract_variables function to generate the list of variables from expression # return a list of lists for this function

# ***This is the function I need help with*** def truth_table(expression): variables = extract_variables(expression) result = []

pass

# count the number of satisfying values # input: expression # output: number of satisfying values in the expression def count_satisfying(expression): pass

# if the expression is a tautology return True, # False otherwise # input: expression # output: bool def is_tautology(expression): pass

# if expr1 is equivalent to expr2 return True, # False otherwise # input: expression 1 and expression 2 # output: bool def are_equivalent(expr1, expr2): pass

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

Tester Code

# NOTE: # This is a Sample Test file. # This file is only for your reference. # Do not submit this file.

import PA1

# This is the function we will use to check the format of your truth table # Do not modify this function. def check_format(table, num_vars):

# check whether the table is a list assert type(table) is list, "table is not a list: %r" % table

# check whether every row in the table is a list for row in table: assert type(row) is list, "table is not a list of lists: %r" % table

# check if the table covers all possible combinations if len(table) < (2**num_vars): print('Truth table %r does not cover all combinations of variables. There should be %r combinations.' % (table, (2**num_vars))) return False

# check whether table has extra rows if len(table) > (2**num_vars): print('Truth table %r has extra rows. There should be %r combinations.' % (table, (2**num_vars))) return False

for row in table: # check if the table has missing columns if len(row) < (num_vars+1): print('One or more columns in the table are absent, total number of columns should be: %r' % len(row)) return False # check if the table has extra columns elif len(row) > (num_vars+1): print('Truth table has extra columns, total number of columns should be: %r' % len(row)) return False

return True

# sample test cases for each function # You should use different expressions to thoroughly test your output def main(): # sample test for truth_table function expression = 'a and b' tt = PA1.truth_table(expression) variables = PA1.extract_variables(expression)

# check format of the truth table if check_format(tt, len(variables)): print(' Truth table for the expression: ' + expression) print(tt)

# sample test for count_satisfying function count = PA1.count_satisfying(expression) # check format of return value assert type(count) is int, "count_satisfying: return value is not an int" % count print(' Number of satisfying values in the expression \'' + expression + '\' is: ' + str(count))

# sample test for is_tautology function is_a_tautology = PA1.is_tautology(expression) # check format of return value assert type(is_a_tautology) is bool, "is_tautology: return value is not a bool" % is_a_tautology if is_a_tautology: print(' The expression \'' + expression + '\' is a tautology!') else: print(' The expression \'' + expression + '\' is NOT a tautology!')

# sample test for are_equivalent function expr1 = 'not a or b' expr2 = 'a |implies| b'

tt1 = PA1.truth_table(expr1) variables1 = PA1.extract_variables(expr1)

if check_format(tt1, len(variables1)): print(' Truth table for expression 1: ' + expr1) print(tt1)

tt2 = PA1.truth_table(expr2) variables2 = PA1.extract_variables(expr2)

if check_format(tt2, len(variables2)): print(' Truth table for expression 2: ' + expr2) print(tt2)

are_equivalent_expressions = PA1.are_equivalent(expr1, expr2) assert type(are_equivalent_expressions) is bool, "are_equivalent: return value is not a bool" % are_equivalent_expressions if are_equivalent_expressions: print(' The expressions \'' + expr1 + '\' & \'' + expr2 + '\' are equivalent!') else: print(' The expressions \'' + expr1 + '\' & \'' + expr2 + '\' are NOT equivalent!')

if __name__ == '__main__': main()