MTH110
|
Assignment 1 Solutions
|
|
|
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:
- Translate the statement from
English into Tilomino.
- Use the Tilomino program to evaluate the Tilomino translation
and briefly explain the answer it gives.
Statements:
-
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.
-
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.
-
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.
-
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.
-
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,
- Explain in English what the set is.
-
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
-
EXAMPLE = { w ∈ WORLDS | square(a) }.
The answer would be:
- The set of all worlds in which the tile 'a' is a square.
- EXAMPLE = { F, A, B, H }
Here are the sets:
-
A = {w ∈ WORLDS | ∃ x ∈ w
such that small(x)},
- All worlds which contain a small tile.
- {F, 2, R, A, B, H} (= WORLDS - {S})
- B = { x ∈ TILENAMES | ∃ w ∈ WORLDS,
x ∈ w ∧ small(x) }
- Tilenames which represent a small tile in some world.
- {a, b, d, e, f, g, j }
-
L = {w ∈ WORLDS | ∀ x ∈ w,
circle(x)}.
- All worlds which only contain circles.
- {R}
-
M = {w ∈ WORLDS | ∃ s ∈ SHAPES
such that ∀ x ∈ w, ~s(x) }
- Worlds which are missing at least one shape
- {F, 2, R, S}
-
M = {s ∈ SHAPES | ∃ w ∈ WORLDS
such that ∀ x, y ∈ w, s(x) = s(y) }
- All shapes for which there is a world containing only those shapes.
- {Square, Circle}
2.2 Set Operations
-
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 } - { φ },
-
List the elements of S(2)
{ {a}, {b}, {c} }
-
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.
-
Find the following:
- ℘(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} }
- R ∪ 2,
{[R:a], [R:b], [R:c], [R:(8,6)], [2:a], [2:b], [2:c], [2:(4,8)]}
- 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:
- Translate the statement from
English into Tilomino.
-
Use the Tilomino program to evaluate the Tilomino translation for each world
given.
-
In each case give a short explanation of the answer it gives.
Statements:
-
The southernmost block is a square.
Ex square(x) & Ay x=y | southof(x,y)
-
Smiling World
False: There is no southernmost block, The two squares are in the same row.
-
All Here Revisited
True: a is a square south of every other block.
-
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))
-
Smiling World
True: The circles a and e are the only tiles that are not
medium squares.
-
The World is Round
True: All blocks are circles, so the statement is vacuously true.
-
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))
-
Two by Two
True: There are no circles in this world, so the statement is
vacuously true.
-
All Here Revisited
True: Note that the circle in (2,2) is not east of any squares.
-
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))
-
Four Squares
False: a is the only small block.
-
All Here
The statement is true.
-
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)
-
All Here
True: c is a triangle west of f, which is not a circle.
-
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)).
-
∀ 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) ∧ 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.
-
∀ 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.
-
∀ 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.
-
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