2021/11/22 Submit A2 Online Questions (individual work) | Gradescope
https://www.gradescope.com/courses/319168/assignments/1663751/submissions/new 1/24
0/22 Questions Answered
A2 Online Questions (individual work)
Q1 Sequent Calculus
10 Points
To answer this question you must give Sequent Calculus proofs using rules
and format of sequent calculus that has been taught in this module. You can
find a concise specification of the ruleset at:
https://teaching.bb-ai.net/KRR/lectures/Sequent_Calculus_Rules.pdf
You can either format your answer within a document and submit a PDF file
or you can write out the proof by hand and submit a scanned or
photographed image in the form of either a PDF, PNG or JPG file.
Q1.1 Propositional Logic Sequent Calculus
4 Points
Using the Sequent Calculus, as specified in the module notes, give a proof
of the following sequent:
Upload your answer file here:
Please select file(s) Select file(s)
Save Answer
Q1.2 First-Order Logic Sequent Calculus
6 Points
Using the Sequent Calculus, as specified in the module notes, give a proof
of the following sequent:
¬A, (B ∨ C) → A ⟹ ¬C
未选择任何文件选择文件
S, ∀x[T (x) → ¬S] ⟹ ∀x[¬T (x)]
未选择任何文件选择文件
https://teaching.bb-ai.net/KRR/lectures/Sequent_Calculus_Rules.pdf
2021/11/22 Submit A2 Online Questions (individual work) | Gradescope
https://www.gradescope.com/courses/319168/assignments/1663751/submissions/new 2/24
Upload your answer file here:
Please select file(s) Select file(s)
Save Answer
Q2
15 Points
Axioms and Models
This question is designed to develop and test your understand the idea of a
model of a set of axioms. A model of a set of axioms is a structure that
satisfies those axioms. This structure could be described as a purely
mathematical object, typically a graph, or it could be an actual physical
structure. What is important is just the structural arrangement of a collection
of entities with certain properties and the relationships between these
entities.
We shall consider a type of physical structure which is an arrangement of
physical items (vegetables and toys) that may be entered into a reative
display competition. These arrangements must obey certain rules stated in
terms of two basic properties of the objects and a relationship that can
hold between them. I then give an interpretation ‘key’ that says how
predicates and quantifiers correspond to the physical situation. This
specifies a domain of discourse, which describes the kind(s) of entities that
should comprise the structure and gives the physical meanings of two
property symbols and a relation. Finally, I give a set of axioms that
precisely specify the rules which all arrangements permitted to enter the
competition must satisfy. Thus, via the interpretation key, these logical
axioms correspond to rules regarding possible physical arrangements.
Note that an axiom, or set of axioms, does not normally specify a single
model that satisfies the axioms. In general, an axiom set may be satisfied by
one, several or even an infinite number of models; or it might be satisfied by
no models at all, in which case it is inconsistent.
The Otley Show
The Otley Show, has taken place for over 200 years. It involves a wide
variety of interesting and spectacular competitions such as Tug O’ War,
Fastest Ferret through a Pipe, Curliest Fleeced Wenslydale Sheep and
Three eggs of most distinctively different colours. But my favourite is:
未选择任何文件选择文件 未选择任何文件选择文件
2021/11/22 Submit A2 Online Questions (individual work) | Gradescope
https://www.gradescope.com/courses/319168/assignments/1663751/submissions/new 3/24
Most creative arrangement of vegetables and toy(s) (preferably
knitted), on a tea tray.
Axiomatisation of the Vegetables and Toys Competition
All entries to this competition must strictly obey all formulae in a set of
traditional axioms, otherwise they will be disqualified. The axioms should be
interpreted according to the following specification (key):
Domain of discourse: All items on the tea tray
Item is a vegetable
Item is a toy
Item is balanced on item .
Notes:
The possible numbers of entities in the domain is not specified explicitly,
but may be restricted by the axioms that must be satisfied.
The tea tray itself is not in the domain of discourse. Thus the axioms only
apply to the items on the tray, not the tray. It is required that a single tea
tray is used, satisfying British tea tray regulations and appropriate
standards of taste and decency. It should preferably be a family heirloom.
The category of vegetable also includes so-called “fruit” — tomatoes and
cucumbers are welcome, and of course rhubarb. For the real competition,
the fruit must have been grown by the contestent but we ignore this in
the present axiomatisation.
The category of toy includes any toy-like individual item. Prizes are most
likely to be awarded for arrangements involving knitted toys made by the
contestant, but this is not a strict requirement.
Rule Axiom Rule Name
1. Essential Ontological Precondition
2. Rule of Plenty
未选择任何文件选择文件 未选择任何文件选择文件
V (x) x
T (x) x
B(x, y) x y
∀x[V (x) ∨ T (x)]
∃x∃y∃z[V (x) ∧ V (y) ∧ ¬(x = y) ∧
T (z)]
2021/11/22 Submit A2 Online Questions (individual work) | Gradescope
https://www.gradescope.com/courses/319168/assignments/1663751/submissions/new 4/24
Rule Axiom Rule Name
3. Yorkshire Rule of Parsimony
4. Requirement of Good Taste
5. Superiority Mandate
6. Each to their own
7. Balancing Principle 1
8. Balancing Principle 2
9. Health and Safety
10. The ‘no straddling’ rule — peculiar to Otley
11. Foundational Structural Law
An arrangement of vegetables and toys that satisfies all of these axioms will
be called a legal arrangment.
General guidelines for the following questions
The following questions are a mixture of multiple choice and multiple
selection questions.
In the multiple choice questions the possible answers are preceded by
circular buttons. You must chose exactly one option from those avalable.
In the multiple selection quetions the possible answers are preceded by
square tick boxes. You must chose all correct options. The correct answer
could be any selection (including none or all) from the option.
Q2.1 Unhallowed mask
1 Point
未选择任何文件选择文件 未选择任何文件选择文件 ∀x∀y∀z∀w[ (V (x) ∧ V (y) ∧ V (z) ∧
V (w))
→ (x = y ∨ x = z ∨
x = w ∨
y = z ∨ y = w ∨
z = w) ]
¬∃x[V (x) ∧ T (x)]
∀x[T (x) → ∃y[V (y) ∧ B(x, y)]]
¬∃x∃y∃v[ T (x) ∧ T (y) ∧ ¬(x = y)
∧ B(x, v) ∧ B(y, v)]
¬∃x∃y[B(x, y) ∧ B(y,x)]
∀x∀y∀z[(B(x, y) ∧ B(y, z)) →
¬B(x, z)]
¬∃x∃y∃z∃w[B(x, y) ∧ B(y, z) ∧
B(z,w)]
¬∃x∃y∃z[¬(y = z) ∧ B(x, y) ∧
B(x, z)]
∃x∀y[ ∀z[¬B(y, z)] ↔ (y = x) ]
2021/11/22 Submit A2 Online Questions (individual work) | Gradescope
https://www.gradescope.com/courses/319168/assignments/1663751/submissions/new 5/24
A certain arrangement has been submitted for the competition. All we know
about the arrangement are the following facts:
The arrangment includes an onion.
The arrangment includes a Halloween mask, made of a carved pumpkin
The Halloween mask has been classed being both a vegetable and a toy.
Which of the following statements regarding this arrangement are true?
Save Answer
Q2.2 Enough is enough
1 Point
What is the maximum number of vegetables allowed in a legal
arrangement?
Save Answer
Q2.3 Limitation
未选择任何文件选择文件 未选择任何文件选择文件
We do not know enough about the arragnment to know whether it
can be included in the competition.
The arrangment satisfies Axiom 2 (Rule of Plenty).
The arrangment is a legal arrangement admissible for entry into the
competition.
The arrangment will be disqualified from the competition.
1
2
3
4
5
7
There is no limit.
2021/11/22 Submit A2 Online Questions (individual work) | Gradescope
https://www.gradescope.com/courses/319168/assignments/1663751/submissions/new 6/24
1 Point
Which, if any of the axioms, directly limits the number of vegetables allowed
in a legal arrangmenet.
Save Answer
Q2.4 Is anyone playing?
1 Point
What is the minimum number of toys allowed in a legal arrangement?
Save Answer
Q2.5 How high?
1 Point
未选择任何文件选择文件 未选择任何文件选择文件
1
2
3
4
5
6
7
8
9
10
11
None of the axioms limits the number of vegetables.
0
1
2
3
4
5
2021/11/22 Submit A2 Online Questions (individual work) | Gradescope
https://www.gradescope.com/courses/319168/assignments/1663751/submissions/new 7/24
What is the maximum number of levels of a legal arrangement?
In other words, what is the maximum length of a sequence of items such
that each item except the last is balanced on the next item in the sequence?
Save Answer
Q2.6 Fundamental
1 Point
Which of the axioms tells us that in any legal arrangement there must be
exactly one item that is not balanced on any other item.
未选择任何文件选择文件 未选择任何文件选择文件
1
2
3
4
5
8
There is no limit to the number of items that can be balanced in
sequence
2021/11/22 Submit A2 Online Questions (individual work) | Gradescope
https://www.gradescope.com/courses/319168/assignments/1663751/submissions/new 8/24
Save Answer
Q2.7 First Entry
1 Point
Consider the image below, which depicts a balanced arrangement of toys
and vegetables:
Select all axioms that are satisfied by this arangement:
未选择任何文件选择文件 未选择任何文件选择文件
1
2
3
4
5
6
7
8
9
10
11
2021/11/22 Submit A2 Online Questions (individual work) | Gradescope
https://www.gradescope.com/courses/319168/assignments/1663751/submissions/new 9/24
Save Answer
Q2.8 How about this?
1 Point
Consider the image below, which depicts a balanced arrangement of toys
and vegetables:
未选择任何文件选择文件 未选择任何文件选择文件
1
2
3
4
5
6
7
8
9
10
11
2021/11/22 Submit A2 Online Questions (individual work) | Gradescope
https://www.gradescope.com/courses/319168/assignments/1663751/submissions/new 10/24
Select all axioms that are satisfied by this arangement:
Save Answer
未选择任何文件选择文件 未选择任何文件选择文件
1
2
3
4
5
6
7
8
9
10
11
2021/11/22 Submit A2 Online Questions (individual work) | Gradescope
https://www.gradescope.com/courses/319168/assignments/1663751/submissions/new 11/24
Q2.9 Or this?
1 Point
Consider the image below, which depicts a balanced arrangement of toys
and vegetables:
Select all axioms that are satisfied by this arangement:
未选择任何文件选择文件 未选择任何文件选择文件
2021/11/22 Submit A2 Online Questions (individual work) | Gradescope
https://www.gradescope.com/courses/319168/assignments/1663751/submissions/new 12/24
Save Answer
Q2.10 Little sweetcorn man
1 Point
Consider the image below, which depicts a balanced arrangement of toys
and vegetables:
未选择任何文件选择文件 未选择任何文件选择文件
1
2
3
4
5
6
7
8
9
10
11
2021/11/22 Submit A2 Online Questions (individual work) | Gradescope
https://www.gradescope.com/courses/319168/assignments/1663751/submissions/new 13/24
Select all axioms that are satisfied by this arangement:
Save Answer
未选择任何文件选择文件 未选择任何文件选择文件
1
2
3
4
5
6
7
8
9
10
11
2021/11/22 Submit A2 Online Questions (individual work) | Gradescope
https://www.gradescope.com/courses/319168/assignments/1663751/submissions/new 14/24
Q2.11 Crossing the great aubergine
1 Point
Consider the image below, which depicts a balanced arrangement of toys
and vegetables:
Select all axioms that are satisfied by this arangement:
未选择任何文件选择文件 未选择任何文件选择文件
2021/11/22 Submit A2 Online Questions (individual work) | Gradescope
https://www.gradescope.com/courses/319168/assignments/1663751/submissions/new 15/24
Save Answer
Q2.12 Entailer
1 Point
Which one of the axioms directly entails another axiom?
未选择任何文件选择文件 未选择任何文件选择文件
1
2
3
4
5
6
7
8
9
10
11
2021/11/22 Submit A2 Online Questions (individual work) | Gradescope
https://www.gradescope.com/courses/319168/assignments/1663751/submissions/new 16/24
Note: entails can be writen formall as .
This means that in any circumstance where is true must also be true.
Or, in terms of models: any model that satisfies also satsifies .
If we have a complete proof system for the the logical language in which
and are expressed, then if we would also have ,
meaning that can be proved from by means of the proof system .
Save Answer
Q2.13 Entailee
1 Point
Which one of the axioms is directly entailed by another axiom?
未选择任何文件选择文件 未选择任何文件选择文件
1
2
3
4
5
6
7
8
9
10
11
ϕ ψ ϕ ⊨ ψ
ϕ ψ
ϕ ϕ
S
ϕ ψ ϕ ⊨ ψ ϕ ⊢ S ψ
ψ ϕ S
2021/11/22 Submit A2 Online Questions (individual work) | Gradescope
https://www.gradescope.com/courses/319168/assignments/1663751/submissions/new 17/24
Save Answer
Q2.14 Independence
1 Point
Select all axioms that could be false in relation to some arrangment for
which all of the other ten axioms are true?
未选择任何文件选择文件 未选择任何文件选择文件
1
2
3
4
5
6
7
8
9
10
11
2021/11/22 Submit A2 Online Questions (individual work) | Gradescope
https://www.gradescope.com/courses/319168/assignments/1663751/submissions/new 18/24
Save Answer
Q2.15 Consistency
1 Point
This question concerns the consistency of the Vegetables and Toys axiom
set (i.e. the set of all the axioms 1-11) and also the concept of consistency in
general.
From the following statements select all and only those that are correct:
未选择任何文件选择文件 未选择任何文件选择文件
1
2
3
4
5
6
7
8
9
10
11
2021/11/22 Submit A2 Online Questions (individual work) | Gradescope
https://www.gradescope.com/courses/319168/assignments/1663751/submissions/new 19/24
Save Answer
Q2.16 Specify Models in Python
0 Points
Submission and grading of this sub-question
This part of the question will be graded separately using a model-checker
autograder. You should submit to this using a separate submission link that
will be made available on Gradescope. There are 10 marks available for
your answer to this part of the question. Those marks will be recorded by
the separate model-checker autograder. They will not included in the marks
associated with the Gradescope assignment you are currently looking at.
To answer this part of the question you will need to specify possible models
of the Vegetable and Toy Competition axioms by means of a Python format
file, with the filename:
vegetables_and_toys_models.py .
The file must define a list MODELS , whose elements are dictionaries. Each
dictionary represents a model. Each of these models should have the
following keys:
‘DOMAIN’ : The value should be a set of ints, which represent the entities
of the domain
‘V’ : The value should be the set of entities with the property
(vegetables)
‘T’ : The value should be the set of entities with the property
(toys)
未选择任何文件选择文件 未选择任何文件选择文件
The Vegetables and Toys Competition axiom set is consistent.
The Vegetables and Toys Competition axiom set is inconsistent.
Every set of axioms specified in first-order logic is consistent.
Any axiom set that is satisfied by at least one model must be
consistent.
If an axiom system is inconsistent it cannot be satisfied by any
model.
V
T
2021/11/22 Submit A2 Online Questions (individual work) | Gradescope
https://www.gradescope.com/courses/319168/assignments/1663751/submissions/new 20/24
‘B’ : The value should be a set of tuples, each consisting of two
ints.
The denotation given for ‘B’ represents all instances of the balancing
relation that holds in the model. For example, ‘B’ : {(3,2),(2,1)}
specifies the balancing relation of a model where: entity 3 is balancing on
entity 2, and entity 2 is balancing on entity 1.
Example of the Python model specification format
The following chunk of Python code gives a syntactically well-formed list of
model specifications. The autograder will be able to read the file and check
the models to see if they satisfy the axioms. It will check each model to see
if it is a correct or incorrect model. It will also check for redundant models
that are equivalent to a model previously given in the list.
## vegetables_and_toys_models.py
MODELS = [
{ #1 carrot carriers
‘DOMAIN’: {1,2,3},
‘V’ : {1},
‘T’ : {2,3},
‘B’ : {(1,2),(1,3)}
},
{ #2 teddy and sprout on a turnip
‘DOMAIN’: {1,2,3},
‘V’ : {1,2},
‘T’ : {3},
‘B’ : {(3,2),(2,1)}
},
{ #3 towering tomatoes
‘DOMAIN’: {1,2,3,4,5},
‘V’ : {1,2,3,4,5},
‘T’ : {},
‘B’ : {(1,2), (2,3), (3,4), (4,5) }
},
## Maybe add more??
]
NOTE: The above code is only an example of the format. It is NOT a
correct answer.
The models specified in this list (ie the particular key values) may not
correspond to legal arragements that satisfy all the required axioms of the
toy and vegetable competition. And you will need more than 3 models to
get the full marks.
Requirements for a good solution
未选择任何文件选择文件 未选择任何文件选择文件
B
2021/11/22 Submit A2 Online Questions (individual work) | Gradescope
https://www.gradescope.com/courses/319168/assignments/1663751/submissions/new 21/24
You should aim to construct your list of models to fulfil the following
desiderata:
Each of the models should represent a possible structure that satisfies
ALL of the axioms 1-11 given above, representing the rules of the Otley
Vegetable and Toy Arrangement Competition. In other words they should
correspond to legal arrangements.(You will loose marks if you include any
models that do not satisfy all the axioms.)
The list should contain as many non-equivalent models that satisfy the
axioms as possible.
The list should not contain any models that are equivalent to other
models in the list.
Equivalent Models:
A pair of Models, M1 and M2 , are considered equivalent if:
either they are identical because they have exactly the same denoted
entity sets for all keys;
or there is a one to one mapping from the ints in M1[‘DOMAIN’] to the ints in
M2[‘DOMAIN’] , such that if we apply the mapping to all integers occurring in
M1 we will get a model identical to M2 . (In other words we can convert M1
to M2 (or vice versa) by simply ‘re-numbering’ the entities, leaving the actual
structure the same.)
Hint: There are fewer than 20 non-equivalent models that satisfy all of the
axioms.
Save Answer
Q3 Solving a Planning Problem with Prolog
10 Points
The Frog and Toad Problem
For this question, you will complete the coding of a Prolog program, which
uses Prolog’s search capabilities to find the solution to a well known puzzle.
The puzzle goes as follows:
Three frogs and three toads are lined up in the configuration illustrated in
the Starting State figure below. The frogs are on the right and the toads on
the left.
未选择任何文件选择文件 未选择任何文件选择文件
2021/11/22 Submit A2 Online Questions (individual work) | Gradescope
https://www.gradescope.com/courses/319168/assignments/1663751/submissions/new 22/24
Frog and Toad Puzzle Start State
By a series of valid amphibian moves you must transform the state to the
Goal state, also illustrated below.
Frog and Toad Puzzle Goal State
The frogs and toads can only move in accordance with the following
specification:
Only one amphibian (either a frog or a toad) can move at a time.
Frogs can only move to the left.
toads can only move to the right.
Each move is ether a crawl or a hop.
A crawl is a move to an adjacent empty space.
A hop is a move to an empty space that is two spaces away from the
starting space, such that the space between the start and end of the hop
is occupied by another amphibian (frog or toad).
Frogs can only hop over toads and toads can only hop over frogs.
To solve this puzzle, you should use the bb_planner.pl Prolog program. In
order to configure it to solve this particular problem you will need to define
the predicates initial_state , goal_state and transition .
Code Resources and Solution File Template
As a starting point for answering this question, three program files are
provided on the SWISH Prolog system. These are:
bb_planner.pl
Link: https://swish.swi-prolog.org/p/bb_planner.pl
This Prolog program implements a simple breadth-first planner program.
bb_jugs.pl
Link: https://swish.swi-prolog.org/p/bb_jugs.pl
This is an example file, which illustrates the use of bb_planner to solve a
simple puzzle.
frog+toad_template.pl
Link: https://swish.swi-prolog.org/p/bb_frog+toad_template.pl
This is a template for you answer file.
You should copy it by selecting “Save” from the File menu. Then rename
it by entering a new name, which should be username_frog+toad.pl where
username is your actual University of Leeds username. Then press the
未选择任何文件选择文件 未选择任何文件选择文件
https://swish.swi-prolog.org/p/bb_planner.pl
https://swish.swi-prolog.org/p/bb_jugs.pl
https://swish.swi-prolog.org/p/bb_frog+toad_template.pl
2021/11/22 Submit A2 Online Questions (individual work) | Gradescope
https://www.gradescope.com/courses/319168/assignments/1663751/submissions/new 23/24
Fork button on the right of the name entry box. Then press the Fork
Program button at the bottom of the dialogue window.
State Representation
Before completing the program, you will first need to work out a
representation for possible states that the frogs and toads can be in during
the movement sequence. There are various ways that you could do this, but
probably best to use something simiple as long as it is sufficient to hold the
information required to specify any state that could arise.
Coding the Required Predicates
Once you have decided on your state representation, you need to code the
initial_state , goal_state and transition , replacing the examples in the
template file. For a successful result you need to ensure that your
transitions cover all the possible moves that can be made by any amphibian
in any possible state. You will paste your solutions in the entry boxes of the
following sub-questions.
Running Your Program to Solve the Problem
Once you have coded the predicates you can try running the find_solution
predicate. If you have defined the problem in a viable way, this should
generate a sequence of moves that solves the puzzle.
Q3.1 initial_state
1 Point
Copy your Prolog code specifying the initial_state predicate into the box
below:
Enter your answer here
Save Answer
Q3.2 ‘goal_state’ predicate definition
1 Point
Copy your Prolog code specifying the goal_state predicate into the box
below:
未选择任何文件选择文件 未选择任何文件选择文件
2021/11/22 Submit A2 Online Questions (individual work) | Gradescope
https://www.gradescope.com/courses/319168/assignments/1663751/submissions/new 24/24
Enter your answer here
Save Answer
Q3.3 ‘transition’ predicate definition
6 Points
Copy your Prolog code specifying the transition predicate into the box
below:
Enter your answer here
Save Answer
Q3.4 The Solution
2 Points
Run the find_solution predicate to find a valid sequence of moves from the
starting state to the goal state. If this works, copy the plan that is produced
into the box below:
Enter your answer here
Save Answer
Save All Answers Submit & View Submission