《离散数学》-教案

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、 集合的概念 集合不能精确定义。集合可以描述为：一个集合把世间万物分成两类 , 一些对象属 于该集合，是组成这个集合的成员，另一些对象不属于该集合。 可以说，由于一个集合 的存在， 世上的对象可分成两类， 任一对象或属于该集合或不属于该集合， 二者必居其 一也只居其一。直观地说， 把一些事物汇集到一起组成一个整体就叫 集合 ，而这些事物就是这个集 合的元素 或成员 。例如：方程 x2 10的实数解集合； 26 个英文字母的集合；坐标平面上所有点的 集合；集合通常用大写的英文字母 A,B,C, , 来标记，元素通常用小写字母 a,b,c, , 来 表示。例如自然数集合 N(在离散数学中认为 0也

5、是自然数 ) ，整数集合 Z，有理数集合 Q，实数集合 R，复数集合 C 等。集合的表示方法 ：表示一个集合的方法通常有三种： 列举法、描述法 和 归纳定义 法。(1) 列举法 列出集合的所有元素， 元素之间用逗号隔开， 并把它们用花括号括起 来。在能清楚地表示集合成员的情况下可使用省略号。例如 A=a ，b，c， z ， Z=0 ，± 1，± 2， 都是合法的表示。(2) 描述法 用谓词来概括集合中元素的属性来表示这个集合。 例如 B x|x Rx1 0表示方程 x10 的实数解集。许多集合可以用两种方法来表示，如B也可以写成 -1 ， 1 。但是 有些集合不可以用列元素

6、法表示 ，如实数集合。(3) 归纳定义法： 1.3 节再讨论。属于、不属于 ：元素和集合之间的关系是隶属关系，即 属于 或不属于 ，属于记作 ，不属于记作 。例如 Aa，b，c ，d，d ，这里 aA，b，cA，dA， d A，但 b A，d A。b和d 是 A的元素的元素。外延公理 ：两个集合 A和 B 相等，当且仅当它们有相同的成员。 集合的元素是彼此不同的 ：如果同一个元素在集合中多次出现应该认为是一个元 素。如 1 ，1，2，2，31 ，2，3。 集合的元素是无序的 ：如1 ， 2， 3 3，1，2。1.1.2 集合间的关系定义 1.1.1 设 A，B 为集合，如果 B中的每个元素都是

7、 A中的元素，则称 B 是 A的 子集合，简称 子集。这时也称 B被 A包含 ，或 A包含 B，记作 B A。称 B是 A的扩集。包含的符号化表示为： B Ax(xBxA)。如果 B 不被 A 包含，则记作B A。例如 N Z Q R C，但 Z N。显然对任何集合 A 都有 A A。注意 ：属于关系和包含关系都是两个集合之间的关系，对于某些集合可以同时成立这两种关系。例如 A a ， a 和a ，既有a A，又有 a A。前者把它们看成是 不同层次上的两个集合，后者把它们看成是同一层次上的两个集合，都是正确的。定义 1.1.2 设 A，B为集合，如果 B A且 BA，则称 B是 A的真子集，

8、 记作 B A。 如果 B不是 A 的真子集，则记作 B A。真子集的符号化表示为： B A B ABA。例如 N Z Q R C，但 N N。为方便起见， 所讨论的全部集合和元素是限于某一 论述域 中，即使这个论述域有时 没有明确地指出， 但表示集合元素的变元只能在该域中取值。 此论述域常用 U表示， 并 称为全集 。定义 1.1.3 不含任何元素的集合叫 空集 ，记作 。空集可以符号化表示为 x|x x 。22例如x|x Rx 2+1=0是方程 x2+1=0 的实数解集， 因为该方程无实数解， 所以是空 集。定理 1.1-1 空集是一切集合的子集。证：对任何集合 A，由子集定义有A x(x

9、x A) ，右边的蕴涵式因前件为假而为真命题，所以A 也为真。推论 空集是唯一的。证：假设存在空集1和 2 ，由定理 6.1 有 1221。根据集合相等的定义，有 12 。含有 n 个元素的集合简称 n 元集，它的含有 m(mn)个元素的子集叫做它的 m元子 集。任给一个 n 元集，怎样求出它的全部子集呢？举例说明如下。例 1.1.1 A 1,2,3 ，将 A 的子集分类：0元子集，也就是空集，只有一个：；1元子集，即单元集： 1 ，2 ，3 ；2 元子集： 1,2 ，1,3 ， 2,3 ； 3 元子集： 1,2,3 。01一般地说，对于 n 元集 A，它的 0 元子集有 Cn0个，1 元子集

