关键词 > comp2022/2922
comp2022/2922 Assignment 4 s2 2022
发布时间：2022-10-13
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
comp2022/2922
Assignment 4 (80 marks)
s2 2022
Problem 1. (15 marks, 5 each)
For each of the following formulas, list the values of the formula under every as- signment, state if the formula is valid or not, and state if the formula is satisfiable or not.
1. (p → q) →(q → p)
2. (p ↔(q ↔ r))
3. (p ↔(q ↔ r)) ↔((p ↔ q) ↔ r)
Problem 2. (10 marks) Consider the following recursive procedure applied to formulas F of the basic syntax (i.e., the only connectives are ∧, ∨, ¬):
MyProc(F) :
• If F is an atom, then return 0.
• 
If F is of the form G then return MyProc(G) + 1 (note: this is ordinary addition, not addition mod 2).
• If F is of the form (G ∨ H) then return max(MyProc(G), MyProc(H)).
• If F is of the from (G ∧ H) then return max(MyProc(G), MyProc(H)).
1. (5 marks) What is the value of MyProc on the following formulas:
(a) ¬q
(b) p ∧ ¬¬q
(c) ¬(p ∧ ¬¬q) ∨ ¬p
(d) (¬q ∧ ¬(p ∨ q)) ∨ (¬p ∧ ¬q)
(e) ¬(¬(¬p ∧ (¬q ∨ ¬p)) ∨ ((¬p ∨ q) ∧ ¬(p ∧ ¬¬q)))
2. State in a brief and precise sentence what MyProc(F) does. (5 marks)
Do not simply ”read off” the pseudocode (i.e., ”if F is an atom then it returns 0, ...”).
Problem 3. (15 marks, 5/10) Prove the following equivalences using the equiva- lence laws taught in the course.
1. F ∧ ¬(G ∨ H) ≡ ¬(¬G →(F → H))
2. ((F → G) →(H → ¬G)) →((G ∧ F) → ¬H) ≡ ¬⊥
Problem 4. (10 marks) The following is a table for an ND proof with some entries replaced by ”?”. Complete the proof by providing the missing entries. None of the missing entries were originally blank.
Line Assumptions Formula Justification References
1 
1 (A B) Asmp. I
2 
2 (B C) Asmp. I
3 
3 (C D) Asmp. I
4 4 B Asmp. I
5 5 C Asmp. I
6 ? B ? ?
7 ? ? I ?
8 ? D ? 7
9 3, 5 ? ? 5, 3
10 ? D ∨ E ?
Problem 5. (10 marks, 5 marks each) Prove the following in ND.
1. (A ∧ B) ∨ (¬B → B) ⊢ B
2. (A → B) → C ⊢ C ∨ A
Problem 6. (20 marks, 10 marks each) Prove the following in ND.
1. ¬((A ∨ B) →(A ∨ C)) ⊢ (A ∨ B) ∧ ¬(B → C)
2. (A ∨ B) →(A ∧ B), (B ∨ C) ∧ ¬(B ∧ C) ⊢ (A ∧ ¬C) ∨ (¬A ∧ C)
