MTH110

Assignment 1 Solutions

Ryerson University

Sets and Statements in Tilomino


This page is best viewed in Firefox.

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.

This solution page is meant to give you an idea of the correct answers to the assignment questions. It is not necessarily comprehensive.

It should be noted that there are often different forms of the correct answer. In this regard note that the following pairs of functions are equivalent:
(Eastof, Rightof), (Westof, Leftof), (Northof, Above), (Southof, Below)

On the other hand note that ~Northof is not equivalent to Southof (since they may be on the same row) and so on.

In many cases DeMorgan's, or other rules, give a different form for the answer.

Part 1 - Propositional Calculus

1.1 From English to Tilomino

For each of the English statements below:
  1. Translate the statement from English into Tilomino.
  2. Use the Tilomino program to evaluate the Tilomino translation and briefly explain the answer it gives.
Statements:

  1. In the Two by Two world:
    b and c are the same size and shape, but a is different in both attributes.

    Sameshape(b,c) & SameSize(b,c) & ~SameSize(a,b) & ~SameShape(a,b)
    Sameshape(b,c) & SameSize(b,c) & ~SameSize(a,b) & ~SameShape(a,b) & ~SameSize(a,c) & ~SameShape(a,c)

    True: b and c are both large squares, but a is a small triangle.

  2. In the The World is Round world:
    b is below a, but neither a nor c are.

    below(b,a) & ~(below(a,a) | below(c,a))
    below(b,a) & ~below(a,a) & ~below(c,a)

    False: c is below a.

  3. In the Four Squares world:
    b is a large circle only if a is a small square.

    (large(b) & circle(b)) -> (small(a) & square(a))

    True(!): b is not a circle, so the predicate is false and thus the implicative statement is true.

  4. In the Smiling World world:
    e and h being in the same column is a necessary condition for e to be a small circle.

    ~(samecol(e,h)) -> ~(small(e) & circle(e)) ≡ (small(e) & circle(e)) -> samecol(e,h)

    True: The predicate is false.

  5. In the All Here world:
    c being a small triangle to the left of d is not a sufficient condition for a to be a large square below d

    ~((small(c) & triangle(c) & leftof(c,d)) -> (large(a) & square(a) & below(a,d)))
    ≡ (small(c) & triangle(c) & leftof(c,d)) & ~(large(a) & square(a) & below(a,d)))
    ≡ (small(c) & triangle(c) & leftof(c,d)) & (~large(a) | ~square(a) | ~below(a,d))

    False: c is not a small triangle.


Part 2 - Sets

2.1 Set Interpretation

For each of the sets at the end of this question,
  1. Explain in English what the set is.
  2. Where possible give an exhaustive definition of the set (listing all the elements inside curly brackets).

Note that, as above, your English explanation should not contain references to quantifiers or free variables, i.e. the variables (like x, y, z, w) that follow quantifiers.

Example
For example, for the set The answer would be:
  1. The set of all worlds in which the tile 'a' is a square.
  2. EXAMPLE = { F, A, B, H }
Here are the sets:

  1. A = {wWORLDS | ∃ x ∈ w such that small(x)},

    1. All worlds which contain a small tile.
    2. {F, 2, R, A, B, H} (= WORLDS - {S})

  2. B = { x ∈ TILENAMES | ∃ w ∈ WORLDS, x ∈ w ∧ small(x) }

    1. Tilenames which represent a small tile in some world.
    2. {a, b, d, e, f, g, j }

  3. L = {wWORLDS | ∀ x ∈ w, circle(x)}.

    1. All worlds which only contain circles.
    2. {R}

  4. M = {wWORLDS | ∃ s ∈ SHAPES such that ∀ xw, ~s(x) }

    1. Worlds which are missing at least one shape
    2. {F, 2, R, S}

  5. M = {sSHAPES | ∃ w ∈ WORLDS such that ∀ x, yw, s(x) = s(y) }

    1. All shapes for which there is a world containing only those shapes.
    2. {Square, Circle}

