离散数学析 第3章集合与关系——关系.ppt

文档介绍：。它与集合论、数理逻辑、组合学、图论和布尔代数都有密切的联系。关系是日常生活以及数学中的一个基本概念,例如:兄弟关系,师生关系、位置关系、大小关系、等于关系、包含关系等。另外,关系理论还广泛用于计算机科学技术,如计算机程序的输入、输出关系;数据库的数据特性关系;数据结构本身就是一个关系等。在某种意义下,关系是有联系的一些对象相互之间的各种比较行为。,B为两个非空集合,称A×B的任何子集R为从A到B的二元关系,简称关系(Relation)。如A=B,则称R为A上的二元关系。 ,当R=Φ时,称R为空关系(emptyrelation);当R=A×B时,则称R为全关系(TotalRelation)。={a,b},B={c,d},试写出从A到B的所有不同关系。解因为A={a,b},B={c,d},所以A×B={<a,c>,<a,d>,<b,c>,<b,d>}。于是A×B的所有不同子集为:0–元子集:Φ;1–元子集:{<a,c>},{<a,d>},{<b,c>},{<b,d>};2–元子集:{<a,c>,<a,d>},{<a,c>,<b,c>},(续){<a,c>,<b,d>},{<a,d>,<b,d>},{<a,d>,<b,d>},{<b,c>,<b,d>};3–元子集:{<a,c>,<a,d>,<b,c>},{<a,c>,<a,d>,<b,d>},{<a,c>,<b,c>,<b,d>},{<a,d>,<b,c>,<b,d>};4–元子集:{<a,c>,<a,d>,<b,c>,<b,d>}。注意当集合A,B都是有限集时,A×B共有2|A|•|B|个不同的子集,即,从A到B的不同关系共有2|A|•|B|个。A到B的二元关系A到B的二元关系:是AB的任意子集。R是A到B的二元关系RABRP(AB)若|A|=m,|B|=n,则|AB|=mn,故|P(AB)|=2mn即A到B不同的二元关系共有2mn个A上的二元关系A上的二元关系:是AA的任意子集R是A上的二元关系RAARP(AA)若|A|=m,则|AA|=m2,故|P(AA)|=即A上不同的二元关系共有个A上的二元关系(例1)例:设A={a1,a2},则A上的二元关系共有16个:R1=,R2={<a1,a1>},R3={<a1,a2>},R4={<a2,a1>},R5={<a2,a2>},