Relations II
Reflexive relation
Reflexive relation
• Rdiv ={(a b), if a |b} on A = {1,2,3,4}
• Rdiv = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}
1 1 1 1
MRdiv = 0 1 0 1
0 0 1 0
0 0 0 1
• A relation R is reflexive if and only if MR has 1 in every
position on its main diagonal.
CS 441 Discrete mathematics for CS M. Hauskrecht
Irreflexive relation
Irreflexive relation
• R? on A={1,2,3,4}, such that a R? b if and only if a ? b.
• R?={(1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),(3,4),(4,1),(4,2),(4,3)}
0 1 1 1
1 0 1 1
MR = 1 1 0 1
1 1 1 0
• A relation R is irreflexive if and only if MR has 0 in every
position on its main diagonal.
5
CS 441 Discrete mathematics for CS M. Hauskrecht
Symmetric relation
Symmetric relation:
• R? on A={1,2,3,4}, such that a R? b if and only if a ? b.
• R?={(1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),(3,4),(4,1),(4,2),(4,3)}
0 1 1 1
1 0 1 1
MR = 1 1 0 1
1 1 1 0
• A relation R is symmetric if and only if mij = mji for all i,j.
CS 441 Discrete mathematics for CS M. Hauskrecht
Anti-symmetric relation
Definition (anti-symmetric relation): A relation on a set A is
called anti-symmetric if
• [(a,b) ? R and (b,a) ? R] ? a = b where a, b ? A.
Example 3:
• Relation Rfun on A = {1,2,3,4} defined as:
• Rfun = {(1,2),(2,2),(3,3)}.
• Is Rfun anti-symmetric?
• Answer: Yes. It is anti-symmetric
6
CS 441 Discrete mathematics for CS M. Hauskrecht
Anti-symmetric relation
Antisymmetric relation
• relation Rfun = {(1,2),(2,2),(3,3)}
0 1 0 0
0 1 0 0
MRfun= 0 0 1 0
0 0 0 0
• A relation is antisymmetric if and only if mij = 1 ? mji = 0 for
i? j.
CS 441 Discrete mathematics for CS M. Hauskrecht
Transitive relation
Definition (transitive relation): A relation R on a set A is called
transitive if
• [(a,b) ? R and (b,c) ? R] ? (a,c) ? R for all a, b, c ? A.
• Example 1:
• Rdiv ={(a b), if a |b} on A = {1,2,3,4}
• Rdiv = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}
• Is Rdiv transitive?
• Answer:
7
CS 441 Discrete mathematics for CS M. Hauskrecht
Transitive relation
Definition (transitive relation): A relation R on a set A is called
transitive if
• [(a,b) ? R and (b,c) ? R] ? (a,c) ? R for all a, b, c ? A.
• Example 1:
• Rdiv ={(a b), if a |b} on A = {1,2,3,4}
• Rdiv = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}
• Is Rdiv transitive?
• Answer: Yes.
CS 441 Discrete mathematics for CS M. Hauskrecht
Transitive relation
Definition (transitive relation): A relation R on a set A is called
transitive if
• [(a,b) ? R and (b,c) ? R] ? (a,c) ? R for all a, b, c ? A.
• Example 2:
• R? on A={1,2,3,4}, such that a R? b if and only if a ? b.
• R?={(1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),(3,4),(4,1),(4,2),(4,3)}
• Is R? transitive ?
• Answer:
8
CS 441 Discrete mathematics for CS M. Hauskrecht
Transitive relation
Definition (transitive relation): A relation R on a set A is called
transitive if
• [(a,b) ? R and (b,c) ? R] ? (a,c) ? R for all a, b, c ? A.
• Example 2:
• R? on A={1,2,3,4}, such that a R? b if and only if a ? b.
• R?={(1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),(3,4),(4,1),(4,2),(4,3)}
• Is R? transitive?
• Answer: No. It is not transitive since (1,2) ? R and (2,1) ? R
but (1,1) is not an element of R.
CS 441 Discrete mathematics for CS M. Hauskrecht
Transitive relations
Definition (transitive relation): A relation R on a set A is called
transitive if
• [(a,b) ? R and (b,c) ? R] ? (a,c) ? R for all a, b, c ? A.
• Example 3:
• Relation Rfun on A = {1,2,3,4} defined as:
• Rfun = {(1,2),(2,2),(3,3)}.
• Is Rfun transitive?
• Answer:
9
CS 441 Discrete mathematics for CS M. Hauskrecht
Transitive relations
Definition (transitive relation): A relation R on a set A is called
transitive if
• [(a,b) ? R and (b,c) ? R] ? (a,c) ? R for all a, b, c ? A.
• Example 3:
• Relation Rfun on A = {1,2,3,4} defined as:
• Rfun = {(1,2),(2,2),(3,3)}.
• Is Rfun transitive?
• Answer: Yes. It is transitive.
CS 441 Discrete mathematics for CS M. Hauskrecht
Combining relations
Definition: Let A and B be sets. A binary relation from A to B is
a subset of a Cartesian product A x B.
• Let R ? A x B means R is a set of ordered pairs of the form (a,b)
where a ? A and b ? B.
Combining Relations
• Relations are sets ? combinations via set operations
• Set operations of: union, intersection, difference and
symmetric difference.
10
CS 441 Discrete mathematics for CS M. Hauskrecht
Combining relations
Example:
• Let A = {1,2,3} and B = {u,v} and
• R1 = {(1,u), (2,u), (2,v), (3,u)}
• R2 = {(1,v),(3,u),(3,v)}
What is:
• R1 ? R2 = ?
CS 441 Discrete mathematics for CS M. Hauskrecht
Combining relations
Example:
• Let A = {1,2,3} and B = {u,v} and
• R1 = {(1,u), (2,u), (2,v), (3,u)}
• R2 = {(1,v),(3,u),(3,v)}
What is:
• R1 ? R2 = {(1,u),(1,v),(2,u),(2,v),(3,u),(3,v)}
• R1 ? R2 = ?
11
CS 441 Discrete mathematics for CS M. Hauskrecht
Combining relations
Example:
• Let A = {1,2,3} and B = {u,v} and
• R1 = {(1,u), (2,u), (2,v), (3,u)}
• R2 = {(1,v),(3,u),(3,v)}
What is:
• R1 ? R2 = {(1,u),(1,v),(2,u),(2,v),(3,u),(3,v)}
• R1 ? R2 = {(3,u)}
• R1 - R2 = ?
CS 441 Discrete mathematics for CS M. Hauskrecht
Combining relations
Example:
• Let A = {1,2,3} and B = {u,v} and
• R1 = {(1,u), (2,u), (2,v), (3,u)}
• R2 = {(1,v),(3,u),(3,v)}
What is:
• R1 ? R2 = {(1,u),(1,v),(2,u),(2,v),(3,u),(3,v)}
• R1 ? R2 = {(3,u)}
• R1 - R2 = {(1,u),(2,u),(2,v)}
• R2 - R1 = ?
12
CS 441 Discrete mathematics for CS M. Hauskrecht
Combining relations
Example:
• Let A = {1,2,3} and B = {u,v} and
• R1 = {(1,u), (2,u), (2,v), (3,u)}
• R2 = {(1,v),(3,u),(3,v)}
What is:
• R1 ? R2 = {(1,u),(1,v),(2,u),(2,v),(3,u),(3,v)}
• R1 ? R2 = {(3,u)}
• R1 - R2 = {(1,u),(2,u),(2,v)}
• R2 - R1 = {(1,v),(3,v)}
CS 441 Discrete mathematics for CS M. Hauskrecht
Combination of relations
Representation of operations on relations:
• Question: Can the relation be formed by taking the union or
intersection or composition of two relations R1 and R2 be
represented in terms of matrix operations?
• Answer: Yes
13
CS 441 Discrete mathematics for CS M. Hauskrecht
Combination of relations: implementation
Definition. The join, denoted by ?, of two m-by-n matrices (aij)
and (bij) of 0s and 1s is an m-by-n matrix (mij) where
• mij = aij ? bij for all i,j
= pairwise or (disjunction)
• Example:
• Let A = {1,2,3} and B = {u,v} and
• R1 = {(1,u), (2,u), (2,v), (3,u)}
• R2 = {(1,v),(3,u),(3,v)}
• MR1 =1 0 MR2 = 0 1 M(R1 ? R2)= 1 1
1 1 0 0 1 1
1 0 1 1 1 1
CS 441 Discrete mathematics for CS M. Hauskrecht
Combination of relations: implementation
Definition. The meet, denoted by ? , of two m-by-n matrices (aij)
and (bij) of 0s and 1s is an m-by-n matrix (mij) where
• mij = aij ? bij for all i,j
= pairwise and (conjunction)
• Example:
• Let A = {1,2,3} and B = {u,v} and
• R1 = {(1,u), (2,u), (2,v), (3,u)}
• R2 = {(1,v),(3,u),(3,v)}
• MR1 =1 0 MR2 = 0 1 MR1 ? MR2= 0 0
1 1 0 0 0 0
1 0 1 1 1 0
14
CS 441 Discrete mathematics for CS M. Hauskrecht
Composite of relations
Definition: 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 the ordered pairs (a,c) where a ? A and c
? C, and for which there is a b ? B such that (a,b) ? R and (b,c)
? S. We denote the composite of R and S by S o R.
Examples:
• Let A = {1,2,3}, B = {0,1,2} and C = {a,b}.
• R = {(1,0), (1,2), (3,1),(3,2)}
• S = {(0,b),(1,a),(2,b)}
• S oR = ?
CS 441 Discrete mathematics for CS M. Hauskrecht
Composite of relations
Definition: 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 the ordered pairs (a,c) where a ? A and c
? C, and for which there is a b ? B such that (a,b) ? R and (b,c)
? S. We denote the composite of R and S by S o R.
Examples:
• Let A = {1,2,3}, B = {0,1,2} and C = {a,b}.
• R = {(1,0), (1,2), (3,1),(3,2)}
• S = {(0,b),(1,a),(2,b)}
• S o R = {(1,b),(3,a),(3,b)}
15
CS 441 Discrete mathematics for CS M. Hauskrecht
Implementation of composite
Definition. The Boolean product, denoted by ?, of an m-by-n
matrix (aij) and n-by-p matrix (bjk) of 0s and 1s is an m-by-p
matrix (mik) where
• mik = 1, if aij = 1 and bjk = 1 for some k=1,2,...,n
0, otherwise
Examples:
• Let A = {1,2,3}, B = {0,1,2} and C = {a,b}.
• R = {(1,0), (1,2), (3,1),(3,2)}
• S = {(0,b),(1,a),(2,b)}
• S o R = {(1,b),(3,a),(3,b)}
CS 441 Discrete mathematics for CS M. Hauskrecht
Implementation of composite
Examples:
• Let A = {1,2}, B= {1,2,3} C = {a,b}
• R = {(1,2),(1,3),(2,1)} is a relation from A to B
• S = {(1,a),(3,b),(3,a)} is a relation from B to C.
• S ? R = {(1,b),(1,a),(2,a)}
0 1 1 1 0
MR=1 0 0 MS = 0 0
1 1
MR ? MS = ?
16
CS 441 Discrete mathematics for CS M. Hauskrecht
Implementation of composite
Examples:
• Let A = {1,2}, {1,2,3} C = {a,b}
• R = {(1,2),(1,3),(2,1)} is a relation from A to B
• S = {(1,a),(3,b),(3,a)} is a relation from B to C.
• S ? R = {(1,b),(1,a),(2,a)}
0 1 1 1 0
MR=1 0 0 MS = 0 0
1 1
MR ? MS = x x
x x
CS 441 Discrete mathematics for CS M. Hauskrecht
Implementation of composite
Examples:
• Let A = {1,2}, {1,2,3} C = {a,b}
• R = {(1,2),(1,3),(2,1)} is a relation from A to B
• S = {(1,a),(3,b),(3,a)} is a relation from B to C.
• S ? R = {(1,b),(1,a),(2,a)}
0 1 1 1 0
MR=1 0 0 MS = 0 0
1 1
MR ? MS = 1 x
x x
17
CS 441 Discrete mathematics for CS M. Hauskrecht
Implementation of composite
Examples:
• Let A = {1,2}, {1,2,3} C = {a,b}
• R = {(1,2),(1,3),(2,1)} is a relation from A to B
• S = {(1,a),(3,b),(3,a)} is a relation from B to C.
• S ? R = {(1,b),(1,a),(2,a)}
0 1 1 1 0
MR=1 0 0 MS = 0 0
1 1
MR ? MS = 1 1
x x
CS 441 Discrete mathematics for CS M. Hauskrecht
Implementation of composite
Examples:
• Let A = {1,2}, {1,2,3} C = {a,b}
• R = {(1,2),(1,3),(2,1)} is a relation from A to B
• S = {(1,a),(3,b),(3,a)} is a relation from B to C.
• S ? R = {(1,b),(1,a),(2,a)}
0 1 1 1 0
MR=1 0 0 MS = 0 0
1 1
MR ? MS = 1 1
1 x
18
CS 441 Discrete mathematics for CS M. Hauskrecht
Implementation of composite
Examples:
• Let A = {1,2}, {1,2,3} C = {a,b}
• R = {(1,2),(1,3),(2,1)} is a relation from A to B
• S = {(1,a),(3,b),(3,a)} is a relation from B to C.
• S ? R = {(1,b),(1,a),(2,a)}
0 1 1 1 0
MR=1 0 0 MS = 0 0
1 1
MR ? MS = 1 1
1 0
MS ? R = ?
CS 441 Discrete mathematics for CS M. Hauskrecht
Implementation of composite
Examples:
• Let A = {1,2}, {1,2,3} C = {a,b}
• R = {(1,2),(1,3),(2,1)} is a relation from A to B
• S = {(1,a),(3,b),(3,a)} is a relation from B to C.
• S ? R = {(1,b),(1,a),(2,a)}
0 1 1 1 0
MR=1 0 0 MS = 0 0
1 1
MR ? MS = 1 1
1 0
MS ? R = 1 1
1 0
19
CS 441 Discrete mathematics for CS M. Hauskrecht
Composite of relations
Definition: Let R be a relation on a set A. The powers Rn, n =
1,2,3,... is defined inductively by
• R1 = R and Rn+1 = Rn ? R.
Examples
• R = {(1,2),(2,3),(2,4), (3,3)} is a relation on A = {1,2,3,4}.
• R1 = ?
CS 441 Discrete mathematics for CS M. Hauskrecht
Composite of relations
Definition: Let R be a relation on a set A. The powers Rn, n =
1,2,3,... is defined inductively by
• R1 = R and Rn+1 = Rn ? R.
Examples
• R = {(1,2),(2,3),(2,4), (3,3)} is a relation on A = {1,2,3,4}.
• R1 = R = {(1,2),(2,3),(2,4), (3,3)}
• R 2 = ?
20
CS 441 Discrete mathematics for CS M. Hauskrecht
Composite of relations
Definition: Let R be a relation on a set A. The powers Rn, n =
1,2,3,... is defined inductively by
• R1 = R and Rn+1 = Rn ? R.
Examples
• R = {(1,2),(2,3),(2,4), (3,3)} is a relation on A = {1,2,3,4}.
• R1 = R = {(1,2),(2,3),(2,4), (3,3)}
• R 2 = {(1,3), (1,4), (2,3), (3,3)}
• R 3 = ?
CS 441 Discrete mathematics for CS M. Hauskrecht
Composite of relations
Definition: Let R be a relation on a set A. The powers Rn, n =
1,2,3,... is defined inductively by
• R1 = R and Rn+1 = Rn ? R.
Examples
• R = {(1,2),(2,3),(2,4), (3,3)} is a relation on A = {1,2,3,4}.
• R1 = R = {(1,2),(2,3),(2,4), (3,3)}
• R 2 = {(1,3), (1,4), (2,3), (3,3)}
• R 3 = {(1,3), (2,3), (3,3)}
• R 4 = ?
21
CS 441 Discrete mathematics for CS M. Hauskrecht
Composite of relations
Definition: Let R be a relation on a set A. The powers Rn, n =
1,2,3,... is defined inductively by
• R1 = R and Rn+1 = Rn ? R.
Examples
• R = {(1,2),(2,3),(2,4), (3,3)} is a relation on A = {1,2,3,4}.
• R1 = R = {(1,2),(2,3),(2,4), (3,3)}
• R 2 = {(1,3), (1,4), (2,3), (3,3)}
• R 3 = {(1,3), (2,3), (3,3)}
• R 4 = {(1,3), (2,3), (3,3)}
• R k = ? , k > 3.
CS 441 Discrete mathematics for CS M. Hauskrecht
Composite of relations
Definition: Let R be a relation on a set A. The powers Rn, n =
1,2,3,... is defined inductively by
• R1 = R and Rn+1 = Rn ? R.
Examples
• R = {(1,2),(2,3),(2,4), (3,3)} is a relation on A = {1,2,3,4}.
• R1 = R = {(1,2),(2,3),(2,4), (3,3)}
• R 2 = {(1,3), (1,4), (2,3), (3,3)}
• R 3 = {(1,3), (2,3), (3,3)}
• R 4 = {(1,3), (2,3), (3,3)}
• R k = R 3, k > 3.
22
CS 441 Discrete mathematics for CS M. Hauskrecht
Transitive relation
Definition (transitive relation): A relation R on a set A is called
transitive if
• [(a,b) ? R and (b,c) ? R] ? (a,c) ? R for all a, b, c ? A.
• Example 1:
• Rdiv ={(a b), if a |b} on A = {1,2,3,4}
• Rdiv = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}
• Is Rdiv transitive?
• Answer: ?
CS 441 Discrete mathematics for CS M. Hauskrecht
Transitive relation
Definition (transitive relation): A relation R on a set A is called
transitive if
• [(a,b) ? R and (b,c) ? R] ? (a,c) ? R for all a, b, c ? A.
• Example 1:
• Rdiv ={(a b), if a |b} on A = {1,2,3,4}
• Rdiv = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}
• Is Rdiv transitive?
• Answer: Yes.
23
CS 441 Discrete mathematics for CS M. Hauskrecht
Connection to Rn
Theorem: The relation R on a set A is transitive if and only if
Rn ? R for n = 1,2,3,... .
Proof: biconditional (if and only if)
( ? ) Suppose Rn ? R, for n =1,2,3,... .
• Let (a,b) ? R and (b,c) ? R
• by the definition of R ? R, (a,c) ? R ? R =R2 ? R
• Therefore R is transitive.
CS 441 Discrete mathematics for CS M. Hauskrecht
Connection to Rn
Theorem: The relation R on a set A is transitive if and only if Rn ?
R for n = 1,2,3,... .
Proof: biconditional (if and only if)
(?) Suppose R is transitive. Show Rn ? R, for n =1,2,3,... .
• Let P(n) : Rn ? R. Mathematical induction.
• Basis Step:
24
CS 441 Discrete mathematics for CS M. Hauskrecht
Connection to Rn
Theorem: The relation R on a set A is transitive if and only if Rn ?
R for n = 1,2,3,... .
Proof: biconditional (if and only if)
(?) Suppose R is transitive. Show Rn ? R, for n =1,2,3,... .
• Let P(n) : Rn ? R. Mathematical induction.
• Basis Step: P(1) says R1 = R so, R1 ? R is true.
CS 441 Discrete mathematics for CS M. Hauskrecht
Connection to Rn
Theorem: The relation R on a set A is transitive if and only if Rn ?
R for n = 1,2,3,... .
Proof: biconditional (if and only if)
(?) Suppose R is transitive. Show Rn ? R, for n =1,2,3,... .
• Let P(n) : Rn ? R. Mathematical induction.
• Basis Step: P(1) says R1 = R so, R1 ? R is true.
• Inductive Step: show P(n) ? P(n+1)
• Want to show if Rn ? R then Rn+1 ? R.
25
CS 441 Discrete mathematics for CS M. Hauskrecht
Connection to Rn
Theorem: The relation R on a set A is transitive if and only if Rn ?
R for n = 1,2,3,... .
Proof: biconditional (if and only if)
(?) Suppose R is transitive. Show Rn ? R, for n =1,2,3,... .
• Let P(n) : Rn ? R. Mathematical induction.
• Basis Step: P(1) says R1 = R so, R1 ? R is true.
• Inductive Step: show P(n) ? P(n+1)
• Want to show if Rn ? R then Rn+1 ? R.
• Let (a,b) ? Rn+1 then by the definition of Rn+1 = Rn ? R there is
an element x ? A so that (a,x) ? R and (x,b) ? Rn ? R
(inductive hypothesis). In addition to (a,x) ? R and (x,b) ? R, R
is transitive; so (a,b) ? R.
• Therefore, Rn+1 ? R.
CS 441 Discrete mathematics for CS M. Hauskrecht
Reflexive relation
Reflexive relation
• Rdiv ={(a b), if a |b} on A = {1,2,3,4}
• Rdiv = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}
1 1 1 1
MRdiv = 0 1 0 1
0 0 1 0
0 0 0 1
• A relation R is reflexive if and only if MR has 1 in every
position on its main diagonal.
CS 441 Discrete mathematics for CS M. Hauskrecht
Irreflexive relation
Irreflexive relation
• R? on A={1,2,3,4}, such that a R? b if and only if a ? b.
• R?={(1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),(3,4),(4,1),(4,2),(4,3)}
0 1 1 1
1 0 1 1
MR = 1 1 0 1
1 1 1 0
• A relation R is irreflexive if and only if MR has 0 in every
position on its main diagonal.
5
CS 441 Discrete mathematics for CS M. Hauskrecht
Symmetric relation
Symmetric relation:
• R? on A={1,2,3,4}, such that a R? b if and only if a ? b.
• R?={(1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),(3,4),(4,1),(4,2),(4,3)}
0 1 1 1
1 0 1 1
MR = 1 1 0 1
1 1 1 0
• A relation R is symmetric if and only if mij = mji for all i,j.
CS 441 Discrete mathematics for CS M. Hauskrecht
Anti-symmetric relation
Definition (anti-symmetric relation): A relation on a set A is
called anti-symmetric if
• [(a,b) ? R and (b,a) ? R] ? a = b where a, b ? A.
Example 3:
• Relation Rfun on A = {1,2,3,4} defined as:
• Rfun = {(1,2),(2,2),(3,3)}.
• Is Rfun anti-symmetric?
• Answer: Yes. It is anti-symmetric
6
CS 441 Discrete mathematics for CS M. Hauskrecht
Anti-symmetric relation
Antisymmetric relation
• relation Rfun = {(1,2),(2,2),(3,3)}
0 1 0 0
0 1 0 0
MRfun= 0 0 1 0
0 0 0 0
• A relation is antisymmetric if and only if mij = 1 ? mji = 0 for
i? j.
CS 441 Discrete mathematics for CS M. Hauskrecht
Transitive relation
Definition (transitive relation): A relation R on a set A is called
transitive if
• [(a,b) ? R and (b,c) ? R] ? (a,c) ? R for all a, b, c ? A.
• Example 1:
• Rdiv ={(a b), if a |b} on A = {1,2,3,4}
• Rdiv = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}
• Is Rdiv transitive?
• Answer:
7
CS 441 Discrete mathematics for CS M. Hauskrecht
Transitive relation
Definition (transitive relation): A relation R on a set A is called
transitive if
• [(a,b) ? R and (b,c) ? R] ? (a,c) ? R for all a, b, c ? A.
• Example 1:
• Rdiv ={(a b), if a |b} on A = {1,2,3,4}
• Rdiv = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}
• Is Rdiv transitive?
• Answer: Yes.
CS 441 Discrete mathematics for CS M. Hauskrecht
Transitive relation
Definition (transitive relation): A relation R on a set A is called
transitive if
• [(a,b) ? R and (b,c) ? R] ? (a,c) ? R for all a, b, c ? A.
• Example 2:
• R? on A={1,2,3,4}, such that a R? b if and only if a ? b.
• R?={(1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),(3,4),(4,1),(4,2),(4,3)}
• Is R? transitive ?
• Answer:
8
CS 441 Discrete mathematics for CS M. Hauskrecht
Transitive relation
Definition (transitive relation): A relation R on a set A is called
transitive if
• [(a,b) ? R and (b,c) ? R] ? (a,c) ? R for all a, b, c ? A.
• Example 2:
• R? on A={1,2,3,4}, such that a R? b if and only if a ? b.
• R?={(1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),(3,4),(4,1),(4,2),(4,3)}
• Is R? transitive?
• Answer: No. It is not transitive since (1,2) ? R and (2,1) ? R
but (1,1) is not an element of R.
CS 441 Discrete mathematics for CS M. Hauskrecht
Transitive relations
Definition (transitive relation): A relation R on a set A is called
transitive if
• [(a,b) ? R and (b,c) ? R] ? (a,c) ? R for all a, b, c ? A.
• Example 3:
• Relation Rfun on A = {1,2,3,4} defined as:
• Rfun = {(1,2),(2,2),(3,3)}.
• Is Rfun transitive?
• Answer:
9
CS 441 Discrete mathematics for CS M. Hauskrecht
Transitive relations
Definition (transitive relation): A relation R on a set A is called
transitive if
• [(a,b) ? R and (b,c) ? R] ? (a,c) ? R for all a, b, c ? A.
• Example 3:
• Relation Rfun on A = {1,2,3,4} defined as:
• Rfun = {(1,2),(2,2),(3,3)}.
• Is Rfun transitive?
• Answer: Yes. It is transitive.
CS 441 Discrete mathematics for CS M. Hauskrecht
Combining relations
Definition: Let A and B be sets. A binary relation from A to B is
a subset of a Cartesian product A x B.
• Let R ? A x B means R is a set of ordered pairs of the form (a,b)
where a ? A and b ? B.
Combining Relations
• Relations are sets ? combinations via set operations
• Set operations of: union, intersection, difference and
symmetric difference.
10
CS 441 Discrete mathematics for CS M. Hauskrecht
Combining relations
Example:
• Let A = {1,2,3} and B = {u,v} and
• R1 = {(1,u), (2,u), (2,v), (3,u)}
• R2 = {(1,v),(3,u),(3,v)}
What is:
• R1 ? R2 = ?
CS 441 Discrete mathematics for CS M. Hauskrecht
Combining relations
Example:
• Let A = {1,2,3} and B = {u,v} and
• R1 = {(1,u), (2,u), (2,v), (3,u)}
• R2 = {(1,v),(3,u),(3,v)}
What is:
• R1 ? R2 = {(1,u),(1,v),(2,u),(2,v),(3,u),(3,v)}
• R1 ? R2 = ?
11
CS 441 Discrete mathematics for CS M. Hauskrecht
Combining relations
Example:
• Let A = {1,2,3} and B = {u,v} and
• R1 = {(1,u), (2,u), (2,v), (3,u)}
• R2 = {(1,v),(3,u),(3,v)}
What is:
• R1 ? R2 = {(1,u),(1,v),(2,u),(2,v),(3,u),(3,v)}
• R1 ? R2 = {(3,u)}
• R1 - R2 = ?
CS 441 Discrete mathematics for CS M. Hauskrecht
Combining relations
Example:
• Let A = {1,2,3} and B = {u,v} and
• R1 = {(1,u), (2,u), (2,v), (3,u)}
• R2 = {(1,v),(3,u),(3,v)}
What is:
• R1 ? R2 = {(1,u),(1,v),(2,u),(2,v),(3,u),(3,v)}
• R1 ? R2 = {(3,u)}
• R1 - R2 = {(1,u),(2,u),(2,v)}
• R2 - R1 = ?
12
CS 441 Discrete mathematics for CS M. Hauskrecht
Combining relations
Example:
• Let A = {1,2,3} and B = {u,v} and
• R1 = {(1,u), (2,u), (2,v), (3,u)}
• R2 = {(1,v),(3,u),(3,v)}
What is:
• R1 ? R2 = {(1,u),(1,v),(2,u),(2,v),(3,u),(3,v)}
• R1 ? R2 = {(3,u)}
• R1 - R2 = {(1,u),(2,u),(2,v)}
• R2 - R1 = {(1,v),(3,v)}
CS 441 Discrete mathematics for CS M. Hauskrecht
Combination of relations
Representation of operations on relations:
• Question: Can the relation be formed by taking the union or
intersection or composition of two relations R1 and R2 be
represented in terms of matrix operations?
• Answer: Yes
13
CS 441 Discrete mathematics for CS M. Hauskrecht
Combination of relations: implementation
Definition. The join, denoted by ?, of two m-by-n matrices (aij)
and (bij) of 0s and 1s is an m-by-n matrix (mij) where
• mij = aij ? bij for all i,j
= pairwise or (disjunction)
• Example:
• Let A = {1,2,3} and B = {u,v} and
• R1 = {(1,u), (2,u), (2,v), (3,u)}
• R2 = {(1,v),(3,u),(3,v)}
• MR1 =1 0 MR2 = 0 1 M(R1 ? R2)= 1 1
1 1 0 0 1 1
1 0 1 1 1 1
CS 441 Discrete mathematics for CS M. Hauskrecht
Combination of relations: implementation
Definition. The meet, denoted by ? , of two m-by-n matrices (aij)
and (bij) of 0s and 1s is an m-by-n matrix (mij) where
• mij = aij ? bij for all i,j
= pairwise and (conjunction)
• Example:
• Let A = {1,2,3} and B = {u,v} and
• R1 = {(1,u), (2,u), (2,v), (3,u)}
• R2 = {(1,v),(3,u),(3,v)}
• MR1 =1 0 MR2 = 0 1 MR1 ? MR2= 0 0
1 1 0 0 0 0
1 0 1 1 1 0
14
CS 441 Discrete mathematics for CS M. Hauskrecht
Composite of relations
Definition: 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 the ordered pairs (a,c) where a ? A and c
? C, and for which there is a b ? B such that (a,b) ? R and (b,c)
? S. We denote the composite of R and S by S o R.
Examples:
• Let A = {1,2,3}, B = {0,1,2} and C = {a,b}.
• R = {(1,0), (1,2), (3,1),(3,2)}
• S = {(0,b),(1,a),(2,b)}
• S oR = ?
CS 441 Discrete mathematics for CS M. Hauskrecht
Composite of relations
Definition: 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 the ordered pairs (a,c) where a ? A and c
? C, and for which there is a b ? B such that (a,b) ? R and (b,c)
? S. We denote the composite of R and S by S o R.
Examples:
• Let A = {1,2,3}, B = {0,1,2} and C = {a,b}.
• R = {(1,0), (1,2), (3,1),(3,2)}
• S = {(0,b),(1,a),(2,b)}
• S o R = {(1,b),(3,a),(3,b)}
15
CS 441 Discrete mathematics for CS M. Hauskrecht
Implementation of composite
Definition. The Boolean product, denoted by ?, of an m-by-n
matrix (aij) and n-by-p matrix (bjk) of 0s and 1s is an m-by-p
matrix (mik) where
• mik = 1, if aij = 1 and bjk = 1 for some k=1,2,...,n
0, otherwise
Examples:
• Let A = {1,2,3}, B = {0,1,2} and C = {a,b}.
• R = {(1,0), (1,2), (3,1),(3,2)}
• S = {(0,b),(1,a),(2,b)}
• S o R = {(1,b),(3,a),(3,b)}
CS 441 Discrete mathematics for CS M. Hauskrecht
Implementation of composite
Examples:
• Let A = {1,2}, B= {1,2,3} C = {a,b}
• R = {(1,2),(1,3),(2,1)} is a relation from A to B
• S = {(1,a),(3,b),(3,a)} is a relation from B to C.
• S ? R = {(1,b),(1,a),(2,a)}
0 1 1 1 0
MR=1 0 0 MS = 0 0
1 1
MR ? MS = ?
16
CS 441 Discrete mathematics for CS M. Hauskrecht
Implementation of composite
Examples:
• Let A = {1,2}, {1,2,3} C = {a,b}
• R = {(1,2),(1,3),(2,1)} is a relation from A to B
• S = {(1,a),(3,b),(3,a)} is a relation from B to C.
• S ? R = {(1,b),(1,a),(2,a)}
0 1 1 1 0
MR=1 0 0 MS = 0 0
1 1
MR ? MS = x x
x x
CS 441 Discrete mathematics for CS M. Hauskrecht
Implementation of composite
Examples:
• Let A = {1,2}, {1,2,3} C = {a,b}
• R = {(1,2),(1,3),(2,1)} is a relation from A to B
• S = {(1,a),(3,b),(3,a)} is a relation from B to C.
• S ? R = {(1,b),(1,a),(2,a)}
0 1 1 1 0
MR=1 0 0 MS = 0 0
1 1
MR ? MS = 1 x
x x
17
CS 441 Discrete mathematics for CS M. Hauskrecht
Implementation of composite
Examples:
• Let A = {1,2}, {1,2,3} C = {a,b}
• R = {(1,2),(1,3),(2,1)} is a relation from A to B
• S = {(1,a),(3,b),(3,a)} is a relation from B to C.
• S ? R = {(1,b),(1,a),(2,a)}
0 1 1 1 0
MR=1 0 0 MS = 0 0
1 1
MR ? MS = 1 1
x x
CS 441 Discrete mathematics for CS M. Hauskrecht
Implementation of composite
Examples:
• Let A = {1,2}, {1,2,3} C = {a,b}
• R = {(1,2),(1,3),(2,1)} is a relation from A to B
• S = {(1,a),(3,b),(3,a)} is a relation from B to C.
• S ? R = {(1,b),(1,a),(2,a)}
0 1 1 1 0
MR=1 0 0 MS = 0 0
1 1
MR ? MS = 1 1
1 x
18
CS 441 Discrete mathematics for CS M. Hauskrecht
Implementation of composite
Examples:
• Let A = {1,2}, {1,2,3} C = {a,b}
• R = {(1,2),(1,3),(2,1)} is a relation from A to B
• S = {(1,a),(3,b),(3,a)} is a relation from B to C.
• S ? R = {(1,b),(1,a),(2,a)}
0 1 1 1 0
MR=1 0 0 MS = 0 0
1 1
MR ? MS = 1 1
1 0
MS ? R = ?
CS 441 Discrete mathematics for CS M. Hauskrecht
Implementation of composite
Examples:
• Let A = {1,2}, {1,2,3} C = {a,b}
• R = {(1,2),(1,3),(2,1)} is a relation from A to B
• S = {(1,a),(3,b),(3,a)} is a relation from B to C.
• S ? R = {(1,b),(1,a),(2,a)}
0 1 1 1 0
MR=1 0 0 MS = 0 0
1 1
MR ? MS = 1 1
1 0
MS ? R = 1 1
1 0
19
CS 441 Discrete mathematics for CS M. Hauskrecht
Composite of relations
Definition: Let R be a relation on a set A. The powers Rn, n =
1,2,3,... is defined inductively by
• R1 = R and Rn+1 = Rn ? R.
Examples
• R = {(1,2),(2,3),(2,4), (3,3)} is a relation on A = {1,2,3,4}.
• R1 = ?
CS 441 Discrete mathematics for CS M. Hauskrecht
Composite of relations
Definition: Let R be a relation on a set A. The powers Rn, n =
1,2,3,... is defined inductively by
• R1 = R and Rn+1 = Rn ? R.
Examples
• R = {(1,2),(2,3),(2,4), (3,3)} is a relation on A = {1,2,3,4}.
• R1 = R = {(1,2),(2,3),(2,4), (3,3)}
• R 2 = ?
20
CS 441 Discrete mathematics for CS M. Hauskrecht
Composite of relations
Definition: Let R be a relation on a set A. The powers Rn, n =
1,2,3,... is defined inductively by
• R1 = R and Rn+1 = Rn ? R.
Examples
• R = {(1,2),(2,3),(2,4), (3,3)} is a relation on A = {1,2,3,4}.
• R1 = R = {(1,2),(2,3),(2,4), (3,3)}
• R 2 = {(1,3), (1,4), (2,3), (3,3)}
• R 3 = ?
CS 441 Discrete mathematics for CS M. Hauskrecht
Composite of relations
Definition: Let R be a relation on a set A. The powers Rn, n =
1,2,3,... is defined inductively by
• R1 = R and Rn+1 = Rn ? R.
Examples
• R = {(1,2),(2,3),(2,4), (3,3)} is a relation on A = {1,2,3,4}.
• R1 = R = {(1,2),(2,3),(2,4), (3,3)}
• R 2 = {(1,3), (1,4), (2,3), (3,3)}
• R 3 = {(1,3), (2,3), (3,3)}
• R 4 = ?
21
CS 441 Discrete mathematics for CS M. Hauskrecht
Composite of relations
Definition: Let R be a relation on a set A. The powers Rn, n =
1,2,3,... is defined inductively by
• R1 = R and Rn+1 = Rn ? R.
Examples
• R = {(1,2),(2,3),(2,4), (3,3)} is a relation on A = {1,2,3,4}.
• R1 = R = {(1,2),(2,3),(2,4), (3,3)}
• R 2 = {(1,3), (1,4), (2,3), (3,3)}
• R 3 = {(1,3), (2,3), (3,3)}
• R 4 = {(1,3), (2,3), (3,3)}
• R k = ? , k > 3.
CS 441 Discrete mathematics for CS M. Hauskrecht
Composite of relations
Definition: Let R be a relation on a set A. The powers Rn, n =
1,2,3,... is defined inductively by
• R1 = R and Rn+1 = Rn ? R.
Examples
• R = {(1,2),(2,3),(2,4), (3,3)} is a relation on A = {1,2,3,4}.
• R1 = R = {(1,2),(2,3),(2,4), (3,3)}
• R 2 = {(1,3), (1,4), (2,3), (3,3)}
• R 3 = {(1,3), (2,3), (3,3)}
• R 4 = {(1,3), (2,3), (3,3)}
• R k = R 3, k > 3.
22
CS 441 Discrete mathematics for CS M. Hauskrecht
Transitive relation
Definition (transitive relation): A relation R on a set A is called
transitive if
• [(a,b) ? R and (b,c) ? R] ? (a,c) ? R for all a, b, c ? A.
• Example 1:
• Rdiv ={(a b), if a |b} on A = {1,2,3,4}
• Rdiv = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}
• Is Rdiv transitive?
• Answer: ?
CS 441 Discrete mathematics for CS M. Hauskrecht
Transitive relation
Definition (transitive relation): A relation R on a set A is called
transitive if
• [(a,b) ? R and (b,c) ? R] ? (a,c) ? R for all a, b, c ? A.
• Example 1:
• Rdiv ={(a b), if a |b} on A = {1,2,3,4}
• Rdiv = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}
• Is Rdiv transitive?
• Answer: Yes.
23
CS 441 Discrete mathematics for CS M. Hauskrecht
Connection to Rn
Theorem: The relation R on a set A is transitive if and only if
Rn ? R for n = 1,2,3,... .
Proof: biconditional (if and only if)
( ? ) Suppose Rn ? R, for n =1,2,3,... .
• Let (a,b) ? R and (b,c) ? R
• by the definition of R ? R, (a,c) ? R ? R =R2 ? R
• Therefore R is transitive.
CS 441 Discrete mathematics for CS M. Hauskrecht
Connection to Rn
Theorem: The relation R on a set A is transitive if and only if Rn ?
R for n = 1,2,3,... .
Proof: biconditional (if and only if)
(?) Suppose R is transitive. Show Rn ? R, for n =1,2,3,... .
• Let P(n) : Rn ? R. Mathematical induction.
• Basis Step:
24
CS 441 Discrete mathematics for CS M. Hauskrecht
Connection to Rn
Theorem: The relation R on a set A is transitive if and only if Rn ?
R for n = 1,2,3,... .
Proof: biconditional (if and only if)
(?) Suppose R is transitive. Show Rn ? R, for n =1,2,3,... .
• Let P(n) : Rn ? R. Mathematical induction.
• Basis Step: P(1) says R1 = R so, R1 ? R is true.
CS 441 Discrete mathematics for CS M. Hauskrecht
Connection to Rn
Theorem: The relation R on a set A is transitive if and only if Rn ?
R for n = 1,2,3,... .
Proof: biconditional (if and only if)
(?) Suppose R is transitive. Show Rn ? R, for n =1,2,3,... .
• Let P(n) : Rn ? R. Mathematical induction.
• Basis Step: P(1) says R1 = R so, R1 ? R is true.
• Inductive Step: show P(n) ? P(n+1)
• Want to show if Rn ? R then Rn+1 ? R.
25
CS 441 Discrete mathematics for CS M. Hauskrecht
Connection to Rn
Theorem: The relation R on a set A is transitive if and only if Rn ?
R for n = 1,2,3,... .
Proof: biconditional (if and only if)
(?) Suppose R is transitive. Show Rn ? R, for n =1,2,3,... .
• Let P(n) : Rn ? R. Mathematical induction.
• Basis Step: P(1) says R1 = R so, R1 ? R is true.
• Inductive Step: show P(n) ? P(n+1)
• Want to show if Rn ? R then Rn+1 ? R.
• Let (a,b) ? Rn+1 then by the definition of Rn+1 = Rn ? R there is
an element x ? A so that (a,x) ? R and (x,b) ? Rn ? R
(inductive hypothesis). In addition to (a,x) ? R and (x,b) ? R, R
is transitive; so (a,b) ? R.
• Therefore, Rn+1 ? R.
CS 441 Discrete mathematics for CS M. Hauskrecht
Reflexive relation
Reflexive relation
• Rdiv ={(a b), if a |b} on A = {1,2,3,4}
• Rdiv = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}
1 1 1 1
MRdiv = 0 1 0 1
0 0 1 0
0 0 0 1
• A relation R is reflexive if and only if MR has 1 in every
position on its main diagonal.
CS 441 Discrete mathematics for CS M. Hauskrecht
Irreflexive relation
Irreflexive relation
• R? on A={1,2,3,4}, such that a R? b if and only if a ? b.
• R?={(1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),(3,4),(4,1),(4,2),(4,3)}
0 1 1 1
1 0 1 1
MR = 1 1 0 1
1 1 1 0
• A relation R is irreflexive if and only if MR has 0 in every
position on its main diagonal.
5
CS 441 Discrete mathematics for CS M. Hauskrecht
Symmetric relation
Symmetric relation:
• R? on A={1,2,3,4}, such that a R? b if and only if a ? b.
• R?={(1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),(3,4),(4,1),(4,2),(4,3)}
0 1 1 1
1 0 1 1
MR = 1 1 0 1
1 1 1 0
• A relation R is symmetric if and only if mij = mji for all i,j.
CS 441 Discrete mathematics for CS M. Hauskrecht
Anti-symmetric relation
Definition (anti-symmetric relation): A relation on a set A is
called anti-symmetric if
• [(a,b) ? R and (b,a) ? R] ? a = b where a, b ? A.
Example 3:
• Relation Rfun on A = {1,2,3,4} defined as:
• Rfun = {(1,2),(2,2),(3,3)}.
• Is Rfun anti-symmetric?
• Answer: Yes. It is anti-symmetric
6
CS 441 Discrete mathematics for CS M. Hauskrecht
Anti-symmetric relation
Antisymmetric relation
• relation Rfun = {(1,2),(2,2),(3,3)}
0 1 0 0
0 1 0 0
MRfun= 0 0 1 0
0 0 0 0
• A relation is antisymmetric if and only if mij = 1 ? mji = 0 for
i? j.
CS 441 Discrete mathematics for CS M. Hauskrecht
Transitive relation
Definition (transitive relation): A relation R on a set A is called
transitive if
• [(a,b) ? R and (b,c) ? R] ? (a,c) ? R for all a, b, c ? A.
• Example 1:
• Rdiv ={(a b), if a |b} on A = {1,2,3,4}
• Rdiv = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}
• Is Rdiv transitive?
• Answer:
7
CS 441 Discrete mathematics for CS M. Hauskrecht
Transitive relation
Definition (transitive relation): A relation R on a set A is called
transitive if
• [(a,b) ? R and (b,c) ? R] ? (a,c) ? R for all a, b, c ? A.
• Example 1:
• Rdiv ={(a b), if a |b} on A = {1,2,3,4}
• Rdiv = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}
• Is Rdiv transitive?
• Answer: Yes.
CS 441 Discrete mathematics for CS M. Hauskrecht
Transitive relation
Definition (transitive relation): A relation R on a set A is called
transitive if
• [(a,b) ? R and (b,c) ? R] ? (a,c) ? R for all a, b, c ? A.
• Example 2:
• R? on A={1,2,3,4}, such that a R? b if and only if a ? b.
• R?={(1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),(3,4),(4,1),(4,2),(4,3)}
• Is R? transitive ?
• Answer:
8
CS 441 Discrete mathematics for CS M. Hauskrecht
Transitive relation
Definition (transitive relation): A relation R on a set A is called
transitive if
• [(a,b) ? R and (b,c) ? R] ? (a,c) ? R for all a, b, c ? A.
• Example 2:
• R? on A={1,2,3,4}, such that a R? b if and only if a ? b.
• R?={(1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),(3,4),(4,1),(4,2),(4,3)}
• Is R? transitive?
• Answer: No. It is not transitive since (1,2) ? R and (2,1) ? R
but (1,1) is not an element of R.
CS 441 Discrete mathematics for CS M. Hauskrecht
Transitive relations
Definition (transitive relation): A relation R on a set A is called
transitive if
• [(a,b) ? R and (b,c) ? R] ? (a,c) ? R for all a, b, c ? A.
• Example 3:
• Relation Rfun on A = {1,2,3,4} defined as:
• Rfun = {(1,2),(2,2),(3,3)}.
• Is Rfun transitive?
• Answer:
9
CS 441 Discrete mathematics for CS M. Hauskrecht
Transitive relations
Definition (transitive relation): A relation R on a set A is called
transitive if
• [(a,b) ? R and (b,c) ? R] ? (a,c) ? R for all a, b, c ? A.
• Example 3:
• Relation Rfun on A = {1,2,3,4} defined as:
• Rfun = {(1,2),(2,2),(3,3)}.
• Is Rfun transitive?
• Answer: Yes. It is transitive.
CS 441 Discrete mathematics for CS M. Hauskrecht
Combining relations
Definition: Let A and B be sets. A binary relation from A to B is
a subset of a Cartesian product A x B.
• Let R ? A x B means R is a set of ordered pairs of the form (a,b)
where a ? A and b ? B.
Combining Relations
• Relations are sets ? combinations via set operations
• Set operations of: union, intersection, difference and
symmetric difference.
10
CS 441 Discrete mathematics for CS M. Hauskrecht
Combining relations
Example:
• Let A = {1,2,3} and B = {u,v} and
• R1 = {(1,u), (2,u), (2,v), (3,u)}
• R2 = {(1,v),(3,u),(3,v)}
What is:
• R1 ? R2 = ?
CS 441 Discrete mathematics for CS M. Hauskrecht
Combining relations
Example:
• Let A = {1,2,3} and B = {u,v} and
• R1 = {(1,u), (2,u), (2,v), (3,u)}
• R2 = {(1,v),(3,u),(3,v)}
What is:
• R1 ? R2 = {(1,u),(1,v),(2,u),(2,v),(3,u),(3,v)}
• R1 ? R2 = ?
11
CS 441 Discrete mathematics for CS M. Hauskrecht
Combining relations
Example:
• Let A = {1,2,3} and B = {u,v} and
• R1 = {(1,u), (2,u), (2,v), (3,u)}
• R2 = {(1,v),(3,u),(3,v)}
What is:
• R1 ? R2 = {(1,u),(1,v),(2,u),(2,v),(3,u),(3,v)}
• R1 ? R2 = {(3,u)}
• R1 - R2 = ?
CS 441 Discrete mathematics for CS M. Hauskrecht
Combining relations
Example:
• Let A = {1,2,3} and B = {u,v} and
• R1 = {(1,u), (2,u), (2,v), (3,u)}
• R2 = {(1,v),(3,u),(3,v)}
What is:
• R1 ? R2 = {(1,u),(1,v),(2,u),(2,v),(3,u),(3,v)}
• R1 ? R2 = {(3,u)}
• R1 - R2 = {(1,u),(2,u),(2,v)}
• R2 - R1 = ?
12
CS 441 Discrete mathematics for CS M. Hauskrecht
Combining relations
Example:
• Let A = {1,2,3} and B = {u,v} and
• R1 = {(1,u), (2,u), (2,v), (3,u)}
• R2 = {(1,v),(3,u),(3,v)}
What is:
• R1 ? R2 = {(1,u),(1,v),(2,u),(2,v),(3,u),(3,v)}
• R1 ? R2 = {(3,u)}
• R1 - R2 = {(1,u),(2,u),(2,v)}
• R2 - R1 = {(1,v),(3,v)}
CS 441 Discrete mathematics for CS M. Hauskrecht
Combination of relations
Representation of operations on relations:
• Question: Can the relation be formed by taking the union or
intersection or composition of two relations R1 and R2 be
represented in terms of matrix operations?
• Answer: Yes
13
CS 441 Discrete mathematics for CS M. Hauskrecht
Combination of relations: implementation
Definition. The join, denoted by ?, of two m-by-n matrices (aij)
and (bij) of 0s and 1s is an m-by-n matrix (mij) where
• mij = aij ? bij for all i,j
= pairwise or (disjunction)
• Example:
• Let A = {1,2,3} and B = {u,v} and
• R1 = {(1,u), (2,u), (2,v), (3,u)}
• R2 = {(1,v),(3,u),(3,v)}
• MR1 =1 0 MR2 = 0 1 M(R1 ? R2)= 1 1
1 1 0 0 1 1
1 0 1 1 1 1
CS 441 Discrete mathematics for CS M. Hauskrecht
Combination of relations: implementation
Definition. The meet, denoted by ? , of two m-by-n matrices (aij)
and (bij) of 0s and 1s is an m-by-n matrix (mij) where
• mij = aij ? bij for all i,j
= pairwise and (conjunction)
• Example:
• Let A = {1,2,3} and B = {u,v} and
• R1 = {(1,u), (2,u), (2,v), (3,u)}
• R2 = {(1,v),(3,u),(3,v)}
• MR1 =1 0 MR2 = 0 1 MR1 ? MR2= 0 0
1 1 0 0 0 0
1 0 1 1 1 0
14
CS 441 Discrete mathematics for CS M. Hauskrecht
Composite of relations
Definition: 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 the ordered pairs (a,c) where a ? A and c
? C, and for which there is a b ? B such that (a,b) ? R and (b,c)
? S. We denote the composite of R and S by S o R.
Examples:
• Let A = {1,2,3}, B = {0,1,2} and C = {a,b}.
• R = {(1,0), (1,2), (3,1),(3,2)}
• S = {(0,b),(1,a),(2,b)}
• S oR = ?
CS 441 Discrete mathematics for CS M. Hauskrecht
Composite of relations
Definition: 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 the ordered pairs (a,c) where a ? A and c
? C, and for which there is a b ? B such that (a,b) ? R and (b,c)
? S. We denote the composite of R and S by S o R.
Examples:
• Let A = {1,2,3}, B = {0,1,2} and C = {a,b}.
• R = {(1,0), (1,2), (3,1),(3,2)}
• S = {(0,b),(1,a),(2,b)}
• S o R = {(1,b),(3,a),(3,b)}
15
CS 441 Discrete mathematics for CS M. Hauskrecht
Implementation of composite
Definition. The Boolean product, denoted by ?, of an m-by-n
matrix (aij) and n-by-p matrix (bjk) of 0s and 1s is an m-by-p
matrix (mik) where
• mik = 1, if aij = 1 and bjk = 1 for some k=1,2,...,n
0, otherwise
Examples:
• Let A = {1,2,3}, B = {0,1,2} and C = {a,b}.
• R = {(1,0), (1,2), (3,1),(3,2)}
• S = {(0,b),(1,a),(2,b)}
• S o R = {(1,b),(3,a),(3,b)}
CS 441 Discrete mathematics for CS M. Hauskrecht
Implementation of composite
Examples:
• Let A = {1,2}, B= {1,2,3} C = {a,b}
• R = {(1,2),(1,3),(2,1)} is a relation from A to B
• S = {(1,a),(3,b),(3,a)} is a relation from B to C.
• S ? R = {(1,b),(1,a),(2,a)}
0 1 1 1 0
MR=1 0 0 MS = 0 0
1 1
MR ? MS = ?
16
CS 441 Discrete mathematics for CS M. Hauskrecht
Implementation of composite
Examples:
• Let A = {1,2}, {1,2,3} C = {a,b}
• R = {(1,2),(1,3),(2,1)} is a relation from A to B
• S = {(1,a),(3,b),(3,a)} is a relation from B to C.
• S ? R = {(1,b),(1,a),(2,a)}
0 1 1 1 0
MR=1 0 0 MS = 0 0
1 1
MR ? MS = x x
x x
CS 441 Discrete mathematics for CS M. Hauskrecht
Implementation of composite
Examples:
• Let A = {1,2}, {1,2,3} C = {a,b}
• R = {(1,2),(1,3),(2,1)} is a relation from A to B
• S = {(1,a),(3,b),(3,a)} is a relation from B to C.
• S ? R = {(1,b),(1,a),(2,a)}
0 1 1 1 0
MR=1 0 0 MS = 0 0
1 1
MR ? MS = 1 x
x x
17
CS 441 Discrete mathematics for CS M. Hauskrecht
Implementation of composite
Examples:
• Let A = {1,2}, {1,2,3} C = {a,b}
• R = {(1,2),(1,3),(2,1)} is a relation from A to B
• S = {(1,a),(3,b),(3,a)} is a relation from B to C.
• S ? R = {(1,b),(1,a),(2,a)}
0 1 1 1 0
MR=1 0 0 MS = 0 0
1 1
MR ? MS = 1 1
x x
CS 441 Discrete mathematics for CS M. Hauskrecht
Implementation of composite
Examples:
• Let A = {1,2}, {1,2,3} C = {a,b}
• R = {(1,2),(1,3),(2,1)} is a relation from A to B
• S = {(1,a),(3,b),(3,a)} is a relation from B to C.
• S ? R = {(1,b),(1,a),(2,a)}
0 1 1 1 0
MR=1 0 0 MS = 0 0
1 1
MR ? MS = 1 1
1 x
18
CS 441 Discrete mathematics for CS M. Hauskrecht
Implementation of composite
Examples:
• Let A = {1,2}, {1,2,3} C = {a,b}
• R = {(1,2),(1,3),(2,1)} is a relation from A to B
• S = {(1,a),(3,b),(3,a)} is a relation from B to C.
• S ? R = {(1,b),(1,a),(2,a)}
0 1 1 1 0
MR=1 0 0 MS = 0 0
1 1
MR ? MS = 1 1
1 0
MS ? R = ?
CS 441 Discrete mathematics for CS M. Hauskrecht
Implementation of composite
Examples:
• Let A = {1,2}, {1,2,3} C = {a,b}
• R = {(1,2),(1,3),(2,1)} is a relation from A to B
• S = {(1,a),(3,b),(3,a)} is a relation from B to C.
• S ? R = {(1,b),(1,a),(2,a)}
0 1 1 1 0
MR=1 0 0 MS = 0 0
1 1
MR ? MS = 1 1
1 0
MS ? R = 1 1
1 0
19
CS 441 Discrete mathematics for CS M. Hauskrecht
Composite of relations
Definition: Let R be a relation on a set A. The powers Rn, n =
1,2,3,... is defined inductively by
• R1 = R and Rn+1 = Rn ? R.
Examples
• R = {(1,2),(2,3),(2,4), (3,3)} is a relation on A = {1,2,3,4}.
• R1 = ?
CS 441 Discrete mathematics for CS M. Hauskrecht
Composite of relations
Definition: Let R be a relation on a set A. The powers Rn, n =
1,2,3,... is defined inductively by
• R1 = R and Rn+1 = Rn ? R.
Examples
• R = {(1,2),(2,3),(2,4), (3,3)} is a relation on A = {1,2,3,4}.
• R1 = R = {(1,2),(2,3),(2,4), (3,3)}
• R 2 = ?
20
CS 441 Discrete mathematics for CS M. Hauskrecht
Composite of relations
Definition: Let R be a relation on a set A. The powers Rn, n =
1,2,3,... is defined inductively by
• R1 = R and Rn+1 = Rn ? R.
Examples
• R = {(1,2),(2,3),(2,4), (3,3)} is a relation on A = {1,2,3,4}.
• R1 = R = {(1,2),(2,3),(2,4), (3,3)}
• R 2 = {(1,3), (1,4), (2,3), (3,3)}
• R 3 = ?
CS 441 Discrete mathematics for CS M. Hauskrecht
Composite of relations
Definition: Let R be a relation on a set A. The powers Rn, n =
1,2,3,... is defined inductively by
• R1 = R and Rn+1 = Rn ? R.
Examples
• R = {(1,2),(2,3),(2,4), (3,3)} is a relation on A = {1,2,3,4}.
• R1 = R = {(1,2),(2,3),(2,4), (3,3)}
• R 2 = {(1,3), (1,4), (2,3), (3,3)}
• R 3 = {(1,3), (2,3), (3,3)}
• R 4 = ?
21
CS 441 Discrete mathematics for CS M. Hauskrecht
Composite of relations
Definition: Let R be a relation on a set A. The powers Rn, n =
1,2,3,... is defined inductively by
• R1 = R and Rn+1 = Rn ? R.
Examples
• R = {(1,2),(2,3),(2,4), (3,3)} is a relation on A = {1,2,3,4}.
• R1 = R = {(1,2),(2,3),(2,4), (3,3)}
• R 2 = {(1,3), (1,4), (2,3), (3,3)}
• R 3 = {(1,3), (2,3), (3,3)}
• R 4 = {(1,3), (2,3), (3,3)}
• R k = ? , k > 3.
CS 441 Discrete mathematics for CS M. Hauskrecht
Composite of relations
Definition: Let R be a relation on a set A. The powers Rn, n =
1,2,3,... is defined inductively by
• R1 = R and Rn+1 = Rn ? R.
Examples
• R = {(1,2),(2,3),(2,4), (3,3)} is a relation on A = {1,2,3,4}.
• R1 = R = {(1,2),(2,3),(2,4), (3,3)}
• R 2 = {(1,3), (1,4), (2,3), (3,3)}
• R 3 = {(1,3), (2,3), (3,3)}
• R 4 = {(1,3), (2,3), (3,3)}
• R k = R 3, k > 3.
22
CS 441 Discrete mathematics for CS M. Hauskrecht
Transitive relation
Definition (transitive relation): A relation R on a set A is called
transitive if
• [(a,b) ? R and (b,c) ? R] ? (a,c) ? R for all a, b, c ? A.
• Example 1:
• Rdiv ={(a b), if a |b} on A = {1,2,3,4}
• Rdiv = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}
• Is Rdiv transitive?
• Answer: ?
CS 441 Discrete mathematics for CS M. Hauskrecht
Transitive relation
Definition (transitive relation): A relation R on a set A is called
transitive if
• [(a,b) ? R and (b,c) ? R] ? (a,c) ? R for all a, b, c ? A.
• Example 1:
• Rdiv ={(a b), if a |b} on A = {1,2,3,4}
• Rdiv = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}
• Is Rdiv transitive?
• Answer: Yes.
23
CS 441 Discrete mathematics for CS M. Hauskrecht
Connection to Rn
Theorem: The relation R on a set A is transitive if and only if
Rn ? R for n = 1,2,3,... .
Proof: biconditional (if and only if)
( ? ) Suppose Rn ? R, for n =1,2,3,... .
• Let (a,b) ? R and (b,c) ? R
• by the definition of R ? R, (a,c) ? R ? R =R2 ? R
• Therefore R is transitive.
CS 441 Discrete mathematics for CS M. Hauskrecht
Connection to Rn
Theorem: The relation R on a set A is transitive if and only if Rn ?
R for n = 1,2,3,... .
Proof: biconditional (if and only if)
(?) Suppose R is transitive. Show Rn ? R, for n =1,2,3,... .
• Let P(n) : Rn ? R. Mathematical induction.
• Basis Step:
24
CS 441 Discrete mathematics for CS M. Hauskrecht
Connection to Rn
Theorem: The relation R on a set A is transitive if and only if Rn ?
R for n = 1,2,3,... .
Proof: biconditional (if and only if)
(?) Suppose R is transitive. Show Rn ? R, for n =1,2,3,... .
• Let P(n) : Rn ? R. Mathematical induction.
• Basis Step: P(1) says R1 = R so, R1 ? R is true.
CS 441 Discrete mathematics for CS M. Hauskrecht
Connection to Rn
Theorem: The relation R on a set A is transitive if and only if Rn ?
R for n = 1,2,3,... .
Proof: biconditional (if and only if)
(?) Suppose R is transitive. Show Rn ? R, for n =1,2,3,... .
• Let P(n) : Rn ? R. Mathematical induction.
• Basis Step: P(1) says R1 = R so, R1 ? R is true.
• Inductive Step: show P(n) ? P(n+1)
• Want to show if Rn ? R then Rn+1 ? R.
25
CS 441 Discrete mathematics for CS M. Hauskrecht
Connection to Rn
Theorem: The relation R on a set A is transitive if and only if Rn ?
R for n = 1,2,3,... .
Proof: biconditional (if and only if)
(?) Suppose R is transitive. Show Rn ? R, for n =1,2,3,... .
• Let P(n) : Rn ? R. Mathematical induction.
• Basis Step: P(1) says R1 = R so, R1 ? R is true.
• Inductive Step: show P(n) ? P(n+1)
• Want to show if Rn ? R then Rn+1 ? R.
• Let (a,b) ? Rn+1 then by the definition of Rn+1 = Rn ? R there is
an element x ? A so that (a,x) ? R and (x,b) ? Rn ? R
(inductive hypothesis). In addition to (a,x) ? R and (x,b) ? R, R
is transitive; so (a,b) ? R.
• Therefore, Rn+1 ? R.
CS 441 Discrete mathematics for CS M. Hauskrecht