RelationsOutlineIntroductionRelations: RepresentationRelations on a SetPropertiesProperties: ReflexivityReflexivity: ExamplesProperties: SymmetrySymmetry versus AntisymmetrySymmetric Relations: ExampleProperties: TransitivityTransitivity: Examples (1)Transitivity: Examples (2)More PropertiesSlide 16Combining RelationsCombining Relations: ExampleComposite of RelationsPowers of RelationsPowers of Relations: ExamplePowers of Relations & TransitivitySlide 23Representing Relations0-1 Matrices (1)0-1 Matrix (2)0-1 Matrix (3)0-1 Matrix (4)Matrix Representation: ExampleUsing the Matrix Representation (1)Using the Matrix Representation (2)Slide 32Matrix Representation: Combining RelationsSlide 34Composing Relations: ExampleComposite Relations: RnDirected Graphs Representation (1)Definition: Directed Graphs (2)Directed Graphs Representation (2)Using the Digraphs Representation (1)Using the Digraphs Representation (2)Slide 42Closures: DefinitionsReflexive ClosureSymmetric ClosureTransitive ClosureWarshall’s Algorithm: Key IdeasWarshall’s AlgorithmWarshall’s Algorithm: ExampleSlide 50Equivalence RelationEquivalence Class (1)Equivalence Class (2)Partitions Partitions (1)Partitions (2)Partitions: Visual InterpretationEquivalence Relations: Example 1Equivalence Relations: Example 2Equivalence Relations: Example 3Equivalence Relations: Example 4RelationsSection 8.1, 8.3—8.5 of RosenFall 2008CSCE 235 Introduction to Discrete StructuresCourse web-page: cse.unl.edu/~cse235Questions: [email protected] 235, Fall 20082Outline•Relation: –Definition, representation, relation on a set•Properties–Reflexivity, symmetry, antisymmetric, irreflexive, asymmetric•Combining relations–, , \, composite of relations•Representing relations–0-1 matrices, directed graphs•Closure of relations–Reflexive closure, diagonal relation, Warshall’s Algorithm,•Equivalence relations:–Equivalence class, partitions,RelationsCSCE 235, Fall 20083Introduction•A relation between elements of two sets is a subset of their Cartesian products (set of all ordered pairs•Definition: A binary relation from a set A to a set B is a subset R AB ={ (a,b) | aA, bB}•Relation versus function– In a relation, each aA can map to multiple elements in B–Relations are more general than functions•When (a,b)R, we say that a is related to b.•Notation: aRb, aRb $aRb$, $a\notR b$RelationsCSCE 235, Fall 20084Relations: Representation•To represent a relation, we can enumerate every element of R•Example–Let A={a1,a2,a3,a4,a5} and B={b1,b2,b3}–Let R be a relation from A to B defined as followsR={(a1,b1),(a1,b2),(a1,b3),(a3,b1),(a3,b2),(a3,b3),(a5,b1)}•We can represent this relation graphicallya1a2a3a4b1b2b3A Ba5RelationsCSCE 235, Fall 20085Relations on a Set•Definition: A relation on the set A is a relation from A to A and is a subset of AA•Example: The following are binary relations on NR1={ (a,b) | a b }R2={ (a,b) | a,bN, a/bZ }R3={ (a,b) | a,bN, a-b=2 }•Question: Give some examples of ordered pairs (a,b) N2 that are not in each of these relationsRelationsCSCE 235, Fall 20086Properties•We will study several properties of relations–Reflexive–Symmetric–Transitive –Antisymmetric–AsymmetricRelationsCSCE 235, Fall 20087Properties: Reflexivity•In a relation on a set, if all ordered pairs (a,a) for every aA appears in the relation, R is called reflexive•Definition: A relation R on a set A is called reflexive ifaA (a,a)RRelationsCSCE 235, Fall 20088Reflexivity: Examples•Recall the relations below, which is reflexive?R1={ (a,b) | a b }R2={ (a,b) | a,bN, a/bZ }R3={ (a,b) | a,bN, a-b=2 }•R1 is reflexive since for every aN, a a •R2 is reflexive since a/a=1 is an integer •R3 is not reflexive since a-a=0 for every aNRelationsCSCE 235, Fall 20089Properties: Symmetry•Definitions: –A relation R on a set A is called symmetric ifa,bA ( (b,a)R (a,b)R )–A relation R on a set A is called antisymmetric ifa,bA [(a,b)R (b,a)R a=b]RelationsCSCE 235, Fall 200810Symmetry versus Antisymmetry•In a symmetric relation aRb bRa•In an antisymmetric relation, if we have aRb and bRa hold only when a=b•An antisymmetric relation is not necessarily a reflexive relation•A relation can be –both symmetric and antisymmetric –or neither –or have one property but not the other•A relation that is not symmetric is not necessarily asymmetricRelationsCSCE 235, Fall 200811Symmetric Relations: Example•Consider R={(x,y)R2|x2+y2=1}, is R–Reflexive?–Symmetric?–Antisymmetric?•R is not reflexive since for example (2,2)R2•R is symmetric because x,yR, xRyx2+y2=1 y2+x2=1 yRx•R is not antisymmetric because (1/3,8/3)R and (8/3,1/3)R but 1/38/3RelationsCSCE 235, Fall 200812Properties: Transitivity•Definition: A relation R on a set A is called transitive if whenever (a,b) R and (b,c)R then (a,c)R for all a,b,c Aa,b,cA ((aRb)(bRc)) aRcRelationsCSCE 235, Fall 200813Transitivity: Examples (1)•Is the relation R={(x,y)R2| xy} transitive?•Is the relation R={(a,b),(b,a),(a,a)} transitive?Yes, it is transitive because xRy and yRz xy and yz xz xRz No, it is not transitive because bRa and aRb but bRbRelationsCSCE 235, Fall 200814Transitivity: Examples (2)•Is the relation {(a,b) | a is an ancestor of b} transitive?•Is the relation {(x,y)R2| x2y} transitive?Yes, it is transitive because aRb and bRc a is an ancestor of b and b is an ancestor of c a is an ancestor of c aRc No, it is not transitive because 2R4 and 4R10 but 2R10RelationsCSCE 235, Fall 200815More Properties•Definitions–A relation on a set A is irreflexive ifaA (a,a)R–A relation on a set A is asymmetric ifa,bA ( (a,b)R (b,a) R )•Lemma: A relation R on a set A is asymmetric if and only if–R is irreflexive and–R is antisymmetricRelationsCSCE 235, Fall 200816Outline•Relation: –Definition, representation, relation on a set•Properties–Reflexivity, symmetry, antisymmetric, irreflexive, asymmetric•Combining relations–, , \, composite of relations•Representing relations–0-1 matrices, directed graphs•Closure of relations–Reflexive closure, diagonal relation, Warshall’s Algorithm,•Equivalence relations:–Equivalence class,
View Full Document
Unlocking...