2.2 Set Operations

  1. For a given world w ∈ TILOMINOUNIVERSE and x ∈ TILENAMES define

    Tx(w) = { y ∈ w | y has label x }.

    Let S(w) = { Tx(w) | x ∈ TILENAMES } - { φ },

    1. List the elements of S(2)

      { {a}, {b}, {c} }

    2. Is { Tx(w) | x ∈ TILENAMES } - { φ }, a partition of w for every w ∈ TILOMINOUNIVERSE,? Explain your answer.

      No. Not all tiles are labeled so the union is not all of the set.

  2. Find the following:
    1. ℘(S) where S = { x ∈ 2 | COLOF(x, R) ≤ 7 } (℘(A) is the power set of A).

      { ∅, {a}, {b}, {c}, {a,b}, {b,c}, {a,c}, {a,b,c} }

    2. R2,

      {[R:a], [R:b], [R:c], [R:(8,6)], [2:a], [2:b], [2:c], [2:(4,8)]}

    3. R × 2.

      {([R:a], [2:a]), ([R:a], [2:b]), ([R:a], [2:c]), ([R:a], [2:(4,8)]), ([R:b], [2:a]), ([R:b], [2:b]), ([R:b], [2:c]), ([R:b], [2:(4,8)]), ([R:c], [2:a]), ([R:c], [2:b]), ([R:c], [2:c]), ([R:c], [2:(4,8)]), ([R:(8,6)], [2:a]), ([R:(8,6)], [2:b]), ([R:(8,6)], [2:c]), ([R:(8,6)], [2:(4,8)]) }

Part 3 - Predicate Calculus - Quantifiers

3.1 From English to Tilomino

For each of the English statements below:
  1. Translate the statement from English into Tilomino.
  2. Use the Tilomino program to evaluate the Tilomino translation for each world given.
  3. In each case give a short explanation of the answer it gives.
Statements:

  1. The southernmost block is a square.

    Ex square(x) & Ay x=y | southof(x,y)

    1. Smiling World

      False: There is no southernmost block, The two squares are in the same row.

    2. All Here Revisited

      True: a is a square south of every other block.

  2. All tiles except circles are medium squares.

    Ax (medium(x) & square(x)) | circle(x)
    ≡ Ax ~(medium(x) & square(x)) -> circle(x)
    ≡ Ax ~circle(x) -> (medium(x) & square(x))

    1. Smiling World

      True: The circles a and e are the only tiles that are not medium squares.

    2. The World is Round

      True: All blocks are circles, so the statement is vacuously true.

  3. Whenever a circle is east of a square there is a triangle west of that circle.

    Ax (circle(x) & Ey (square(y) & eastof(x,y))) -> Ez (triangle(z) & westof(z,x))

    1. Two by Two

      True: There are no circles in this world, so the statement is vacuously true.

    2. All Here Revisited

      True: Note that the circle in (2,2) is not east of any squares.

  4. For every size that appears, there are at least two blocks of that size.

    AxEy x#y & (small(x) -> small(y)) & (medium(x) -> medium(y)) & (large(x) -> large(y))

    1. Four Squares

      False: a is the only small block.

    2. All Here

      The statement is true.

  5. For a block to be round it is not sufficient that it be West of a triangle.

    ~(Ax (Ey triangle(y) & westof(x,y)) -> circle(x))
    ≡ ~(Ax Ay (triangle(y) & westof(x,y)) -> circle(x))
    ≡ Ex Ey triangle(y) & westof(x,y) & ~circle(x)

    1. All Here True: c is a triangle west of f, which is not a circle.
    2. The World is Round False: ~circle(x) is always false, for every tile in the world.

3.2 Translate expressions

Translate each of the Tilomino statements below in English. This translation should not contain references to quantifiers or free variables, i.e. the variables (like x, y, z, w) that follow quantifiers.

Where relevant the statements talk about a world N. You will need to use the Tilomino Notation to understand the some of the statements. Many will not work in the Tilomino Program, though some will.

Note that "below" does not necessarily mean in the same column. You may use the phrase "directly below" to mean "below and in the same column" (below(x,y) & samecol(x,y)). Similarly, you may use the phrase "directly above" to mean "above and in the same column" (above(x,y) & samecol(x,y)).

  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) ∧ above(x, y))
    Given two blocks of differing sizes in the same column, the larger one is a square, and is above the smaller which 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) ∨ samerow(x, y))
    No tile appears to the right of a circle, circles appear only in the rightmost column.

  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.


Maintained by Peter Danziger.
This page is best viewed with Mozilla Firefox.
Last modified Friday, 13-Nov-2009 09:45:17 EST