离散数学(全套课件400P).ppt

1、离散数学第一章 集合论初步1 集合论基础1.1 关于集合的概念关于集合的概念 集合集合：一些不同的确定的对象的全体。：一些不同的确定的对象的全体。 元素元素：构成集合的对象。：构成集合的对象。 如如：（：（1）全班同学）全班同学 （2）计算机内存的全部单元）计算机内存的全部单元 集合用集合用大写大写字母表示，如字母表示，如A,B,C；元素用；元素用小写小写字母表示，字母表示，如如a,x,y。 集合集合A元素的个数称为元素的个数称为A的的基数基数，记为，记为|A|。Note:1集合中的元素是确定的。集合中的元素是确定的。对集合对集合A，即任意元素，即任意元素a要么属于此集合，要要么属于此集合，要

2、么不属于，分别记为么不属于，分别记为aA ,和和aA。2 集合中的每个元素均不相同。集合中的每个元素均不相同。 如：如：a,b,c,d 和和a,b,b,c,d 是相同的。是相同的。 3集合中元素具体不作限制集合中元素具体不作限制如如: a,b,a,b相关概念：相关概念：有限集有限集无限集无限集空集空集 （元素个数为零）（元素个数为零）全集全集（包含所有研究问题的对象全体的集合，用（包含所有研究问题的对象全体的集合，用E表示）表示）集合的表示方法：集合的表示方法：（1）枚举法）枚举法 即全部列出来。即全部列出来。 A=1,2,3,20（2）描述法）描述法 A=x|p(x)，p表示某性质，表示某性

3、质， 如：如：A=x|x+50,xR1.2 集合间的关系集合间的关系如果集合如果集合A与集合与集合B的元素相同，则称两的元素相同，则称两个集合个集合相等相等，记为，记为A=B。（否则，称为不相等，记为（否则，称为不相等，记为A B。）。）定义定义1、定义定义2、 a A，必有，必有a B,则称则称B包含包含A（或称（或称A包含于包含于B，或称，或称A时时B的的子集子集）,记作记作AB。若若A B，且存在，且存在b B，使，使b A，则称，则称A是是B的的真子集真子集，记为，记为AB 。 Note:对于相等关系和包含关系，对于相等关系和包含关系，可用文氏图（可用文氏图（venn diagram)

