Description
One way to represent a compound proposition in Python is to use lists as follows: the first element is a
logical connective, and the remaining elements will be the atomic propositions in the compound proposition.
For example:
• p1 ∧ ¬p2 =⇒ p3 will be represented with the list
1 [“if”, [” and “, “p1”, [“not”, “p2”] ] , “p3″]
• p1 ⇐⇒ p2 ∨ ¬p3 will be represented with the list
1 [” iff “, “p1”, [“or”, “p2″, [” not “, “p3”]]]
(a) Write a python function format prop that allows to print a proposition in Propositional Logic using
the indicated list representation. Consider the connectives: ∨, ∧, =⇒ , ⇐⇒ , ¬. and ⊕ (XOR).
Remark. To facilitate the problem assume that we consider only unary operator not and binary operations: functions that take only two inputs.
For example, such list will be a valid input:
1 [“or”, “p1”, “p2”]
List with more variables is an invalid input:
1 [“or”, “p1”, “p2”, “p3”]
Your python function format prop should take one argument prop, list of strings and other lists. It
should return a formatted string corresponding to the desired compound proposition. Assume all inputs
are valid.
1 def format_prop ( prop ):
2 # your code
3 return # your string
For example, inputs from our sample example
1 lst1 = [“if”, [” and “, “p1″, [” not “, “p2”]] , “p3″]
2 lst2 = [” iff “, “p1”, [“or”, “p2″, [” not “, “p3” ]]]
3 print ( format_prop ( lst1 ) )
4 print ( format_prop ( lst2 ) )
produce the following strings:
((p1 and (not p2)) -> p3)
(p1 <-> (p2 or (not p3)))
You may assume that atomic propositions are in the format of p[1-9], meaning that they have a prefix
p and one digit from 1 to 9, or a string true or false. The list of valid operators is
1 [“or”, ” and “, “if”, ” iff “, ” not “, ” xor “]
You may wrap all operations into parentheses even if they are not required.
Hint: You may find recursion to be very helpful.
Page 2
(b) Given a proposition p over atomic propositions p1, p2, · · · , pn, n ≤ 9, and a truth value assigned to
each atomic proposition, evaluate whether p is true or false under this assignment.
Assume that the values of atomic propositions are given as a Python list of length n where each element
is 0 or 1. For example if we have p1 = 0, p2 = 1, p3 = 0 the corresponding list is:
1 values = [0 , 1, 0]
Your python function evaluate should take 2 arguments prop, a proposition in the list representation,
and values, values of atomic propositions. It should return a Boolean value or a corresponding integer,
0 or 1. Assume all inputs are valid.
1 def eval_prop ( prop , values ):
2 # your code
3 return # your boolean or integer (0 or 1)
Hint: Again you may find recursion to be very helpful.
(c) Print the truth table for p. Feel free to use any formatting as far as the table your code outputs is
readable.
Your python function print table should take two arguments: prop in the list representation and an
integer defining the number of atomic propositions n var. It should print a corresponding truth table.
Assume all inputs are valid.
1 def print_table ( prop , n_var ):
2 # your code
Hint: Use functions format prop and eval prop
Example of propositions to try:
1. p1 → p2
2. true ∨ (p1 ∧ p2)
3. p1 ∧ p2
4. p1 ∨ p2
5. p1 ↔ p2
6. ¬p1 → p2
7. (p1 ∨ p2) ∨ (p1 ∨ ¬p2)
8. (¬(¬p1)) ↔ p1
9. ((p1 → p2) ∧ (p2 → p3)) → (p1 → p3)
10. (p1 ∨ p2) ∧ (¬p1 ∧ ¬p2)
11. ¬((p1 → f alse) → ¬p1)
12. ¬(p2 → p1) ∧ ((p1 ∧ p2) → p3) ∧ p4
13. Try more!
