COMP30026代做、Java/Python程序代写

日期：2023-09-02 09:27

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.