Codelet 2: Evaluating Propositional Logic

The due date for this codelet is February 6, 11:59PM.

Introduction

The goals of this codelet are to solidify your knowledge of propositional logic and refresh your knowledge of recursive functions.

Outline

• Grading
• Core Task

Your assignment

Your task is to:

1. Download codelet2.zip from the course website and open it. You will find these instructions and codelet2.py which has scaffolding for you.
2. Complete the core task which is implementing two functions, one which evaluates a formula of propositional logic given an assignment and the other determines whether a formula is a tautology.

Grading

When assessing your code, satisfactory achievement is demonstrated, in part, by:

• Simple, clear, and clean code
• Uses only basic Python with the exception of itertools (as discussed below)
• Code passes all relevant tests
• Demonstrates knowledge of propositional logic

Core Tasks

Your core task is to determine whether a formula of propositional logic is a tautology (or not). To scaffold this, you should first complete evaluate_formula which takes a formula and a dictionary of truth-value assignments for each atomic element of the formula and returns whether that formula is true (or false) given that assignment.

Format of Formula

The formula from propositional logic will conform to a pre-order format, represented as nested tuples. You may assume all your input is well-formed. Here are some examples to help you see how formula are formatted:

• The formula p is represented as 'p'
• The formula ¬p is represented as ('not', 'p')
• The formula p ∧ q is represented as ('and', 'p', 'q')
• The formula (p ∧ q) → r is represented as ('implies', ('and', 'p', 'q'), 'r')
• The formula (p ∧ q) → (r v s) is represented as ('implies', ('and', 'p', 'q'), ('or', 'r', 's'))

That is, formula are either a single string representing an atom or a tuple where we have an operator as the first element of the tuple, the left-hand side as the second element, and the right-hand side (if applicable) as the third element of the tuple. Elements may themselves be compound formula, written in the same format.

You should expect the following operators:

• ¬ (not)
• ∧ (and)
• v (or)
• → (implies)
• ⊕ (exclusive or)

Contents of Assignments

Assignments are dictionaries mapping from atomic elements to their truth value. For example,

• {'p': True, 'q': False} and the formula ('and', 'p', 'q') would return False
• {'p': True, 'q': True, 'r': True} and the formula ('implies', ('and', 'p', 'q'), 'r') would return True

Hints for evaluate_formula

The most natural solution to evalute_formula uses a recursive function. Let’s think through some concrete examples.

• Say we have the formula 's' and the assignment {'s': True}. This returns True, since we can look up 's' in our assignment.

• Say we have the formula ('not', 't'), which represents ¬t, and the assignment {'t': True}. We only have a left-hand side, 't'. If we recursed on that formula, we would get a base case, which is a atomic formula 't', which returns True. Applying 'not' to True returns False.

• Say we have the formula ('implies', 'u', 'v'), which represents u → v, and the assignment {'u': True, 'v': False}. We have a formula on the left-hand side, 'u'. We recurse and get the base case, returning True. We have a formula on the right-hand side, 'v'. We recurse and get the base case, returning False. The operator 'implies' applied to these values returns False.

• Say we have the formula ('or', ('and', 'p', 'q'), 'r'), which represents ((p ∧ q) v r), and the assignment {'p': True, 'q': True', 'r': False}. We have the operator 'or' combining with the left-hand side, which is itself a compound expression, and a right-hand side which is an atomic element. What if we recurse on both of the sides and evaluate them. On the right hand side we hit a base case, namely we know that 'r' is False given our assignment. The left-hand side, we have the operator 'and' and 'p' on the left and 'q' on the right. If we recurse again on the left and right hand side, we hit a base case, namely 'p' maps to True and 'q' to True. With that 'and' we now combine the left and right, which is True and True returning True and then we 'or' that with the False from 'r', which gives us True. We are then done.

Hints for is_tautology

You may use the method product from the library itertools. You may even find it helpful! See the code snippet below. Notice that given a set, \(S\), we can get all the elements in the set \(T := S \times S \times S\) using product(S, repeat=3).

>>> from itertools import product
>>> for s in product({'cat', 'dog', 'lizard'}, repeat=2):
...     print(s)
...
('dog', 'dog')
('dog', 'cat')
('dog', 'lizard')
('cat', 'dog')
('cat', 'cat')
('cat', 'lizard')
('lizard', 'dog')
('lizard', 'cat')
('lizard', 'lizard')

Other Notes

• You may add helper functions, if you’d like.

Submitting

Submit your file codelet2.py (with that EXACT name) to gradescope. There is an autograder which will tests your code. You may re-submit as many times as you would like prior to the deadline.