Page 25 - Discrete Structure II

Let A ={ 1, 2, 3} and B ={1, 2, 3, 4}. Let R1 = { (1, 1), (2, 2), (3, 3)} and R2 = { (1, 1), (1, 2), (1, 3), (1, 4)}

Find

1. R1 ∪ R2 = { (1, 1), (2, 2), (3, 3), (1, 2) (1, 3) , (1, 4)}
2. R1 ∩ R2 = {(1, 1)}
3. R1 - R2 ={(2, 2), (3, 3)}
4. R2 - R1 ={ (1, 2), (1, 3) , (1, 4)}

Composite of Relations

Let R be a relation from a set A to a set B and S a relation from B to a set C. The composite of R and S is
the relation consisting of ordered pairs (a, c), where a ∈ A, c ∈ C, for which there exists an element b
∈ B, such that (a, b) ∈ R and (b, c) ∈ S

Recall from algebra f(x) = 2x + 1 and g(x) = 3x what is f o g (x)?

Answer: f(g(x) = f(3x)= 2(3x) + 1 = 6x + 1

Example

What is the composite of the relation R and S, where
R is the relation from A={1, 2, 3} to B={ 1, 2, 3, 4} with R = {(1, 1), (1, 4), (2, 3), (3, 1), (3, 4)}

and S is the relation from B= { 1, 2, 3, 4} to C= {0, 1, 2} with S = {(1, 0), (2, 0), (2, 3), (3, 1), (3, 2), (4,1)}?

SOR?

Answer: A={1, 2, 3} to B={ 1, 2, 3, 4} C= {0, 1, 2}

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

11
1 4

23

31

34

S = {(1, 0), (2, 0), (2, 3), (3, 1), (3, 2), (4,1)}

8