Description

Homework 1: Course Basics, Logic
Prof. Stefan Muller
Updated Aug. 30
This assignment contains 7 written task(s) and 3 task(s) for which you’ll submit logic proofs from the online tool, for a total of 60 points.
Logistics
Please read and follow these instructions carefully.
Submit your written answers in a single PDF or Word document. Typed answers are preferred (You can use any program as long as you can export a .pdf, .doc or .docx; LaTeX is especially good for typesetting logic and math, and well worth the time to learn it), but legible handwritten and scanned answers are acceptable as well.
Your Blackboard submission should contain exactly the file with your written answers and all of the .log files with your proofs (with the names given in each problem); do not rename these files. Do not compress or put any files in folders.
Read the policy on the website and be sure you understand it.
1 Course Basics
Task 1.1 (Written, 10 points).
For each statement, say whether it is true or false and explain in 1-2 sentences.
a) Testing provides more of a guarantee that a program is correct than verification, because you actually run the program.
b) It is useful to do both testing and verification on a program before deploying it.
Task 1.2 (Written, 10 points).
For each pair of propositions, say whether they are
(I) syntactically equal (≡) (and therefore also semantically equal)
(II) semantically equal (=) but not syntactically equal, or
(III) neither
a) p ∧ q ∨ r (p ∧ q) ∨ r
b) p → q ¬p →¬q
c) (p → q) ↔ (¬q →¬p) T
d) ¬p p → q
e) p ∧ q ∨ r p ∧ (q ∨ r)
2 Propositional Logic
Task 2.1 (Written, 5 points).
For the following proposition, construct a truth table and say whether it is a tautology, contradiction or contingency. Explain your answer briefly.
(P → Q) → (¬P →¬Q)
Task 2.2 (Programming, 5 points).
Prove that P → (Q ∨ P) is a tautology by proving T ⇒ P → (Q ∨ P).
Important: Submit your proof (and only your proof) in the file tauto.log. It should be in a format checkable by the proof checker at http://www.cs.iit.edu/~smuller/cs536-f23/logic/proofs.html. That is, you should be able to copy and paste the entire contents of your file into the text box of the proof checker, click “Check” and have it respond that the proof is correct. To help you, you can select “HW1 Task 2” from the dropdown box on the proof checker page to load the editor with the statement above, and work on your proof there. When you’re done, click “Download” to download the finished proof.
Task 2.3 (Written, 2 points).
As we saw in the previous task, proving T ⇒ P shows that P is a tautology. What does it show if we instead prove P ⇒ T?
Task 2.4 (Programming, 5 points).
Prove the following implication. Submit your proof in the file uncurry.log, following the same instructions as in Task 2.
P → (Q → R) ⇒ (P ∧ Q) → R
3 Predicate Logic
Task 3.1 (Written, 4 points).
Let Z be the set of integers and let M be the set of prime numbers (clearly M ⊂ Z). Goldbach’s Conjecture states that every even integer greater than 2 is the sum of two prime numbers. Updated 8/30: Clarified that this holds only for even numbers greater than 2. State Goldbach’s Conjecture formally in our predicate logic notationa You can quantify universally and existentially over M in the same way that you do over Z (∀x ∈ M.P(x), ∃y ∈ M.Q(y), …). You can use standard mathematical symbols and operators (<, >, ≤, ≥, =, +, etc.).

aYou do not need to prove this, and I would suggest not trying since it’s been an open problem since 1742. However, if
you do happen to prove it, it would be worth substantial extra credit and probably a Fields Medal.
Task 3.2 (Written, 9 points).
Are the following statements true (provable) or false (have a counterexample)? Explain briefly (1-2 sentences).
a) ∀x ∈Z.∀y ∈Z.x < y
b) ∀x ∈Z.¬(∃a ∈Z.∃b ∈Z.a > 1 ∧ b > 1 ∧ a ∗ b = x)
c) ∀x ∈Z.∃y ∈Z.y = x ∗ 2.
Task 3.3 (Programming, 10 points).
Prove the following implication. Submit your proof in the file pred.log, following the same instructions as in Task 2.
(∀x.P(x) → Q(x)) ⇒¬(∃x.P(x) ∧¬Q(x))
4 One more wrap-up question
Task 4.1 (Written, 0 points).
How long (approximately) did you spend on this homework, in total hours of actual working time? Your honest feedback will help us with future homeworks.