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.
1
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)
2
We also introduced the following predicate logic equivalences, which hold for any formulas
and :
?(?) ≡ ?? (3.12)
?(?) ≡ ?? (3.13)
?( ∨ ) ≡ (?) ∨ (?) (3.14)
?( ∧ ) ≡ (?) ∧ (?) (3.15)
Additionally, the following equivalences hold whenever is not free in :
? ≡ (3.16)
? ≡ (3.17)
?( ∧ ) ≡ (?) ∧ (3.18)
?( ∨ ) ≡ (?) ∨ (3.19)
?( → ) ≡ (?) → (3.20)
?( → ) ≡ → (?) (3.21)
Task 3A. (10 marks) Using only the equivalences above, give a step-by-step proof that ? ,
where
∶ ? (? ((, )) → ? (? (?(,) ∨ ?(, )) → ?(, ))),
∶ ?, , (((, ) ∧ (, )) → ?((, ) ∧ (, )))
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.
3
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. (2 marks) ?, ( < ∧ < )
2. (3 marks) ?, , (((, ) ∧ (, )) → (, )) ∧ ?, ((, )) ∧ ?, (?(, ))
3. (5 marks) ?, , ((, ) ∧ (, ) ∧ (, )) ∧ ?, ((, ) → ?(, )) ∧ ??((, ))
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
3. Fry
4. Goldberg
5. Laurie
6. Robbie
4
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
: 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
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:
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
1Note that this is a helper variable because , ≡
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
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.
6
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, and satisfy the space limit of 2 MB. 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. If you scan your document, make sure you set the resolution so that the generated
document is no more than 2 MB. The Canvas module, from which you downloaded this document,
has advice to help you satisfy the 2 MB requirement while maintaining readability.
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.