10、有 C1n个， m元子 集有 Cnm个， n元子集有 C nn个。子集总数为 Cn0 Cn1 L Cnn 2n 个。全集与空集在本章中起重要作用，注意掌握它们的基本概念。注意 ：与 的联系与区别。（1）表示集合的元素（可以为集合）与集合本身的从属关系，（2）表示两个集合之间的包含关系。例如：对于集合 A=a,b,c,a 是 A的子集： a A，a 是 A的元素： aA。注意：不要写成 a A 和 a A。a a ，但 a a ； 是一元集，而不是空集。 | | 1，| | 0。1.1.3 集合的运算集合的交、并和差运算1. 集合交、并、差运算的定义（注意集合运算与逻辑运算的对应关系）定义 设

11、A 和 B 是集合，(1)A和 B 的交记为 AI B，定义为：AIBx|xAxB ；(2)A和 B 的并记为 AU B，定义为：AUBx|xAxB ；(3)A和 B 的差记为 A B ，定义为：ABx|xAxB 。例：设 A a,b,c,d ， B b,c,e ，则AI B b,c ， AUB a,b,c,d,e ，A B a,d ， B A e定义：如果 A, B是两个集合， AI B ，那么称 A和 B是不相交 的。如果 C是 一个集合的族，且 C 中的任意两个不同元素都不相交，那么称 C 是（两两） 不相交集 合的族 。2. 集合的并和交运算的推广（广义交、广义并）nA1 x A2x

12、An ，n 个集合I Ai A1 I A2 I L I An x|xi1(7)吸收律AU(AIB) A ，AI (AU B)A，UAi A1U A2UL UAn i1x| x A1x A2 L xAn ，无穷可数个集合： I Ai A1 Ii1A2IL ，U Ai i1A1U A2UL一般 情 形 ： I Sx|S(S Cx S) (C ） ，SCUSx| S(S C x S)SC3.集合交、并、差运算的性质：(1)交换律 AI B BI A ，AUB BUA，(2)结合律 (AI B)I C AI(BIC)，(AUB)UCAU(BUC)(3)分 配 律AU(BIC) (AUB)I(AUC)

13、，AI (BUC) (AI B)U(AI C)(4)幂等律 AI A A,AUA A,(5)同一律 AU A,AI U A，n零律AUUUAI(6)(8)(BIC)(AB)U(A C)(9) (a)A, (b)A BA, (c) A AU B, (d)AI B A,(e) 若 AB，C D ,则 (AUC)(BUD)， (AI C)(BI D),(f) 若 AB，则 AI B A, (g)若 A B ，则 AU BB，(h) AI BAUB B AB。A (BUC) (A B)I (A C)证：利用运算的定义（与逻辑运算的关系）或已证明的性质。集合的补运算1. 集合的补运算的定义定义：设 U

14、是论述域而 A是U 的子集，则 A的(绝对)补 为：A U A x |x U x A x |x AB A当且仅当 AUB U 和 AI B 。2. 集合补运算的性质：(1)矛盾律AI A ；(2)排中律 AU A U ；(3)德摩根律U ， U ，AUB AI B， AI B AUB ；(4)双重否定律( A 的补的补是 A )：AA；(5) 若 A B ，则 B A例：证明 A(BC)(AB)( A C)。证对任意的 x，xA(BC)x Ax BCx A (x B x C)x A ( x B x C)x A x B x C(x Ax B)(xAx C)x AB)xACx (AB)(AC)所以

