# Assignment 2 Solutions

## Tilomino Sets, Proofs and Relations

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.

## 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:

1. ∀ y ∈ LABELS, ∃ x ∈ N, ROW(x, N) = y;
Every row has a tile in it.

2. ∀ 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.

3. ∀ x, y ∈ TILENAMES, (x ∈ N ∧ y ∈ N ∧ larger(x, y)) → x > y
Larger blocks have higher names.

4. ∀ 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.

5. ∀ x, y ∈ N, COLOF(x, N) - COLOF(y, N) ∉ {-1, 1}
There are no blocks in adjacent columns.

6. (∀ x ∈ SHAPE, ∃ y ∈ N, x(y)) ∧ (∀ x ∈ SIZE, ∃ y ∈ N, x(y))
There is a tile of each size and shape.

7. ∀ 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.

8. ∀ x, y ∈ TILENAMES (x ∈ N ∧ y ∈ N ∧ x > y) → (northof(x, y) ∧ (sameshape(x,y) → rightof(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.

9. ∀ x, y ∈ N, circle(x) → (rightof(x, y) ∨ circle(y))
Circles appear to the right of all other shapes.

10. 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:
1. small(e) ∧ large(g) ∧ triangle(b) ∧ triangle(c)
##### 3.1 Number of tiles
What is the exact number of tiles in N?
(Hint: first show that this number is the minimum possible and then the maximum possible).

There are at least 8 tiles:
There is at least one tile in each row (1), so there must be at least 8 tiles.

There are at most 8 tiles:
At least every other column is empty (5), since there are 8 columns in total, there are at most 4 nonempty columns. Every nonempty column contains exactly 2 tiles (2), giving 8 tiles in total.

##### 3.2 Identify all tiles
Complete the following table:
Tileabcdefghij
Tile ∈ Na YYYYYYYYNN
SizeS (3)cS (3)cS (3)c S (3)cS (10)bM (6)d L (10)bL (3)c..
Possible Rowse12345678..
Possible Columns (2)(10)2 (10)4 (8)i6 (8)i 8 j8 j 2 (10)4 (8)h6 (8)h..
ShapeT (10)(7)fT (11)T (11)Cj Cj S (10)(7)f S(10)(7)g S (10)(7)g..

#### Tile Names (Existence)

1. We first note that a, h ∈ N (10) and so all names from a to h must appear as well (4). These are the 8 tiles in N.

#### Sizes

1. e is small and g is large (11).

2. Larger blocks have higher names (3), so a to d cannot be larger than e, and so must be small as well. Similarly, since g is large h must be too.

3. Now all blocks except f have assigned sizes, but there are no medium sized blocks. There is at least one tile of each size (6), and so f must be medium.

#### Rows

1. Higher named tiles are above lower named ones (8). There are 8 named tiles, a to h so they correspond one to each of the 8 rows in order.

#### Columns and Shapes

Each non-empty column has exactly 2 tiles in it (2) and so each tile shares a column with at exactly one other. Columns adjacent to nonempty ones are empty (5), since there are tiles in column 2 (10) the only columns with tiles are 2, 4, 6, 8. Finally, the two tiles in col 8 are circles (6 and 9).

1. We know that a and f are of different sizes (sizes above) and they are both in column 2 (10), and so f is a square and a is a triangle (7).

2. Consider the column containing h, it is not in the same column as g (10), and hence is in a column with a smaller tile (g and h are the only large tiles by sizes above). Thus h is a square above a triangle (7).

A similar argument shows that g is also a square which is above a triangle.

3. Since f, g and h are all squares, h is to the right of g (8) which is to the right of f (8). None of them can be in the last column (since that must contain a circle (6 and 9)). So f, g, h must appear in columns 2, 4 and 6 respectively.

4. By 2 and 7 there must be three small triangles in columns 2, 4 and 6, with names from a to e, the one in column 2 is a (11). a, b and c are all triangles so the higher the name the further right the tile (8).

5. This leaves d and e for column 8. Both of them must be circles (6 and 9).

### 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:

1. RH = { (a,a), (a,f), (a,b), (b,b), (c,c), (c,d), (e,e), (f,f), (f,b), ((2,2),(2,2)), ((2,4),(2,4)), ((7,6),(7,6)) }

2. SR = { (a, b), (a, c), (a, (6,8)), (b, a), (b, c), (b, (6,8)), (c, a), (c, b), ((6,8), a) ((6,8), b) }

3. TA = { (a, a), (a, f), (a, e), (b, b), (b, c), (b, (2,4)), (c, c), (c, b), (c, (2,4)), (d, g), (d, (2,2)), (e, a), (e, e), (e, f), (f, a), (f, e), (f, f), (g, d), (g, g), (g, (2,2)), ((2,2), d), ((2,2), g), (2,2), (2,2)) ((2,4), b), ((2,4), c), ((2,4), (2,4))}

### 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)
RelationReflexiveSymmetricAntisymmetricTransitive Equivalence
relation
Partial
Order
Total
Order
RW T F T T F T F
SW F T F F F F F
TW T T F T T F F

### 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.

1. 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
 samecol(x,y)
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).

• RW is Antisymmetric.

To Provex,y ∈ W, x TW y & y TW x ⇒ x = y

Proof  Let x,y ∈ W, with x RW y and y RW x. Thus (samecol(x, y) & below(x, y)) | x = y, and (samecol(y, x) & below(y, x)) | x = y. Noting that samecol(x, y) is equivalent to samecol(y, x) and using distribution and negation gives x = y | (samecol(x, y) & below(x, y) & below(y, x)). But below(x, y) & below(y, x)) is a contradiction (Negation) So x = y, (Elimination)

