Logic Review CS 536: Science of Programming

Logic Review
CS 536: Science of Programming
A. Why?
• We use propositions and predicates to write program specifications.
• Propositions and predicates can be related or manipulated syntactically or semantically.
B. Objectives
At the end of this homework, you should be able to
• Perform various syntactic operations and checks n propositions and predicates.
• Describe the difference between syntactic and semantic equivalence.
• Form proofs of propositions using some standard proof rules.
• Design predicate functions for simple properties on values and arrays.
C. Problems [60 points total]
Quantified variables range over ℤ unless otherwise specified.
1. [8 = 4 * 2 points] Which of the following mean(s) p → q and which mean q → p?
a. p is sufficient for q
b. p only if q
c. p if q
d. p is necessary for q
2. [4 = 2 * 2 points] Let e₁ and e₂ be expressions.
a. In general, does e₁ ≠ e₂ imply e₁ ≢ e₂? If yes, briefly justify (a sentence or two is fine); if no,
give a counterexample (specific values for e₁ and e₂ that show that this implication does not
always hold).
b. In general, does e₁ = e₂ imply e₁ ≡ e₂,? Again give a brief justification or counterexample.
CS 536: Science of Programming – 1 – © James Sasaki, 2022
Illinois Institute of Technology HW 1: Lectures 1 - 2
3. [6 = 3 * 2 points] For each pair below, characterize the state as well- or ill-formed; if wellformed, is it proper? If proper, does the given expression evaluate successfully or cause a
runtime error (and if so, how?)
a. {v = 5, w = 6} and v + 0* z
b. {v = -4, w = 6} and sqrt(v) * sqrt(w)
c. {y = 2, z = -4} and y*y / (z+4)
4. [6 points] The goal is to show that p ∧ ¬(q ∧ r) → q ∧ r → ¬p is a tautology by proving it is 㱻 T.
To do this, complete the proof of equivalence below using (only) the propositional logic rules
(from Lecture 2). Be sure to include the names of the rules. There's more than one correct
answer [just give one of them].
5. [6 points] Simplify ¬(∀ x . (∃ y . x ≤ y) ∨ ∃ z . x ≥ z) to a predicate that has no uses of ¬. Present a
proof of equivalence. You'll need DeMorgan's Laws. Also use rules like "¬(e₁ ≤ e₂) 㱻 e₁ > e₂ by
negation of comparison".
6. [4 = 2 * 2 points] What is the full parenthesization of
a. p ∧ ¬r ∧ s → ¬q ∨ r → ¬p 㲗 ¬s → t ?
b. ∃ m . 0 ≤ m < n ∧ ∀ j . 0 ≤  j < m → b[0] ≤ b[j] ≤ b[m] *
7. [4 = 2 * 2 points] Give the minimal parenthesization of each of the following by showing what
remains after removing all redundant parentheses. Hint: To avoid getting confused about
which parentheses match each other, try rewriting the given parentheses with subscripts: (₁ … )₁
versus (₂ and )₂ and so on.
a. ((¬(p ∨ q) ∨ r) → (((¬q) ∨ r) → ((p ∨ (¬r)) ∨ (q ∧ s))))
b. (∃ i . (((0 ≤ i) ∧ (i < m)) ∧ (∀  j . (((m ≤ j) ∧ (j < n)) → (b[i] = b[j]))))). (This predicate asks “Is there a
value in b[0..m-1] > every value in b[m..n-1]?)
c. ( ∀x.((∃ y.(p → q)) → (∀z.(q ∨ (r ∧ s)))))
p ∧ ¬(q ∧ r) → q ∧ r → ¬p
[you fill in] Defn →
[you fill in] Defn →
[and so on]
 Leave (0 ≤  j < m) as is; don't expand it to ((0 ≤  j) ∧ (j < m)). Don't forget to parenthesize (b[0]), e.g. *
CS 536: Science of Programming – 2 – © James Sasaki, 2022
Illinois Institute of Technology HW 1: Lectures 1 - 2
8. [10 points total] Say whether the given propositions or predicates are ≡ or ≢. Briefly justify your
answer.
a. [2 points] Is p ∧ q ∨ ¬r → ¬p → q ≡ ((p ∧ q) ∨ ((¬r → ((¬p) → q)))) ?
b. [2 points] Is ∀ x . p → ∃ y . q → r ≡ ((∀ x . p) → (∃ y . q)) → r ?
c. [3 points] Is ∃ x . p ∧ ∃ y . (q → r) ∨ ∃ z . r → s ≡ ∃ x . p ∧ (∃ y . q → r) ∨ (∃ z . r → s) ?
d. [3 points] Is (∀ x . p ∨ ∀ y . q) ∨ (∀ z . r) → s ≡ ∀ x . p ∨ (∀ y . q) ∨ ∀ z . r → s ?
9. [6 = 2 * 3 points] Say whether each of the following is a tautology, contradiction, or contingency.
If it's a contingency, show an instance when the proposition is true and show an instance where
it's false.
a. (p → (q → r)) 㲗 ((p → q) → r)
b. (∀ x ∈ ℤ.∀ y ∈ ℤ.f(x, y) > 0) → (∃ x ∈ ℤ. ∃ y ∈ ℤ.f(x, y) > 0). Rely on the idea that for (∀u.  φ) to be
false, we need some value for u for which φ is false. I.e., we need (∃ u.¬φ). Similarly, for
(∃v.ψ) to be false, we ψ to be false for every value of v. I.e., we need (∀v. ¬ψ).
10. [6 points] Write the definition of a predicate function GT(b, x, m, k) that yields true iff x > b[m],
… b[m+k-1]. E.g., in the state {b = (1, 3, -2, 8, 5)}, GT(b, 4, 0, 3) is true; GT(b, 0, 1, 2) is false. You
can assume without testing that the indexes m, … m+k-1 are all in range. If k ≤ 0, the sequence
b[m], b[m+1], …, b[m+k-1] is empty and GT(b, x, m, k) is true. (It's straightforward to write GT so
that this is not a special case.)
Remember, this has to be a predicate function, not a program that calculates a boolean value.
Hint: Check the discussion in the Class 2 notes about trying to translate programs to predicates.
CS 536: Science of Programming – 3 – © James Sasaki, 2022