Discrete Structures
Relations
Lecture-14
Relations
• Relationships between elements of sets are represented using the
structure called a relation, which is just a subset of the Cartesian
product of the sets.
• Relations can be used to solve problems such as determining:
1. which pairs of cities are linked by airline flights in a network,
2. finding a viable order for the different phases of a complicated
project, or
3. producing a useful way to store information in computer
databases.
2
3
4
5
Example: Let A = {1, 2, 3} and B = {a, b}. Then
A × B = {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)}
6
7
8
9
10
11
12
13
14
15
16
17
Properties of Relations
18
19
Example
Example: Consider the following relations on {1, 2, 3, 4}:
R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)},
R2 = {(1, 1), (1, 2), (2, 1)},
R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)},
R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)},
R5 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)},
R6 = {(3, 4)}.
Which of these relations are reflexive?
20
Solution
The relations R3 and R5 are reflexive because they both contain
all pairs of the form (a, a), namely, (1, 1), (2, 2), (3, 3), and (4, 4).
The other relations are not reflexive because they do not contain
all of these ordered pairs.
In particular, R1, R2, R4, and R6 are not reflexive because (3, 3) is
not in any of these relations.
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
??
46
47
