第04章离散.ppt

第04章离散
第1页，共74页，2022年，5月20日，13点44分，星期五
二元关系
二元关系，这里是指集合中两个元素之间的关系。
1．基本概念
给定任意集合A和B，若RAB，则称R为从A到B上关系R是对称的
(x)(y)(x,yAxRy→yRx)
该定义表明了，在表示对称的关系R的有序对集合中，若有有序对<x, y>，则必定还会有有序对<y, x>。
第13页，共74页，2022年，5月20日，13点44分，星期五
在全集U的所有子集的集合中，相等关系是对称的，包含关系和真包含关系都不是对称的；在整数集合Z中，相等关系=是对称的，而关系≤和<都不是对称的。
第14页，共74页，2022年，5月20日，13点44分，星期五
令RAA，对于A中每个x和y，若xRy且yRx，则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>。
第15页，共74页，2022年，5月20日，13点44分，星期五
在全集U的所有子集的集合中，相等关系=，包含关系和真包含关系都是反对称的，但全域关系不是反对称的。在整数集合Z中，=，≤和<也都是反对称的。
可见，有些关系既是对称的又是反对称的，如相等关系；有些关系是对称的但不是反对称的，如Z中的“绝对值相等”；有些关系是反对称的，但不是对称的，如Z中的≤和<。还有的关系既不是对称的又不是反对称的，例如，A={a, c, b>,中R={<a, b>,<a, c>,<c, a>}。
第16页，共74页，2022年，5月20日，13点44分，星期五
令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>。
第17页，共74页，2022年，5月20日，13点44分，星期五
显然，上述提到的关系中，，=和≤，<，=都是传递的；在直线的集合中，平行关系是传递的，但垂直关系不是传递的。
通过上面几个实例，看出：
①若A上关系R是自反的，则MR中主对角线上元素全为1，而GR中每个结点有有向环；反之亦然。
第18页，共74页，2022年，5月20日，13点44分，星期五
②若A上关系R是反自反的，则MR中主对角线上元素全为0，而GR中每个结点无有向环；反之亦然。
③若A上关系R是对称的，则MR是对称矩阵，而GR中任何两结点若有弧必成对出现；反之亦然。
第19页，共74页，2022年，5月20日，13点44分，星期五
④若A上关系R是反对称的，则MR中以主对角线为对称元素不能同时为1，而GR中若两结点间有弧不能成对出现；反之亦然。
⑤若A上关系R是传递的，则MR中若rij=rjk=1，则rik=1，而GR中若有弧<x, y>和<y, z>则必有弧<x, z>；反之亦然。上述是正确的，但不易从MR和GR中判定关系R传递性。
第20页，共74页，2022年，5月20日，13点44分，星期五
此外，还有：
①任何集合上的相等关系=是自反的、对称的，反对称的和传递的，但不是反自反的。
②整数集合Z中，关系≤是自反的、反对称的和传递的，但不是反自反的和对称的。关系<是反自反的，反对称的和传递的，但不是自反的和对称的。
第21页，共74页，2022年，5月20日，13点44分，星期五
③非空集合上的空关系是反自反的，对称的，反对称的和传递的，但不是自反的。空集合上的空关系则是自反的，反自反的，对称的，反对称的和传递的。
④非空集合上的全域关系是自反的，对称的和传递的，但不是反自反的和反对称的。
第22页，共74页，2022年，5月20日，13点44分，星期五
下面给出一个定理，以结束本小节。
设RAA，若R是反自反的和传递的，则R是反对称的。
第23页，共74页，2022年，5月20日，13点44分，星期五
关系运算
前已述及，关系是有序对的集合，因此可以对关系进行运算。若R, SAB，则R∪S，R∩S，R’，R-SAB。
第24页，共74页，2022年，5月20日，13点44分，星期五
1．复合运算
设R是从A到B的关系，S是从B到C的关系。经过对R和