Relations III.
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.
Example:
a
A B C
R S
b c
2
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.
Example:
a
A B C
R S
b c
(a,c) ? S o R
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 = ?
3
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.
Example:
• 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
Representing binary relations with graphs
• We can graphically represent a binary relation R from A to B as
follows:
• if a R b then draw an arrow from a to b.
a ? b
Example:
• Relation Rdiv (from previous lectures) on A={1,2,3,4}
• Rdiv = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}
1
2
3
4
1
2
3
4
4
CS 441 Discrete mathematics for CS M. Hauskrecht
Representing relations on a set with digraphs
Definition: A directed graph or digraph consists of a set of
vertices (or nodes) together with a set E of ordered pairs of
elements of V called edges (or arcs). The vertex a is called the
initial vertex of the edge (a,b) and vertex b is the terminal vertex
of this edge. An edge of the form (a,a) is called a loop.
Example
• Relation Rdiv ={(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}
1
2
3
4
1
2
3
4
1
2
3
4
digraph
CS 441 Discrete mathematics for CS M. Hauskrecht
Powers of R
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 o R.
Examples
• R = {(1,2),(2,3),(2,4), (3,3)} is a relation on A = {1,2,3,4}.
1
2
3
4
5
CS 441 Discrete mathematics for CS M. Hauskrecht
Powers of R
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 o 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)}
• What does R 2 represent?
1
2
3
4
CS 441 Discrete mathematics for CS M. Hauskrecht
Powers of R
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 o 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)}
• What does R 2 represent?
• Paths of length 2
1
2
3
4
6
CS 441 Discrete mathematics for CS M. Hauskrecht
Powers of R
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 o 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)}
• What does R 2 represent?
• Paths of length 2
• R 3 = {(1,3), (2,3), (3,3)}
1
2
3
4
CS 441 Discrete mathematics for CS M. Hauskrecht
Powers of R
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 o 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)}
• What does R 2 represent?
• Paths of length 2
• R 3 = {(1,3), (2,3), (3,3)} path of length 3
1
2
3
4
7
CS 441 Discrete mathematics for CS M. Hauskrecht
Powers of R
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 o 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)}
1
2
3
4
CS 441 Discrete mathematics for CS M. Hauskrecht
Powers of R
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 o 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 = {(1,3), (2,3), (3,3)} k>3
1
2
3
4
8
CS 441 Discrete mathematics for CS M. Hauskrecht
Transitive relation and Rn
Theorem: The relation R on a set A is transitive if and only if
Rn ? R for n = 1,2,3,... .
Proof: bi-conditional (if and only if)
Proved last lecture
CS 441 Discrete mathematics for CS M. Hauskrecht
Closures of relations
• Let R={(1,1),(1,2),(2,1),(3,2)} on A ={1 2 3}.
• Is this relation reflexive?
• Answer: ?
9
CS 441 Discrete mathematics for CS M. Hauskrecht
Closures of relations
• Let R={(1,1),(1,2),(2,1),(3,2)} on A ={1 2 3}.
• Is this relation reflexive?
• Answer: No. Why?
CS 441 Discrete mathematics for CS M. Hauskrecht
Closures of relations
• Let R={(1,1),(1,2),(2,1),(3,2)} on A ={1 2 3}.
• Is this relation reflexive?
• Answer: No. Why?
• (2,2) and (3,3) is not in R.
• The question is what is the minimal relation S ? R that is
reflexive?
• How to make R reflexive with minimum number of additions?
• Answer: ?
10
CS 441 Discrete mathematics for CS M. Hauskrecht
Closures of relations
• Let R={(1,1),(1,2),(2,1),(3,2)} on A ={1 2 3}.
• Is this relation reflexive?
• Answer: No. Why?
• (2,2) and (3,3) is not in R.
• The question is what is the minimal relation S ? R that is
reflexive?
• How to make R reflexive with minimum number of additions?
• Answer: Add (2,2) and (3,3)
• Then S= {(1,1),(1,2),(2,1),(3,2),(2,2),(3,3)}
• R ? S
• The minimal set S ? R is called the reflexive closure of R
CS 441 Discrete mathematics for CS M. Hauskrecht
Reflexive closure
The set S is called the reflexive closure of R if it:
– contains R
– has reflexive property
– is contained in every reflexive relation Q that contains R (R
? Q) , that is S ? Q
11
CS 441 Discrete mathematics for CS M. Hauskrecht
Closures on relations
• Relations can have different properties:
• reflexive,
• symmetric
• transitive
• Because of that we define:
• symmetric,
• reflexive and
• transitive
closures.
CS 441 Discrete mathematics for CS M. Hauskrecht
Closures
Definition: Let R be a relation on a set A. A relation S on A with
property P is called the closure of R with respect to P if S is a
subset of every relation Q (S ? Q) with property P that contains
R (R ? Q).
12
CS 441 Discrete mathematics for CS M. Hauskrecht
Closures
Definition: Let R be a relation on a set A. A relation S on A with
property P is called the closure of R with respect to P if S is a
subset of every relation Q (S ? Q) with property P that contains
R (R ? Q).
Example (symmetric closure):
• Assume R={(1,2),(1,3), (2,2)} on A={1,2,3}.
• What is the symmetric closure S of R?
• S=?
CS 441 Discrete mathematics for CS M. Hauskrecht
Closures
Definition: Let R be a relation on a set A. A relation S on A with
property P is called the closure of R with respect to P if S is a
subset of every relation Q (S ? Q) with property P that contains
R (R ? Q).
Example (a symmetric closure):
• Assume R={(1,2),(1,3), (2,2)} on A={1,2,3}.
• What is the symmetric closure S of R?
• S = {(1,2),(1,3), (2,2)} ? {(2,1), (3,1)}
= {(1,2),(1,3), (2,2),(2,1), (3,1)}
13
CS 441 Discrete mathematics for CS M. Hauskrecht
Closures
Definition: Let R be a relation on a set A. A relation S on A with
property P is called the closure of R with respect to P if S is a
subset of every relation Q (S ? Q) with property P that contains
R (R ? Q).
Example (transitive closure):
• Assume R={(1,2), (2,2), (2,3)} on A={1,2,3}.
• Is R transitive?
CS 441 Discrete mathematics for CS M. Hauskrecht
Closures
Definition: Let R be a relation on a set A. A relation S on A with
property P is called the closure of R with respect to P if S is a
subset of every relation Q (S ? Q) with property P that contains
R (R ? Q).
Example (transitive closure):
• Assume R={(1,2), (2,2), (2,3)} on A={1,2,3}.
• Is R transitive? No.
• How to make it transitive?
• S = ?
14
CS 441 Discrete mathematics for CS M. Hauskrecht
Closures
Definition: Let R be a relation on a set A. A relation S on A with
property P is called the closure of R with respect to P if S is a
subset of every relation Q (S ? Q) with property P that contains
R (R ? Q).
Example (transitive closure):
• Assume R={(1,2), (2,2), (2,3)} on A={1,2,3}.
• Is R transitive? No.
• How to make it transitive?
• S = {(1,2), (2,2), (2,3)} ? {(1,3)}
= {(1,2), (2,2), (2,3),(1,3)}
• S is the transitive closure of R
CS 441 Discrete mathematics for CS M. Hauskrecht
Transitive closure
We can represent the relation on the graph. Finding a transitive
closure corresponds to finding all pairs of elements that are
connected with a directed path (or digraph).
Example:
Assume R={(1,2), (2,2), (2,3)} on A={1,2,3}.
Transitive closure S = {(1,2), (2,2), (2,3),(1,3)}.
1
2
3
R
15
CS 441 Discrete mathematics for CS M. Hauskrecht
Transitive closure
We can represent the relation on the graph. Finding a transitive
closure corresponds to finding all pairs of elements that are
connected with a directed path (or digraph).
Example:
Assume R={(1,2), (2,2), (2,3)} on A={1,2,3}.
Transitive closure S = {(1,2), (2,2), (2,3),(1,3)}.
1
2
3
R
CS 441 Discrete mathematics for CS M. Hauskrecht
Transitive closure
We can represent the relation on the graph. Finding a transitive
closure corresponds to finding all pairs of elements that are
connected with a directed path (or digraph).
Example:
Assume R={(1,2), (2,2), (2,3)} on A={1,2,3}.
Transitive closure S = {(1,2), (2,2), (2,3),(1,3)}.
1
2
3
R S
1
2
3
16
CS 441 Discrete mathematics for CS M. Hauskrecht
Path length
Theorem: Let R be a relation on a set A. There is a path of length
n from a to b if and only if (a,b) ? Rn.
Proof (math induction):
Path of length n
a x b
Path of length 1
Path of length n+1
a b
Path of length 1
CS 441 Discrete mathematics for CS M. Hauskrecht
Path length
Theorem: Let R be a relation on a set A. There is a path of length
n from a to b if and only if (a,b) ? Rn.
Proof (math induction):
• P(1): There is a path of length 1 from a to b if and only if (a,b) ?
R1, by the definition of R.
17
CS 441 Discrete mathematics for CS M. Hauskrecht
Path length
Theorem: Let R be a relation on a set A. There is a path of length
n from a to b if and only if (a,b) ? Rn.
Proof (math induction):
• P(1): There is a path of length 1 from a to b if and only if (a,b) ?
R1, by the definition of R.
• Show P(n) ? P(n+1): Assume there is a path of length n from
a to b if and only if (a,b) ? Rn ? there is a path of length n+1
from a to b if and only if (a,b) ? Rn+1.
CS 441 Discrete mathematics for CS M. Hauskrecht
Path length
Theorem: Let R be a relation on a set A. There is a path of length
n from a to b if and only if (a,b) ? Rn.
Proof (math induction):
• P(1): There is a path of length 1 from a to b if and only if (a,b) ?
R1, by the definition of R.
• Show P(n) ? P(n+1): Assume there is a path of length n from
a to b if and only if (a,b) ? Rn ? there is a path of length n+1
from a to b if and only if (a,b) ? Rn+1.
• There is a path of length n+1 from a to b if and only if there
exists an x ? A, such that (a,x) ? R (a path of length 1) and (x,b)
? Rn is a path of length n from x to b.
• (x,b) ? Rn holds due to P(n). Therefore, there is a path of length
n + 1 from a to b. This also implies that (a,b) ? Rn+1.
Path of length n
a x b
18
CS 441 Discrete mathematics for CS M. Hauskrecht
Connectivity relation
Definition: Let R be a relation on a set A. The connectivity
relation R* consists of all pairs (a,b) such that there is a path (of
any length, ie. 1 or 2 or 3 or ...) between a and b in R.
Example:
• A = {1,2,3,4}
• R = {(1,2),(1,4),(2,3),(3,4)}
? ?
?
?
1
*
k
R R k
1
2 3
4
CS 441 Discrete mathematics for CS M. Hauskrecht
Connectivity relation
Definition: Let R be a relation on a set A. The connectivity
relation R* consists of all pairs (a,b) such that there is a path (of
any length, ie. 1 or 2 or 3 or ...) between a and b in R.
Example:
• A = {1,2,3,4}
• R = {(1,2),(1,4),(2,3),(3,4)}
• R2 = ?
•
? ?
?
?
1
*
k
R R k
1
2 3
4
19
CS 441 Discrete mathematics for CS M. Hauskrecht
Connectivity relation
Definition: Let R be a relation on a set A. The connectivity
relation R* consists of all pairs (a,b) such that there is a path (of
any length, ie. 1 or 2 or 3 or ...) between a and b in R.
Example:
• A = {1,2,3,4}
• R = {(1,2),(1,4),(2,3),(3,4)}
• R2 = {(1,3),(2,4)}
• R3 = ?
•
? ?
?
?
1
*
k
R R k
1
2 3
4
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.
Example:
a
A B C
R S
b c
2
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.
Example:
a
A B C
R S
b c
(a,c) ? S o R
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 = ?
3
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.
Example:
• 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
Representing binary relations with graphs
• We can graphically represent a binary relation R from A to B as
follows:
• if a R b then draw an arrow from a to b.
a ? b
Example:
• Relation Rdiv (from previous lectures) on A={1,2,3,4}
• Rdiv = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}
1
2
3
4
1
2
3
4
4
CS 441 Discrete mathematics for CS M. Hauskrecht
Representing relations on a set with digraphs
Definition: A directed graph or digraph consists of a set of
vertices (or nodes) together with a set E of ordered pairs of
elements of V called edges (or arcs). The vertex a is called the
initial vertex of the edge (a,b) and vertex b is the terminal vertex
of this edge. An edge of the form (a,a) is called a loop.
Example
• Relation Rdiv ={(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}
1
2
3
4
1
2
3
4
1
2
3
4
digraph
CS 441 Discrete mathematics for CS M. Hauskrecht
Powers of R
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 o R.
Examples
• R = {(1,2),(2,3),(2,4), (3,3)} is a relation on A = {1,2,3,4}.
1
2
3
4
5
CS 441 Discrete mathematics for CS M. Hauskrecht
Powers of R
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 o 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)}
• What does R 2 represent?
1
2
3
4
CS 441 Discrete mathematics for CS M. Hauskrecht
Powers of R
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 o 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)}
• What does R 2 represent?
• Paths of length 2
1
2
3
4
6
CS 441 Discrete mathematics for CS M. Hauskrecht
Powers of R
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 o 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)}
• What does R 2 represent?
• Paths of length 2
• R 3 = {(1,3), (2,3), (3,3)}
1
2
3
4
CS 441 Discrete mathematics for CS M. Hauskrecht
Powers of R
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 o 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)}
• What does R 2 represent?
• Paths of length 2
• R 3 = {(1,3), (2,3), (3,3)} path of length 3
1
2
3
4
7
CS 441 Discrete mathematics for CS M. Hauskrecht
Powers of R
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 o 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)}
1
2
3
4
CS 441 Discrete mathematics for CS M. Hauskrecht
Powers of R
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 o 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 = {(1,3), (2,3), (3,3)} k>3
1
2
3
4
8
CS 441 Discrete mathematics for CS M. Hauskrecht
Transitive relation and Rn
Theorem: The relation R on a set A is transitive if and only if
Rn ? R for n = 1,2,3,... .
Proof: bi-conditional (if and only if)
Proved last lecture
CS 441 Discrete mathematics for CS M. Hauskrecht
Closures of relations
• Let R={(1,1),(1,2),(2,1),(3,2)} on A ={1 2 3}.
• Is this relation reflexive?
• Answer: ?
9
CS 441 Discrete mathematics for CS M. Hauskrecht
Closures of relations
• Let R={(1,1),(1,2),(2,1),(3,2)} on A ={1 2 3}.
• Is this relation reflexive?
• Answer: No. Why?
CS 441 Discrete mathematics for CS M. Hauskrecht
Closures of relations
• Let R={(1,1),(1,2),(2,1),(3,2)} on A ={1 2 3}.
• Is this relation reflexive?
• Answer: No. Why?
• (2,2) and (3,3) is not in R.
• The question is what is the minimal relation S ? R that is
reflexive?
• How to make R reflexive with minimum number of additions?
• Answer: ?
10
CS 441 Discrete mathematics for CS M. Hauskrecht
Closures of relations
• Let R={(1,1),(1,2),(2,1),(3,2)} on A ={1 2 3}.
• Is this relation reflexive?
• Answer: No. Why?
• (2,2) and (3,3) is not in R.
• The question is what is the minimal relation S ? R that is
reflexive?
• How to make R reflexive with minimum number of additions?
• Answer: Add (2,2) and (3,3)
• Then S= {(1,1),(1,2),(2,1),(3,2),(2,2),(3,3)}
• R ? S
• The minimal set S ? R is called the reflexive closure of R
CS 441 Discrete mathematics for CS M. Hauskrecht
Reflexive closure
The set S is called the reflexive closure of R if it:
– contains R
– has reflexive property
– is contained in every reflexive relation Q that contains R (R
? Q) , that is S ? Q
11
CS 441 Discrete mathematics for CS M. Hauskrecht
Closures on relations
• Relations can have different properties:
• reflexive,
• symmetric
• transitive
• Because of that we define:
• symmetric,
• reflexive and
• transitive
closures.
CS 441 Discrete mathematics for CS M. Hauskrecht
Closures
Definition: Let R be a relation on a set A. A relation S on A with
property P is called the closure of R with respect to P if S is a
subset of every relation Q (S ? Q) with property P that contains
R (R ? Q).
12
CS 441 Discrete mathematics for CS M. Hauskrecht
Closures
Definition: Let R be a relation on a set A. A relation S on A with
property P is called the closure of R with respect to P if S is a
subset of every relation Q (S ? Q) with property P that contains
R (R ? Q).
Example (symmetric closure):
• Assume R={(1,2),(1,3), (2,2)} on A={1,2,3}.
• What is the symmetric closure S of R?
• S=?
CS 441 Discrete mathematics for CS M. Hauskrecht
Closures
Definition: Let R be a relation on a set A. A relation S on A with
property P is called the closure of R with respect to P if S is a
subset of every relation Q (S ? Q) with property P that contains
R (R ? Q).
Example (a symmetric closure):
• Assume R={(1,2),(1,3), (2,2)} on A={1,2,3}.
• What is the symmetric closure S of R?
• S = {(1,2),(1,3), (2,2)} ? {(2,1), (3,1)}
= {(1,2),(1,3), (2,2),(2,1), (3,1)}
13
CS 441 Discrete mathematics for CS M. Hauskrecht
Closures
Definition: Let R be a relation on a set A. A relation S on A with
property P is called the closure of R with respect to P if S is a
subset of every relation Q (S ? Q) with property P that contains
R (R ? Q).
Example (transitive closure):
• Assume R={(1,2), (2,2), (2,3)} on A={1,2,3}.
• Is R transitive?
CS 441 Discrete mathematics for CS M. Hauskrecht
Closures
Definition: Let R be a relation on a set A. A relation S on A with
property P is called the closure of R with respect to P if S is a
subset of every relation Q (S ? Q) with property P that contains
R (R ? Q).
Example (transitive closure):
• Assume R={(1,2), (2,2), (2,3)} on A={1,2,3}.
• Is R transitive? No.
• How to make it transitive?
• S = ?
14
CS 441 Discrete mathematics for CS M. Hauskrecht
Closures
Definition: Let R be a relation on a set A. A relation S on A with
property P is called the closure of R with respect to P if S is a
subset of every relation Q (S ? Q) with property P that contains
R (R ? Q).
Example (transitive closure):
• Assume R={(1,2), (2,2), (2,3)} on A={1,2,3}.
• Is R transitive? No.
• How to make it transitive?
• S = {(1,2), (2,2), (2,3)} ? {(1,3)}
= {(1,2), (2,2), (2,3),(1,3)}
• S is the transitive closure of R
CS 441 Discrete mathematics for CS M. Hauskrecht
Transitive closure
We can represent the relation on the graph. Finding a transitive
closure corresponds to finding all pairs of elements that are
connected with a directed path (or digraph).
Example:
Assume R={(1,2), (2,2), (2,3)} on A={1,2,3}.
Transitive closure S = {(1,2), (2,2), (2,3),(1,3)}.
1
2
3
R
15
CS 441 Discrete mathematics for CS M. Hauskrecht
Transitive closure
We can represent the relation on the graph. Finding a transitive
closure corresponds to finding all pairs of elements that are
connected with a directed path (or digraph).
Example:
Assume R={(1,2), (2,2), (2,3)} on A={1,2,3}.
Transitive closure S = {(1,2), (2,2), (2,3),(1,3)}.
1
2
3
R
CS 441 Discrete mathematics for CS M. Hauskrecht
Transitive closure
We can represent the relation on the graph. Finding a transitive
closure corresponds to finding all pairs of elements that are
connected with a directed path (or digraph).
Example:
Assume R={(1,2), (2,2), (2,3)} on A={1,2,3}.
Transitive closure S = {(1,2), (2,2), (2,3),(1,3)}.
1
2
3
R S
1
2
3
16
CS 441 Discrete mathematics for CS M. Hauskrecht
Path length
Theorem: Let R be a relation on a set A. There is a path of length
n from a to b if and only if (a,b) ? Rn.
Proof (math induction):
Path of length n
a x b
Path of length 1
Path of length n+1
a b
Path of length 1
CS 441 Discrete mathematics for CS M. Hauskrecht
Path length
Theorem: Let R be a relation on a set A. There is a path of length
n from a to b if and only if (a,b) ? Rn.
Proof (math induction):
• P(1): There is a path of length 1 from a to b if and only if (a,b) ?
R1, by the definition of R.
17
CS 441 Discrete mathematics for CS M. Hauskrecht
Path length
Theorem: Let R be a relation on a set A. There is a path of length
n from a to b if and only if (a,b) ? Rn.
Proof (math induction):
• P(1): There is a path of length 1 from a to b if and only if (a,b) ?
R1, by the definition of R.
• Show P(n) ? P(n+1): Assume there is a path of length n from
a to b if and only if (a,b) ? Rn ? there is a path of length n+1
from a to b if and only if (a,b) ? Rn+1.
CS 441 Discrete mathematics for CS M. Hauskrecht
Path length
Theorem: Let R be a relation on a set A. There is a path of length
n from a to b if and only if (a,b) ? Rn.
Proof (math induction):
• P(1): There is a path of length 1 from a to b if and only if (a,b) ?
R1, by the definition of R.
• Show P(n) ? P(n+1): Assume there is a path of length n from
a to b if and only if (a,b) ? Rn ? there is a path of length n+1
from a to b if and only if (a,b) ? Rn+1.
• There is a path of length n+1 from a to b if and only if there
exists an x ? A, such that (a,x) ? R (a path of length 1) and (x,b)
? Rn is a path of length n from x to b.
• (x,b) ? Rn holds due to P(n). Therefore, there is a path of length
n + 1 from a to b. This also implies that (a,b) ? Rn+1.
Path of length n
a x b
18
CS 441 Discrete mathematics for CS M. Hauskrecht
Connectivity relation
Definition: Let R be a relation on a set A. The connectivity
relation R* consists of all pairs (a,b) such that there is a path (of
any length, ie. 1 or 2 or 3 or ...) between a and b in R.
Example:
• A = {1,2,3,4}
• R = {(1,2),(1,4),(2,3),(3,4)}
? ?
?
?
1
*
k
R R k
1
2 3
4
CS 441 Discrete mathematics for CS M. Hauskrecht
Connectivity relation
Definition: Let R be a relation on a set A. The connectivity
relation R* consists of all pairs (a,b) such that there is a path (of
any length, ie. 1 or 2 or 3 or ...) between a and b in R.
Example:
• A = {1,2,3,4}
• R = {(1,2),(1,4),(2,3),(3,4)}
• R2 = ?
•
? ?
?
?
1
*
k
R R k
1
2 3
4
19
CS 441 Discrete mathematics for CS M. Hauskrecht
Connectivity relation
Definition: Let R be a relation on a set A. The connectivity
relation R* consists of all pairs (a,b) such that there is a path (of
any length, ie. 1 or 2 or 3 or ...) between a and b in R.
Example:
• A = {1,2,3,4}
• R = {(1,2),(1,4),(2,3),(3,4)}
• R2 = {(1,3),(2,4)}
• R3 = ?
•
? ?
?
?
1
*
k
R R k
1
2 3
4
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.
Example:
a
A B C
R S
b c
2
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.
Example:
a
A B C
R S
b c
(a,c) ? S o R
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 = ?
3
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.
Example:
• 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
Representing binary relations with graphs
• We can graphically represent a binary relation R from A to B as
follows:
• if a R b then draw an arrow from a to b.
a ? b
Example:
• Relation Rdiv (from previous lectures) on A={1,2,3,4}
• Rdiv = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}
1
2
3
4
1
2
3
4
4
CS 441 Discrete mathematics for CS M. Hauskrecht
Representing relations on a set with digraphs
Definition: A directed graph or digraph consists of a set of
vertices (or nodes) together with a set E of ordered pairs of
elements of V called edges (or arcs). The vertex a is called the
initial vertex of the edge (a,b) and vertex b is the terminal vertex
of this edge. An edge of the form (a,a) is called a loop.
Example
• Relation Rdiv ={(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}
1
2
3
4
1
2
3
4
1
2
3
4
digraph
CS 441 Discrete mathematics for CS M. Hauskrecht
Powers of R
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 o R.
Examples
• R = {(1,2),(2,3),(2,4), (3,3)} is a relation on A = {1,2,3,4}.
1
2
3
4
5
CS 441 Discrete mathematics for CS M. Hauskrecht
Powers of R
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 o 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)}
• What does R 2 represent?
1
2
3
4
CS 441 Discrete mathematics for CS M. Hauskrecht
Powers of R
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 o 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)}
• What does R 2 represent?
• Paths of length 2
1
2
3
4
6
CS 441 Discrete mathematics for CS M. Hauskrecht
Powers of R
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 o 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)}
• What does R 2 represent?
• Paths of length 2
• R 3 = {(1,3), (2,3), (3,3)}
1
2
3
4
CS 441 Discrete mathematics for CS M. Hauskrecht
Powers of R
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 o 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)}
• What does R 2 represent?
• Paths of length 2
• R 3 = {(1,3), (2,3), (3,3)} path of length 3
1
2
3
4
7
CS 441 Discrete mathematics for CS M. Hauskrecht
Powers of R
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 o 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)}
1
2
3
4
CS 441 Discrete mathematics for CS M. Hauskrecht
Powers of R
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 o 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 = {(1,3), (2,3), (3,3)} k>3
1
2
3
4
8
CS 441 Discrete mathematics for CS M. Hauskrecht
Transitive relation and Rn
Theorem: The relation R on a set A is transitive if and only if
Rn ? R for n = 1,2,3,... .
Proof: bi-conditional (if and only if)
Proved last lecture
CS 441 Discrete mathematics for CS M. Hauskrecht
Closures of relations
• Let R={(1,1),(1,2),(2,1),(3,2)} on A ={1 2 3}.
• Is this relation reflexive?
• Answer: ?
9
CS 441 Discrete mathematics for CS M. Hauskrecht
Closures of relations
• Let R={(1,1),(1,2),(2,1),(3,2)} on A ={1 2 3}.
• Is this relation reflexive?
• Answer: No. Why?
CS 441 Discrete mathematics for CS M. Hauskrecht
Closures of relations
• Let R={(1,1),(1,2),(2,1),(3,2)} on A ={1 2 3}.
• Is this relation reflexive?
• Answer: No. Why?
• (2,2) and (3,3) is not in R.
• The question is what is the minimal relation S ? R that is
reflexive?
• How to make R reflexive with minimum number of additions?
• Answer: ?
10
CS 441 Discrete mathematics for CS M. Hauskrecht
Closures of relations
• Let R={(1,1),(1,2),(2,1),(3,2)} on A ={1 2 3}.
• Is this relation reflexive?
• Answer: No. Why?
• (2,2) and (3,3) is not in R.
• The question is what is the minimal relation S ? R that is
reflexive?
• How to make R reflexive with minimum number of additions?
• Answer: Add (2,2) and (3,3)
• Then S= {(1,1),(1,2),(2,1),(3,2),(2,2),(3,3)}
• R ? S
• The minimal set S ? R is called the reflexive closure of R
CS 441 Discrete mathematics for CS M. Hauskrecht
Reflexive closure
The set S is called the reflexive closure of R if it:
– contains R
– has reflexive property
– is contained in every reflexive relation Q that contains R (R
? Q) , that is S ? Q
11
CS 441 Discrete mathematics for CS M. Hauskrecht
Closures on relations
• Relations can have different properties:
• reflexive,
• symmetric
• transitive
• Because of that we define:
• symmetric,
• reflexive and
• transitive
closures.
CS 441 Discrete mathematics for CS M. Hauskrecht
Closures
Definition: Let R be a relation on a set A. A relation S on A with
property P is called the closure of R with respect to P if S is a
subset of every relation Q (S ? Q) with property P that contains
R (R ? Q).
12
CS 441 Discrete mathematics for CS M. Hauskrecht
Closures
Definition: Let R be a relation on a set A. A relation S on A with
property P is called the closure of R with respect to P if S is a
subset of every relation Q (S ? Q) with property P that contains
R (R ? Q).
Example (symmetric closure):
• Assume R={(1,2),(1,3), (2,2)} on A={1,2,3}.
• What is the symmetric closure S of R?
• S=?
CS 441 Discrete mathematics for CS M. Hauskrecht
Closures
Definition: Let R be a relation on a set A. A relation S on A with
property P is called the closure of R with respect to P if S is a
subset of every relation Q (S ? Q) with property P that contains
R (R ? Q).
Example (a symmetric closure):
• Assume R={(1,2),(1,3), (2,2)} on A={1,2,3}.
• What is the symmetric closure S of R?
• S = {(1,2),(1,3), (2,2)} ? {(2,1), (3,1)}
= {(1,2),(1,3), (2,2),(2,1), (3,1)}
13
CS 441 Discrete mathematics for CS M. Hauskrecht
Closures
Definition: Let R be a relation on a set A. A relation S on A with
property P is called the closure of R with respect to P if S is a
subset of every relation Q (S ? Q) with property P that contains
R (R ? Q).
Example (transitive closure):
• Assume R={(1,2), (2,2), (2,3)} on A={1,2,3}.
• Is R transitive?
CS 441 Discrete mathematics for CS M. Hauskrecht
Closures
Definition: Let R be a relation on a set A. A relation S on A with
property P is called the closure of R with respect to P if S is a
subset of every relation Q (S ? Q) with property P that contains
R (R ? Q).
Example (transitive closure):
• Assume R={(1,2), (2,2), (2,3)} on A={1,2,3}.
• Is R transitive? No.
• How to make it transitive?
• S = ?
14
CS 441 Discrete mathematics for CS M. Hauskrecht
Closures
Definition: Let R be a relation on a set A. A relation S on A with
property P is called the closure of R with respect to P if S is a
subset of every relation Q (S ? Q) with property P that contains
R (R ? Q).
Example (transitive closure):
• Assume R={(1,2), (2,2), (2,3)} on A={1,2,3}.
• Is R transitive? No.
• How to make it transitive?
• S = {(1,2), (2,2), (2,3)} ? {(1,3)}
= {(1,2), (2,2), (2,3),(1,3)}
• S is the transitive closure of R
CS 441 Discrete mathematics for CS M. Hauskrecht
Transitive closure
We can represent the relation on the graph. Finding a transitive
closure corresponds to finding all pairs of elements that are
connected with a directed path (or digraph).
Example:
Assume R={(1,2), (2,2), (2,3)} on A={1,2,3}.
Transitive closure S = {(1,2), (2,2), (2,3),(1,3)}.
1
2
3
R
15
CS 441 Discrete mathematics for CS M. Hauskrecht
Transitive closure
We can represent the relation on the graph. Finding a transitive
closure corresponds to finding all pairs of elements that are
connected with a directed path (or digraph).
Example:
Assume R={(1,2), (2,2), (2,3)} on A={1,2,3}.
Transitive closure S = {(1,2), (2,2), (2,3),(1,3)}.
1
2
3
R
CS 441 Discrete mathematics for CS M. Hauskrecht
Transitive closure
We can represent the relation on the graph. Finding a transitive
closure corresponds to finding all pairs of elements that are
connected with a directed path (or digraph).
Example:
Assume R={(1,2), (2,2), (2,3)} on A={1,2,3}.
Transitive closure S = {(1,2), (2,2), (2,3),(1,3)}.
1
2
3
R S
1
2
3
16
CS 441 Discrete mathematics for CS M. Hauskrecht
Path length
Theorem: Let R be a relation on a set A. There is a path of length
n from a to b if and only if (a,b) ? Rn.
Proof (math induction):
Path of length n
a x b
Path of length 1
Path of length n+1
a b
Path of length 1
CS 441 Discrete mathematics for CS M. Hauskrecht
Path length
Theorem: Let R be a relation on a set A. There is a path of length
n from a to b if and only if (a,b) ? Rn.
Proof (math induction):
• P(1): There is a path of length 1 from a to b if and only if (a,b) ?
R1, by the definition of R.
17
CS 441 Discrete mathematics for CS M. Hauskrecht
Path length
Theorem: Let R be a relation on a set A. There is a path of length
n from a to b if and only if (a,b) ? Rn.
Proof (math induction):
• P(1): There is a path of length 1 from a to b if and only if (a,b) ?
R1, by the definition of R.
• Show P(n) ? P(n+1): Assume there is a path of length n from
a to b if and only if (a,b) ? Rn ? there is a path of length n+1
from a to b if and only if (a,b) ? Rn+1.
CS 441 Discrete mathematics for CS M. Hauskrecht
Path length
Theorem: Let R be a relation on a set A. There is a path of length
n from a to b if and only if (a,b) ? Rn.
Proof (math induction):
• P(1): There is a path of length 1 from a to b if and only if (a,b) ?
R1, by the definition of R.
• Show P(n) ? P(n+1): Assume there is a path of length n from
a to b if and only if (a,b) ? Rn ? there is a path of length n+1
from a to b if and only if (a,b) ? Rn+1.
• There is a path of length n+1 from a to b if and only if there
exists an x ? A, such that (a,x) ? R (a path of length 1) and (x,b)
? Rn is a path of length n from x to b.
• (x,b) ? Rn holds due to P(n). Therefore, there is a path of length
n + 1 from a to b. This also implies that (a,b) ? Rn+1.
Path of length n
a x b
18
CS 441 Discrete mathematics for CS M. Hauskrecht
Connectivity relation
Definition: Let R be a relation on a set A. The connectivity
relation R* consists of all pairs (a,b) such that there is a path (of
any length, ie. 1 or 2 or 3 or ...) between a and b in R.
Example:
• A = {1,2,3,4}
• R = {(1,2),(1,4),(2,3),(3,4)}
? ?
?
?
1
*
k
R R k
1
2 3
4
CS 441 Discrete mathematics for CS M. Hauskrecht
Connectivity relation
Definition: Let R be a relation on a set A. The connectivity
relation R* consists of all pairs (a,b) such that there is a path (of
any length, ie. 1 or 2 or 3 or ...) between a and b in R.
Example:
• A = {1,2,3,4}
• R = {(1,2),(1,4),(2,3),(3,4)}
• R2 = ?
•
? ?
?
?
1
*
k
R R k
1
2 3
4
19
CS 441 Discrete mathematics for CS M. Hauskrecht
Connectivity relation
Definition: Let R be a relation on a set A. The connectivity
relation R* consists of all pairs (a,b) such that there is a path (of
any length, ie. 1 or 2 or 3 or ...) between a and b in R.
Example:
• A = {1,2,3,4}
• R = {(1,2),(1,4),(2,3),(3,4)}
• R2 = {(1,3),(2,4)}
• R3 = ?
•
? ?
?
?
1
*
k
R R k
1
2 3
4
CS 441 Discrete mathematics for CS M. Hauskrecht