西北师范大学《离散数学》课件-第4章关系.ppt

第四章 关系本章学习目标：本章学习目标： 在上一章讨论了集合及集合的运算，在这一章中我们将要研究集合内元素间的关系，这就是“关系”关系是一个很重要的数学基本概念，它在计算机科学中的许多方面如数据结构、数据库、情报检索、算法分析等都有很多应用本章主要讨论二元关系理论通过本章学习，读者应该掌握以下内容： （1）关系的表示 （2）关系的性质和运算 （3）等价关系和集合的划分 （4）偏序关系 西北师范大学离散数学第四章 关系4.1 序偶与笛卡儿积 4.2 二元关系及其表示4.3 关系的运算4.4 关系的性质4.5 关系的闭包4.6 等价关系与集合的划分4.7 相容关系4.8 偏序关系第四章 关系4.1 序偶与笛卡儿积 4.1.1 有序n元组 定义定义4.14.1 由两个固定次序的个体x，y组成的序列称为序偶，记为，其中x，y分别称为序偶的第一、二分量（或称第一、二元素）定义定义4.24.2 两序偶，是相等的，当且仅当a=c，b=d；记作=第四章 关系4.1 序偶与笛卡儿积 4.1.2 笛卡儿积的概念 定义定义4.34.3 给定两个集合A和B，如果序偶的第一个分量是A中的一个元素，第二个分量是B中的一个元素，则所有这种序偶的集合称为集合A和B的笛卡儿积，简称为卡氏积，记为AB，即AB=xAyB。

第四章 关系4.1 序偶与笛卡儿积 4.1.2 笛卡儿积的概念 例4.1 （1）A=a，b，B=c，d，求AB2）A=a，b，B=c，d，求BA3）A=a，b，B=1，2，C=c，求（AB）C和A（BC）第四章 关系4.1 序偶与笛卡儿积 4.1.2 笛卡儿积的概念 解 （1）AB=a，bc，d=， 2）BA=c，da，b=，3）（AB）=a，b1，2=， 第四章 关系4.1 序偶与笛卡儿积 4.1.2 笛卡儿积的概念 （AB）C=，c，c，c， ，c =， BC=1，2c=， A（BC）=a，a，b， b，第四章 关系4.1 序偶与笛卡儿积 4.1.3 笛卡儿积的性质 定理定理4.1 设A，B，C为任意3个集合，则有（1）A（BC）=（AB）（AC）（2）A（BC）=（AB）（AC）（3）（AB）C=（AC）（BC）（4）（AB）C=（AC）（BC）第四章 关系4.1 序偶与笛卡儿积 4.1.3 笛卡儿积的性质 定理定理4.3 设A，B，C，D为四个非空集合，则ABCD的充分必要条件是：AC且BD定理定理4.2 设A，B，C为任意3个集合，且C，则有AB （AC BC）（CA CB） 第四章 关系4.1 序偶与笛卡儿积 4.1.3 笛卡儿积的性质 反之，如果AC且BD，设任意xC和yB，有 AB xAyB xCyD xCyD CD所以，ABCD。

第四章 关系4.2 二元关系及其表示4.2.1 二元关系的概念 定义定义4 4.5 5 设R是二元关系，由R的所有x组成的集合称为R的定义域，记作D（R），即D（R）=xy（yBR）由R的所有y组成的集合称为R的值域，记作R（R），即R（R）=yx（xAR） 定义定义4 4.4 4 设A，B是两个集合，R是笛卡儿积AB的任一子集，则称R为从A到B的一个二元关系，简称关系特别当A=B时，则称R为A上的二元关系（或A上的关系） 第四章 关系4.2 二元关系及其表示4.2.1 二元关系的概念 例4.3 设A=1，3，5，7，R是A上的二元关系，当a，bA且ab时，R，求R和它的定义域和值域解 R=，D（R）=1，3，5，R（R）=3，5，7例4.2 设A=a，b，c，d，e，B=1，2，3，R=，求R的定义域和值域解 D（R）=a，b，c，R（R）=2，3 第四章 关系4.2 二元关系及其表示4.2.1 二元关系的概念 定定义义4.64.6 设IA为集合A上的二元关系，且满足IA=xA，则称IA为集合A上的恒等关系 第四章 关系4.2 二元关系及其表示4.2.2 二元关系的表示 1关系矩阵表示法 设给定集合A=a1，a2，an，集合B=b1，b2，bm，R为从A到B的一个二元关系，构造一个nm矩阵。

