MTH110
|
Assignment 2 Solutions
|
|
|
Tilomino Sets, Proofs and Relations
|
Due: Dec 3 In Class. No Late Submissions.
|
This page is best viewed in Firefox or Mozilla.
If you are having trouble reading some of the symbols in this page it probably
means that your browser is not HTML 4.0 compliant.
Rules
- This assignment has 2 parts and is worth 10% of the course mark.
-
Once again this assignment is based on Tilomino, also known as Tarski's world. You will
need the Additional Tilomino Notation
for Assignments.
- You are allowed to work on this assignment in groups of up to 4.
Each team only hands in one assignment for the whole team.
All the members of the group must be listed on the marking sheet
of that assignment.
- Please don't cheat, you will be caught and it is a distasteful
experience for all concerned and can have serious consequences. Read the
MTH110 Teamwork and Cheating
Policy before submitting your assignment.
-
Please read the MTH110
General Assignment Information
before submitting your assignment.
Part 1
1.0 Explanation
In ths question you will invent a new Tilomino world called N (i.e an 8
X 8 grid with tiles on it of the types allowed in Tilomino) which satisfies all the
properties 1 to 11 listed below. Properties 1 - 10 are those of question 3.2 of
Assignment 1, except
that numbers 7 and 9 have been changed slightly.
So here is a list of all the rules that it satisfies, each
is stated in both logical form and in English:
-
∀ y ∈ LABELS, ∃ x ∈ N, ROW(x, N) = y;
Every row has a tile in it.
-
∀ x ∈ N, ∃ y ∈ N, x ≠ y ∧ samecol(x, y) ∧
(∀ z ∈ N (z ≠ x ∧ z ≠ y) → ~samecol(x, z))
Every nonempty column has exactly two tiles in it.
-
∀ x, y ∈ TILENAMES, (x ∈ N ∧ y ∈ N ∧ larger(x, y))
→ x > y
Larger blocks have higher names.
-
∀ x, z ∈ N,
(x ∈ TILENAMES ∧ z ∈ TILENAMES ∧ x > z)
→ (∀ y ∈ TILENAMES, x > y > z → y ∈ N)
Tile names in N are consecutive.
There are no gaps in tile names.
-
∀ x, y ∈ N, COLOF(x, N) - COLOF(y, N) ∉ {-1, 1}
There are no blocks in adjacent columns.
-
(∀ x ∈ SHAPE, ∃ y ∈ N, x(y)) ∧
(∀ x ∈ SIZE, ∃ y ∈ N, x(y))
There is a tile of each size and shape.
-
∀ x, y ∈ N (samecol(x, y) ∧ larger(x, y))
→ (square(x) ∧ triangle(y) )
Given two blocks of differing sizes in the same column, the larger one is a
square and the smaller is a triangle.
-
∀ x, y ∈ TILENAMES
(x ∈ N ∧ y ∈ N ∧ x > y) →
(northof(x, y) ∧ (sameshape(x,y) → (
rightof(x, y) | samecol(x, y))))
Higher named tiles are above lower named ones, if they are of the same shape
then the higher named ones are also to the right or in the same
column.
-
∀ x, y ∈ N, circle(x) → (rightof(x, y) ∨ circle(y))
Circles appear to the right of all other shapes.
-
COL(a, N) = 2 ∧ ~samecol(g, h) ∧ samecol(a, f)
a is in column 2 and so is f, but g and h are in different columns.
In addition it also satisfies the following rule:
-
small(e) ∧ large(g) ∧ triangle(b) ∧ triangle(c)
3.1 Number of tiles
What is the exact number of tiles in N?
Justify your answer using the properties 1 to 11.
(Hint: first show that this number is the minimum possible and then the
maximum possible).
3.2 Identify all tiles
Complete the following table:
Tile | a | b | c | d | e | f | g | h | i | j |
Tile ∈ N
| . | . | . | . | . | . | . | . | . | . |
Size
| . | . | . | . | . | . | . | . | . | . |
Possible Rows
| . | . | . | . | . | . | . | . | . | .
|
Possible Columns
| . | . | . | . | . | . | . | . | . | . |
Shape
| . | . | . | . | . | . | . | . | . | . |
- If N contains unnamed tiles, add one extra column to the table for
each unnamed tile.
- In the first row of the table, specify whether there is a tile with that
name in N.
- If there is such a tile in N, specify its size and shape in the
next two rows.
- Note that there may be more than one solution.
Justify each entry in the table by
- listing the properties (1 to 11) that you used to deduce this answer
(if you used any);
- listing the previous answers that you used to deduce the current answer
(if you used any);
- stating other relevant facts about Tilomino worlds that are needed to
deduce this answer (if there are any);
- explaining how all this information is combined to give you this answer.
Only provide answers that you can prove.
You will get marks for reaching conclusions that can be proved with complete certainty,
and you may lose marks for reaching conclusions that have not been proven.
Give your justification in the order in which you are making your deductions
(i.e. in the order in which you are finding the answers).
If two or more entries in this table have the same justification,
you may justify them together.
You should provide justifications for each of the following categories.
Tile Names (Existence)
Sizes
Rows
Columns and Shapes
1.3 Place tiles in world
Now that you have identified all the tiles, place them in N so that all
the expressions 1 to 11 are true and all the other constraints listed so far are
satisfied. Do this with a drawing. You don't need to explain your answer, but
it must be correct. Note that there may be more than one possible solution.
Part 2 - Relations
2.0 Definitions
Given an arbitrary world W ∈ TILOMINOUNIVERSE we define
three binary relations RW, SW and
TW as follows:
-
∀ x, y ∈ W, x RW y ⇔
(samecol(x, y) & below(x, y)) |
x = y.
-
∀ x, y ∈ W, x SW y ⇔
~samerow(x, y).
-
∀ x, y ∈ W, x TW y ⇔
sameshape(x,y)
2.1 Specification
List the ordered pairs which make up the following relations:
-
RH
- SR
-
TA
2.2 Table
Fill out each cell of the following table with True or False.
(Note that the answers should be the same no matter what W is)
Relation | Reflexive | Symmetric | Antisymmetric | Transitive
| Equivalence relation | Partial Order | Total Order
|
---|
RW | . | . | . | . | . | . | .
|
SW | . | . | . | . | . | . | .
|
TW | . | . | . | . | . | . | .
|
2.3 Justification
The answers in this section refer to the table in the previous section.
Note that this section will be marked independently of the previous one. Thus
if your answer in the table are incorrect you will receive 0 for the
corresponding answer in this section.
Check your answers to the table carefully before continuing.
-
In each case where you answered True to Symmetric or
Antisymmetric provide a proof of the result. Be
sure to clearly state what you are trying to prove, both in English and
symbolic form and to justify each step as appropriate.
Note that in your proof you may assume that Tilomino functions act as described.
For example, suppose we know
then we now that x and y are in the same column,
and so we could make the statement:
| x and y are in the same column (Definition of samecol).
|
We can use the definitions in reverse as well.
Thus, if we know that x and y are in the same column in a world,
we can conclude
| samecol(y,x) (Definition of samecol).
|
- In each case where you answered False to Reflexive,
Symmetric, Antisymmetric or Transitive give a world
from the Tilomino program { F, 2, R, A, B, S, H } where the property
fails, identify why the property fails in that world.
-
In each case where you answered True to Equivalence relation:
Describe an arbitrary equivalence class, [x], x ∈ W,
both as a set and in English.
-
In each case where you answered True to Partial Order or
Total Order, for W = B:
-
Give the Hasse diagram.
-
Specify any greatest or least elements.
-
Identify all maximal and minimal elements.
-
If possible give two non-comparable elements which are neither
maximal nor minimal.
-
Where possible give:
-
A chain of length 1, which is not contained in a chain of length 2.
-
A chain of length 2, which is not contained in a chain of length 3.
-
A chain of length 3, which is not contained in a chain of length 4.
Hand in
Maintained by Peter Danziger.
This page is best viewed with Mozilla Firefox.
Last modified
Thursday, 26-Nov-2009 13:07:31 EST