15、 A(BC)(AB)( A C)。 例：证明 AE A。证 对任意的 x，xAE xA xE xA( 因为 xE是恒真命题 ) ，所以 A E A。注意： 以上证明的基本思想是： 设 P，Q为集合公式， 欲证 PQ，即证 P QQ P 为真。也就是要证对于任意的 x 有 x P xQ和 xQ xP 成立。对于某些恒等式 可以将这两个方向的推理合到一起，就是x P x Q。不难看出， 集合运算的规律和命题演算的某些规律是一致的， 所以命题演算的方法 是证明集合恒等式的基本方法。证明集合恒等式的另一种方法是 利用已知的恒等式来代入 。 例：证明 A(AB) A。证 A(A B)(A E) (AB)

16、 A(E B)A(B E) A E A。例：证明等式 ABA B。证 对于任意的 x，xAB xAx B xAxB xA B， 所以 A B A B。注意 ：上式把相对补运算转换成交运算， 这在证明有关相对补的恒等式中是很有用 的。例：证明 (AB) BAB证 (A B)B(A B)B(AB)(BB)(A B)E AB。 例：证明命题 AB B ABA AB 。证(1) 证 AB B A B，对于任意的 x，xA xAxB x AB xB(因为 A BB)，所以 A B。(2) 证 A B ABA。显然有 AB A，下面证 A A B，对于任意的 x， xA xAxA x AxB(因为 A B

17、)xAB，由集合相等的定义有A BA。(3) 证 ABA A B 。A B A B (A B) B(因为 A B A) A(B B)A 。(4) 证 ABABB。ABB(AB) B B。注意 ：上式给出了 A B 的另外三种等价的定义，这不仅为证明两个集合之间的包 含关系提供了新方法，同时也可以用于集合公式的化简。例：化简 (A BC) (A B) (A (BC) A)。解 因为 AB A BC，A A(B C)，故有(A BC)(AB) (A (BC) A) (AB)AB A。定义：两集合 A,B 的环和(对称差) 定义为：环和： A B (A B)U(B A) x|x A x B x A

18、x B2. 环和与环积的性质 ：(1)AB(AU B)I(AUB)(AUB) (AI B)，(2)ABA B ，BAA B ，(3)(AB)CA(BC)， CI (A B) (CI A) (CI B) ；(5)ABACBC例：已知 ABAC，证明 B C。证已知 ABAC，所以有A(A B) A (AC) (A A)B (A A) CBCB CB C。(4) A AA，3. 集合运算的文氏图表示注意 ：如果没有特殊说明，任何两个集合都画成 相交 的。幂集合定义：设 A是一个集合， A的幂集是 A的所有子集的集合， 即 (A) B| B A 。若 A是 n 元集，则(A)有2n 个元素。例：若

19、A ，则 (A) ；若 A 1,2 ，则 (A) ,1,2, 1,2 。 对任意集合 A：(A)， A (A)。集合运算的顺序 ：为了使得集合表达式更为简洁，我们对 集合运算的优先顺序 做如下 规定：称 广义交 ，广义并 ，幂集 ，绝对补 运算为 一类运算 ，交，并，补，环和 ，环积 运算为 二类运算 。一类运算优先于二类运算； 一类运算之间由右向左顺序进行； 二类运 算之间由括号决定先后顺序。1.2关系及其表示1.2.1 集合的笛卡儿积与二元关系定义 1 由两个元素 x 和 y（允许 x=y ）组成的序列记作 <x,y> ，称为 二重组 或有 序对 或序偶 ，其中 x 是它的第一

20、元素（分量） ， y 是它的第二元素（分量） 。有序对 <x,y> 具有以下性质：。原因1当 xy时， <x,y> <y,x> ； 2 <x,y>=<u,v> 的充分必要条件是 x=u 且 y=v。 注意：这些性质是二元集 x,y 所不具备的。例如当 xy 时有 x,y=y,x 在于有序对中的元素是有序的，而集合中的元素是无序的。例 1 已知 <x+2,4>=<5,2x+y> ，求 x 和 y 。x=3， y=-2 。解 由有序对相等的充要条件有 x+2=5， 2x+y=4 ，解得定义 2 设a1,a2,K ,

