COMP30026 Models of Computation
Models of Computation
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COMP30026 Models of Computation
Aims
To improve your understanding of propositional logic and first-order predicate
logic, including their use in mechanised reasoning; to develop your skills in
analysis and formal reasoning about complex concepts, and to practise writing
down formal arguments with clarity.
Marking
Each question is worth 2 marks, for a total of 12. We aim to ensure that
anyone with a basic comprehension of the subject matter receives a passing
mark. Getting full marks is intended to be considerably more difficult; the
harder questions provide an opportunity for students to distinguish themselves.
Your answers will be marked on correctness and clarity. Do not leave us
guessing! It is better to be clear and wrong; vague answers will attract few
if any marks. This also means you must show your working in mechanical
questions!
Finally, make sure your writing is legible! We cannot mark what we cannot
read. (Keep in mind that the exam will be on paper, so this will be even more
important later!)
Academic Integrity
In this assignment, individual work is called for. By submitting work for
assessment you declare that:
1. You understand the University’s policy on academic integrity.
2. The work submitted is your original work.
3. You have not been unduly assisted by any other person or third party.
4. You have not unduly assisted anyone else.
5. You have not used any unauthorized materials, including but not limited
to AI and translation software.
1
However, if you get stuck, you can use the discussion board to ask any ques-
tions you have. If your question reveals anything about your approach or work-
ing, please make sure that it is set to “private”.
You may only discuss the assignment in basic terms with your peers (e.g.
clarifying what the question is asking, or recommending useful exercises). You
may not directly help others in solving these problems, even by suggesting
strategies.
Soliciting or accepting further help from non-staff is cheating and will lead
to disciplinary action.
Q1 Propositional Logic: Island Puzzle
You come across three inhabitants of the Island of Knights and Knaves. Now, a
mimic has eaten one of them and stolen their appearance, as well as their status
as a knight or knave. (And is thus bound by the same rules. Remember that
knights always tell the truth, and knaves always lie!)
Each makes a statement:
1. A says: “C is either the mimic or a knight, or both.”
2. B says: “It is not the case that both A is the mimic and C is a knave.”
3. C says: “If B is a knight, then the mimic is a knave.”
Task A
Translate the information above into propositional formulas. Give an appropri-
ate interpretation of all propositional letters used. Use the same interpretation
throughout the question; do not give multiple interpretations.
Task B
Determine which of , , and is the mimic, and prove that it must be the
case using an informal argument.
Some advice: A good answer should not be much longer than about 250
words. But do not worry about the length of your first draft! Instead focus on
finding a proof in the first place. Once you have that, it is much easier to find a
shorter proof. Also, remember that clarity is key: write in complete sentences
with good grammar, but do not include irrelevant information or repeat yourself
unnecessarily.
Q2 Propositional Logic:
Validity and Satisfiability
For each of the following propositional formulas, determine whether it is valid,
unsatisfiable, or contingent. If it is valid or unsatisfiable, prove it by drawing
an appropriate resolution refutation. If it is contingent, demonstrate this with
two appropriate truth assignments.
1. ¬ ∧ ( → ¬)
2
2. ( ∨ ( ∧ ( → ))) ∧ (¬ ∨ ¬(¬ → ¬))
3. ¬(( ∨ ) → ) ∨ ( ↔ ) ∨ ( ∧ ¬)
4. ( ↔ ) → (( → ) ↔ ( ↔ ))
Hint: If you are unsure, you can use a truth table to help you decide!
Q3 Predicate Logic: Translation and Seman-
tics
Task A
Translate the following English sentences into formulas of predicate logic. Give
an appropriate interpretation of any non-logical symbols used. Use the same
interpretation throughout this question; do not give multiple interpretations.
1. Iron is heavier than oxygen.
2. All actinides are radioactive.
3. Some, but not all, lanthanides are radioactive.
4. Actinides are heavier than lanthanides.
5. Both lanthanides and actinides are heavier than iron and oxygen.
6. At least three isotopes of lanthanides are radioactive, but the only lan-
thanide without any non-radioactive isotopes is promethium.
Task B
By arguing from the semantics of predicate logic, prove that the universe of
every model of following formula has at least 3 distinct elements. (Resolution
refutations will receive 0 marks.)
∀∀((, ) → ¬(, )) ∧ ∀∃((, ))