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.
Please read the MTH110
General Assignment Information
before submitting your assignment.
Preamble
This assignment is based on Tilomino,
also known as Tarski's world. It is a universe consisting of tiles of various
sizes, shapes and colors, about which logical questions can be asked.
Tilomino can be accessed by any Java enabled browser on any modern
operating system. There is also information about Tilomino in the textbook
under the name Tarski's world, see pages 85, 98, 99, 103-107 and 120-121.
Additional notation will need to be introduced to describe this
assignment and the next one. This notation is described in a separate web
page titled Additional Tilomino
Notation for Assignments.
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.
-
In the The World is Round world:
b is below a, but neither a nor c are.
-
In the Four Squares world:
b is a large circle only if a is a small square.
-
In the Smiling World world:
e and h being in the same column is a necessary condition for
e to be a small circle.
-
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
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 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)},
- B = { x ∈ TILENAMES | ∃ w ∈ WORLDS,
x ∈ w ∧ small(x) }
-
L = {w ∈ WORLDS | ∀ x ∈ w,
circle(x)}.
-
M = {w ∈ WORLDS | ∃ s ∈ SHAPES
such that ∀ x ∈ w, ~s(x) }
-
N = {s ∈ SHAPES | ∃ w ∈ WORLDS
such that ∀ x, y ∈ w, s(x) = s(y) }
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)
-
Is { Tx(w) | x ∈ TILENAMES } - { φ },
a partition of w for every w ∈ TILOMINOUNIVERSE,?
Explain your answer.
-
Find the following:
- ℘(S) where S = { x ∈ 2 | COLOF(x, R) ≤ 7 }
(℘(A) is the power set of A).
- R ∪ 2,
- R × 2.
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.
Example:
For example if the statement is:
-
Every small shape is a triangle, but not all triangles are small.
- Smiling World
- Two by Two
The answer might look like:
-
(Ax small(x) -> triangle(x)) & ~(Ay triangle(y) -> small(y))
- Smiling World
- False
- Saying not all triangles are small implies that there is at
least one triangle, which is false.
- Two by Two
- True
- The only small shape is a, which is a triangle, but the block at
(8,3) is a triangle which is not small.
Statements:
-
The southernmost block is a square.
-
Smiling World
-
All Here Revisited
-
All tiles except circles are medium squares.
-
Smiling World
-
The World is Round
-
Whenever a circle is east of a square there is a triangle west of that circle.
-
Two by Two
-
All Here Revisited
-
For every size that appears, there are at least two blocks of that size.
-
Four Squares
-
All Here
-
For a block to be round it is not sufficient that it be West of a triangle.
-
All Here
-
The World is Round
3.2 Translate expressions
Translate each of the Tilomino statements below into 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.
-
∀ y ∈ LABELS, ∃ x ∈ N, ROW(x, N) = y;
-
∀ x ∈ N, ∃ y ∈ N, x ≠ y ∧ samecol(x, y) ∧
(∀ z ∈ N (z ≠ x ∧ z ≠ y) → ~samecol(x, z))
-
∀ x, y ∈ TILENAMES, (x ∈ N ∧ y ∈ N ∧ larger(x, y))
→ x > y
-
∀ x, z ∈ N,
(x ∈ TILENAMES ∧ z ∈ TILENAMES ∧ x > z)
→ (∀ y ∈ TILENAMES, x > y > z → y ∈ N)
-
∀ x, y ∈ N, COLOF(x, N) - COLOF(y, N) ∉ {-1, 1}
-
(∀ x ∈ SHAPE, ∃ y ∈ N, x(y)) ∧
(∀ x ∈ SIZE, ∃ y ∈ N, x(y))
-
∀ x, y ∈ N (samecol(x, y) ∧ larger(x, y))
→ (square(x) ∧ triangle(y) ∧ above(x, y))
-
∀ x, y ∈ TILENAMES
(x ∈ N ∧ y ∈ N ∧ x > y) →
(northof(x, y) ∧ (sameshape(x,y) → rightof(x, y)))
-
∀ x, y ∈ N, circle(x) → (rightof(x, y) ∨ samerow(x, y))
-
COL(a, N) = 2 ∧ ~samecol(g, h) ∧ samecol(a, f)
Hand in
A writeup of your answers to all questions.
The Assignment 1 Marking Sheet
(in pdf format)
stapled to the front of your assignment
Maintained by Peter Danziger.
This page is best viewed with Mozilla Firefox.
Last modified
Thursday, 12-Nov-2009 06:52:56 EST