Matematisk Lingvistik VT97:03

Exercise class 1

Deadline

These exercises are supposed to be handed in on Thursday April 10. These exercises cover chapter 1 and 2 from the course book.

Notation

Because of the limitation of the range of characters in HTML I cannot display every character I need. I will use the following replacements in this exercise:

   A /\ B  the intersection of A and B
   A \/ B  the union of A and B
   P(A)    the power set of A
   A <= B  A is a subset of B
   A < B   A is a proper subset of B
   R-1     the inverse of relation R
   idA     the identity relation over set A
   F o G   the composition of F and G

Definitions

In these exercises we will use the definitions for 6 sets, 2 relations and 1 function.

   A = { a , b , c , d , e }
   B = { d , e }
   C = { b }
   D = { { b } , c }
   E = Ø
   U = A \/ B \/ C \/ D \/ E     universe
   F = { <a,b> , <b,c> , <c,d> } relation from A to A
   G = { <b,e> }                 relation from C to B
   H = { <d,b> , <e,b> }         function from B to C

Exercises

1. Determine which of the following statements are true:
   1. b is an element of A
   2. c is an element of B
   3. d is an element of E
   4. b is an element of D
   5. C is an element of D (the C is a capital character!)
   
   
   

2. Determine which of the following statements are true:
   1. B <= A
   2. C <= D
   3. { C } <= D
   4. E < B
   5. E < E

3. Compute the elements of
   1. C \/ D
   2. A /\ B
   3. (A - D ) \/ C
   4. D' - B
   5. ( C /\ B )' /\ E

4. Use the laws presented in figure 1.7 (p18) of the course book to prove that for any sets X, Y and Z:
   1. ( X \/ Y ) /\ Z' = ( X - Z ) \/ ( Y - Z )

   2. ( Y /\ X' )' \/ ( Z \/ Y ) = U

5. Compute the elements of
   1. AxC
   2. ( CxA ) - ( CxB )

6. Compute the elements of the relation R = { <x,y> | x is an element of A and y is an element of A and x immediately precedes y in the alphabet }

7. Is F a function? Is G a function? Motivate your answers.

8. Compute F' and compute G-1.

9. Determine if function H is into, onto, one-to-one or many-to-one and determine if it is a one-to-one correspondence.

10. H can also be interpreted as a relation from A to A. Compute H o F for this interpretation and find a relation J such that J o F = F.

Each exercise is worth 1 point.