MTH110

Assignment 2 Solutions

Ryerson University

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

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

  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?
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:
Tileabcdefghij
Tile ∈ N ..........
Size ..........
Possible Rows ..........
Possible Columns ..........
Shape ..........

Justify each entry in the table by

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:

2.1 Specification

List the ordered pairs which make up the following relations:

  1. RH

  2. SR

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

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

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

  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.

  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.

  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.

    3. Identify all maximal and minimal elements.

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

    5. Where possible give:
      1. A chain of length 1, which is not contained in a chain of length 2.
      2. A chain of length 2, which is not contained in a chain of length 3.
      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