21、an是n（n 2） 个元素，定义a1,a2,K ,an 1 ,ana1,a2,K,an 1,an例2 设 A=a,b, B=0,1,2，则注意：n重组是一个二重组，其中第一个分量是 n1 重组。如 2,3,5代表2,3,5而 不 代 表 2, 3,5，按定义后者不是三重组，并且2,3,52, 3,5 。n 重 组a1,a2,L ,an 1,an 与b1,b2,L ,bn 1,bn相等 当且 仅 当 aibi ，为 n 重组 。n。1i定义 3设 A， B 为集合，用A中元素为第元素， B 中元素为第二元素构成有序对。所有这样的有序对组成的集合叫做 A和 B的笛卡儿积（叉积） ，记作 A

22、5;B。笛卡儿积的符号化表示为 A×B=<x,y>|x AyB 。n集合 A1,A2,K ,An （ n 2 ）的叉积记为 A1 A2 L An 或 Ai ，定义为 i1nAi (A1 A2 L An 1) An i1A× B=<a,0>,<a,1>,<a,2>,<b,0>,<b,1>,<b,2>B× A=<0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b>由排列组合的知识不难证明，如果|A|

23、=m ， |B|=n ，则|A ×B|=mn。笛卡儿积的运算性质(1) . 对任意集合 A，根据定义有 A × = ,×A= ；(2) . 一般地说， 笛卡儿积运算不满足交换律， 即 A×BB× A(当 A B A B时)；(3) 笛卡儿积运算不满足结合律，即 (A×B)×CA×(B×C)(当 A B C 时 ) ；(4) . 笛卡儿积运算对并和交运算满足分配律，即A×(B C)=(A×B)(A×C)； (B C)×A=(B×A)(C×A)；A&

24、#215;(B C)=(A×B)(A×C)； (B C)×A=(B×A)(C×A)。我们证明其中第一个等式。证 任取 <x,y> ，<x,y> A×(B C)x AyBC xA(y ByC)(x AyB)(x AyC)<x,y> A× B <x,y> A× C <x,y> (A×BA×C)所以有 A×(BC) = (A ×B)(A×C)。(5) A C B D A× B C× D性质 5

25、 的证明和性质 4 类似，也采用命题演算的方法。注意 ：性质 5的逆命题不成立，可分以下情况讨论。(a) 当 A=B= 时，显然有 A C 和 B D 成立。(b) 当 A 且 B 时，也有 A C 和 B D 成立。证明如下：任取 x A，由于 B , 必存在 y B，因此有 x AyB <x,y> A×B <x,y> C×D xCy D x C，从而证明了 A C。同理可证 B D。(c) 当 A= 而 B 时，有 A C成立，但不一定有 B D 成立。反例：令 A= ，B=1 ，C=3 ，D=4 。(d) 当 A 而 B= 时，有 B D 成立

26、，但不一定有 A C 成立。反例类似于 (c) 。 例 3 设 A=1,2, 求 P(A)×A。解 P(A) ×A= ,1,2,1,2× 1,2=< ,1>,< ,2>,<1,1>,<1,2>,<2,1>,<2,2>,<1,2,1>,<1,2,2>例4 设 A，B，C，D为任意集合，判断以下命题是否为真，并说明理由。(1) A × B=A× C B=C； (2) A-(B× C)=(A-B) × (A-C) ；(3) A=B C=

27、D A× C=B× D； (4) 存在集合 A，使得 A A×A。解 (1) 不一定为真。当 A= ，B=1,C=2 时，有 A×B= =A×C，但 B C。 (2) 不一定为真。当 A=B=1,C=2 时有 A-(B ×C)=1 <1,2>=1 ，(A-B)× (A-C)=× 1=(3)为真。由等量代入的原理可证。(4)为真。当 A= 时有 A A×A 成立。定理 1 ： 若 Ai(i 1,2,K ,n)都是有限集合，则| A1 A2L An | |A1|g|A2|gL g|An |。定义4

