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.
3

学霸联盟