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.
Let’s 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 it’s 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 Python’s 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 you’ll be able to evaluate expressions such as:
>>> eval('a |implies| b')
>>> eval('a |iff| b')This was the hard part. Next, we’ll 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|.PA1.py; you can add functions of your own as needed.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:
[ [True], [False] ]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.