28、 如果一个集合满足以下条件之一： (1)集合非空，且它的元素都是有序对；( 2)集合是空集；则称该集合为一个 二元关系 ，记作 R。二元关系也可简称为 关系 。 对于二元关系 R，若 x,y R ，则称 x,y有关系 R，可记作 xRy ；若x, y R ，则记作 xRy 。一般地 x, y y,x ，因此 xRy yRx 。例1 R1 1,2 , a,b ，R2 1,2 ,a,b ，则 R1是二元关系， R2不是二 元关系，只是一个集合， 除非将 a和 b定义为有序对。根据以上记法可以写成 1R12 ，aR1b 等。定义 5 设 A, B为集合， A B的任何子集所定义的二元关系叫做从A到

29、B的二元关系，特别地，当 A B时，则叫做 A上的二元关系 。 A1 A2 L An的子集称为 A1 A2 L An上的一个 n元关系 ，当 A1 A2 LAn时称为 A上的一个 n元关系。例 2 A 0,1 , B 1,2,3 ，那么 R1 0,2 ， R2 A B， R3 ， R4 0,1 等都是从 A到 B的二元关系，而其中 R3和 R4同时也是 A上的二元关系。注：可把 A到 B的二元关系看成是 AUB上的二元关系或 ( A U B)2上的二元关系。 二元关系的数目 ：集合 A上的二元关系的数目依赖于 A中的元素数。 如果| A| n， 2n2那么 |A A| n2 ，A A的子集就有

30、 2n 个。每一个子集代表一个 A上的二元关系， 所 22以 A上有 2n 个不同的二元关系。 例如|A| 3，则 A上有 23 512个不同的二元关系。 如果 |Ai | mi，则|A1A2LAn |m1m2Lmn ，因此A1A2LAn上有2m1m2L mn个不同的 n 元关系。一些重要关系：(1)空关系 ：若 R，则 R称为空关系 ；(2)全域关系 ： EA x,y |xAyBAB(3)恒等关系 ： A 上的二元关系IA x,x |xA 称为 恒等关系 。(4)小于或等于关系： LA x, y| x,yAxy ，这里 A R ；(5)B 上的整除关系： DB x,y| x,yBx整除 y

31、，这里 A Z (非零整数集)；(6)A上的包含关系： R x,y|x,yAxy ，这里 A 是集合族。例3 设 A 1,2,3 ，B a,b，C (B) , a, b, a,b ，则LA 1,1 ,1,2 ,1,3 , 2,2 ,2,3 , 3,3 ，DA 1,1, 1,2, 1,3 , 2,2, 2,3 C上的包含关系：R , ,a ,b, ,a,b ,a, a ,a, a,b , b, b , b, a,b , a,b, a,b 。类似的还可以定义 大于等于关系 ， 小于关系 ，大于关系 ，真包含关系 等等。 关系是有序对的集合， 因此对它可进行集合运算， 运算结果定义一个新的关系。 例

32、 如：设 R和 S是给定集合上的关系， 则 RUS，RI S，R S ， R分别称为关系 R与 S的并关系 ，交关系 ，差关系 和 R的补关系 。这样一来，可以从已知关系派生出各种 新关系。二元关系A到 B 的二元关系可以用一个图来形象地表示。定义 6 设 R是 A到 B的一个二元关系， 则 A叫着关系 R的前域，B 叫着关系 R 的陪域； D(R) x| y( x,y R) 称为关系 R的定义域 ；R(R) y| x( x,y R) 称为关系 R的值域 。关于关系的定义域、值域的一些性质：D(RU S) D(R)UD(S)； D(RI S) D(R)I D(S)；R(RUS) R(R)UR(

33、S)； D(RI S) R(R)I R(S)。证明 (证明第一个式子，其余类似)x D(RUS) y(x(RUS)y) y(xRy xSy) y(xRy) y( xSy)x D(R) x D(S) x D(R)U D(S)1.2.2 关系矩阵与关系图(1) 集合表示法 ：非空关系都是元素为有序对的集合。(2) 关系图 ：设 A x1,x2,K ,xn ， R是 A上的关系，令图 G V,E ，其中 顶点集合 V A，边集为 E，对于 xi,xj V ，满足 xi,xj E xiRxj ，则称图 G 为 R的关系图 ，记作 GR。1 xi Rxj(3) 关系矩阵 ：设 A x1,x2,K ,xn

