§7.1 Binary Relations (2nd pass) and §7.2 n-ary Relations Longin Jan Latecki§7.1 Binary Relations (2nd pass)Complementary RelationsInverse RelationsRelations on a SetReflexivity and relativesSlide 7Slide 8Some examplesSymmetry & relativesSome direct consequencesSlide 12Slide 13AntisymmetrySlide 15TransitivityComposite RelationsSlide 18Slide 19§7.2: n-ary RelationsSlide 21Relational DatabasesSelection OperatorsSelection Operator ExampleProjection OperatorsProjection ExampleJoin OperatorJoin Example01/14/19 1§7.1 Binary Relations (2nd pass)and §7.2 n-ary Relations Longin Jan Latecki Slides adapted from Kees van Deemter who adopted them Slides adapted from Kees van Deemter who adopted them from Michael P. Frank’s from Michael P. Frank’s Course Based on the TextCourse Based on the TextDiscrete Mathematics & Its ApplicationsDiscrete Mathematics & Its Applications (5(5thth Edition) Edition)by Kenneth H. Rosenby Kenneth H. Rosen01/14/19 2§7.1 Binary Relations (2nd pass)•Let Let AA, , BB be any sets. A be any sets. A binary relationbinary relation RR from from AA to to B B is a subset of is a subset of AA××BB. . –E.g.E.g.,, << can be seen ascan be seen as {({(nn,,mm)) | | n n < < mm}}•((aa,,bb))R R means thatmeans that aa is related to is related to bb (by (by RR))•Also written asAlso written as aRbaRb; ; alsoalso R(a,b)R(a,b)–E.g.,E.g., aa<b<b and and << ( (a,b)a,b) both both meanmean (a,b)(a,b) <<•A binary relation A binary relation R R corresponds to a characteristic corresponds to a characteristic function function PPRR::AA××BB→{→{TT,,FF} }01/14/19 3Complementary Relations•Let Let RR::AA,,BB be any binary relation. be any binary relation.•Then, Then, RR::AA××BB, the , the complementcomplement of of RR, is the , is the binary relation defined bybinary relation defined by RR:≡{(:≡{(aa,,bb))AA××BB | ( | (aa,,bb))RR}=(}=(AA××BB) − ) − RR•Note this is just Note this is just RR if the universe of if the universe of discourse is discourse is UU = = AA××BB; thus the name ; thus the name complement.complement.•Note the complement of Note the complement of RR is is RR..Example: << = {( = {(aa,,bb) | () | (aa,,bb))<<} = {(} = {(aa,,bb) | ) | ¬¬aa<<bb} = } = ≥≥01/14/19 4Inverse Relations•Any binary relation Any binary relation RR::AA××BB has an has an inverseinverse relation relation RR−1−1::BB××AA, defined by, defined byRR−1 −1 :≡ {(:≡ {(bb,,aa) | () | (aa,,bb))RR}}..E.g.E.g., , <<−1−1 = {( = {(bb,,aa) | ) | aa<<bb} = {(} = {(bb,,aa) | ) | bb>>aa} = } = >>..•E.g.E.g., if , if RR:People x Foods is defined by :People x Foods is defined by a R ba R b  aa eatseats bb, then: , then: bb RR−1−1 aa  bb is eaten byis eaten by aa. (Passive voice.). (Passive voice.)01/14/19 5Relations on a Set•A (binary) relation from a set A (binary) relation from a set AA to itself is to itself is called a relation called a relation onon the set the set AA..•E.g.E.g., the “, the “<<” relation from earlier was ” relation from earlier was defined as a relation defined as a relation onon the set the set NN of natural of natural numbers.numbers.01/14/19 6Reflexivity and relatives•A relation A relation RR on on AA is is reflexivereflexive iff iff aaA(aRa)A(aRa)..–E.g.E.g., the relation , the relation ≥≥ :≡ {( :≡ {(aa,,bb) | ) | aa≥≥bb}} is reflexive. is reflexive.•RR is is irreflexiveirreflexive iff iff aaA(A(aRa)aRa)•Note “Note “irreflexiveirreflexive” does ” does NOTNOT mean “ mean “notnot reflexivereflexive”, which is just ”, which is just aaA(aRa)A(aRa)..01/14/19 7Reflexivity and relatives•Theorem:Theorem: A relation A relation RR is is irreflexiveirreflexive iff its iff its complementarycomplementary relation relation RR is reflexive. is reflexive.–Example: Example: << is irreflexive; ≥ is reflexive. is irreflexive; ≥ is reflexive.–Proof: trivialProof: trivial01/14/19 8•Can you think ofCan you think of–Reflexive relationsReflexive relations–Irreflexive relationsIrreflexive relationsInvolving numbers, propositions or sets?Involving numbers, propositions or sets?01/14/19 9Some examples•Reflexive: Reflexive: =, `have same cardinality’, =, `have same cardinality’, <=, >=, <=, >=, , , , etc., etc.•Irreflexive:Irreflexive:<, >, `have different cardinality’, <, >, `have different cardinality’, 01/14/19 10Symmetry & relatives•A binary relation A binary relation RR on on AA is is symmetricsymmetric iff iff a,b((a,b((aa,,bb))RR ↔ (↔ (bb,,aa))R)R)..–E.g.E.g., , == (equality) is symmetric. (equality) is symmetric. << is not. is not.–““is married to” is symmetric, “likes” is not.is married to” is symmetric, “likes” is not.•A binary relation A binary relation RR is is asymmetricasymmetric if if aa,,bb((((aa,,bb))RR → (→ (bb,,aa))R)R)..–Examples: <Examples: < is asymmetric, “likes” is not. is asymmetric, “likes” is not.01/14/19 11Some direct consequencesTheorems:Theorems:1.1.R is symmetric iff R is symmetric iff RR = = RR−1−1,, 2.2.R is asymmetric iff R is asymmetric iff RRRR−1−1 is empty is empty. .01/14/19 12Symmetry & relatives1. R is symmetric iff 1. R is symmetric iff RR = = RR−1−1Suppose R is symmetric. Then Suppose R is symmetric. Then (x,y) (x,y)  R R  (y,x) (y,x)  R R  (x,y) (x,y)  RR−1−1 Suppose RR = = RR−1 −1 Then Then (x,y) (x,y)  R R  (x,y) (x,y)  RR−1 −1  (y,x) (y,x)  R R01/14/19 13Symmetry & relatives2. R is asymmetric iff 2. R is asymmetric iff RRRR−1−1 is empty is empty..(Straightforward application of the (Straightforward application of the definitions of asymmetry and definitions of asymmetry and RR−1−1) )01/14/19 14Antisymmetry•Consider the relation Consider the relation xxyy–It is not symmetric. (For instance, It is not symmetric. (For instance, 5566 but not but not 6655))–It is not asymmetric. (For instance, It is not asymmetric. (For instance, 5 5 55))–You might say it’s You might say it’s nearlynearly symmetric, since the symmetric, since the only symmetries occur when only symmetries occur when