CompSci 102 © Michael Frank15.1Today’s topics••RelationsRelations––Kinds of relationsKinds of relations––n-ary n-ary relationsrelations––Representations of relationsRepresentations of relations••Reading: Sections 7.1-7.3Reading: Sections 7.1-7.3••UpcomingUpcoming––MinesweeperMinesweeperCompSci 102 © Michael Frank15.2Binary Relations••Let Let AA, , BB be any sets. A be any sets. A binary relationbinary relation RR from from AA to to BB,,written (with signature) written (with signature) RR::AABB,, or or RR::AA,,BB, , is (can beis (can beidentified with) a subset of the set identified with) a subset of the set AABB..––E.g.E.g., let , let : : NN NN : : {({(nn,,mm)) | | n n < < mm}}••The notation The notation a Ra R bb or or aRbaRb means that means that ((aa,,bb))RR..––E.g.E.g., , a a bb means means ((aa,,bb)) ••If If aRbaRb we may say we may say ““aa is related to is related to bb (by relation (by relation RR))””,,––or just or just ““aa relates to relates to bb (under relation (under relation RR))””..••A binary relation A binary relation R R corresponds to a predicate functioncorresponds to a predicate functionPPRR::AABB{{TT,,FF}} defined over the 2 sets defined over the 2 sets AA,,BB;;––e.g.e.g., predicate , predicate ““eatseats”” : : {({(aa,,bb)| organism )| organism a a eats food eats food bb}}CompSci 102 © Michael Frank15.3Complementary Relations••Let Let RR::AA,,BB be any binary relation. be any binary relation.••Then, Then, RR::AABB, the , the complementcomplement of of RR, is the, is thebinary relation defined bybinary relation defined byRR : : {({(aa,,bb) | () | (aa,,bb))RR} = (} = (AABB) ) RR••Note this is just Note this is just RR if the universe of if the universe ofdiscourse is discourse is UU = = AABB; thus the name; thus the namecomplement.complement.••Note the complement of Note the complement of RR is is RR..Example: << = {( = {(aa,,bb) | () | (aa,,bb))<<} = {(} = {(aa,,bb) | ) | ¬¬aa<<bb} = } = CompSci 102 © Michael Frank15.4Inverse Relations••Any binary relation Any binary relation RR::AABB has an has an inverseinverserelation relation RR11::BBAA, defined by, defined byRR11 :: {({(bb,,aa) | () | (aa,,bb))RR}}..E.g.E.g., , <<11 = {( = {(bb,,aa) | ) | aa<<bb} = {(} = {(bb,,aa) | ) | bb>>aa} = } = >>..••E.g.E.g., if , if RR:People:People F Foods is defined byoods is defined by a R ba R b aa eatseats bb, then:, then: bb RR11 aa bb is eaten byis eaten by aa. (Passive voice.). (Passive voice.)CompSci 102 © Michael Frank15.5Relations on a Set••A (binary) relation from a set A (binary) relation from a set AA to itself is to itself iscalled a relation called a relation onon the set the set AA..••E.g.E.g., the , the ““”” relation from earlier was relation from earlier wasdefined as a relation defined as a relation onon the set the set NN of natural of naturalnumbers.numbers.••The (binary) The (binary) identity relation identity relation IIAA on a set on a set AAis the set is the set {({(aa,,aa)|)|aaAA}}..CompSci 102 © Michael Frank15.6Reflexivity••A relation A relation RR on on AA is is reflexivereflexive if if aaAA,, aRaaRa..––E.g.E.g., the relation , the relation : : {({(aa,,bb) | ) | aabb}} is reflexive. is reflexive.••A relation A relation RR is is irreflexiveirreflexive iff iff its its complementarycomplementary relation relation RRis reflexive.is reflexive.––Example: Example: << is is irreflexiveirreflexive, because , because is reflexive. is reflexive.––Note Note ““irreflexiveirreflexive”” does does NOTNOT mean mean ““notnot reflexivereflexive””!!••For example: the relation For example: the relation ““likeslikes”” between people is not reflexive, but between people is not reflexive, butit is not it is not irreflexive irreflexive either.either.––Since not everyone likes themselves, but not everyone Since not everyone likes themselves, but not everyone dislikesdislikesthemselves either!themselves either!CompSci 102 © Michael Frank15.7Symmetry & Antisymmetry••A binary relation A binary relation RR on on AA is is symmetricsymmetric iffiffRR = = RR11,, that is, if that is, if ((aa,,bb))RR ((bb,,aa))RR..––E.g.E.g., , == (equality) is symmetric. (equality) is symmetric. << is not. is not.––““is married tois married to”” is symmetric, is symmetric, ““likeslikes”” is not. is not.••A binary relation A binary relation RR is is antisymmetricantisymmetric if ifaabb, (, (aa,,bb))RR ((bb,,aa))RR..––Examples: <Examples: < is is antisymmetricantisymmetric, , ““likeslikes”” is not. is not.––Exercise:Exercise: prove this definition of prove this definition of antisymmetricantisymmetric is isequivalent to the statement that equivalent to the statement that RRRR11 IIAA..CompSci 102 © Michael Frank15.8Transitivity••A relation A relation RR is is transitivetransitive iff iff (for all (for all aa,,bb,,cc))((aa,,bb))RR ( (bb,,cc))RR ((aa,,cc))RR..••A relation is A relation is intransitiveintransitive iff iff it is notit is nottransitive.transitive.••Some examples:Some examples:––““is an ancestor ofis an ancestor of”” is transitive. is transitive.––““likeslikes”” between people is intransitive. between people is intransitive.––““is located within 1 mile ofis located within 1 mile of”” is is…… ? ?CompSci 102 © Michael Frank15.9Totality••A relation A relation RR::AABB is is totaltotal if for every if for every aaAA,,there is at least one there is at least one bbBB such that such that ((aa,,bb))RR..••If If RR is not total, then it is called is not total, then it is called strictlystrictlypartialpartial..••A A partial relationpartial relation is a relation that is a relation that mightmight be bestrictly partial. (Or, it might be total.)strictly partial. (Or, it might be total.)––In other words, In other words, all all relations are consideredrelations are
View Full Document
Unlocking...