34、 ， R是 A上的关系，令 riji j ，0 xiRxj(i, j 1,2,K ,n)r11r12Lr1n则 (rij )r21 r22 L r2n 称为关系 R的关系矩阵 ，记作 M R。 M M O M R rn1 rn2 L rnn例 空关系的关系矩阵为全 0 矩阵： M A 0 ； 全域关系的关系矩阵为全 1 矩阵， 记为 J ；相等关系的关系矩阵为单位矩阵： M I A I 。基于关系 R与关系矩阵 M R 互相唯一决定的特性，可用关系矩阵有效地刻画关系的许 多 性 质 。 如对 于 有 限 集 A 上 的 任 意 关 系 R 与 S ： R S MR MS ；R S MR M S

35、1.3 关系的运算1.3.1 关系的逆定义 1 设 R是从 A到 B的二元关系，关系 R的逆（ R的逆关系）记为 R%，定义 如下：R% x,y | x,y R当 A上的关系 R具有对称性时， R% R 。 相等关系的逆是相等关系；空关系的逆是空关系；全域关系的逆是全域关系。列举法 ：把 R 中每个有序对的第一和第二成分都加以交换，就可得到逆关系R%的所有元素。对 x A和 y B 来说，这意味着 xRy yR%x 。关系矩阵 ：将 M R的行和列交换即可得到 M R%，即 MR% MRT （M RT表示 M R的转 置）。关系图 ：颠倒 R 的关系图中的每条弧（有向边）的箭头，就得到R%的关

36、系图。逆关系的性质：(1)设 R,R1,R2都是从 A到 B的二元关系，则(a)(R%) R ； (b)R1 U%R2 R%1 UR%2 ；(c)R1 I%R2R%1 IR%2 ； (d)R1 %R2R% R% ；R1R2 ；(e)R% R%，( RA B R )； (f)R1 R2R%1R%2；(2)设 R1是从 A到 B 的关系， R2 是从 B到 C的关系，则 (R1 %R2) R%2 R%1。1.3.2 关系的合成定义 2 设R1是从 A到B的关系， R2是从 B到C的关系，则 R1与R2的合成(右复合) 为从 A到 C的关系，记为R1R2 或 R1gR2 (其中 g表示 合成运算 )

37、，定义为R1R2 a,c |a A cC b(b Ba,b R1 b,c R2) 。例1 设 A 1,2,3,4 ，B2,3,4 ， C1,2,3 ，R1是从 A到 B的关系， R2是从 B到 C的关系：R1 x,y |x y 6 2,4 , 3,3, 4,2 ，R2 y,z |y z 1 2,1 , 3,2, 4,3 。分别用 列举法、图示法 、关系矩阵 表示关系的合成 R1gR2 ， R2 gR1 。例2 设 A 1,2,3,4,5 ， R1和R2都是 A上的二元关系，如果R1 1,2 , 3,4 , 2,2 ，R2 4,2 , 2,5 , 3,1 , 1,3 ，分别用 列举法、图示法 、

38、关系矩阵 表示关系的合成 R1 R2，R2 R1， (R1 R2) R1， R1 (R2 R1 ) ， R1 R1 ， R2 R2 等。合成关系的性质 ：(1) 设 R是从 A到 B的关系， IA,IB分别是 A,B上的相等关系，则I A R R I B R；(2) 如果关系 R1的值域与 R2 的定义域的交集为空集，则合成关系R1 R2是空关系；(3) 关系的合成关于交和并的 分配律 ：设 R1是从 A到B的关系， R2, R3是从 B到C的关系， R4是从 C到D的关系，则(a) R1(R2 UR3) (R1R2)U(R1R3) ，(b) R1(R2 I R3) (R1R2)I (R1R3

39、)；(c) (R2 UR3)R4 (R2R4)U(R3R4)，(d) (R2 I R3)R4 (R2R4)I (R3R4)；(4) 关系的合成满足 结合律 ：设 R1, R2 , R3分别是从 A到 B，B到C ，C到 D 的关系，则(R1R2)R3 R1( R2R3) 。1.3.3 关系的幂定义 3设R是集合 A上的二元关系， n N 为任一自然数， 则 R的n次幂记为 Rn， 定义为： (1) R0为 A上的相等关系， R0 x,x |x A (2) Rn 1 Rn R。关系的幂运算的性质：(1)对 A 上的任意关系 R1,R2 有：R10 R20 IA， R11R10R1I A R1R1

