第04章离散.ppt

第04章离散
本讲稿第一页，共七十四页
二元关系
二元关系，这里是指集合中两个元素之间的关系。
1．基本概念
给定任意集合A和B，若RAB，则称R为从A到B的二元关系，特别在A=B时，称R为A上x=y，称R是反对称的，即
A上关系R是反对称的
(x)(y)(x,yAxRyyRx→x=y)
该定义表明了，在表示反对称关系R的有序对集合中，若存在有序对<x, y>和<y, x>，则必定是x=y。或者说，在R中若有有序对<x, y>，则除非x=y，否则必定不会出现<y, x>。
本讲稿第十五页，共七十四页
在全集U的所有子集的集合中，相等关系=，包含关系和真包含关系都是反对称的，但全域关系不是反对称的。在整数集合Z中，=，≤和<也都是反对称的。
可见，有些关系既是对称的又是反对称的，如相等关系；有些关系是对称的但不是反对称的，如Z中的“绝对值相等”；有些关系是反对称的，但不是对称的，如Z中的≤和<。还有的关系既不是对称的又不是反对称的，例如，A={a, c, b>,中R={<a, b>,<a, c>,<c, a>}。
本讲稿第十六页，共七十四页
令RAA，对于A中每个x, y, z，若xRy且yRx，则xRz，称R是传递的，即
A上关系R是传递的
(x)(y)(z)(x,y,zAxRyyRz→xRz)
该定义表明了，在表示可传递关系R的有序对集合中，若有有序对<x, y>和<y, z>，则必有有序对<x, z>。
本讲稿第十七页，共七十四页
显然，上述提到的关系中，，=和≤，<，=都是传递的；在直线的集合中，平行关系是传递的，但垂直关系不是传递的。
通过上面几个实例，看出：
①若A上关系R是自反的，则MR中主对角线上元素全为1，而GR中每个结点有有向环；反之亦然。
本讲稿第十八页，共七十四页
②若A上关系R是反自反的，则MR中主对角线上元素全为0，而GR中每个结点无有向环；反之亦然。
③若A上关系R是对称的，则MR是对称矩阵，而GR中任何两结点若有弧必成对出现；反之亦然。
本讲稿第十九页，共七十四页
④若A上关系R是反对称的，则MR中以主对角线为对称元素不能同时为1，而GR中若两结点间有弧不能成对出现；反之亦然。
⑤若A上关系R是传递的，则MR中若rij=rjk=1，则rik=1，而GR中若有弧<x, y>和<y, z>则必有弧<x, z>；反之亦然。上述是正确的，但不易从MR和GR中判定关系R传递性。
本讲稿第二十页，共七十四页
此外，还有：
①任何集合上的相等关系=是自反的、对称的，反对称的和传递的，但不是反自反的。
②整数集合Z中，关系≤是自反的、反对称的和传递的，但不是反自反的和对称的。关系<是反自反的，反对称的和传递的，但不是自反的和对称的。
本讲稿第二十一页，共七十四页
③非空集合上的空关系是反自反的，对称的，反对称的和传递的，但不是自反的。空集合上的空关系则是自反的，反自反的，对称的，反对称的和传递的。
④非空集合上的全域关系是自反的，对称的和传递的，但不是反自反的和反对称的。
本讲稿第二十二页，共七十四页
下面给出一个定理，以结束本小节。
设RAA，若R是反自反的和传递的，则R是反对称的。
本讲稿第二十三页，共七十四页
关系运算
前已述及，关系是有序对的集合，因此可以对关系进行运算。若R, SAB，则R∪S，R∩S，R’，R-SAB。
本讲稿第二十四页，共七十四页
1．复合运算
设R是从A到B的关系，S是从B到C的关系。经过对R和S实行复合（或合成）运算“”，得到了一个新的从A到C的关系，记为RS，也称RS为关系R和S的复合（或合成）关系；或称RS为R和S的复合运算。形式地表为：
RS={<a, c>|(b)(bBaRbbSc)}
本讲稿第二十五页，共七十四页
设RAA，则RIA=IAR=R
若RAB，S,TBC，WCD，则
① R(S∪T)=RS∪RT
② R(S∩T)  RS∩RT
③ (S∪T)W=SW∪TW
④ (S∩T)W  SW∩TW
本讲稿第二十六页，共七十四页
若RAB，SBC，TCD，则
(RS)T=R(ST)
复合运算是可结合的，但不是可交换的。望读者举例说明。
本讲稿第二十七页，共七十四页
2．幂运算
设R是集合A上的二元关系，nN，R的n次幂记为Rn，定义为：
(1) R0=IA
(2) Rn+1=RnR