用集合A的元素标注矩阵的行，用集合B的元素标注矩阵的列，对于aA和bB，若R，则在行a和列b交叉处标1，否则标0这样得到的矩阵称为R的关系矩阵第四章 关系4.2 二元关系及其表示4.2.2 二元关系的表示 2关系图表示法 有限集的二元关系可以用有向图来表示，设集合A=a1，a2，an，集合B=b1，b2，bm，R为从A到B的一个二元关系，首先在平面上作出n个结点分别记作a1，a2，an，然后另外作出m个结点分别记作b1，b2，bm，如果aA、bB且R，则自结点a到结点b作出一条有向弧，其箭头指向b如果R，则结点a和结点b之间没有线段联结用这种方法得到的图称为R的关系图第四章 关系4.2 二元关系及其表示4.2.1 二元关系的概念 解 R的关系图，如图所示：例4.8 A=1，2，3，4，B=5，6，7，R=，作出R的关系图第四章 关系4.2 二元关系及其表示4.2.1 二元关系的概念 解 A上的关系图如图所示例4.9 设A=1，2，3，4，R=，画出A上的关系图第四章 关系4.3 关系的运算关系的运算 4.3.1 关系的交、并、差、补运算 例4.10 设X=1，2，3，4，5，若A=x与y的差能被2整除，B=x与y的差为正且能被3整除，求AB，AB，A-B，B-A，A。

第四章 关系4.3 关系的运算关系的运算 4.3.1 关系的交、并、差、补运算 解 A=，B=，AB=，AB=A-B=，B-A=，A=1，2，3，4，51，2，3，4，5-，=，第四章 关系4.3 关系的运算关系的运算 4.3.2 关系的复合运算 定义定义4.7 设R是从集合A到集合B上的二元关系，S是从集合B到集合C上的二元关系，则RS称为R和S的复合关系，表示为RS=xAzCy（yBRS第四章 关系4.3 关系的运算关系的运算 4.3.2 关系的复合运算 例4.10 （1）A=1，2，3，4，B=3，5，7，C=1，2，3，R=，S=，RS=，如图所示：第四章 关系4.3 关系的运算关系的运算 4.3.2 关系的复合运算 （2）设R，S都是A上的关系，A=1，2，3，4R=，S=，即S为A上的恒等关系，则RS=SR=R如图所示： （3）设R是A上的关系，S为A上的空关系，即S=，则RS=SR=第四章 关系4.3 关系的运算关系的运算 4.3.2 关系的复合运算 定理定理4.4 设R是从A到B的关系，S是从B到C的关系，其中A=a1，a2，am，B=b1，b2，bn，C=c1，c2，ct。

而MR，MS和MR S分别为关系R，S和RS的关系矩阵，则有MRS=MRMS第四章 关系4.3 关系的运算关系的运算 4.3.2 关系的复合运算 定理定理4.5 设R是从集合A到集合B上的二元关系，S是从集合B到集合C上的二元关系，T是从集合C到集合D上的二元关系，则有：（1）R（ST）=RSRT（2）R（ST）RSRT（3）（RS）T= RTST（4）（RS）TRTST第四章 关系4.3 关系的运算关系的运算 4.3.2 关系的复合运算 定理定理4.6 设R是从A到B的关系，S是从B到C的关系，T是从C到D 的关系，则有R（ST）=（RS）T定义定义4.8 设R是从A上的关系，n为整数，关系R的n次幂定义如下：（1）R0=xA=IA；（2）Rn+1=RnR从关系R的n次幂定义，可得出下面的结论：（1）Rn+m=RnRm；（2）（Rn）m=Rnm第四章 关系4.3 关系的运算关系的运算 4.3.3 关系的逆运算 定义定义4.9 设R是从集合A到集合B的二元关系，如果将R中每序偶的第一元素和第二元素的顺序互换，所得到的集合称为R的逆关系，记为R1，即R1=R定理定理4.7 设R，S和T都是从A到B的二元关系，则下列各式成立：（1）（R）1）1=R（2）（RS）1=R1S1（3）（RS）1=R1S1（4）（AB）1 =BA（5）（R）1= （R1）（这里R=AB-R）（6）（R-S）1=R1-S1第四章 关系4.3 关系的运算关系的运算 4.3.3 关系的逆运算 定理定理4.8 设R是从A到B的二元关系，S是从B到C的二元关系，则下面的式子成立：（RS）1=S1R1证明 （RS）1RS y（yBRS） y（yBS1R1） S1R1。