4、 表示表示:AB 例例1、A=1,2,100，N=0,1,2,，则，则 AN且且AN。例例2、A=1,2,3,3，B=1,2,3，则，则A=B。例例3、设、设P=x|(x+1)2 4, Q=x|x2+16 5x，求，求P,Q间的关系。间的关系。解：解：Q=R (因为因为x2+16 5x恒成立）恒成立） 所以所以PQ。定理定理1、对任一集合、对任一集合A，必有，必有A。 定理定理2、对任一集合、对任一集合A,必有必有AE。 定理定理3、集合、集合A,B，则，则A=BAB且且BA。 1.3 集合代数集合代数用代数的方法讨论集合，建立集合的一些运算。用代数的方法讨论集合，建立集合的一些运算。定义定义

5、3 并集并集：由集合：由集合A、B所有元素合并组成所有元素合并组成的集合，记为的集合，记为AB。 即即A B=x|xA或或xB定义定义4 交集交集：由集合：由集合A、B所有的公共元素所所有的公共元素所组成的集合。组成的集合。AB=x|xA且且xB定义定义5 分离分离：AB= 定义定义6 差集差集：属于集合：属于集合A而不属于而不属于B的元素所的元素所组合成的集合。组合成的集合。 A-B=x|xA且且x B 例：例：A=a,b,c,d,e,，B=d,e,f,g,h，则，则 A-B=a,b,c定义定义7、补集：、补集：A=E-A定义定义8、对称差（或称布尔和）：、对称差（或称布尔和）： A+B=(

6、A-B)(B-A) = AB-AB例例: (上例中）上例中）A+B=a,b,c,f,g,h至此，定义了五种运算：并，交，差，对称差，至此，定义了五种运算：并，交，差，对称差，（二元）和补（一元）。（二元）和补（一元）。1.4 集合代数的基本公式集合代数的基本公式1 交换律交换律 AB=BA; AB=BA.2 结合律结合律 A(BC)=(AB)C A(BC)=(AB)C3 分配律分配律 A(BC)=(AB) (AC) A(BC)=(AB) (AC)4 同一律同一律 A=A AE=A5 零一律零一律 AE=E A=7 等幂律等幂律 AA=A AA=A8 吸收律吸收律 A(AB)=A A(AB)=A

7、6 补余律补余律 AA=E AA=9 狄狄-莫根定律莫根定律(De Morgens Law) (AB)=AB (AB)=AB例：设例：设M=x|f1(x)=0,N=x|f2(x)=0,则方程则方程f1(x)*f2(x)=0的解为的解为( )。(1)MN (2)M (3)MN (4)N答案答案: (3)例：设例：设A=,B=,则则B-A是是( )(1) (2) (3), (4) 答案答案: (3)1.5 有限集的基数有限集的基数定理定理1 A、B为有限集，则为有限集，则BABABA 定理定理2 A、B、C为有限集，则为有限集，则CBCABACBACBA CBA 例例：P44例例4.42 幂集，幂

8、集，n重有序组及笛卡尔乘积重有序组及笛卡尔乘积2.1 幂集幂集定义：定义： 由集合由集合A的所有子集（包括空集及的所有子集（包括空集及A本身）本身）所组成的集合叫所组成的集合叫A的的幂集幂集，记作，记作2A 或或(A)。例：例：A=1,2,3,则则(A)=，1，2，3，1，2，1，3，2，3，A。定理：定理：若集合若集合A为有为有n个元素所组成的有限集，个元素所组成的有限集，则则(A)为有限，且由为有限，且由2n 个元素组成。个元素组成。证：证：C +C +C =2 nnnnn012.2 n重有序组重有序组定义定义: 两个客体两个客体a,b按一定次序排列，组成一个有按一定次序排列，组成一个有序

9、序列，叫做序序列，叫做有序偶有序偶，记作，记作(a,b)。Note: (a,b)一般不与一般不与(b,a)相等，如在坐标中，相等，如在坐标中，可用一个有序偶来表示一个点，有可用一个有序偶来表示一个点，有(1,3) (3,1)。定义定义: 有序偶有序偶(a,b)和和(c,d)，如果有，如果有a=c,b=d,则则说说(a,b)和和(c,d)相等相等。定义定义: n个个(n1)客体客体a1 ,an 按一定次序排按一定次序排列，构成一个有序序列，叫做列，构成一个有序序列，叫做n重有序组重有序组，记，记以以(a1 ,an )定义：定义： 两个两个n重有序组重有序组(a ,a ,a )与与(b ,b ,b

10、 )如果有如果有a =b (i=1,n)， 则称它们是相等的。则称它们是相等的。1122nnii2.3 笛卡尔乘积笛卡尔乘积定义定义: 集合集合A,B的笛卡尔乘积定义为：的笛卡尔乘积定义为： AB=(a,b)|a A,b B例：例：平面直角坐标系中的所有点可用一笛卡尔平面直角坐标系中的所有点可用一笛卡尔乘积表示：乘积表示：R R=(x,y)|xR,yR定义定义7：集合：集合A1 ,A2 ,An 的笛卡尔乘积定义为：的笛卡尔乘积定义为：A 1 A 2 An=(x1 ,xn )|x1A1 ,xn An例：例：设设A=1,2,B=a,b,A=,，则：，则： AB=(1,a),(1,b),(2,a),

11、(2,b) ABC=(1,a,),(1,a, ),(1,b,),(1,b,), (2,a,),(2,a,),(2,b,),(2,b,)例：例：设设A=1,2 ,则则 A 2= (1,1),(1,2),(2,1),(2,2)定义定义: 集合的集合的幂幂：An =AAAn个个3 无限集无限集定义定义1. 集合集合A与与B的元素间如果存在一一对应的的元素间如果存在一一对应的 关系，则称关系，则称A A与与B B是是等势等势的。记以的。记以A B。对于有限集：对于有限集：AB A、B元素个数相等。元素个数相等。 如如 1，2 3，4 对于无限集：对于无限集：AB 存在存在A B的一一的一一 映射映射f

12、 f 。3.1 无限集的性质无限集的性质例例1.1.自然数集自然数集N=0N=0，1 1，2 2，33与其子集与其子集 S=1S=1，3 3，5 5，均为无限集。均为无限集。0 1 2 3 1 3 5 7f f (x)(x) = 2x + 1 (xN)= 2x + 1 (xN)对应关系：对应关系： NS例例2. 设设A=（ 0, 1 ）, B=（ 0, 2 ）。构造一个从）。构造一个从 A到到B的一一映射函数，以说明的一一映射函数，以说明A B。解：解：令令 f (x) = 2x（ x（0，1），则），则 f (x) 为一一映射函数，且为一一映射函数，且Df f = =（0，1），）， Cf

13、f = =（0 0，2 2）。）。 A B 。定理定理1. 一集合为无限集，则它一集合为无限集，则它必必含有与其等势含有与其等势 的真子集。的真子集。推论：推论：一集合为无限集一集合为无限集它含有与其等势它含有与其等势的真子集。的真子集。定义定义2. 一集合若存在与其等势的子集，则该集合称一集合若存在与其等势的子集，则该集合称为为无限集无限集，否则称为，否则称为有限集有限集。定义定义3. 凡与自然数集凡与自然数集N等势的集合叫等势的集合叫可列集可列集。有限集有限集可列集可列集可数集可数集定理定理2. 一无限集必包含一可列集。一无限集必包含一可列集。定理定理3. 可列集的无限子集仍为一可列集。可

14、列集的无限子集仍为一可列集。定理定理4. 整数集整数集I为可列集。为可列集。证证：即要证明：即要证明IN。为此建立一一对应关系。为此建立一一对应关系如下：如下：N：0 1 2 3 4 5 I：0 1 -1 2 -2 3 定理定理5. 有理数集有理数集Q为可列集。为可列集。之之和和，由由小小到到大大排排列列。）正正分分数数按按其其分分子子分分母母1按按以以下下规规则则排排序序：形形式式，将将所所有有一一切切有有理理数数均均可可写写成成证证mnmn 到到大大排排列列。正正分分数数，按按分分子子从从小小）分分子子分分母母之之和和相相同同的的2。数数）排排列列于于正正分分数数之之后后的的负负分分数数（

15、即即其其相相反反）与与正正分分数数有有相相同同形形式式3为为可可列列集集。可可知知为为其其无无限限子子集集。由由定定理理而而集集，对对应应，故故此此数数列列为为可可列列此此数数列列与与自自然然数数集集一一一一，：按按以以上上规规则则可可得得一一序序列列Q3Q1313222231311212212111110 3.2 无限集的基数无限集的基数有限集：集合有限集：集合A的基数的基数|A|表示元素的个数。表示元素的个数。令令|N|= ? 0（Aleph） 。则由可列集的定义知，。则由可列集的定义知，所有可列集的基数均为所有可列集的基数均为? 0 。对于无限集，若对于无限集，若AB，则，则|A|= |

16、B|，认为，认为A、B“大小大小”相等。故相等。故N是是“最小最小”的无限集。的无限集。定理定理1. 实数集实数集R是不可列的。是不可列的。由以上可得到关于无限集的大小：由以上可得到关于无限集的大小： （1）无限集也有大小，最小的无限集为）无限集也有大小，最小的无限集为可列集，其次是实数集，等等。可列集，其次是实数集，等等。 （2）无限集的）无限集的“大小大小”也是无限的，即也是无限的，即对任意集合，总存在比其基数更大的集合。对任意集合，总存在比其基数更大的集合。德国数学家康托尔（德国数学家康托尔（Cantor）证明，）证明，|(A)|A|。此外，他还认为：此外，他还认为： |A|:t . s

17、A0，结论结论 1. 两个可列集之并仍为可列集。两个可列集之并仍为可列集。 2. 可列个可列集之并仍为可列集。可列个可列集之并仍为可列集。第二章第二章 关系与映射关系与映射1 关系的基本概念关系的基本概念1.1 关系及其定义关系及其定义例例1：讨论旅馆的讨论旅馆的“某旅客住在某房间某旅客住在某房间”关关系，记为系，记为R,设有设有3各房间，一个房间可住各房间，一个房间可住2人。人。 旅客与房间之间关系示意图如下：旅客与房间之间关系示意图如下：abefcd旅客旅客房间房间123 从图上可看出；从图上可看出；a与与1存在关系存在关系R，记为，记为aR1;同理有同理有bR1, cR2, dR2, e

18、R3, fR3.Note: 1满足满足R的关系的关系pRq可看成是一个有序偶可看成是一个有序偶: (p, q), 如如aR1可写成（可写成（a, 1）. 2满足满足R的所有关系可看成是一个有序偶的所有关系可看成是一个有序偶的集合，即的集合，即 R=(a,1), (b,1), (c,2), (d,2), (e,3), (f,3) 关系是一些有序偶的集合。关系是一些有序偶的集合。 3令令A=a, b, c, d, e, f, B=1, 2, 3.则则:AB=(a,1), (b,1),(c,1), (d,1), (e,1), (f,1) RAB定义定义1：从集合：从集合A到集合到集合B的一个的一个关

19、系关系R是是 AB的一个子集。的一个子集。定义定义2：当：当A=B时，则时，则A到到B的关系称为集的关系称为集合合A上上的关系。的关系。 例例2：给定集合给定集合A=0, 1, 2, 3, 4, 令令R=(0,1), (0,2), (0,3), (0,4), (1,2), (1,3), (1,4), (2,3), (2,4), (3,4) 则则R为集合为集合A上的上的“小于小于”关系，即关系，即（x, y）RR表示表示xy.xy.例例3：给定集合：给定集合B=2,3,4,8,求集合求集合B上的上的“整除整除”关系。关系。解：解：R=(2,2), (3,3), (4,4), (8,8), (2,

20、4), (2,8), (4,8)定义定义3: 空关系空关系: 若集合若集合X到集合到集合Y不存在不存在某种关系某种关系R，则称此种关系为，则称此种关系为空关系空关系。定义定义4: 全关系全关系: 若若X的每个元素到的每个元素到Y的每的每个元素均具有某种关系，则称此关系为个元素均具有某种关系，则称此关系为全关系全关系。 X到到Y的全关系即为的全关系即为 XY.定义定义5: n元关系元关系: 由集合由集合X1,X2,，Xn所确定所确定的的n元关系是元关系是X1X2Xn的一个子集。的一个子集。1.2 关系的图形表示和矩阵表示关系的图形表示和矩阵表示一个从一个从X到到Y的关系的关系R可用图形或矩阵表示

21、。可用图形或矩阵表示。1.2.1 图形表示图形表示 先用结点把先用结点把X和和Y的元素表示出来的元素表示出来,若若xi R yj (xi X, y X, yj j Y Y), 则用一带箭头的线段把则用一带箭头的线段把xi和和yj连接起来。连接起来。例例4: X=x1,x2,x3, Y=y1,y2,y3,R为为X到到Y的一的一个关系，个关系，R=(x1,y1), (x1,y2), (x2,y2), (x2,y3), (x3,y3), (x3,y1)。则其图形表示如下。则其图形表示如下y1y2y3x1x2x3Note: 集合集合X上的关系亦可用关系图表示上的关系亦可用关系图表示.XYR例例5: S

22、=a, b, c,令令R1=(a, b), (b, c), (c, a), R2=(a, a), (a, b), (a, c),则则R1的关系图的关系图R2的关系图的关系图注注:上述关系可理解为程序调用关系，如上述关系可理解为程序调用关系，如R2表示表示a递归调用递归调用, a调用调用b, a调用调用c.acbabc 设设X元素个数为元素个数为m, Y元素个数为元素个数为n, 则则X到到Y的的关系的表示矩阵关系的表示矩阵:1 若若(xi ,yi) RR0 若若(xi ,yi) R R如如例例4中，中，1 1 0 0 1 11 0 11.2.2 矩阵表示矩阵表示MR=(aij)mn=MR=例例4

23、: X=x1,x2,x3, Y=y1,y2,y3,R为为X到到Y的一个关系，的一个关系，R=(x1,y1), (x1,y2), (x2,y2), (x2,y3), (x3,y3), (x3,y1)。0 1 0 0 0 11 0 0MR1=1 1 1 0 0 00 0 0MR2=例例5中，中，例例5: S=a, b, c,令令R1=(a, b), (b, c), (c, a), R2=(a, a), (a, b), (a, c),2 关系的运算关系的运算2.1 关系的交、并、补、差关系的交、并、补、差 由于关系是一些有序偶的组成的集合，故由于关系是一些有序偶的组成的集合，故有关集合的运算关系仍适

24、用。有关集合的运算关系仍适用。例例1:X=a, b, c, Y=1, 2; X到到Y的关系的关系R=(a, 1), (c, 2), S=(a, 2), (b, 1), (c, 2) (a, 2), (b, 1), (b, 2), (c, 1)则则 RS=(c, 2)R=(注：注：E=XY)2.2 复合关系复合关系2.2.1 复合关系的定义复合关系的定义定义定义1: 设设R是一是一X到到Y的关系，的关系，S是一是一Y到到Z的关的关系，则系，则R与与S的复合关系的复合关系ROS可定义为可定义为: ROS=(x, z)| x X, z Z, 且存在且存在y Y, 使使 (x, y) R, 且且(y,

25、 z) S例例2: 给定集合给定集合A=1, 2, 3, 4, 5及及A上的二个二元上的二个二元关系关系R=(1, 2), (3, 4), (2, 2),S=(4, 2), (2, 5), (3, 1)(1, 5), (3, 2), (2, 5)(4, 2), (3, 2)(4, 5)=(1, 2), (2, 2)则则ROS=SOR=SOS=ROR2.2.2 复合关系的图形与矩阵表示复合关系的图形与矩阵表示例例3: 设设X=x1, x2, x3, Y=y1, y2, y3, Z=z1, z2, z3,从从X到到Y的关系的关系R=(x1, y1), (x1, y2), (x2, y2) ,从从Y

26、到到Z的的关系关系S=(y1, z2), (y2, z3), (y3, z3) 则则ROS=(x1, z2), (x1, z3), (x2, z3)用关系图表示如下：用关系图表示如下：Xx3x2x1Yy3y2y1Zz1z3z2Xx2x1x3Zz2z1z3SRROS的矩阵的矩阵MRS=MR MS (其中其中” ”运算为运算为布布尔矩阵乘法，即尔矩阵乘法，即0 1 1 0 0 10 0 0定理定理1: 设设R, S, T分别表示从分别表示从X到到Y, Y到到Z，Z到到U的关系，则有的关系，则有 (ROS) OT=RO (SOT)则则MRS=MR MS =) ) )( (v vs sr rm mj

27、jk ki ij jn n1 1j ji ik k1 1 0 0 1 00 0 00 1 0 0 0 10 0 1如：如：MR=MS=2.3 逆关系逆关系 定义：定义：R为为X到到Y的关系，则的关系，则Y到到X的关系的关系:R-1:=(y, x)| (x, y) R R 称为称为R的逆关系。的逆关系。例例:设设X=1, 2, 3. Y=a, b, c R为从为从X到到Y的关系，的关系， R=(1, a), (2, b), (3, c),定理定理2:设设R, S分别为从分别为从X到到Y, Y到到Z的关系，则的关系，则RR 1)- -1 1( (1 1) )( ( (a, 1), (b, 2),

28、(c, 3)则则 R-1 =111) RSSR( ( (2)(2)TRR)M(M (3)1 3. 关系的某些性质关系的某些性质例例1: 实数集实数集R上的上的”关系是自反的。关系是自反的。例例2: 实数集实数集R上的上的”不是反自反不是反自反. 反自反反自反=不是自反不是自反. 不是自反不是自反=反自反反自反不是反自反不是反自反=自反自反是是则称则称. .，均有，均有，上的关系上的关系定义1：集合定义1：集合RRx,xXxRX )(自反自反的。的。是是则称则称. .，均有，均有，上的关系上的关系定义2：集合定义2：集合RRx,xXxRX )(反自反反自反的。的。,两条即说明两条即说明,存在既不

29、是自反存在既不是自反,又不是反自反又不是反自反的关系的关系.例例3: X=1, 2, 3, 4上的关系上的关系R R=(1, 1), (1, 2), (3, 4), (2, 2)则则R既不是自反的，也不是反自反的。既不是自反的，也不是反自反的。定义定义3: 集合集合X上的关系上的关系R，如果有，如果有(x, y) R, 必必有有(y, x) R,则称则称R是是对称对称的。的。是是则称则称，必有必有，且且有有如果如果，上的关系上的关系定义4：集合定义4：集合RRy,xyxRx,yRX )()(反对称反对称的。的。例例4：集合：集合X=1, 2, 3, 4上的关系上的关系 R1=(1, 2), (

30、2, 1) R2=(1, 2), (2, 4), (3, 2) R3=(1, 2), (2, 1), (3, 4), (4, 2)则则: R1是对称的，是对称的，R2是反对称的，是反对称的，R3既不是对既不是对称的，也不是反对称的。称的，也不是反对称的。 关关系系均均是是传传递递的的 , , 例例5 5：整整数数集集I I上上的的 定义定义3: 集合集合X上的关系上的关系R，如果有，如果有(x, y) R且且(y, z) R, 必有必有(x, z) R, 则称则称R是是传递传递的。的。Note: 从关系图及关系矩阵来判断关系的性质从关系图及关系矩阵来判断关系的性质的的主主对对角角元元均均为为1

31、 1关关系系图图每每个个节节点点均均有有环环自自反反关关系系1 1RMR 的主对角元均为0的主对角元均为0关系图每个节点没有环关系图每个节点没有环自反自反关系关系2 2RMR 反反为对称阵则必成对出现边相连，关系图两结点若有有向对称关系RMR 3相相连连，则则只只有有一一条条. .向向边边关关系系图图中中两两结结点点若若有有有有对对称称反反关关系系R R4 4 例例6 (P22. 例例2.20) 是是整整数数 2 2y yx xy y) ) ( (x x, ,: :R R自反的.自反的.是自反的，不是是自反的，不是故故; ;，即，即有有 ， 解：(1)解：(1)反反RRx,xxxxIx )(2

32、例例7 整数集整数集I上定义一个关系上定义一个关系R试验证试验证R具有哪几种性质。具有哪几种性质。是传递的.是传递的.故故, ,) )也是整数，即(也是整数，即(是整数.是整数.、则则R,R,) )、()、( (RRx,zyzyyxzxzyyxy,zx,y 22222)3(的的. .是是故故, ,) )即即( (是是整整数数, ,则则, ,对对称称）（RRy,xxyR(x,y) 224 4 关系的闭包运算关系的闭包运算定义定义1 设设 R 是集合是集合X上的一个关系，则上的一个关系，则R的的自反自反闭包是一个满足下列条件的关系闭包是一个满足下列条件的关系 R:（1 1） R是是自反自反的；的；

33、分别记为分别记为t (R) 传递闭包传递闭包s (R) 对称闭包对称闭包r (R) 自反闭包自反闭包；）（RR 2是是）若）若（ 3R. RRRR ，则必有，则必有的，且的，且思考：思考：若若R是自反（对称、传递）的，则其是自反（对称、传递）的，则其自反（对称、传递）闭包是自反（对称、传递）闭包是？“”关系关系；对称闭包是对称闭包是“”关系；关系；例例1 1 整数集整数集I 上上的的“”关系的自反闭包是关系的自反闭包是传递闭包是传递闭包是 本身本身. .定理定理1 1 设设R是集合是集合X上的关系上的关系，则则，QRRr )(),(XxxxQ 其中其中例例2 设有程序集设有程序集P=p1, p

34、2, p3, p4及其上的及其上的“调调用用”关系：关系：R=(p1, p2), (p1, p3), (p2, p4), (p3, p4)。Q=(p1, p1), (p2, p2), (p3, p3), (p4, p4)调用”)调用”) 的自反闭包.(“递归的自反闭包.(“递归为为则则RQR定理定理2 2 设设R是集合是集合X上的关系，则上的关系，则.)(1 RRRs例例3 设设X =a, b, c上关系上关系R的关系图如图所示，求的关系图如图所示，求s(R). abc解：解：由关系图由关系图 R=(a, a), (a, b), (a, c), 1)(RRRs),(),(),(),(),(ac

35、caabbaaa定理定理3 设设R是集合是集合X上的关系，则上的关系，则定理定理4 设设R是有限集合是有限集合X上的关系，并设上的关系，并设X有有n个元素，则有个元素，则有.)(321RRRRRtii .)(1iniRRt 解解：(1)例例3 设设S=a, b, c, d, 给定给定S上的一个关系上的一个关系 R=(a, b), (b, c), (c, d), (d, a)求求r (R), s (R), t (R).Q=(a, a), (b, b), (c, c), (d, d) r (R)=RQ=(a, b), (b, c), (c, d), (d, a), (a, a), (b, b),

36、(c, c), (d, d) 解解： （2）例例3 设设S=a, b, c, d, 给定给定S上的一个关系上的一个关系 R=(a, b), (b, c), (c, d), (d, a)求求r (R), s (R), t (R).1)( RRRs),(),(),(),(1adcdbcabR 1)( RRRs),(),(),(),(),(),(),(),(adcdbcabaddccbba 解解： （3）例例3 设设S=a, b, c, d, 给定给定S上的一个关系上的一个关系 R=(a, b), (b, c), (c, d), (d, a)求求r (R), s (R), t (R). R2=ROR

37、=(a, c), (b, d), (c, a), (d, b) R3=R2 OR=(a, d), (b, a), (c, b), (d, c) R4=R3 O R=(a, a), (b, b), (c, c), (d, d)t (R)=RR2R3R4=(a, a), (b, b), (c, c), (d, d), (a, b), (a, c), (a, d), (b, c), (b, d), (c, d), (d, c), (d, b), (d, a), (c, b), (c, a), (b, a)5 5 次序关系次序关系定义定义1 集合集合X上的关系上的关系R如果是自反的、反对称的、传如果是

38、自反的、反对称的、传递的，则称递的，则称R是是X上的上的偏序关系偏序关系，称，称X为为R的的偏序集偏序集，记，记为为(X,R).Note: 用用“”表示偏序表示偏序 （不作特殊说明）（不作特殊说明）是一偏序关系是一偏序关系.例例1 集合集合A的幂集的幂集(A )上的关系上的关系 例例2 整数集整数集I上的上的“”(不是偏序关系的符号不是偏序关系的符号) 是偏序关系。是偏序关系。例例3 集合集合X=2, 3, 6, 8上的整除关系上的整除关系 R=(2, 2), (3, 3), (6, 6), (8, 8), (2, 6), (2, 8), (3, 6) 是偏序的是偏序的.定义定义2 集合集合X

39、上的关系上的关系R如果是反自反的、传递的，如果是反自反的、传递的，则称则称R在在X上是上是拟序的拟序的，或称，或称R是是X上的上的拟序关系拟序关系。Note: 拟序关系一般用拟序关系一般用“”表示表示.定理定理1 集合集合X上的关系上的关系R是拟序的，则其必反对称是拟序的，则其必反对称.)(关系是拟序关系关系是拟序关系 上的上的 A”是是拟拟序序关关系系. .上上的的“整整数数集集 I定理定理2 设设R是是X上的关系，则上的关系，则 （1） 若若R是一个拟序关系，则是一个拟序关系，则r (R)是一个偏是一个偏序关系序关系. （2） 若若R是一个偏序关系，则是一个偏序关系，则R-Q是一个拟是一个

40、拟序关系序关系.定义定义3 “”是集合是集合X上的偏序，若上的偏序，若 x, y X，都有，都有xy或或y x. .则称则称“”是是X上的上的线性次序线性次序关系关系。 例例6 集合集合X=a, b, c上的关系上的关系 R=(a, b), (b, c), (a, c), (a, a), (b, b), (c, c) 则则 R首先是一个偏序关系；首先是一个偏序关系； R是一个线性次序关系。是一个线性次序关系。(a, b两元素之间不存在两元素之间不存在“ ”关系关系.) 不是线性次序的不是线性次序的.例例7 集合集合A=a, b, (A)=, a, b, a, b (A)上的上的“ ”关系，关系

41、，定义定义4 “”为集合为集合X上的偏序关系，且上的偏序关系，且Y X （2） yY，且不存在，且不存在yY， 有有y y且且 yy，则称，则称y是是Y的的极大元素极大元素；若有；若有yy，则，则称称y是是Y的的极小元素极小元素。 （1） yY，使，使 yY， 均有均有yy，则称，则称y是是Y 的的最大元素最大元素；若有；若有yy，则称，则称y是是Y的的最小元最小元素素。 Note:最大最大(小小)元素、极大元素、极大(小小)元素只在元素只在Y中讨论中讨论.上上(下下)界、上界、上(下下)确界在确界在X中讨论中讨论. 上、下界可能不唯一上、下界可能不唯一.（4）若）若 xX是是Y的上的上(或下

42、或下)界界 ，且对每一个，且对每一个Y 的上的上(或下或下)界界 x，均有，均有xx(或或xx)，则称，则称x是是Y的的上确界上确界（或（或下确界下确界）。）。（3） xX，使，使 yY， 均有均有yx，则称，则称x是是Y 的的上界上界；若有；若有xy，则称，则称x是是Y 的的下界下界。 B=a, b, b, c, b, c, ，则，则B的的例例8 集合集合A=a, b, c，(A)= , a , b , c , a, b, a, c, b, c, a, b, c上的上的“ ”关系关系是一个偏序关系是一个偏序关系 (4) 极小极小元元:(1)最大最大元元 :没有没有(2) 最小元最小元: (3

43、)(3)极大元极大元:(5) 上界上界: a, b, c(6) 下界下界 : (7)(7)上确界上确界: a, ,b, , c (8)(8)下确界下确界 : a, ,b, , b, ,c 若若B=a, c, 则它的则它的 (4) 极小极小元元:(1)最大最大元元 :没有没有(2) 最小元最小元:(3)(3)极大元极大元:(5) 上界上界:(6) 下界下界 : (7)(7)上确界上确界: a, ,c (8)(8)下确界下确界 : a, , c 没有没有 a, , c a, c, a, b, c定理定理3 “”是是X上的一个偏序关系，且上的一个偏序关系，且Y X（1） 最大最大(小小)元元 = 极

44、大极大(小小)元元（2） 最大最大(小小)元元 = 上上(下下)确界确界（3） x是上是上(下下)确界确界,且且x Y = x是最大是最大(小小)元元 方法：方法：X上的偏序关系上的偏序关系” ” 若若x y且不存在且不存在zX使使xz, z y,则将结点则将结点x画在画在y的下面；且用一线相连的下面；且用一线相连. 若若x, y不存在不存在关系，则放在同一水平线上，关系，则放在同一水平线上，不用线相连不用线相连.哈斯图分析偏序关系哈斯图分析偏序关系例例9 X=2, 3, 6, 12, 24, 36上的整除关系上的整除关系263123624由哈斯图可看出，子集由哈斯图可看出，子集Y=2, 3,

45、 6的的最大元：最大元：最小元：最小元：6无无极大元：极大元：6极小元：极小元： 2,3上界：上界： 6,12,24,36上确界：上确界：6下界：下界： 无无下确界：下确界： 无无作业：作业：P34 2.7(1)、(2) 2.8 (3) 补充：补充：设设A= , a , b , a, b上的关系上的关系“ ”. （1）画出哈斯图；）画出哈斯图； （2）求子集）求子集B1= , a 和和B2= a , b的最大的最大元、最小元、极大元、极小元、上界、下界、上确元、最小元、极大元、极小元、上界、下界、上确界、下确界界、下确界 6 相容关系相容关系定义定义1 集合集合X上的关系上的关系R，如果它是自

46、反的、对，如果它是自反的、对称的，则称此关系为称的，则称此关系为相容关系相容关系.一般用一般用“”表示表示相容关系相容关系.例例1 X=2166,243,375,648,455,关系关系R为元素间为元素间有相同的数字有相同的数字 如如(2166, 243) 则则R是相容关系是相容关系 相容关系的关系图由于边均是双向边，且各点相容关系的关系图由于边均是双向边，且各点均有环出现，故可简化均有环出现，故可简化. (具体方法：具体方法：去掉环去掉环 双向有向边双向有向边单向无向边单向无向边)如如例例1中中x1x2x3x4x5关系矩阵为对称矩阵且主对角元为关系矩阵为对称矩阵且主对角元为1.(故可故可简化

47、为下三角简化为下三角.)X=2166,243,375,648,455,关系关系R为元素间有相同的数字为元素间有相同的数字Note:X=2166,243,375,648,455,关系关系R为元素间有相同的数字为元素间有相同的数字例例2 例例1中中定义定义2 “”为集合为集合X上的相容关系且上的相容关系且A X，如，如果果 x、yA，均有，均有xy，且，且 zXA，使，使 xA均有均有xz，则称，则称A是是X的的极大相容性分块极大相容性分块。 极大相容性分块极大相容性分块在关系图中找在关系图中找“最大完全最大完全多边形多边形”. 最大完全多边形：任何两顶点之间均有最大完全多边形：任何两顶点之间均有

48、边相连，且不能再行扩充边相连，且不能再行扩充.x1, x2, x4为为X的一个极大相容性分块的一个极大相容性分块. 例例3：X=1,2,3,4,5上的相容关系上的相容关系R的关系图如下的关系图如下:13452则则R的极大相容分块为的极大相容分块为2,3,4,5和和1,3,4例例4 X=x1, x2, x3, x4, x5, R1和和R2为为X上的相容关上的相容关系，其简化图如图系，其简化图如图a, b所示，求所示，求R1和和R2的极大相的极大相容性分块容性分块.x1x2x3x4x5x1x2x3x4x5(a)(b)解解 R1：x1, x2, x5, x2, x3, x4, x5 R2：x1, x

49、2, x4, x2, x3, x4, x3, x4, x5例例5 （P30. 例例2.44）定义定义3 X上的相容关系上的相容关系“”由它的所有极大相由它的所有极大相容性分块所构成的集合成为容性分块所构成的集合成为X的的完全覆盖完全覆盖.例例6 例例3中的完全覆盖是中的完全覆盖是定理定理1 X上的每个相容关系，唯一的定义一个完上的每个相容关系，唯一的定义一个完全覆盖全覆盖.13452 2，3，4，5，1，3，4 7 等价关系等价关系定义定义1 集合集合X上的关系上的关系R，如果它是自反的、对，如果它是自反的、对称的、传递的，则称此关系为称的、传递的，则称此关系为等价关系等价关系.例例1 信息管

50、理专业学生集上的信息管理专业学生集上的“同姓关同姓关系系”. 全校学生集合上的全校学生集合上的“同班同学同班同学”关系关系. 所有三角形组成集合上的所有三角形组成集合上的“相似相似”关关系系. 52张扑克牌中的同花关系张扑克牌中的同花关系例例2 整数集整数集I上的关系上的关系R： R=(x, y)| x-y可被可被3整除整除 讨论讨论R是否为等价关系。是否为等价关系。例例3 整数集整数集I上的关系上的关系R: R=(x, y)| (x-y)能被能被m整除整除, m为正整数为正整数称此关系为称此关系为以以m为模的同余关系为模的同余关系. x R y, 记作记作 xy (mod m)定义定义2 S