School of Computing and Information Systems COMP30026 Models of Computation
Assignment 1
Released: 24 Aug. 2023; Deadline: 7 Sep. 2023
Aims & Procedure
One aim of this assignment is to improve and test your understanding of propositional logic and first-order predicate logic, including their use in mechanised reasoning. A second aim is to develop your skills in analysis and formal reasoning about complex concepts, and to practise writing down formal arguments with clarity.
This document is the assignment spec. There are six questions which you will find in the re- mainder of this document. Your answers to questions 1–5 are to be submitted through Gradescope, for which there is a menu item on Canvas.
Your answers to question 6 will be submitted on Grok, where you will find a module called “Assignment 1”. This module will become available on August 31. It will explain the submission formats in detail, and contain detailed instructions for submission.
You are required to solve the challenges individually. You will probably find them to be of varying difficulty, but each is worth 20 marks, for a total of 120.
The marks listed on each question do not always reflect the difficulty. 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.
Q1 – Propositional Logic: Island Puzzle
The Island of Truth-Tellers and Liars has gained some newcomers. Whereas truth-tellers always tell the truth and liars always lie, the newcomers sometimes lie and other times tell the truth. In the following scenario, we have three inhabitants of the island, named A, B, and C. They make the following statements:
1. A says: “C is a truth-teller and B is a truth-teller.” 2. B says: “C is a liar or A is a truth-teller.”
3. C says: “If B is a liar, then A is a truth-teller.”
Task 1A. (6 marks, 2 each) Translate (1)–(3) into formulas of propositional logic. Remember to explain your translation!
Task 1B. (14 marks) Assuming there is at least one truth-teller and at least one liar, identify (2 marks) and prove (12 marks) which of A, B and C is a truth-teller, liar or newcomer.
Q2 – Propositional Logic: Validity and Satisfiability
(20 marks, 5 marks each) For each of the following propositional formulas, determine whether it is valid, unsatisfiable, or neither. If it is valid or unsatisfiable, prove it using resolution. If it is neither, demonstrate this with two appropriate truth assignments, one for which the formula is true and one for which it is false.
1. (𝑃 → 𝑃 ) → ¬𝑃
2. ¬(𝑃 ↔𝑄)↔((𝑃 ∨𝑄)∧¬(𝑃 ∧𝑄)) 3. ¬(((𝑃 →𝑄)→𝑃)→𝑃)
4. ((𝑃 →𝑄)→(𝑄→𝑅))→(𝑃 →𝑅)
Hint: If you are unsure, you can use a truth table to help you decide!
Q3 – Predicate Logic: Equivalence Proofs
In the lectures, we introduced the following propositional equivalences:
𝑃 ∧(𝑄∧𝑅)≡(𝑃 ∧𝑄)∧𝑅
𝑃 ∨(𝑄∨𝑅)≡(𝑃 ∨𝑄)∨𝑅
𝑃 ∧(𝑄∨𝑅)≡(𝑃 ∧𝑄)∨(𝑃 ∧𝑅) 𝑃 ∨(𝑄∧𝑅)≡(𝑃 ∨𝑄)∧(𝑃 ∨𝑅) ¬(𝑃 ∧𝑄)≡¬𝑃 ∨¬𝑄
¬(𝑃 ∨𝑄)≡¬𝑃 ∧¬𝑄
𝑃 → 𝑄 ≡ ¬𝑃 ∨ 𝑄
¬𝑃 →¬𝑄≡𝑄→𝑃
(3.1) (3.2) (3.3) (3.4) (3.5) (3.6) (3.7) (3.8) (3.9)
(3.10) (3.11)
We also introduced the following predicate logic equivalences, which hold for any formulas 𝐹 and 𝐺:
∃𝑥(¬𝐹 ) ≡ ¬∀𝑥 𝐹 ∀𝑥(¬𝐹 ) ≡ ¬∃𝑥 𝐹
∃𝑥(𝐹 ∨𝐺)≡(∃𝑥𝐹)∨(∃𝑥𝐺) ∀𝑥(𝐹 ∧𝐺)≡(∀𝑥𝐹)∧(∀𝑥𝐺)
Additionally, the following equivalences hold whenever 𝑥 is not free in 𝐺:
∃𝑥 𝐺 ≡ 𝐺 ∀𝑥 𝐺 ≡ 𝐺
∃𝑥(𝐹 ∧ 𝐺) ≡ (∃𝑥 𝐹 ) ∧ 𝐺 ∀𝑥(𝐹 ∨ 𝐺) ≡ (∀𝑥 𝐹 ) ∨ 𝐺 ∀𝑥(𝐹 →𝐺)≡(∃𝑥𝐹)→𝐺 ∀𝑥(𝐺 → 𝐹 ) ≡ 𝐺 → (∀𝑥 𝐹 )
Finally, we have the following equivalences for reordering quantifiers:
(3.12) (3.13) (3.14) (3.15)
(3.16) (3.17) (3.18) (3.19) (3.20) (3.21)
(3.22) (3.23)
∀𝑥∀𝑦 𝐹 ≡ ∀𝑦∀𝑥 𝐹 ∃𝑥∃𝑦 𝐹 ≡ ∃𝑦∃𝑥 𝐹
(10 marks) Using only the equivalences above, give a step-by-step proof that 𝐴 ⊨ 𝐵, 𝐴∶ ∀𝑦 (∃𝑥 (𝑅(𝑥, 𝑦)) → ∀𝑧 (∀𝑤 (¬𝑅(𝑦, 𝑤) ∨ ¬𝑅(𝑤, 𝑧)) → ¬𝑅(𝑦, 𝑧))),
𝐵∶ ∀𝑥, 𝑦, 𝑧 ((𝑅(𝑥, 𝑦) ∧ 𝑅(𝑦, 𝑧)) → ∃𝑤(𝑅(𝑦, 𝑤) ∧ 𝑅(𝑤, 𝑧)))
Specify the number of the equivalence used at each step.
Task 3B. (10 marks) Use resolution to prove that 𝐶 ⊨ 𝐵, where
𝐶 ∶ ∀𝑥(∃𝑦(𝑅(𝑥, 𝑦)) → 𝑅(𝑥, 𝑥))
Q4 – Predicate Logic: Hollywood Logic
Consider the following predicates:
𝑀(𝑥)∶ 𝑥 is a movie 𝐴(𝑥)∶ 𝑥 is an actor 𝑃(𝑥)∶ 𝑥 is popular
𝑆(𝑥, 𝑦)∶ 𝑥 stars in 𝑦
Task 4A. (10 marks, 2 marks per formula) Using the predicates given above, translate each of
the following sentences into a formula of predicate logic: 1. No actor is a movie, and no movie is an actor.
2. Only actors star in movies, and only movies are starred in by actors. 3. Some movies are popular, and some movies are not popular.
4. At least one popular actor stars in every popular movie.
5. At least one actor who is not popular stars in every movie.
Task 4B. (10 marks) Let 𝐼 be an interpretation with domain 𝐷 satisfying your formulas for (1)–(5). Argue that, given any 𝑚 ∈ 𝐷 such that 𝐼(𝑀)(𝑚) and 𝐼(𝑃)(𝑚) are both true, we have two distinct 𝑎1, 𝑎2 ∈ 𝐷 such that 𝐼(𝑆)(𝑎1, 𝑚) and 𝐼(𝑆)(𝑎2, 𝑚) are both true.
Q5 – Predicate Logic: Interpretations
Task 5A. (10 marks, 2 marks each) Consider an interpretation 𝐼 with domain 𝐷. Determine whether the following closed formulas are true under 𝐼. Whenever possible, prove your claim by giving an appropriate assignment of variables. Otherwise, give a short argument to justify your claim.
1. ∃𝑥(𝑥 + 1 < 1) where 𝐷 is the set of integers, 𝐼(<) is the usual less-than relation, 𝐼(+) is addition, and 𝐼(1) is the integer 1.
2. ∃𝑥(𝑥 + 1 < 1) where 𝐷 is the set of integers, 𝐼(<) is the usual less-than relation, 𝐼(+) is maximum, and 𝐼(1) is the integer 1.
3. ∀𝑥,𝑦∃𝑡(𝑥 < 𝑦 → (𝑥 < 𝑡∧𝑡 < 𝑦)) where 𝐷 is the set of rational numbers and 𝐼(<) is the usual less-than relation.
4. ∀𝑥∃𝑦∀𝑧(𝐴(𝑥, 𝑦) → 𝐴(𝑦, 𝑧)) where 𝐷 is the set of sides of a triangle and 𝐼(𝐴) is the adjacency relation. (Sides are not considered adjacent to themselves.)
5. ∃𝑥, 𝑦∀𝑧(¬𝐴(𝑥, 𝑧) → 𝐴(𝑦, 𝑧)) where 𝐷 is the set of sides of a square and 𝐼(𝐴) is the adjacency relation.
Task 5B. (10 marks total) For each of the following formulas, give two interpretations with finite domains: one that makes it false, and one that makes it true. For the false cases, prove your claim by giving an appropriate assignment of variables (one mark each). In the true cases, give an argument to justify your claim (remaining marks).
1. (2marks)∀𝑥,𝑦(𝑥<𝑦∧𝑦<𝑥)
2. (3marks)∀𝑥,𝑦,𝑧((𝑅(𝑥,𝑦)∧𝑅(𝑦,𝑧))→𝑅(𝑥,𝑧))∧∃𝑥,𝑦(𝑅(𝑥,𝑦))∧∃𝑥,𝑦(¬𝑅(𝑥,𝑦))
3. (5marks)∃𝑥,𝑦,𝑧(𝑅(𝑥,𝑦)∧𝑅(𝑦,𝑧)∧𝑅(𝑥,𝑧))∧∀𝑥,𝑦(𝑅(𝑥,𝑦)→¬𝑅(𝑦,𝑥))∧∀𝑥∃𝑦(𝑅(𝑥,𝑦))
Q6 – Puzzle: Casting Conflicts
Sometimes, casting actors for roles can be filled with conflict. At this casting agency, our job will be to fill as many roles as we can for the upcoming filming season. We will be using our skill at propositional logic to help out.
At our agency, we have the following 6 actors: 1. Aniston
2. Atkinson
Computer Science Tutoring
4. Goldberg 5. Laurie
And the following 13 potential roles across 7 films: • 3 roles in an action film
• 2 roles in a rom-com
• 2 roles in another rom-com
• 2 roles in a thriller
• 2 roles in a comedy
• 1 role in a romance film • 1 role in a horror film
Numbering the actors, films, and roles in the order given above (starting from 1)—so that e.g. Goldberg is actor 4, and roles 1–3 belong to film 1—we denote their relationships and properties using the following indexed propositional variables:
• 𝐴𝑅𝑖,𝑗: actor 𝑖 stars in role 𝑗 • 𝑅𝐹𝑖,𝑗: role 𝑖 is in film 𝑗
• 𝑅𝑜𝑚𝑖: film 𝑖 is a romance • 𝐶𝑜𝑚𝑖: film 𝑖 is a comedy
• 𝑅𝑜𝑚𝐶𝑜𝑚𝑖: film 𝑖 is a rom-com • 𝐻𝑜𝑟𝑟𝑖: film 𝑖 is a horror film
• 𝐴𝑐𝑡𝑖: film 𝑖 is an action film
• 𝑇h𝑟𝑖: film 𝑖 is a thriller
For the sake of convenience, we also define the following helper1 variable: • 𝐴𝐹𝑖,𝑗: actor 𝑖 stars in film 𝑗
Indexed variables are very useful, because they allow us to simulate quantified reasoning over finite domains by using indexed conjunctions and disjunctions. For instance, in our domain, the
indexed formula
⋀ ⋁ 𝐴𝐹𝑎,𝑓 (6.1)
says that every actor stars in a film. However, it is not obvious without referring back to our list of actors and films what the numbers mean. Instead, we will typically define some constants for the maximum indices. We will assume the following constants are provided:
1Note that this is a helper variable because 𝐴𝐹𝑖,𝑗 ≡ ⋁ (𝐴𝑅𝑖,𝑘 ∧ 𝑅𝐹𝑘,𝑗).
• For each actor, a constant for their index, with the same name as the actor • 𝑁𝐴: the total number of actors
• 𝑁𝐹: the total number of films
• 𝑁𝑅: the total number of roles
We can now translate “every actor stars in a film” as
⋀ ⋁ 𝐴𝐹𝑎,𝑓.
This notation also allows us to use a bit of arithmetic, if necessary. For instance, if we wish to say that everyone who is not Fry is in a film, we could use the formula
Fry−1 𝑁𝐹 NA 𝑁𝐹
( ⋀ ⋁𝐴𝐹𝑎,𝑓)∧( ⋀ ⋁𝐴𝐹𝑎,𝑓). (6.3)
𝑎=1 𝑓=1 𝑎=Fry+1 𝑓=1
Task 6A. (10 marks, 1 per formula) Our agency has numerous conditions and constraints it must obey to find roles. Translate the following statements into propositional formulas using indexed conjunctions and disjunctions:
1. Atkinson will not work on action films.
2. Goldberg only works on thrillers and comedies.
3. Every rom-com is both a romance and a comedy.
4. Fry will not work on a romance without also working on a thriller.
5. Robbie won’t take any roles unless given an action role.
6. Anyone who works on a horror film also has to work on a rom-com.
7. An actor cannot take multiple roles in the same film.
8. An actor who takes any roles must take at least two roles.
9. Aniston will not work with anyone else on the same film, but must take at least one role.
10. Laurie can work on at most one comedy that does not have either Fry or Atkinson in it.
Submission and Marking: Submit your formulas for this questions on the Grok module named “Assignment 1”. This module will be available from August 31.
You will be able to check that your answers have the correct syntax before submission. The formula format will be similar to the format from Worksheet 1. It will be described in more detail on the Grok module page.
You will receive 1 mark for each correct formula.
Task 6B. (10 marks, maximum 1 per role filled) Having assessed the situation, we must now match actors to roles. Find an assignment of actors to roles which satisfies all of the conditions above. Note that you do not have to fill every role, assign someone to every film, or give every actor a role.
Submission and Marking: Submit your answer for this question on the Grok module named “Assignment 1”. This module will be available from August 31. You will submit your answer as a list of pairs of the form (𝑎, 𝑟), where 𝑎 is the actor index and 𝑟 is the role index.
Each role successfully filled is worth 1 mark, up to a maximum of 10 marks. Beware: an answer which does not satisfy the conditions will receive zero marks for this task.
Programming Help
Further Submission Advice
The deadline is 7 September at 17:00. Late submission will be possible, but a late submission penalty will apply: a flagfall of 10 marks, and then 10 marks per 12 hours late.
Note that on Grok, “saving” your file does not mean submitting it for marking. To submit, you need to click Mark and then Submit. You can submit as many times as you like. What gets marked is the last submission you have made before the deadline.
For questions 1–5, if you produce an MS Word document, it must be exported and submitted as PDF, We also accept neat hand-written submissions, but these must be scanned and provided as PDF. Illegible or poorly-written submission will likely attract few, if any, marks.
Make sure that you have enough time towards the end of the assignment to present your solutions carefully. A nice presentation is sometimes more time consuming than solving the problems. Start early; note that time you put in early usually turns out more productive than a last-minute effort.
Academic Honesty Statement
By submitting work for assessment you implicitly declare that you understand the University’s policy on academic integrity and that the work submitted is your original work. You declare that you have not been unduly assisted by any other person (collusion). In this assignment, individual work is called for, but if you get stuck, you can use the Ed Discussion board to ask any questions you have. As long as nobody directly gives away solutions, our discussion forum is both useful and appropriate for this; we can all use it to support each other’s learning. If your question is simply to clarify some aspect of the assignment, your post can be ‘public’, but if it reveals anything about your attempted solution, make sure it is submitted as a ‘private’ post to the teaching team. Soliciting help from sources other than the above will be considered cheating and will lead to disciplinary action.
CS Help, Email: tutorcs@163.com