Mat2033 - Discrete Mathematics
Relations and their Properties
Continue…
Lecture 8 1
Composite Relations Definition
Let R be a relation from set A to set B
Let S be a relation from set B to set C
The composite of R and S is a relation from set A to set C
and is a set of ordered pairs (a,c) such that
there exists an (a,b) in R and an (b,c) in S
The composite of R and S is denoted as SoR
The composite of R with S
Lecture 8 2
Composite Relations Example
Lecture 8 3
Composite Relations So?
Assume we have a relation R of people to motorcycles they own.
A person could have more that one motorcycle.
R is a set of ordered pairs {(Patrick,RGV),(Denis,Buell),
(Stan,ElectraGlide),(Denis,Hayabusa),(Gordon,Bandit),
(Gordon,R6)}
We could have a relation S of motorcycles to top speed
{(RGV,130),(Buell,126),(ElectraGlide,110),(Hayabusa,182),
(Bandit,140),(R6,155)}
So R is then the relation of people to possible top speeds
{(Patrick,130),(Denis,126),(Denis,182),(Stan,110),
(Gordon,140),(Gordon,155)}
Lecture 8 4
Composite of a Relation with itself
Let R be a relation on the set A. The powers Rn are
defined inductively as follows
Lecture 8 5
Composite of a Relation with itself
Lecture 8 6
A Transitive Relation
Theorem: A relation R on a set A is transitive iff Rn is a subset
of R for n = 1,2,3,...
Lecture 8 7
A Transitive Relation Proof
Lecture 8 8
Example:
A = {1,2,3,4}
R = {(a,b) | a divides b}
R = {(1,1),(1,2),(1,3),(1,4),(2,2),(2,4),(3,3),(4,4)}
RoR = {(1,1),(1,2),(1,3),(1,4),(2,2),(2,4),(3,3),(4,4)}
RoR is a subset of R, therefore transitive
Obvious! If a divides b abd b divides c then a divides c!
Lecture 8 9
Exercise:
Let R be a relation on people such that (a,b)
is “a is a parent of b”
Let S be a relation on people such that (a,b)
is “a is a sibling of b”
• What is SoR, RoS, RoR?
• SoR composes R with S
• (a,c) is in SoR if there exists
• (a,b) in R and a (b,c) in S
• “a is parent of b” and “b is sibling of c”
• SoR should be in R!
• RoS composes S with R
• “a is sibling of b” and “b is a parent of c”
• therefore (a,c) is “a is an aunt/uncle of c”
Lecture 8 10
Lecture 8 11
Lecture 8 12
Lecture 8 13
Lecture 8 14
Lecture 8 15
Lecture 8 16
Lecture 8 17
Lecture 8 18
Lecture 8 19
Lecture 8 20
Lecture 8 21
Lecture 8 22
Lecture 8 23
Lecture 8 24
Lecture 8 25
Lecture 8 26
Lecture 8 27
Lecture 8 28
Lecture 8 29
Lecture 8 30
Exercise:
Lecture 8 31
Lecture 8 32
Lecture 8 33
Theorem 1 :
Lecture 8 34
Theorem 1 :
Lecture 8 35
Theorem 1 :
Lecture 8 36
Theorem 1 :
Lecture 8 37
Lecture 8 38
Lecture 8 39
Lecture 8 40
Lecture 8 41
Lecture 8 42
Lecture 8 43
Lecture 8 44
Lecture 8 45
Lecture 8 46
Lecture 8 47
Lecture 8 48
Lecture 8 49
• Floor Function: x means take the greatest
integer less than or equal to the number
Let n be an integer
(1a) x = n if and only if n ≤ x < n+1
Lecture 8 50
Lecture 8 51
Lecture 8 52
Lecture 8 53
Lecture 8 54
Exercise:
Lecture 8 55
Exercise:
Lecture 8 56
Exercise:
Lecture 8 57
Exercise:
Lecture 8 58