《《离散数学(贾振华主编)》电子教案 第四章 关系》由会员分享，可在线阅读，更多相关《《离散数学(贾振华主编)》电子教案 第四章 关系（71页珍藏版）》请在金锄头文库上搜索。
1、第四章 关系,本章学习目标： 在上一章讨论了集合及集合的运算，在这一章中我们将要研究集合内元素间的关系，这就是“关系”。关系是一个很重要的数学基本概念，它在计算机科学中的许多方面如数据结构、数据库、情报检索、算法分析等都有很多应用。本章主要讨论二元关系理论。通过本章学习，读者应该掌握以下内容： （1）关系的表示 （2）关系的性质和运算 （3）等价关系和集合的划分 （4）偏序关系,第四章 关系,4.1 序偶与笛卡儿积 4.2 二元关系及其表示 4.3 关系的运算 4.4 关系的性质 4.5 关系的闭包 4.6 等价关系与集合的划分 4.7 相容关系 4.8 偏序关系,第四章 关系,4.1 序偶与
2、笛卡儿积 4.1.1 有序n元组,定义4.1 由两个固定次序的个体x，y组成的序列称为序偶， 记为，其中x，y分别称为序偶的第一、二分量（或称第 一、二元素）。,定义4.2 两序偶，是相等的，当且仅当a=c， b=d；记作=。,第四章 关系,4.1 序偶与笛卡儿积 4.1.2 笛卡儿积的概念,定义4.3 给定两个集合A和B，如果序偶的第一个分量是A中的 一个元素，第二个分量是B中的一个元素，则所有这种序偶的集 合称为集合A和B的笛卡儿积，简称为卡氏积，记为AB，即 AB=xAyB。,第四章 关系,4.1 序偶与笛卡儿积 4.1.2 笛卡儿积的概念,例4.1 （1）A=a，b，B=c，d，求AB
3、。 （2）A=a，b，B=c，d，求BA。 （3）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）=， 。,第四章 关系,4.1 序偶与笛卡儿积 4.1.3 笛卡儿积的性质,定理4.1 设A，B，C为任意3个集合，则有 （1）A（BC）=（AB）（AC） （2）A（BC）
4、=（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.5 设R是二元关系
5、，由R的所有x组成的集合称 为R的定义域，记作D（R），即D（R）=xy（yBR）。由R的所有y组成的集合称为R的值域，记作 R（R），即R（R）=yx（xAR）。,定义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且aR，求R和它的定义域和值域。 解 R=， D（R）=1，3，5，R（R）=3，5，7。,例4.2 设A=a，b，c，d，e，B=1，2，
6、3，R=，求R的定义域和值域。 解 D（R）=a，b，c，R（R）=2，3。,第四章 关系,4.2 二元关系及其表示 4.2.1 二元关系的概念,定义4.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
7、.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的关系图。,第
8、四章 关系,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=，4，,第四章 关系,4.3 关系的运算 4.3.1 关系的交、并、差、补运算,2， B-A=， A=1，2，3，
9、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，4。 R=，S=， ，即S为A上的恒等关系，则RS=SR=R。 如
10、图所示：,（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）
11、（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中每序偶 的第一元素和第二元素的顺序互换，所得到的
12、集合称为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.
13、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是反对
14、 称的。,第四章 关系,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。 再
