1M. HauskrechtCS 441 Discrete mathematics for CSCS 441 Discrete Mathematics for CSLecture 22Milos [email protected] Sennott SquareRelations IIM. HauskrechtCS 441 Discrete mathematics for CSCartesian product (review)•Let A={a1, a2, ..ak} and B={b1,b2,..bm}.• The Cartesian product A x B is defined by a set of pairs {(a1b1), (a1, b2), … (a1, bm), …, (ak,bm)}.Example:Let A={a,b,c} and B={1 2 3}. What is AxB?AxB = {(a,1),(a,2),(a,3),(b,1),(b,2),(b,3)}2M. HauskrechtCS 441 Discrete mathematics for CSBinary relationDefinition: Let A and B be sets. A binary relation from A to B is a subset of a Cartesian product A x B. Example: Let A={a,b,c} and B={1,2,3}. • R={(a,1),(b,2),(c,2)} is an example of a relation from A to B.M. HauskrechtCS 441 Discrete mathematics for CSRepresenting binary relations• We can graphically represent a binary relation R as follows:•if a R b then draw an arrow from a to b.a  bExample:• Let A = {0, 1, 2}, B = {u,v} and R = { (0,u), (0,v), (1,v), (2,u) }•Note: R  A x B.• Graph:201uv3M. HauskrechtCS 441 Discrete mathematics for CSRepresenting binary relations• We can represent a binary relation R by a table showing (marking) the ordered pairs of R.Example:• Let A = {0, 1, 2}, B = {u,v} and R = { (0,u), (0,v), (1,v), (2,u) }• Table:R | u v 0 | x x1 | x2 | xR | u v 0 | 1 11 | 0 12 | 1 0orM. HauskrechtCS 441 Discrete mathematics for CSProperties of relationsProperties of relations on A: • Reflexive• Irreflexive• Symmetric• Anti-symmetric• Transitive4M. HauskrechtCS 441 Discrete mathematics for CSReflexive relationReflexive 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)}1111MRdiv=010100100001• A relation R is reflexive if and only if MR has 1 in every position on its main diagonal.M. HauskrechtCS 441 Discrete mathematics for CSIrreflexive relationIrreflexive 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)}01111011MR =11011110• A relation R is irreflexive if and only if MR has 0 in every position on its main diagonal.5M. HauskrechtCS 441 Discrete mathematics for CSSymmetric relationSymmetric 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)}01111011MR =11011110• A relation R is symmetric if and only if mij= mjifor all i,j.M. HauskrechtCS 441 Discrete mathematics for CSAnti-symmetric relationDefinition (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 Rfunon A = {1,2,3,4} defined as:•Rfun= {(1,2),(2,2),(3,3)}.• Is Rfunanti-symmetric? • Answer: Yes. It is anti-symmetric6M. HauskrechtCS 441 Discrete mathematics for CSAnti-symmetric relationAntisymmetric relation• relation Rfun= {(1,2),(2,2),(3,3)} 01000100MRfun= 00100000• A relation is antisymmetric if and only if mij= 1  mji= 0 for i≠ j.M. HauskrechtCS 441 Discrete mathematics for CSTransitive relationDefinition (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 Rdivtransitive?• Answer:7M. HauskrechtCS 441 Discrete mathematics for CSTransitive relationDefinition (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 Rdivtransitive?• Answer: Yes.M. HauskrechtCS 441 Discrete mathematics for CSTransitive relationDefinition (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:8M. HauskrechtCS 441 Discrete mathematics for CSTransitive relationDefinition (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.M. HauskrechtCS 441 Discrete mathematics for CSTransitive relationsDefinition (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 Rfunon A = {1,2,3,4} defined as:•Rfun= {(1,2),(2,2),(3,3)}.• Is Rfun transitive? • Answer:9M. HauskrechtCS 441 Discrete mathematics for CSTransitive relationsDefinition (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 Rfunon A = {1,2,3,4} defined as:•Rfun= {(1,2),(2,2),(3,3)}.• Is Rfuntransitive? • Answer: Yes. It is transitive. M. HauskrechtCS 441 Discrete mathematics for CSCombining relationsDefinition: 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.10M. HauskrechtCS 441 Discrete mathematics for CSCombining relationsExample:• 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 = ?M. HauskrechtCS 441 Discrete mathematics for CSCombining relationsExample:• 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