离散数学教案.pdf

《离散数学教案.pdf》由会员分享，可在线阅读，更多相关《离散数学教案.pdf（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、.-优选离散数学教案第一章集合与关系集合是数学中最基本的概念，又是数学各分支、自然科学及社会科学各领域的最普遍采用的描述工具。集合论是离散数学的重要组成部分，是现代数学中占有独特地位的一个分支。G.Cantor(康脱)是作为数学分支的集合论的奠基人。1870 年前后，他关于无穷序列的研究导致集合论的系统发展。1874 年他发表了关于实数集合不能与自然数集合建立一一对应的有名的证明。1878 年，他引进了两个集合具有相等的“势”的概念。然而，朴素集合论中包含着悖论。第一个悖论是布拉利-福尔蒂的最大序数悖论。1901 年罗素发现了有名的罗素悖论。1932 年康脱也发表了关于最大基数的悖论。集合论的

2、现代公理化开始于1908 年策梅罗所发表的一组公理，经过弗兰克尔的加工，这个系统称为策梅罗-弗兰克尔集合论（ZF），其中包括1904 年策梅罗引入的选择公理。另外一种系统是 诺伊曼-伯奈斯-哥德尔集合论。公理集合论中一个有名的猜想是连续统假设（CH）。哥德尔证明了连续统假设与策梅罗-弗兰克尔集合论的相容性，科恩证明了连续统假设与策梅罗-弗兰克尔集合论的独立性。现在把策梅罗-弗兰克尔集合论与选择公理一起称为 ZFC系统。一、学习目的与要求本章目的是介绍集合的基本概念，讲授集合运算的基本理论，关系的定义与运算。通过本章的学习，使学生了解集合是数学的基本语言，掌握主要的集合运算方法和关系运算方法，为

3、学习后续章节打下良好基础。二、知识点1集合的基本概念与表示方法；2集合的运算；3序偶与笛卡尔积；4关系及其表示、关系矩阵、关系图；5关系的性质，符合关系、逆关系；.-优选6关系的闭包运算；7集合的划分与覆盖、等价关系与等价类；相容关系；8序关系、偏序集、哈斯图。三、要求1识记集合的层次关系、集合与其元素间的关系，自反关系、对称关系、传递关系的识别，复合关系、逆关系的识别。2领会领会下列概念：两个集合相等的概念几证明方法，关系的闭包运算，关系等价性证明。.-优选1.1 集合论的基本概念与运算1.1.1 集合的概念集合不能精确定义。集合可以描述为：一个集合把世间万物分成两类,一些对象属于该集合，是

4、组成这个集合的成员，另一些对象不属于该集合。可以说，由于一个集合的存在，世上的对象可分成两类，任一对象或属于该集合或不属于该集合，二者必居其一也只居其一。直观地说，把一些事物汇集到一起组成一个整体就叫集合，而这些事物就是这个集合的 元素 或成员。例如：方程x210 的实数解集合；26 个英文字母的集合；坐标平面上所有点的集合；集合通常用大写的英文字母A,B,C,来标记，元素通常用小写字母a,b,c,来表示。例如自然数集合N(在离散数学中认为0 也是自然数)，整数集合Z，有理数集合Q，实数集合 R，复数集合C 等。集合的表示方法：表示一个集合的方法通常有三种：列举法、描述法和 归纳定义法。(1)

5、列举法列出集合的所有元素，元素之间用逗号隔开，并把它们用花括号括起来。在能清楚地表示集合成员的情况下可使用省略号。例如A=a，b，c，z，Z=0，1，2，都是合法的表示。(2)描述法用谓词来概括集合中元素的属性来表示这个集合。例如Bx|xRx210表示方程x210 的实数解集。许多集合可以用两种方法来表示，如B 也可以写成-1，1。但是 有些集合不可以用列元素法表示，如实数集合。(3)归纳定义法：1.3 节再讨论。属于、不属于：元素和集合之间的关系是隶属关系，即属于 或不属于，属于记作，不属于记作。例如 Aa，b，c，d，d，这里 aA，b，cA，dA，dA，但 bA，dA。b 和d是 A的元

6、素的元素。.-优选外延公理：两个集合A和 B相等，当且仅当它们有相同的成员。集合的元素是彼此不同的：如果同一个元素在集合中多次出现应该认为是一个元素。如 1，1，2，2，31，2，3。集合的元素是无序的：如 1，2，33，1，2。1.1.2 集合间的关系定义 1.1.1 设 A，B为集合，如果B 中的每个元素都是A 中的元素，则称B 是 A的子集合，简称 子集。这时也称B 被 A包含，或 A包含 B，记作 BA。称 B是 A 的扩集。包含的符号化表示为：BAx(xB xA)。如果 B不被 A包含，则记作 BA。例如NZQRC，但 ZN。显然对任何集合A 都有 AA。注意：属于关系和包含关系都是

7、两个集合之间的关系，对于某些集合可以同时成立这两种关系。例如Aa，a和a，既有 a A，又有 aA。前者把它们看成是不同层次上的两个集合，后者把它们看成是同一层次上的两个集合，都是正确的。定义 1.1.2设 A，B为集合，如果 BA 且 BA，则称 B是 A 的真子集，记作 BA。如果 B 不是 A的真子集，则记作 BA。真子集的符号化表示为：BABABA。例如NZQRC，但 NN。为方便起见，所讨论的全部集合和元素是限于某一论述域 中，即使这个论述域有时没有明确地指出，但表示集合元素的变元只能在该域中取值。此论述域常用U 表示，并称为 全集。定义1.1.3不含任何元素的集合叫空集，记作。空集

8、可以符号化表示为x|xx。例如 x|x Rx2+1=0是方程x2+1=0 的实数解集，因为该方程无实数解，所以是空集。定理 1.1-1空集是一切集合的子集。.-优选证：对任何集合A，由子集定义有()Ax xxA，右边的蕴涵式因前件为假而为真命题，所以A也为真。推论 空集是唯一的。证：假设存在空集1和2，由定理6.1 有12，21。根据集合相等的定义，有12。含有 n 个元素的集合简称n 元集，它的含有m(mn)个元素的子集叫做它的m 元子集。任给一个n 元集，怎样求出它的全部子集呢？举例说明如下。例 1.1.1A1,2,3，将 A 的子集分类：0 元子集，也就是空集，只有一个：；1 元子集，即

9、单元集：1，2，3；2 元子集：1,2，1,3，2,3；3 元子集：1,2,3。一般地说，对于n 元集 A，它的 0 元子集有0nC个，1 元子集有1nC个，m 元子集有mnC个，n 元子集有nnC个。子集总数为012nnnnnCCC个。全集与空集在本章中起重要作用，注意掌握它们的基本概念。注意：与的联系与区别。(1)表示集合的元素（可以为集合）与集合本身的从属关系，(2)表示两个集合之间的包含关系。例如：对于集合A=a,b,c,a 是 A 的子集：aA，a 是 A 的元素：aA。注意：不要写成 aA 和 aA。aa，但 aa；是一元集，而不是空集。|1，|0。1.1.3 集合的运算集合的交、

10、并和差运算.-优选1.集合交、并、差运算的定义（注意集合运算与逻辑运算的对应关系）定义设A和B是集合，(1)A和B的交记为AB，定义为：|ABx xAxB；(2)A和B的并记为AB，定义为：|ABx xAxB；(3)A和B的差记为AB，定义为：|ABx xAxB。例：设,Aa b c d，,Bb c e，则,ABb c，,ABa b c d e，,ABa d，BAe定义：如果,A B是两个集合，AB，那么称A和B是不相交 的。如果C是一个集合的族，且C中的任意两个不同元素都不相交，那么称C是（两两）不相交集合的族。2.集合的并和交运算的推广（广义交、广义并）n个集合12121|ninniAAA

