1M. HauskrechtCS 441 Discrete mathematics for CSCS 441 Discrete Mathematics for CSLecture 23Milos [email protected] Sennott SquareRelations III.M. HauskrechtCS 441 Discrete mathematics for CSComposite of relationsDefinition: 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:aAB CRSbc2M. HauskrechtCS 441 Discrete mathematics for CSComposite of relationsDefinition: 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:aAB CRSbc(a,c)  S o RM. HauskrechtCS 441 Discrete mathematics for CSComposite of relationsDefinition: 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 = ?3M. HauskrechtCS 441 Discrete mathematics for CSComposite of relationsDefinition: 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)}M. HauskrechtCS 441 Discrete mathematics for CSRepresenting 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  bExample:• 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)}123412344M. HauskrechtCS 441 Discrete mathematics for CSRepresenting relations on a set with digraphsDefinition: 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)}123412341234digraphM. HauskrechtCS 441 Discrete mathematics for CSPowers of RDefinition: 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= RnoR.Examples• R = {(1,2),(2,3),(2,4), (3,3)} is a relation on A = {1,2,3,4}.12345M. HauskrechtCS 441 Discrete mathematics for CSPowers of RDefinition: 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= RnoR.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 2represent?1234M. HauskrechtCS 441 Discrete mathematics for CSPowers of RDefinition: 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= RnoR.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 2represent?• Paths of length 212346M. HauskrechtCS 441 Discrete mathematics for CSPowers of RDefinition: 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= RnoR.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 2represent? • Paths of length 2•R 3= {(1,3), (2,3), (3,3)} 1234M. HauskrechtCS 441 Discrete mathematics for CSPowers of RDefinition: 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= RnoR.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 2represent? • Paths of length 2•R 3= {(1,3), (2,3), (3,3)} path of length 312347M. HauskrechtCS 441 Discrete mathematics for CSPowers of RDefinition: 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= RnoR.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)}1234M. HauskrechtCS 441 Discrete mathematics for CSPowers of RDefinition: 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= RnoR.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>312348M. HauskrechtCS 441 Discrete mathematics for CSTransitive relation and RnTheorem: 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 lectureM. HauskrechtCS 441 Discrete mathematics for CSClosures of relations• Let R={(1,1),(1,2),(2,1),(3,2)} on A ={1 2 3}. • Is this relation reflexive?• Answer: ?9M. HauskrechtCS 441 Discrete mathematics for CSClosures of relations• Let R={(1,1),(1,2),(2,1),(3,2)} on A ={1 2 3}. • Is this relation reflexive?• Answer: No. Why? M. HauskrechtCS 441 Discrete mathematics for CSClosures 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: