PA1: Propositional Logic


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:

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

Instructions:

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: a or b [[True, True, True], [True, False, True], [False, True, True], [False, False, False]]

Truth table for expression 2: x or y [[True, True, True], [True, False, True], [False, True, True], [False, False, False]]

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:

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.