11、Ax xAxAxA，12121|ninniAAAAx xAxAxA，无穷可数个集合：121iiAAA，121iiAAA一般情形：|()S CSxS SCxS（C），|()S CSxS SCxS3.集合交、并、差运算的性质：(1)交换律ABBA，ABBA，(2)结合律()()ABCABC，()()ABCABC.-优选(3)分配律()()()ABCABAC，()()()ABCABAC(4)幂等律AAA,AAA,(5)同一律AA,AUA，(6)零律AUU A,(7)吸收律()AABA，()AABA，(8)德摩根律()()()ABCABAC()()()ABCABAC(9)(a)AA,(b)ABA,(c

12、)AAB,(d)ABA,(e)若AB，CD,则()()ACBD，()()ACBD,(f)若AB，则ABA,(g)若AB，则ABB，(h)ABAABBAB。证：利用运算的定义（与逻辑运算的关系）或已证明的性质。集合的补运算1.集合的补运算的定义定义：设U是论述域而A是U的子集，则A的（绝对）补 为：|AUAx xUxAx xABA当且仅当ABU和AB。2.集合补运算的性质：(1)矛盾律AA；(2)排中律AAU；(3)德摩根律U，U，_ABAB，_ABAB；(4)双重否定律（A的补的补是A）：AA；(5)若AB，则BA。.-优选例：证明 A(BC)(AB)(AC)。证对任意的x，xA(BC)xA

13、xBC xA(xBxC)x A(x B xC)xAxBxC(xAxB)(x AxC)xAB)xAC x(AB)(AC)所以A(BC)(AB)(AC)。例：证明 AEA。证对任意的x，xAExAxExA(因为 xE是恒真命题)，所以AEA。注意：以上证明的基本思想是：设 P，Q为集合公式，欲证 PQ，即证 PQ QP为真。也就是要证对于任意的x 有 x Px Q 和 xQxP 成立。对于某些恒等式可以将这两个方向的推理合到一起，就是xPxQ。不难看出，集合运算的规律和命题演算的某些规律是一致的，所以命题演算的方法是证明集合恒等式的基本方法。证明集合恒等式的另一种方法是利用已知的恒等式来代入。例：

14、证明 A(AB)A。证A(AB)(AE)(AB)A(EB)A(BE)AEA。例：证明等式A BA B。证对于任意的x，xABxAxBxAx BxA B，所以 AB A B。注意：上式把相对补运算转换成交运算，这在证明有关相对补的恒等式中是很有用的。例：证明(AB)BAB 证(AB)B(A B)B(AB)(BB)(A B)EAB。例：证明命题A BBA BAAB。证.-优选(1)证 A BBAB，对于任意的x，xAxAxBxABxB(因为 A BB)，所以 AB。(2)证 ABABA。显然有ABA，下面证 AAB，对于任意的x，xAxAxAxAxB(因为 AB)xAB，由集合相等的定义有ABA。

15、(3)证 A BAAB。ABA B(AB)B(因为 ABA)A(B B)A。(4)证 A BABB。ABB(AB)BB。注意：上式给出了AB 的另外三种等价的定义，这不仅为证明两个集合之间的包含关系提供了新方法，同时也可以用于集合公式的化简。例：化简(ABC)(AB)(A(BC)A)。解因为 ABABC，AA(BC)，故有(ABC)(AB)(A(BC)A)(AB)ABA。定义：两集合,A B的环和（对称差）定义为：环和：()()|ABABBAx xAxBxAxB2.环和与环积的性质：(1)()()()()ABABABABAB，(2)ABAB，BAAB，(3)()()ABCABC，()()()C

16、ABCACB；(4)AA，AA，(5)ABACBC例：已知 ABAC，证明 BC。.-优选证 已知 ABAC，所以有A(AB)A(AC)(AA)B(AA)C BCBCBC。3.集合运算的文氏图表示注意：如果没有特殊说明，任何两个集合都画成相交 的。幂集合定义：设A是一个集合，A的幂集是A的所有子集的集合，即()|AB BA。若A是n元集，则()A有2n个元素。例：若A，则()A；若1,2A，则(),1,2,1,2A。对任意集合A：()A，()AA。集合运算的顺序：为了使得集合表达式更为简洁，我们对集合运算的优先顺序做如下规定：称 广义交，广义并，幂集，绝对补 运算为 一类运算，交，并，补，环和

17、，环积运算为 二类运算。一类运算优先于二类运算；一类运算之间由右向左顺序进行；二类运算之间由括号决定先后顺序。1.2关系及其表示1.2.1 集合的笛卡儿积与二元关系定义 1 由两个元素x 和 y（允许 x=y）组成的序列记作，称为 二重组 或有序对或序偶，其中 x 是它的第一元素（分量），y 是它的第二元素（分量）。有序对 具有以下性质：1当 xy 时，；2=的充分必要条件是x=u 且 y=v。注意：这些性质是二元集x,y所不具备的。例如当 xy 时有 x,y=y,x。原因在于有序对中的元素是有序的，而集合中的元素是无序的。例 1 已知=，求 x 和 y。解 由有序对相等的充要条件有x+2=5

18、，2x+y=4，解得 x=3，y=-2。.-优选定义 2 设12,na aa是(2)n n个元素，定义121121,nnnna aaaa aaa为n重组。注意：n重组是一个二重组，其中第一个分量是1n重组。如2,3,5代表2,3,5而 不 代 表2,3,5，按 定 义 后 者 不 是 三 重 组，并 且2,3,52,3,5。n重 组121,nna aaa与121,nnb bbb相 等 当 且 仅 当iiab，1in。定义 3 设 A，B 为集合，用A 中元素为第一元素，B中元素为第二元素构成有序对。所有这样的有序对组成的集合叫做A 和 B 的笛卡儿积（叉积），记作 A B。笛卡儿积的符号化表示

19、为A B=|x AyB。集合12,nAAA（2n）的叉积记为12nAAA或1niiA，定义为1211()ninniAAAAA例 2 设 A=a,b,B=0,1,2，则A B=,；B A=,。由排列组合的知识不难证明，如果|A|=m，|B|=n，则|A B|=mn。笛卡儿积的运算性质(1).对任意集合A，根据定义有A=,A=；(2).一般地说，笛卡儿积运算不满足交换律，即A BB A(当 ABAB 时)；(3)笛卡儿积运算不满足结合律，即(A B)CA(B C)(当 ABC时)；(4).笛卡儿积运算对并和交运算满足分配律，即.-优选A(BC)=(A B)(A C)；(BC)A=(B A)(C A

20、)；A(BC)=(A B)(A C)；(BC)A=(B A)(C A)。我们证明其中第一个等式。证 任取，A(BC)xAyBCxA(yB yC)(xAyB)(xAyC)A B A C(A BAC)所以有A(BC)=(A B)(A C)。(5)ACBDA BC D 性质 5 的证明和性质4 类似，也采用命题演算的方法。注意：性质 5的逆命题不成立，可分以下情况讨论。(a)当 A=B=时，显然有AC和 BD 成立。(b)当 A且 B时，也有AC和 BD 成立。证明如下：任取xA，由于B,必存在 yB，因此有 xAyBA BC DxCyDxC，从而证明了AC。同理可证BD。(c)当 A=而 B时，有

21、 AC 成立，但不一定有BD 成立。反例：令A=，B=1，C=3，D=4。(d)当 A而 B=时，有 BD 成立，但不一定有AC 成立。反例类似于(c)。例 3 设 A=1,2,求 P(A)A。解 P(A)A=,1,2,1,2 1,2=,例 4 设 A，B，C，D 为任意集合，判断以下命题是否为真，并说明理由。(1)A B=A CB=C；(2)A-(B C)=(A-B)(A-C)；(3)A=BC=DA C=B D；(4)存在集合A，使得 AA A。.-优选解(1)不一定为真。当A=，B=1,C=2 时，有 A B=A C，但 BC。(2)不一定为真。当A=B=1,C=2 时有 A-(B C)=

22、1=1，(A-B)(A-C)=1=(3)为真。由等量代入的原理可证。(4)为真。当A=时有 AA A成立。定理1：若(1,2,)iA in都是有限集合，则1212|nnAAAAAA。定义 4 如果一个集合满足以下条件之一：（1）集合非空，且它的元素都是有序对；（2）集合是空集；则称该集合为一个二元关系，记作 R。二元关系也可简称为关系。对于二元关系R，若,x yR，则称,x y有关系R，可记作xRy；若,x yR，则记作xRy。一般地,x yy x，因此xRyyRx。例 111,2,Ra b，21,2,Ra b，则1R是二元关系，2R不是二元关系，只是一个集合，除非将 a和 b定义为有序对。根

23、据以上记法可以写成112R，1aRb等。定义 5 设,A B为集合，AB的任何子集所定义的二元关系叫做从A到B的二元关系，特别地，当AB时，则叫做A上的二元关系。12nAAA的子集称为12nAAA上的一个n元关系，当12nAAA时称为A上的一个n元关系。例 20,1A,1,2,3B，那么10,2 R，2RAB，3R，40,1 R等都是从A到B的二元关系，而其中3R和4R同时也是A上的二元关系。注：可把A到B的二元关系看成是AB上的二元关系或2()AB上的二元关系。.-优选二元关系的数目：集合A上的二元关系的数目依赖于A中的元素数。如果|An，那么2|AAn，AA的子集就有22n个。每一个子集代

24、表一个A上的二元关系，所以A上有22n个不同的二元关系。例如|3A，则A上有232512个不同的二元关系。如果|iiAm，则1212|nnAAAmmm，因此12nAAA上有122nm mm个不同的n元关系。一些重要关系：(1)空关系：若R，则R称为 空关系；(2)全域关系：,|AEx yxAyBAB(3)恒等关系：A上的二元关系,|AIx xxA称为 恒等关系。(4)小于或等于关系：,|,ALx yx yAxy，这里AR；(5)B上的整除关系：,|,BDx yx yBxy整除，这里AZ（非零整数集）；(6)A上的包含关系：,|,Rx yx yAxy，这里A是集合族。例 3设1,2,3A，,Ba

25、 b，(),CBaba b，则1,1,1,2,1,3,2,2,2,3,3,3 AL，1,1,1,2,1,3,2,2,2,3ADC上的包含关系：,Raba baa,aa bbbba ba ba b。类似的还可以定义大于等于关系，小于关系，大于关系，真包含关系 等等。.-优选关系是有序对的集合，因此对它可进行集合运算，运算结果定义一个新的关系。例如：设R和S是给定集合上的关系，则RS，RS，RS，R分别称为关系R与S的 并关系，交关系，差关系 和 R 的补关系。这样一来，可以从已知关系派生出各种新关系。二元关系A到B的二元关系可以用一个图来形象地表示。定义 6 设R是A到B的一个二元关系，则A叫着

26、关系R的前域，B叫着关系R的陪域；()|(,)D Rxyx yR称为关系R的定义域；()|(,)R Ryxx yR称为关系R的值域。关于关系的定义域、值域的一些性质：()()()D RSD RD S；()()()D RSD RD S；()()()R RSR RR S；()()()D RSR RR S。证明（证明第一个式子，其余类似）()()()()()()()()()xD RSy x RS yy xRyxSyy xRyy xSyxD RxD SxD RD S1.2.2 关系矩阵与关系图(1)集合表示法：非空关系都是元素为有序对的集合。(2)关系图：设12,nAx xx，R是A上的关系，令图,G

27、V E，其中顶点集合VA，边集为E，对于,ijx xV，满足,ijijx xEx Rx，则称图G为R的关系图，记作RG。(3)关系矩阵：设12,nAx xx，R是A上的关系，令10ijijijx Rxrx Rx，(,1,2,)i jn.-优选则111212122212()nnijnnnnrrrrrrrrrr称为关系R的关系矩阵，记作RM。例空关系的关系矩阵为全0矩阵：0AM；全域关系的关系矩阵为全1矩阵，记为J；相等关系的关系矩阵为单位矩阵：AIMI。基于关系R与关系矩阵RM互相唯一决定的特性，可用关系矩阵有效地刻画关系的许多 性 质。如 对 于 有 限 集A上 的 任 意 关 系R与S：RS

28、RSMM；RSRSMM。1.3 关系的运算1.3.1 关系的逆定义 1 设R是从A到B的二元关系，关系R的逆（R的逆关系）记为R，定义如下：,|,Rx yx yR当A上的关系R具有对称性时，RR。相等关系的逆是相等关系；空关系的逆是空关系；全域关系的逆是全域关系。列举法：把R中每个有序对的第一和第二成分都加以交换，就可得到逆关系R的所有元素。对xA和yB来说，这意味着xRyyRx。关系矩阵：将RM的行和列交换即可得到RM，即TRRMM（TRM表示RM的转置）。.-优选关系图：颠倒R的关系图中的每条弧（有向边）的箭头，就得到R的关系图。逆关系的性质：(1)设12,R R R都是从A到B的二元关系

29、，则(a)()RR；(b)1212RRRR；(c)1212RRRR；(d)1212RRRR；(e)RR，（RABR）；(f)1212RRRR；(2)设1R是从A到B的关系，2R是从B到C的关系，则1221()RRRR。1.3.2 关系的合成定义 2 设1R是从A到B的关系，2R是从B到C的关系，则1R与2R的 合成（右复合）为从A到C的关系，记为12R R或12R R（其中表示 合成运算），定义为1212,|(,)R Ra caAcCb bBa bRb cR。例 1设1,2,3,4A，2,3,4B，1,2,3C，1R是从A到B的关系，2R是从B到C的关系：1,|62,4,3,3,4,2Rx y

30、xy，2,|1 2,1,3,2,4,3Ry zyz。分别用 列举法、图示法、关系矩阵 表示关系的合成12R R，21RR。例 2设1,2,3,4,5A，1R和2R都是A上的二元关系，如果11,2,3,4,2,2R，24,2,2,5,3,1,1,3R，.-优选分别用 列举法、图示法、关系矩阵 表示关系的合成12RR，21RR，121()RRR，121()RRR，11RR，22RR等。合成关系的性质：(1)设R是从A到B的关系，,ABII分别是,A B上的相等关系，则ABIRR IR；(2)如果关系1R的值域与2R的定义域的交集为空集，则合成关系12RR是空关系；(3)关系的合成关于交和并的分配律

31、：设1R是从A到B的关系，23,RR是从B到C的关系，4R是从C到D的关系，则(a)1231213()()()R RRR RR R，(b)1231213()()()R RRR RR R；(c)2342434()()()RR RR RR R，(d)2342434()()()RR RR RR R；(4)关系的合成满足结合律：设123,R RR分别是从A到B，B到C，C到D的关系，则123123()()R RRR R R。1.3.3 关系的幂定义 3 设R是集合A上的二元关系，nN为任一自然数，则R的n次幂记为nR，定义为：(1)0R为A上的相等关系，0,|Rx xxA(2)1nnRRR。关系的幂运

32、算的性质：(1)对A上的任意关系12,R R有：0012ARRI，1011111ARRRIRR；(2)设R是集合A上的二元关系，,m nN，则mnm nRRR，()mnmnRR；(3)设|An，R是集合A上的一个二元关系，则存在i和j，202nij使ijRR；.-优选(4)循环性质：设R是集合A上的二元关系，若存在i和j，ij，使ijRR，则(a)对所有0k，ikj kRR；(b)对所有,0k m，imdkikRR（其中dji）；(c)令0121,jSRRRR，则R的每一次幂是S的元素，即对nN，nRS。关系的幂的计算：给定A上的关系R和自然数n，怎样计算nR呢？若n是0或1，结果是很简单的。

33、下面考虑2n的情况。如果R是用 集合表达式 给出的，可以通过1n次合成计算得到nR。如果R是用 关系矩阵M给出的，则nR的关系矩阵是nM，即n个矩阵M之积。与普通矩阵乘法不同的是，其中的相加是逻辑加，即1 11,10011,000。如果 R 是用 关系图G给出的，可以直接由图G得到nR的关系图G。G的顶点集与G相同。考察G的每个顶点ix，如果在G中从ix出发经过n步长的路径到达顶点jx，则在G中加一条从ix到jx的边。当把所有这样的边都找到以后，就得到图G。例 3 设,Aa b c d，,Ra bb ab cc d，求R的各次幂，分别用矩阵和关系图表示。解R的关系矩阵为010010100001

34、0000M，则234,RRR的关系矩阵分别是.-优选21010010100000000MMM，320101101000000000MM M，431010010100000000MM M因此42MM，53RR，。所以可以得到246RRR，357RRR，而0R，即AI的关系矩阵为01000010000100001M。至此，R各次幂的关系矩阵都得到了。用关系图的方法得到0123,RRRR的关系图如下图所示。合成关系的矩阵表达二元集,1,0T F上的 布尔运算：TFFTTTT，FFF；10011 11，000；TFFTFFF，TTT；1001000，.-优选1 11；TF?，FT?；10?，01?；配

