Preamble

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

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.

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

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

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

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.

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

Part 2 - Sets

2.1 Set Interpretation

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

• EXAMPLE = { w ∈ WORLDS | square(a) }.

1. The set of all worlds in which the tile 'a' is a square.
2. EXAMPLE = { F, A, B, H }

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

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

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

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

5. N = {s ∈ SHAPES | ∃ w ∈ WORLDS such that ∀ x, y ∈ w, s(x) = s(y) }

2.2 Set Operations

1. For a given world w ∈ TILOMINOUNIVERSE and x ∈ TILENAMES define
   T_x(w) = { y ∈ w | y has label x }.
   Let S(w) = { T_x(w) | x ∈ TILENAMES } - { φ },

   1. List the elements of S(2)

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

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

   2. R ∪ 2,
   3. R × 2.

Part 3 - Predicate Calculus - Quantifiers

3.1 From English to Tilomino

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.

Example:

For example if the statement is:

• Every small shape is a triangle, but not all triangles are small.
  1. Smiling World
  2. Two by Two

• (Ax small(x) -> triangle(x)) & ~(Ay triangle(y) -> small(y))
  1. Smiling World
     2. False
     3. Saying not all triangles are small implies that there is at least one triangle, which is false.
  2. Two by Two
     2. True
     3. The only small shape is a, which is a triangle, but the block at (8,3) is a triangle which is not small.

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.

1. ∀ y ∈ LABELS, ∃ x ∈ N, ROW(x, N) = y;

2. ∀ x ∈ N, ∃ y ∈ N, x ≠ y ∧ samecol(x, y) ∧ (∀ z ∈ N (z ≠ x ∧ z ≠ y) → ~samecol(x, z))

3. ∀ x, y ∈ TILENAMES, (x ∈ N ∧ y ∈ N ∧ larger(x, y)) → x > y

4. ∀ x, z ∈ N, (x ∈ TILENAMES ∧ z ∈ TILENAMES ∧ x > z) → (∀ y ∈ TILENAMES, x > y > z → y ∈ N)

5. ∀ x, y ∈ N, COLOF(x, N) - COLOF(y, N) ∉ {-1, 1}

6. (∀ x ∈ SHAPE, ∃ y ∈ N, x(y)) ∧ (∀ x ∈ SIZE, ∃ y ∈ N, x(y))

7. ∀ x, y ∈ N (samecol(x, y) ∧ larger(x, y)) → (square(x) ∧ triangle(y) ∧ above(x, y))

8. ∀ x, y ∈ TILENAMES (x ∈ N ∧ y ∈ N ∧ x > y) → (northof(x, y) ∧ (sameshape(x,y) → rightof(x, y)))

9. ∀ x, y ∈ N, circle(x) → (rightof(x, y) ∨ samerow(x, y))

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