Page 28 - Discrete Structure II

5
4
R = R o R
R = { (1, 1), (2, 1), (3, 2), (4, 3)}.

4
R = {(1,1), (2, 1), (3,1), (4, 1)}
5
4
R = R o R = {(1, 1), (2, 1), (3, 1), (4, 1) }

5
6
R = R o R = {(1, 1), (2, 1), (3, 1), (4, 1) }

n
n-1
R = R o R = {(1, 1), (2, 1), (3, 1), (4, 1) }

Exercises

1) List the ordered pairs in the relation R from A = {0, 1, 2, 3, 4} to B = {0, 1, 2, 3}, where (a,b)  R if
and only if

a) a = b
b) a > b
c) a + b = 4
d) a|b
e) gcd(a, b) = 1
f) lcm(a, b) = 2
Solution

a) a = b
R = { (0, 0), (1, 1), (2, 2), (3, 3) }
b) a > b
R= {(1, 0), (2, 0), (3, 0), (4, 0), (2, 1), (3, 1) ,(4, 1), (3, 2), (4, 2), (4, 3)}

c) a + b = 4
R = {(1, 3), (2, 2), (3, 1), (4,0)}

d) a|b

R = {(1, 2), (1, 1), (1, 3), (1, 0), (2,0), (3, 0) (4, 0), (2, 2), (3, 3)}
e) gcd(a, b) = 1
R = { (1, 1), (1, 2), (1, 3), (2, 1), (3, 1), (4, 1), (3, 2), (4, 3)}
f) lcm(a, b) = 2

R={(1, 2), (2, 1), (2, 2)}