ELEN 500

Spring 1999

Homework Assignment 2 98765

1. What are the meet and join for all pairs of vertices in the lattice representation below (the one described in class).

 The meet and join for the 15 pairs of veritices in the lattice representation are shown in the table below.
 
 
PAIR MEET JOIN
(1,3) 1 3
(1,5) 1 5
(1,9) 1 9
(1,15) 1 15
(1,45) 1 45
(3,5) 1 15
(3,9) 3 9
(3,15) 3 15
(3,45) 3 45
(5,9) 1 45
(5,15) 5 15
(5,45) 5 45
(9,15) 3 45
(9,45) 9 45
(15,45) 15 45

 

2. For the set A = {1, 2, 3, 4, 5} and the four relations

R1 which is £ (hint, this is almost the example on page 80 and discussed in class)

R2 which is <

R3 which is =

R4 which is equality modulo 3, (hint problem 13 on page 111 gives an example of equality modulo 3)

Are each of the relations
 
  R1 R2 R3 R4
a) Reflexive  Y  N  Y  Y
b) Symmetric  N  N  Y  Y
c) antisymmetric  Y  Y  Y  N
d) transitive  Y Y  Y Y 
e) a Partial Order Y  N  Y  Y 
f) an equivalence relation N  N  Y  Y 
g)a function N  N  Y  N 

 R1 = {(1,1), (1,2), (1,3), (1,4), (1,5),
                      (2,2), (2,3), (2,4), (2,5),
                                (3,3), (3,4), (3,5),
                                         (4,4), (4,5),
                                                   (5,5)}

 R2 = {(1,2), (1,3), (1,4), (1,5),
                      (2,3), (2,4), (2,5),
                                (3,4), (3,5),
                                         (4,5)}

R3 = {(1,1), (2,2), (3,3), (4,4), (5,5)}

R4 = {(1,1), (1,4), (2,2), (2,5), (3,3), (4,1), (4,4), (5,2), (5,5)}

Recall defintions:

Reflexive:               iff xRx for every x in A
Symmetric:             iff xRy implies yRx for every x, y in A
Anti-symmetric:    iff xRy and yRx implies x=y for every x,y in A
Transitive:             iff xRy and yRz implies xRz for every x,y,z in A

In the above defintions, if the antecedent is false, then the statement is true.

For example, if R dosen't contain (x,y) for any x,y in A, the relation is symmetric.

Similarly, if R contains (x,y) but does not contain (y,x) for any x,y in A, the relation is anti-symmetric. If there exist
atleast one (x,y) in R for which (y,x) exists in R and y is not equal to x, the relation is not anti-symmetric.

If R contains (x,y) but does not contain any pair (y,z), for any x,y,z in A, the relation is transitive.