comp2022/2922 A4 (90 marks) – Propositional Logic s2 2023
• This assignment is due in Week 13 on Sunday 5 November, 11:59pm.
• Submission is on GradeScope. Formatting details will be forthcoming and posted A4 clarifications and guidelines.
• All work must be done individually without consulting anyone else’s solutions in accor- dance with the University’s “Academic Dishonesty and Plagiarism” policies.
• For clarifications and more details on all aspects of this assignment (e.g., level of justifica- tion expected, late penalties, repeated submissions, what to do if you are stuck, etc.) you are expected to regularly monitor the Ed Forum post “Assignment FAQ”.
Problem 1. (10 marks) Draw truth tables for the following formulas: 1. (p∨q)∧¬q
2. ¬(p→q)∨(¬r→(q∧¬p))
Problem 2. (20 marks) Design formulas over the basic syntax for the following
propositions:
1. p and q have the same truth value.
2. p≤q≤r≤s(interpretingtrueas1andfalseas0).
3. The number of true variables out of {p, q, r, s} is exactly 2.
4. The number of true variables out of {p,q,r,s} is strictly greater than the number of true variables out of {r, s, u, v, w}.
Problem 3. (15 marks) Prove the following equivalences using the equivalence laws shown in class:
1. (5marks)(p↔q)≡(¬p↔¬q)
2. (5marks)((p∧q)→r)≡(p→(q→r))
3. (5 marks) (p → (q → (r → s))) ≡ ¬(¬s∧((p∧q)∧r))
Problem 4. (30 marks) Prove the following consequents in natural deduction. For full marks, use as few lines as possible.
1. (5marks)(p→p)→q⊢q
2. (5 marks) p∧q⊢(q→r)→((p∧r)∨¬p)
3. (10 marks) r→¬q,p→s,¬(s∧¬r)⊢¬(p∧q) 4. (10 marks) p ∨ q, ¬p ∨ ¬q, ¬(q ∧ ¬p) ⊢ p ∧ ¬q
comp2022/2922 A4 (90 marks) – Propositional Logic s2 2023
Problem 5. (15 marks) You have been hired by a mysterious man named Thanos. He has several lists of people, and he wants to select a set that contains exactly half of each list, for what are probably completely legitimate reasons. However, he’s having trouble figuring out whether this is possible, which is where you come in. The problem seems to involve nondeterminism, so you’ve decided to try to reduce it to your favourite NP-complete problem: CNF-SAT which takes a Boolean formula in CNF as input and decides whether or not it is satisfiable.
An instance consists of an integer n and several sets S1, ..., Sk ⊆ {1, 2, ..., n}. A solution is a set T such that for each i in {1,2,··· ,k}, we have |Si ∩T| = |Si \T|. SNAP is the set of instances where there exists such a solution.
1. (5 marks) Explain why SNAP is in NP.
2. (10 marks) Show a polynomial reduction from SNAP to CNF-SAT. Explain
the correctness of your reduction, and briefly analyse its complexity.