35、合,的其他性质(结合律、分配律等)可计算更复杂的式子。注0,1关于上述两个运算构成二元数域。(0,1)-矩阵的布尔运算：对于mn的(0,1)矩阵()RijmnMr，()SijmnMs，定义下列运算：()RijmnMr?，()RSijijmnMMrs，()RSijijmnMMrs；对mn和np的(0,1)矩阵()RijmnMr和()SijnpMr：1()nRSikkjmpkMMrs。例 4 对全0矩阵0，全1矩阵J有零律：000MM，JMMJJ；同一律：0MM，JMM。用关系矩阵的布尔运算研究关系的运算：定理 1.3-1：设12,mXx xx，12,nYyyy，12,pZz zz，R是X到Y的关

36、系，()RijmnMa是mn矩阵，S是Y到Z的关系，()SijnpMb是np矩阵，则()R SijRSMcMM，这里1()nijikkjkcab，1,2,im，1,2,jp。设,R S是X到Y的关系，()RijMa，()SijMb，ijc是运算后得到新关系的关系矩阵的元素，则R SRSMMM，ijijijcab；R SRSMMM，ijijijcab；.-优选RM，ijijca?；R SRSMMM，ijijijcab?。定理 1.3-2：关系矩阵的乘法是可结合的。证明：利用关系合成的可结合律：()()()()RSTR STRS TR STRS TRSTMMMMMMMMMMMM。借助关系矩阵及其运

37、算还可导出其他一些结论，如：R为A上的传递关系2RRR RRMM；R为A上的自反关系ARIRIM。本节要求：1.掌握关系的合成运算、关系的幂运算的概念及性质；2.能分别利用关系的不同的表示方法（集合的表示法、图示法、关系矩阵、关系图）对关系进行合成和幂运算。1.4 关系的性质定义 1 设R是A上的一个二元关系，(1)若对A中的每一x，xRx，则称R是自反 的；(2)若对A中的每一x，xRx，则称R是反自反 的；(3)若对每一,x yA，xRy蕴含着yRx，则称R是对称 的；(4)若对每一,x yA，xRy，yRx蕴含着xy，则称R是反对称 的；(5)若对每一,x y zA，xRy，yRz蕴含着

38、xRz，则称R是 传递 的。对于A上的任意关系R，对应于不同的关系特性的关系图和关系矩阵的性质（如.-优选下表）：(1)R是自反的()x xAxRxRM主对角元全为1RG每一节点有自回路；(2)R是反自反的()x xAxRxRM主对角元全为0RG每一节点无自回路(3)R是对称的()x y xAyAxRyyRxRM是对称矩阵RG有向边是成对出现的（若有从a到b的弧，则必有从b到a的弧）；(4)R是反对称的()x y xAyAxRyyRxxy(,1,2,(1)(0)jiijij i jnaa；RG中若有从a到b的弧，则必没有从b到a的弧；(5)R是传递的()x y z xAyAzAxRyyRzxR

39、zRG中若从a到b有一条路径，则从a到b有一条弧。自反性反自反性对称性反对称性传递性逻辑表达式()x xAxRx()x xAxRx()x y xAyAxRyyRx()x y xAyAxRyyRxxy()xy z xAyAzAxRyyRzxRz集合表达式AIRARI1RR1ARRIR RR.-优选关系矩阵主对角线元素全是1主对角线元素全是0矩阵是对称矩阵若1ijr，且ij，则0jir对2M中1所在位置，M中相应的位置都是1关系图每个顶点都有环每个顶点都没有环如果两个顶点之间有边，一定是一对方向相反的边(无单边)如果两点之间有边，一定是一条有向边(无双向边)如果顶点ix到jx有边，jx到kx有边，则从ix到kx也有边关系的性质和运算之间的联系：设1R和2R是A上的关系，它们都具有某些共同的性质。在经过并，交，相对补，求逆或复合运算以后，所得到的新关系12RR，12RR，12RR，1R，12RR等是否还能保持原来关系的性质呢？有关的结论给在下表中，其中的和分别表示“能保持”和“不一定能保持”的含义。自反性反自反性对称性反对称性传递性1R12RR12RR12RR12RR.-优选