08ab逆关系复合关系闭包.ppt

复合关系composite relation逆关系inverse relation闭包closure 存 疑 解 答 存 疑 解 答 重点回顾 重点回顾：关系的性质 重点回顾：关系的性质 复合关系的性质 定义复合关系 课本练习 定义逆关系 逆关系的性质 有关定理 课本练习 关系的闭包 闭包的讨论 本节总结 课 后 任 务 * * 第十四讲 A、B、C、D为任意非空集合， 则 (A∩B) ? (C∩D) = (A?C)∩(B?D) 分析： (A∩B) ? (C∩D) = (A?C)∩(B?D)∩(B?C)∩(A?D) (A?C)∩(B?D) = (B?C)∩(A?D) ？ 如何证明？ 课本99 习题（1） │A∪B∪C│=│A│+│B│+│C| -│A∩B│-│A∩C│-B∩C│+│A∩B∩C│ 故： |A∩B|+|B∩C|+|A∩C| =│A│+│B│+│C|+│A∩B∩C│- │A∪B∪C│ = 38+20+15+3-58 =18 同时参加两队的队员为 18-3*3 = 9（个） 序偶(ordered pair)：有序的偶对 序偶相等的定义： x,y=u,v ? x=u 且 y=v 集合(set)A、B的笛卡儿乘积(Cartesian product) A?B = ?x,y?(x?A)∧(y?B)? 性质：A?B ? B?A 讨论非空集合A上的关系R（即R?A?A） 自反性： ?a?A, ?a, a??R 反自反性：?a?A, ?a, a??R 对称性： ?a, b ?A, 若?a, b??R，则?b, a??R 反对称性：若a?b，则?a,b??R或?b,a??R ； 传递性： ?a,b,c?A, 若?a,b??R且?b,c??R， 则?a,c??R 讨论非空集合A上的关系R（即R?A?A） 自反性：关系图中每个点都有环； 反自反性：关系图中每个点都没环； 对称性：关系图中任意两个不同的点之间要么没有边，要么有双向边； 反对称性：关系图任意两个不同的点之间要么没有边，要么只有单向边； 传递性：关系图中任意两个点之间若经过第三点有路接通，则必有直达边； 复合关系的关系矩阵： 由两个关系矩阵的逻辑乘（用0、1表示零和非零值）得到。见课本P116例题3。 复合关系的关系图： 两点间有一点，接通这两点，省去中间点集，得到复合关系的关系图。 复合关系是不可交换的（没有公共域） 复合关系是可结合的。 设R是A到B的关系，S是B到C的关系，则R?S称为R和S的复合关系，表示为 R?S = { x,z | x?A∧z?C∧ (?y)(y?B∧x,y?R∧y,z?S)} 见课本P114例题1、例题2 课本P118（1） 补充 (e): 若R1和R2是反对称的，则R1?R2也是反对称的 结论： 关系的性质（自反、反自反、对称、反对称、传递）在关系复合之后，只保持了自反性。 设R是A到B的关系， 将R中每一序偶元素顺序互换，得到的集合称为关系R的逆关系，表示为 Rc = { y,x | x,y?R} 可见， Rc是B到A的关系。 逆关系保持了关系的性质 ： 即保持了原关系的自反性、反自反性、对称性、反对称性、传递性（若原关系有这些性质的话）。见课本P119习题（5） 逆关系的矩阵： 原关系矩阵转置之后得到逆关系的矩阵 逆关系的图： 把弧的方向反转，得到逆关系的图 证明两个关系相等，实质上是证明两个集合（元素是序偶）相等 (R1∪R2)c = R1c∪R2c (R1∩R2)c = R1c∩R2c (R1-R2)c = R1c-R2c (A?B)c = B?A ( R1?R2)c = R2c ?R1c (R1?R2) ?R3 = R1? (R2 ?R3) R是对称的 ? R= Rc R是反对称的 ? R∩Rc ?Ix 课本P119 关系R的自反（对称、传递）闭包： 是指包含R的、而且是自反的、最小的自反（对称、传递）关系 严格的定义：见课本P119 如果R本身是自反的（对称的、传递的），则其自反的（对称的、传递的）闭包就是R 自反闭包：reflexitive closure 对称闭包：symmetric closure 传递闭包：transitive closure 自反闭包 r ?R? ? R∪Ix（R是集合X上的关系） 对称闭包 s ?R? ? R∪Rc 传递闭包 t (R) = R∪R2∪…∪Rn∪… 若 |X| = n，则只需前m个（m ? n）关系的并 ? rs ?R? ? sr (R)