Content provided under a Creative Commons Attribution license, CC-BY 4.0. Bong-Sik Kim. (25 September, 2016)
The connection between logic, proofs and programming is a very rich and interesting field that goes far byond the scope of an introductory course in discrete mathematics. But instead of illustrating this point here by introducing loads of material not covered in the text book, we will limit our ambitionsto simply emphasizing the obvious: the similarities between logical truth values and Python’s boolean type and its operations.
In Python terms, a logical statement is an expression of boolean type, such as $3 < 7$. Variables can be used in such expressions, although it should be noted that every variable will stand for some concrete value at run-time.
Of the logical connectives, Python directly supports conjunction and disjunction in terms of the built-in primitives and and or, as well as negation via the primitive not (for more details, see the section "Booleans - AND, OR" in the note Introduction to Python Programming).
A nested loop can be constructed to generate the truth table for standard logic operators such as the and
In [ ]:
for p in (True, False):
for q in (True, False):
print("%10s %10s %10s" %(p, q, (p and q)))
To get more intuition, let's consider the code segment that generates the truth table for the expression $\neg p \wedge (q\vee r)$
In [ ]:
for p in (True, False):
for q in (True, False):
for r in (True, False):
print("%10s %10s %10s %s" %(p, q, r, not p and (q or r)))
Other connectives can easily be encoded as functions by use of the if statement. The implication arrow, for example, may be defined as follows:
In [ ]:
def implies(a, b):
if a:
return b
else:
return True
To express the logical statement $x\geq 0 \wedge y\geq 0 \rightarrow x*y\geq 0$ in Python one simply writes
In [ ]:
x = 4
y = -1
implies(x >= 0 and y >= 0, x*y >= 0)
Notice, though, that the Python interpreter will merely check whether the implication statement holds for the particular values assigned to $x$ and $y$ at run-time. To check the validity of the statement in general, one has to run it for every possible combination of values for $x$ and $y$ – a daunting task even considering the limited range of Python’s integers!
Exercises
1.1 [5 points] If statement $q$ has the truth value True, determine all truth value asignments for the primitive statements, $p$, $r$, and $s$ for which the truth value of the statement
$$ (q\rightarrow [(\neg p \vee r)\wedge \neg s])\wedge [\neg s\rightarrow (\neg r\wedge q)]$$ is True. Write a Python program that prints the truth table. The table
should contain a row for each possible combination of values for variables $p$, $r$ and $s$ ($q$ should be constantly true) and columns for the final result.
1.2 [5 points] Consider the following logical implication representing an argument. $$ [(p\vee q)\wedge \neg p]\rightarrow q$$
(a) Show that it is impossible for the conclusion to be False while the hypothesis is True.
(b) Write a Python program that verifies the validity of the above argument. Truth tables do not have to be printed here, the programs should instead simply print INVALID! in case a combination of variable values is found for which the implication is false.
1.3 [15 points] Consider the following system specifications.
"Wheneverthe system software is being upgraded, users cannot access the file system. If users can access the file system, then they can save new files. If users cannot save new files, then the system software is not being upgraded".
(a) Determine if the system specifications are consistent.
(b) Realize that "consistency" simply means that there are no inherent "contradictions" in the specifications. It is a minimal requirement that a set of system specifications has to pass. It simply means that, there exists at least one state of the system that satisfies the specifications. List all states of the above system that satisfy the specifications.
(c) Write a python program verifying (a) and (b) that prints the truth table of statements.
(d) Now this is a question of engineering judgement. Do you think that the above set of system specifications make sense from an engineering point of view? For example, it would make sense that, from an engineering point of view, one may want to say that "Users can access the file system if and only if the system software is not being upgraded. Users can save new files if and only if the system software is not being upgraded. Users can save new files if and only if they can access the file system". Suppose you add these new speicfications to the ones of part (a). Is the system still consistent? Write a python code illustrating your answer.
(e) Now suppose that you consider the system specifications consisting only of: "Users can access the file if and only if they can access the file system". Argue that the above specifications are consistent. Write a python code printing the list of all states that satisfy these specifications.
In [ ]: