关键词 > COMP2022/2922
COMP2022/2922 A4 (90 marks) – Propositional Logic S2 2023
发布时间：2023-10-25
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
COMP2022/2922
A4 (90 marks) – Propositional Logic
S2 2023
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 (interpreting true as 1 and false as 0).
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. (5 marks) (p ↔ q) ≡ (¬p ↔ ¬q)
2. (5 marks) ((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. (5 marks) (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
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.
