Name:___________________________________ Date: ____________

Quiz 8 Median 8.5/10
  1. The relation R = {(a, a), (b, b), (b,d), (c,c), (d, b), (d, d)} is an equivalence relation on the set L = {a, b, c, d}.

        a. Draw directed graph for the relation R.

 

        b. Find the distinct equivalence classes of R.

         [a],
[b] = [d] = {b, d},
[c]

        c. Create an adjacency matrix for R on L x L.

        

 

 R =
1    0    0    0
0    1    0    1
0    0    1    0
0    1    0    1


        d. Find R2.
             Let A = R and B = R, we have C = R2

         C[r][c] = A[r][0] * B[0][c] + A[r][1] * B[1][c] + ... + A[r][k] * B[k][c]
Row 0:
C[0][0] = 1*1 + 0*0 + 0*0 + 0*0 = 1,  
C[0][1] = 1*0 + 0*1 + 0*0 + 0*1 = 0, 
C[0][2] = 1*0 + 0*0 + 0*1 + 0*0 = 0,
C[0][3] = 1*0 + 0*1 + 0*0 + 0*1 = 0
Row 1:
C[1][0] = 0*1 + 1*0 + 0*0 + 1*0 = 0,  
C[1][1] = 0*0 + 1*1 + 0*0 + 1*1 = 2, 
C[1][2] = 0*0 + 1*0 + 0*1 + 1*0 = 0,
C[1][3] = 0*0 + 1*1 + 0*0 + 1*1 = 2
Row 2:
C[2][0] = 0*1 + 0*0 + 1*0 + 0*0 = 0,  
C[2][1] = 0*0 + 0*1 + 1*0 + 0*1 = 0, 
C[2][2] = 0*0 + 0*0 + 1*1 + 0*0 = 1,
C[2][3] = 0*0 + 0*1 + 1*0 + 0*1 = 0
Row 3:
C[3][0] = 0*1 + 1*0 + 0*0 + 1*0 = 0,  
C[3][1] = 0*0 + 1*1 + 0*0 + 1*1 = 2, 
C[3][2] = 0*0 + 1*0 + 0*1 + 1*0 = 0,
C[3][3] = 0*0 + 1*1 + 0*0 + 1*1 = 2
  R2 =
1    0    0    0
0    2    0    2
0    0    1    0
0    2    0    2
  1. How many numbers are relatively prime to 144?       
    We find the prime divisors of 144. In this case there are two, say a and b from which we can generate the sets of divisors, sets A and B. We want to count the numbers not in these two sets. The union of the numbers that divide into 144 is the compliment of the set we are looking for.
    |A U B| = |A| + |B| - |A Ç B|, |A U B|c = U - |A U B| = |Ac Ç Bc|.
    |Ac Ç Bc| = U - |A| - |B| + |A Ç B|
    144 = 12 * 12 = 2 * 2 * 3 * 2 * 2 * 3 = 24 * 32
    Phi(144) = 144 - 144/2 - 144/3 + 144/6 = 144 - 72 - 48 +  24 = 48