联系我们： 手动添加方式: 微信>添加朋友>企业微信联系人>13262280223 或者 QQ: 1483266981

Logic Foundation and Exchange Problems COMP 4418 – Assignment 1 Due 10 Oct. 2025 Total Marks: 100 Late Penalty: 20 marks per day Worth: 15% of the course Question 1 (10 marks) True or False questions. 1. Propositional logic contains existence quantifier. 2. Modus Ponens is complete in propositional logic. 3. Every valid formula in first-order logic can be expressed as an equivalent proposi- tional logic formula. 4. The formula ((P→ Q)∧ (Q→ R))→ (P→ R) is a tautology. 5. x. y.(x < y) and y. x.(x < y) are logically equivalent statements over the natural numbers. Notice: For question 2-6, a complete solution must be provided. Proofs or justifying calcu- lations are required to obtain full marks. Answers stated without adequate explanation will receive at most half credit. Question 2 (15 marks) You are given the following English sentences. “I will feel happy if I watch the COMP4418 lecture videos, or I will watch COMP4418 lecture videos if I feel happy.” 1. Translate the following English sentence to propositional logic. 2. Determine whether the statement is valid (i.e., tautology) by using a truth table. 3. Determine whether the statement is valid (i.e., tautology) by using the resolution rule. Question 3 (15 marks) Convert the following formulae into Conjunctive Normal Form (CNF). (P→ Q)∨ ( R→ Q). (P→ (Q∨R))∧ (P→ (Q∨ R)). ((P→ R)→ Q)∧ ( Q→ R). 1 Due Date: 10 Oct. 2025, 17:00 COMP 4418 – Assignment 1 Question 4 (15 marks) Translate the following English sentences to first-order logic. (Use meaningful predicate names or state the scheme of abbreviation that you are using.) No dog can fly. Everyone who teaches one student is taught by someone else. There exists some student who doesn’t like all the operating systems. Question 5 (15 marks) Given the following statements: C1 : x. y.P(x,y) C2 : x. y.P(x,y)→ P(y,x) C3 : x. y. z.((P(x,y)∧P(y,z))→ P(x,z)) C4 : x.P(x,x) Prove by resolution that C1∧C2∧C3 C4. Question 6 (30 marks) Consider a Shapley-Scarf housing market with a set of agents N = {1,2,3,4,5}, a set of items O = {o1,o2,o3,o4,o5}, and an endowment function ω : N → 2O such that ω(i) = {oi}. The preferences of the agents are as follows from left to right in decreasing order of preference. 1 : o5,o2,o1,o3,o4 2 : o4,o5,o3,o1,o2 3 : o4,o2,o3,o5,o1 4 : o2,o1,o5,o3,o4 5 : o2,o4,o5,o1,o3 1. Find the outcome of the TTC (top trading cycles) algorithm. Can agent 3 misreport her preference to get a more preferred allocation Prove or disprove that the outcome is individually rational. 2. Serial Dictatorship (SD) is another mechanism for the house market allocation. Initialize H to the set of all houses O. Determine the permutation order π of the agents. for i= 1,2, . . . ,n do Assign the π(i)-th agent her favorite house o from among those in H. Delete o from H. Consider the permutation order π = (3,2,5,4,1). Find the outcome of the Serial Dictatorship rule. Can agent 3 misreport her preference to get a more preferred allo- cation Prove or disprove that the outcome is core stable. 2 Due Date: 10 Oct. 2025, 17:00 COMP 4418 – Assignment 1 SUBMISSION Submit your solution directly via Moodle in the assessment hub at the end of the Moodle page. Please make sure that your manuscript contains your name and zID. Your answers are to be submitted in a single PDF file. We will NOT accept any other file formats. Please make sure that your solutions are clearly readable. The deadline for this submission is 10 Oct. 2025, 17:00. Academic Honesty and Plagiarism All work submitted for assessment must be your own work. Assignments must be com- pleted individually. We regard copying of assignments, in whole or part, as a very serious offence. Be warned that: the submission of work derived from another person, or jointly written with someone else will, at the very least, result in automatic failure for COMP4418 with a mark of zero; allowing another student to copy from you will, at the very least, result in a mark of zero for your own assignment; and severe or second offences will result in automatic failure, exclusion from the Univer- sity, and possibly other academic discipline. students are not allowed to derive solutions together as a group during such discus- sions. Students are also warned not to send solution fragments of the assignments to each other in any form (e.g. as email or listings). In addition, copying/purchasing of solutions that is available on the web is also not permitted. Students are strongly advised to protect their work. Do not leave your terminal/computer unattended, or leave printouts at the printer for others to take. Read the study guide carefully for the rules regarding plagiarism.