Matematisk Lingvistik VT97:06

Exercise class 2

Deadline

These exercises are supposed to be handed in on Thursday April 17. These exercises cover chapter 3 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  A is a subset of B
   R-1     the inverse of relation R

Definitions

In these exercises we will use the definitions for one set and two relations:

   A = { a , b , c , d }
   F = { <a,b> ,  <b,b> ,  <b,c> ,  <b,d> } relation from A to A
   G = A x A                                relation from A to A

Exercises

1. Draw the relational diagrams for F and G.

2. Determine for F and G whether they are reflexive, nonreflexive or irreflexive.

3. Determine for F and G whether they are symmetric, nonsymmetric, asymmetric or anti-symmetric.

4. Determine for F and G whether they are transitive, nontransitive or intransitive.

5. Determine for F and G whether they are connected or nonconnected.

6. Determine if F-1 is transitive and determine if G' is connected.

7. Give the ordered pairs that are in the equivalence relation which divides A in the partition { { a , b , c } , { d } } .

8. Determine for F and G whether they are orders (weak or strong).

9. Construct the relation H for which the following is true: H <= F and H is a strong order.

10. An arbitrary relation J is not irreflexive. Can J be asymmetric? If your answer is yes then give an example for J. If your answer is no then explain why not.

Each exercise is worth 1 point.