CS 536: Science of Programming - HW 1: Propositional & Predicate Logic
Logic Review
CS 536: Science of Programming, Fall 2023
New due date: Fri Jan 27, 11:59 pm Due Wed Jan 25, 11:59 pm
ver. Mon 2023-01-23, 19:40; p.3; 01-26: p.2
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 on 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 Z unless otherwise specified.
- [8=4*2 points] Which of the following mean(s) p → q and which mean q → p ?
- p is sufficient for q
- ponlyifq
- pifq
- p is necessary for q
- [4=2*2 points] Let e1 and e2 be expressions.
- In general, does e1 ≠ e2 imply e1 ≢ e2? If yes, briefly justify (a sentence or two is fine); if no,
give a counterexample (specific values for e1 and e2 that show that this implication does not always hold).
- In general, does e1 = e2 imply e1 ≡ e2,? Again give a brief justification or counterexample.
- [6=3*2 points] For each pair below, characterize the state as well- or ill-formed; if well- formed, is it proper? If proper, does the given expression evaluate successfully or cause a runtime error (and if so, how?)
- {v=5, z=6} andv+0*w
- {v=–4, w=6} and sqrt(v)*sqrt(w)
- {y=18, z=2} and y*y/(z+4)
- [6points] Thegoalistoshowthatp∧¬(q∨r)→q∨r→¬p isatautologybyprovingitis⇔T. To do this, complete the proof of equivalence below using (only) the propositional logic rules (from Class 2). Be sure to include the names of the rules. There's more than one correct answer [just give one of them].
p∧¬(q∨r)→q∨ r→¬p [2023-01-26]
[you fill in] Defn → [you fill in] Defn → [and so on]
- [6points] Simplify¬(∀x.(∃y.x≤y)∨∀z.x≥z) toapredicatethathasnousesof¬. Presenta proof of equivalence. Use DeMorgan's laws for quantified predicates: ¬ ∀ u . r ⇔ ∃ u . ¬ r and ¬∃u.r ⇔ ∀u.¬r. [2023-01-12]. Also use rules like "¬(e1≤e2) ⇔ e1>e2 by negation of comparison".
- [4=2*2 points] What is the full parenthesization of
- p∧¬r∨s→¬q∧r→¬p↔¬s→t ?
- ∀m.0<m<n∧∃j.0≤j<m→b[0]≤b[j]≤b[m] *
- [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: (1 and )1 versus (2 and )2 and so on.
- ((¬(p∨q)∧r)→(((¬q)∨r)→((p∨(¬r))∧(q∧s))))
- (∃j.(((0≤j)∧(j<m))∧(∀k.(((m≤k)∧(k<n))→(b[j]<b[k]))))). (Thispredicateasks
“Is there a value in b[0..m-1] < every value in b[m..n-1]?)
- (∀x.((∃y.(p∧q))→(∀z.(p→(q∧r)))))
[10 points total] Say whether the given propositions or predicates are ≡ or ≢. Briefly justify your answer.
- [2points] Is∀x.p→∃y.q→r≡((∀x.p)→(∃y.q))→r ?
- [3points] Is∃x.p∧∃y.(q→r)∨∃z.r→s≡∃x.p∧(∃y.q→r)∨(∃z.r→s) ?
- [3 points] Is(∀x.p∨∀y.q)∨(∀z.r)→s≡∀x.p∨(∀y.q)∨∀z.r→s ?
- [2points] Isp∧q∨¬r→¬p→q≡((p∧q)∨((¬r→((¬p)→q)))) ?
- [6=3*2 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. (p→(q→r))→((p→q)→r)
c. (∀x∈Z.∀y∈Z.f(x,y)>0)→(∃x∈Z. ∃y∈Z.f(x,y)>0).
[2023-01-12] Use DeMorgan's laws for quantified predicates: ¬∀u.r ⇔ ∃u.¬r and ¬∃u.r ⇔ ∀u.¬r.
10. [6 points] Write the definition of a predicate function GT ( b , x , m , k ) that yields true iff x>b[m],... b[k]. E.g., in the state {b=(1,3,-2,8,5)}, GT(b,4,0,2) is true [2023-01-23: 2, not 3]; GT(b,0,1,2) is false. You can assume without testing that the indexes m,... k are all in range. If k<m, the sequence b[m],b[m+1],...,b[k] 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.