• SW is Symmetric:

To Provex,y ∈ W, x SW y ⇒ y SW x

Proof  Let x,y ∈ W, with x SW y. Thus ~samerow(x, y). (Definition of SW) So x and y are not in the same row. (Definition of samesrow) But then ~samerow(y, x). (Definition of samesrow) So y SW x (Definition of SW)

• TW is Symmetric.

To Provex,y ∈ W, x TW y ⇒ y TW x

Proof  Let x,y ∈ W, with x TW y. Thus sameshape(x, y) (Definition of TW) So x and y are the same shape. (Definition of sameshape) Thus sameshape(y, x). (Definition of sameshape) So y TW x. (Definition of TW)

2. 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.

• RW is not symmetric:
World A, a and b are in the same column, and below(a, b), so (a RA b) but ~below(b, a) so ~(b RA a)
(Same for any other pair of tiles one below the other in the same column in any world.)

• SW is not Reflexive:
World A, a is in the same row as itself, so ~(a SA a).
(Same for any tile in any world.)

• SW is not Antiymmetric:
World A, (g SA a) and (a SA g), but a ≠ g
(Works for any pair of distinct tiles.)

• SW is not Transitive:
World A, (a SA g), and (g SA d), but ~(a SA d).
(Works for tiles x, y and z, with x and z in the same row and y not.)

• TW is not Antisymmetric:
In world A, (b SA c), and (c SW b), but b ≠ c
(Works for any pair of tiles not the same shape.)

3. 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.

[x] = { y ∈ W | x and y are the same shape }
or
[x] = { y ∈ W | sameshape(x, y) }

[x] is the set of tiles which are the same shape as x.

4. In each case where you answered True to Partial Order or Total Order, for W = B:
1. Give the Hasse diagram.

2. Specify any greatest or least elements.

There are no greatest or least elements.

3. Identify all maximal and minimal elements.

a, c, b, g, f and (5,6) are all maximal elements.
h, (8,3), d, i, f and (5,6) are all minimal elements.

4. If possible give two non-comparable elements which are neither maximal nor minimal.

j, e.

5. Where possible give:
1. A chain of length 1, which is not contained in a chain of length 2.

{g, i}, or {b, d}.

2. A chain of length 2, which is not contained in a chain of length 3.

{a, j, h}, or {c, e, (8,3)}.

3. A chain of length 3, which is not contained in a chain of length 4.

There are no chains of length 3.