40、；(2)设 R 是集合A 上的二元关系，m,n N ，则 RmRnRmn， (Rm)nRmn；(3)设| A| n ，R 是集合 A 上的一个二元关系，则存在i和j，20 i j 2n 使Ri Rj ；(4) 循环性质：设 R是集合 A上的二元关系，若存在 i 和 j ，i j ，使 Ri Rj， 则(a) 对所有 k 0， Ri k Rj k ； (b) 对所有 k,m 0， Ri mdk Ri k (其中 d j i )； (c) 令S R0,R1,R2,L ,Rj 1 ，则 R的每一次幂是 S的元素，即对 n N ， Rn S。关系的幂的计算：给定 A上的关系 R和自然数 n ，怎样计算

41、 Rn呢？若 n是 0或1，结果是很简单的。下面考虑 n 2 的情况。如果 R是用集合表达式 给出的，可以通过 n 1次合成计算得到 Rn 。如果 R是用关系矩阵 M 给出的，则 Rn的关系矩阵是 M n，即 n 个矩阵 M 之积。与普通矩阵乘法不同的是， 其中的相加是逻辑加， 即1 1 1,1 0 0 1 1,0 0 0 。如果 R是用关系图 G给出的， 可以直接由图 G得到 Rn的关系图 G 。G 的顶点集 与 G 相同。考察 G 的每个顶点 xi ，如果在 G 中从 xi 出发经过 n 步长的路径到达顶点xj，则在 G 中加一条从 xi 到 x j的边。当把所有这样的边都找到以后，就得到

42、图G 。例 3 设 A a,b,c,d， R a,bb, ab,c , c,d ，求 R 的各次幂，分别用矩阵和关系图表示。10201M 2 MM00001014 3 0 M 4 M 3M10000000因此 M4 M 2， R501001010，则R2,R3,R4的关系矩阵分别是0001000010010101，321010，M3M2M0000000000000100解 R 的关系矩阵为 MR3 ，L 。所以可以得到 R2 R4 R6 L ，R3 R5R7L ，而 R0 ，即 I A 的关系矩阵为 M10000100。至此， R 各001000010次幂的关系矩阵都得到了。用关系图的方法得到

43、 R0, R1,R2,R3,L 的关系图如下图所示。合成关系的矩阵表达TFFTTTT ， F FF；1 0 0 1000；TFFTFFF ，T TT；1001111；?TF，?FT；?10， ?0 1；元集 T,F 1,0 上的布尔运算 ： 配合的其他性质 ( 结合律、分配律等)可计算更复杂的式子。1 1 1，0 0 0 ，注 0,1 关于上述两个运算构成二元数域。(0,1) - 矩阵的布尔运算：?MR(?rij )mn ， M R M S(rijsij )mn ， M R M S(rijsij )mn ；对mn和 n p的 (0,1)矩阵 M R (rij )mn和 MS (rij)np ：

44、M R MSn(k 1(rikskj )mp 。对于 m n的(0,1) 矩阵 M R (rij )mn， MS(sij )mn ，定义下列运算：例 4 对全 0 矩阵 0 ，全 1矩阵 J 有零律：0 M M 0 0 ， J M M J J ； 同一律 ：0 M M ， J M M 。用关系矩阵的布尔运算研究关系的运算：定理 1.3-1 ：设 X x1, x2 ,L ,xm ，Y y1,y2,L , yn ，Z z1,z2,L ,zp ，R 是 X 到Y的关系， MR (aij )mn是 m n矩阵， S是 Y到 Z 的关系， MS (bij)np是nn p 矩阵，则 M R S (cij )MR MS ，这里 cijk 1(aikbkj) ，i 1,2,L ,m，j 1,2,L ,p。设 R,S是 X 到Y的关系，M R (aij ) ，MS(bij)，cij 是运算后得到新关系的关系矩阵的元素，则M RI SMRMS，cijaijb；ij ；M RUSMRMS，cijaij