所以，（RS）1=S1R1第四章 关系4.4 关系的性质4.4.1 自反性和反自反性 定义定义4.10 设R是集合A上的二元关系，如果对于每个xA，都有R，则称二元关系R是自反的R在A上是自反的 x（xAR）定义定义4.11 设R是集合A上的二元关系，如果对于每个xA，都有 R，则称二元关系R是反自反的R在A上是反自反的 x（xA R）第四章 关系4.4 关系的性质4.4.2 对称性和反对称性 定义定义4.12 设R是集合A上的二元关系，如果对于每个x，yA， 当R，就有R，则称二元关系R是对称的R在A上是对称的x y（xAyARR） 定义定义4.13 设R是集合A上的二元关系，如果对于每个x，yA，当R和R时，必有x=y，则称二元关系R是反对称的 第四章 关系4.4 关系的性质4.4.3 传递性 定义定义4.14 设R是集合A上的二元关系，如果对于任意x，y，zA，当R，R，就有R，则称二元关系R在A上是传递的R在A上是传递的x y z（xAyAzARRR）第四章 关系4.4 关系的性质4.4.3 传递性 例4.13 设A=a，b，c，R，S，T是A上的二元关系，其中R=，S=，T=说明R，S，T是否为A上的传递关系。

解 根据传递性的定义知，R和T是A上的传递关系，S不是A上的传递关系，因为R，R，但R第四章 关系4.4 关系的性质4.4.4 关系性质的判定 1自反性的判定方法 定理定理4.9 设R是A上的二元关系，则R在A上是自反的当且仅当IA R 证明 先证必要性任取，由于R在A上是自反的，则有IAx，yAx=yR从而证明了IA R再证充分性任取xA，有xA IAR因此，R在A上是自反的 第四章 关系4.4 关系的性质4.4.4 关系性质的判定 1自反性的判定方法R的关系矩阵为： 第四章 关系4.4 关系的性质4.4.4 关系性质的判定 1自反性的判定方法R的关系图为： 第四章 关系4.4 关系的性质4.4.4 关系性质的判定 2反自反性的判定方法 定理定理4.10 设R是A上的二元关系，则R在A上是反自反的当且仅当IAR=例4.15 设集合A=a，b，c，d，A上的二元关系R=，讨论R的性质，写出R的关系矩阵，画出R的关系图解 由于，R，即IAR=，所以R是反自反的 第四章 关系4.4 关系的性质4.4.4 关系性质的判定 2反自反性的判定方法 R的关系矩阵为： 第四章 关系4.4 关系的性质4.4.4 关系性质的判定 2反自反性的判定方法 R的关系图为： 第四章 关系4.4 关系的性质4.4.4 关系性质的判定 3对称性的判定方法定理定理4.114.11 设R是A上的二元关系，则R在A上是对称的当且仅当R=R1。

例4.16 设集合A=a，b，c，d，A上的二元关系R=，讨论R的性质，写出R的关系矩阵，画出R的关系图解 因为R，所以R不是自反的由于R，即IAR，所以R不是反自反的R1=，R=R1，由上面的定理可知，关系R是对称的第四章 关系4.4 关系的性质4.4.4 关系性质的判定 3对称性的判定方法R的关系矩阵为： 第四章 关系4.4 关系的性质4.4.4 关系性质的判定 3对称性的判定方法R的关系图为： 第四章 关系4.4 关系的性质4.4.4 关系性质的判定 4反对称性的判定方法 定理定理4.124.12 设R是A上的二元关系，则R在A上是反对称的当且仅当RR1IA ：例4.17 设集合A=a，b，c，d，A上的二元关系R=，讨论R的性质，写出R的关系矩阵，画出R的关系图。