离散数学第3章

1、 Discrete MathematicsLecturer： 王振宏Email: mobile:ffice Address： 北7-1203D第第3 3章章 集合与关系集合与关系问题一日常生活中的关系： 父子关系、母子关系、祖孙关系、兄弟父子关系、母子关系、祖孙关系、兄弟关系、同学关系、同事关系、朋友关系、关系、同学关系、同事关系、朋友关系、领导与被领导关系、整除关系、三角形领导与被领导关系、整除关系、三角形相似关系、命题等价关系等相似关系、命题等价关系等如何用集合的方法来体现这些关系？如何用集合的方法来体现这些关系？问题二 北宋时，北宋时，皇帝两个亲戚平分财产时皇帝

2、两个亲戚平分财产时发生了争执发生了争执，他们不断向皇帝告状。俗，他们不断向皇帝告状。俗话说：话说：“清官难断家务事。清官难断家务事。”皇帝对此皇帝对此事大伤脑筋，于是将此事交给大臣张齐事大伤脑筋，于是将此事交给大臣张齐贤处理。结果，张齐贤很快就处理了此贤处理。结果，张齐贤很快就处理了此事，当事人都很满意，皇帝也很满意。事，当事人都很满意，皇帝也很满意。 张齐贤用的什么方法？张齐贤用的什么方法？集 合 论 集合论是研究集合的一般性质的数学分支，它研究集合不依赖于组成它的事物的特性的性质。在现代数学中，每个对象（如数、函数等）每个对象（如数、函数等）本质上都是集合本质上都是集合，都可以用某种集合来

3、定义。数学的各个分支，本质上都是在研究这种或那种对各个分支，本质上都是在研究这种或那种对象的集合的性质象的集合的性质。集合论已成为全部现代数学的理论基础。集合论的特点是研究对象的广泛性特点是研究对象的广泛性。它总结出由各种对象构成的集合的共同性质，并用统一的方法来处理。因此，集合论被广泛地应用于各种科学和技术领域。由于集合论的语言适合于描述和研究离散对由于集合论的语言适合于描述和研究离散对象及其关系象及其关系，所以也是计算机科学与工程的理论基础，在程序设计、关系数据库、排队论、开关理论，形式语言和自动机理论等学科领域中都有重要的应用。本篇主要介绍：集合集合、二元关系二元关系和函数函数，以及集合

4、的基数集合的基数问题。 集 合 论 第三章第三章集合与关系集合与关系1集合的概念和表示法2集合的运算4序偶与笛卡尔积5关系及其表示6关系的性质7复合关系和逆关系8关系的闭包运算 9集合的划分和覆盖10等价关系与等价类12序关系集 合 论第三章第三章 重点问题重点问题1 1关系的表示方法关系的表示方法（序偶、关系矩阵和关系图）（序偶、关系矩阵和关系图）2 2关系的性质判断关系的性质判断3 3关系的复合、逆和闭包运算关系的复合、逆和闭包运算 4 4等价关系和集合的划分概念等价关系和集合的划分概念，会证明一个关系，会证明一个关系是等价关系，会求等价类是等价关系，会求等价类 5 5偏序关系的概念偏序关

5、系的概念（哈斯图的画法、全序集、最（哈斯图的画法、全序集、最大（小）元、极大（小）元、上（下）界、上大（小）元、极大（小）元、上（下）界、上（下）确界）（下）确界）1集合的概念和表示法1、集合与元素 （1）集合集合：具有某种特殊性质的客体的聚合。讨论：一些不同的确定的对象之全体。客体客体：是泛指一切，可以是具体的、抽象的元素元素（成员）：属于任何集合的任何客体。符号符号：用大写英文字母表示集合，用小写英文字母或其它符号表示元素。集合：A，B.元素：a，b. 常用的集合符号常用的集合符号N：所有自然数的集合。：所有自然数的集合。 Q：所有有理数的集合。：所有有理数的集合。Z或或I：所有整数的集合

6、。：所有整数的集合。 R：所有实数的集合。：所有实数的集合。C：所有复数的集合。：所有复数的集合。1集合的概念和表示法元素与集合间的关系元素与集合间的关系： 若a是集合S中的元素，则可写成a S ；若b不是集S合中的元素，则可写成b S 。集合集合S的基数的基数(势势)：S中的元素个数。用|S|表示。有限集合有限集合：集合的基数（元素）是有限的。 无限集合无限集合：集合的基数（元素）是无限的。 1集合的概念和表示法(2)集合的表示方法:(a)枚举法枚举法 (列举法列举法) 把集合的元素列于花括号内。例：S=T,F，P=0,1,2,3,4(b)谓词公式描述法谓词公式描述法所有集合均可用谓词公式来

7、表示： S=x | p(x) 例：A=1,4= x | (x-5x+4=0) 1集合的概念和表示法(3)两个特殊集合：全集、空集定义定义如果一个集合包含了所要讨论的每一个集合，则称该集合为全集合，简称全集全集，用E表示。E=x | p(x) p(x) p(x)为任何谓词公式定义定义不拥有任何元素的集合称为空集空集，用表示。 =x | p(x) p(x) = 注意：注意： 前者是空集，是没有元素的集合；后者是以作为元素的集合。2、集合之间的关系公理公理给定二个集合A和B，当且仅当A和B具有同样的元素（成员），则A和B才是相等相等的，记作A=B并规定：（A=B）x (x A x B)例：a, b,

8、 c=b, a, a, c, c 定义定义设A、B是任意二个集合，如果集合A的每一个元素都是B的一个元素，则称A 是B的子集子集，或者说A包含于B，或者说B包含A，记作AB，或者BA。 并规定：ABBAx(x A x B)1集合的概念和表示法例：A1=1,2,3 A2=0 B=1,2,3,0 则A1、A2均为B的子集合，并记为 A1B，A2B定义定义设A、B是任意二个集合，若AB且AB，则称A是B的真子集真子集，记作AB（A真包含于B） 并规定：AB（AB AB）注意：区分区分“ ”和和“ ”的关系的关系：“”关系是指集合和该集合中元素之间的关系。 例：S=a,b,c 则a S，bS，c S而

9、“”关系是指二个集合之间的关系。 例：S1=a, b S2=a,b,1,2 则S1 S2若A不包含于B，则也可表示成AB集合上的集合上的 关系（运算）关系（运算）（1 1）对于任一集合A，则有A A。 （自反性）（自反性）（2 2）设A、B是任意二个集合，当且仅当A B和B A才有A=B。 （反对称性）（反对称性）（3 3）设A、B、C是任意集合，如果AB和BC，则AC （传递性）（传递性）故故集合上的包含关系是一个偏序关系。集合上的包含关系是一个偏序关系。1集合的概念和表示法3、幂集例：给定S1=a 则子集为，a S2=1，2 则子集为，1，2，1，2 S3= 则子集有（而不是）由此可见：给

10、定一个集合S，则必有子集，且和S一定是S的子集。 1集合的概念和表示法定义定义 设A是集合，A的所有子集（作为元素）的集合称为A的幂集幂集。记作(A)或2A 且有：(A)(=2A)=x | x A例：若A1=， 则(A1)= 若A2=a 则(A2)=，a 若A3=1，2 则(A3)=，1，2，1，21集合的概念和表示法讨论定义：(a)集合的元素个数称为集合的“基数基数”或叫“势势” |(S)|=2 |s| 为幂集(S)的基数(b) 若若A为有限集合为有限集合，则(A)也为有限集合。 若若A为无限集合为无限集合，则(A)也为无限集合。(c)一定有A (A)， (A)，即对非空集，幂集中至少有两个

11、元素：幂集中至少有两个元素：和和A。 练习题练习题P86 （6）b)、e) P86 （9）2 集合的运算 1.交集（交运算）定义定义任何二个集合A和B的交集交集AB是由A和B所共有的全部元素构成的集合，即：AB=x | x A x B定理定理 集合的相交运算是可交换可交换的和可结可结合合的，即对于任何集合A，B，C有 AB=BA （AB）C=A（BC）2 集合的运算2.并集（并运算） 定义定义 A、B是任意二个集合，A和B的并集并集AB是由A和B的所有元素构成的集合，即：AB=x xAxB。定理定理集合的并运算是可交换可交换的和可结合可结合的，即对任何A，B，C有 AB=BA （AB）C=A（

12、BC） 2 集合的运算定理定理集合的并和交运算，每一个对另一个都是可分配的。即：(1)A（BC） =（AB）（AC） (2)A（BC） =（AB）（AC） 3.相对补集：定义定义设A和B是二个任意集合，B对A的相对补集（相对补集（A-B）是由A中且不属于B的所有元素组成的集合。即：A-B=xxAxB=xxAxB 。例：设A=0，1，2 B=2，3，4 则A-B=? B-A=?A-BB-A相对补集不满足交换律。4、绝对补集（补运算 ）定义定义设E是全集，任一集合A对E的相对补集称为A的绝对补集（或称补集）记作绝对补集（或称补集）记作A（或A）。 即：A=E-A=x| xExA=x| xA例：设E

13、=a，b，c，d A=a，b 则A=？定理）定理）A是E的任一子集，则有 (1)AA=E (2)AA=2 集合的运算补集的性质：（1）（A）=A（2）（AB）=AB（3）（AB）=AB（4）=E（5）A-B=AB 例：设A=2，5，6，B=2，3，4，C=1，3，4， E=1，2，3，4，5，6 则A-B=5，6 =AB=2，5，61，5，6=5，62 集合的运算5、环和(对称差)定义定义设A、B是任意二集合，A和B的环和环和记作记作A B。即： A B=(A-B)(B-A)=(AB)(BA)或者x(A B)xx |xAxB 例：设A=2，5，6，B=2，3，4 则AB=？2 集合的运算6、文

14、氏图(1)文氏图的画法规则： 规定矩形表示E。子集用圆画在E中。(2)文氏图应用：（a）表示集合和运算的关系 可用文氏图画出各种运算。（b）证明集合恒等式证明：（AB）=AB4 序偶与笛卡尔乘积 1.序偶： 定义定义由二个具有给定次序的客体所组成的序列称为序偶序偶。记作x，y 例：XY二维平面上的一个点的坐标x，y就是一个序偶。说明：在序偶中二个元素要有确定的排列次序。即： 若ab时，则a，bb，a 若x，y=a，b（x=ay=b）下面定义n元组： 三元组三元组x，y，z=x，y，z n元组元组 x1,xn=x1，x2，x3，xn 4 序偶与笛卡尔乘积2.笛卡尔乘积定义定义设A，B为二个任意集

15、合，若序偶的第一个成员（左元素）是A的一个元素，序偶的第二个成员（右元素）是B的一个元素，则所有这样的序偶的集合称为A和和B的笛卡尔乘积的笛卡尔乘积。记作：AB=x，y|（xA）（yB）例：设A=1，2 B=a，b则AB=1，a，1，b，2，a，2，b BA=a，1，a，2，b，1，b，2ABBA 即即“ ”是不满足交换律。是不满足交换律。4 序偶与笛卡尔乘积例：设A=a，b，B=1，2，C=z 则(AB)C=a,1,a,2,b,1,b,2z =a,1,z,a,2,z,b,1,z,b,2,z A ( BC ) =a,b1,z,2,z=a,1,z,a,2,z,b,1,z,b,2,z （AB）CA

16、（BC） “ ”不满足结合律。不满足结合律。 定理定理若A，B，C是三个集合，则有(分配律分配律)： A（BC）=（AB）（AC） A（BC）=（AB）（AC） （AB）C=（AC）（BC） （AB）C=（AC）（BC） （P102） n个集合的笛卡儿乘积的定义个集合的笛卡儿乘积的定义 ：A1A2An = （A1A2）A3）An 其元素为n元组特别地，若A1A2 An A则AAA An （n个A相乘）A2= A A=,例例 A=0,1求求A2笛卡儿积笛卡儿积AA常记为常记为A2 5关系及其表示日常生活中的关系： 父子关系、母子关系、兄弟关系、同学父子关系、母子关系、兄弟关系、同学关系、同事关系

17、、朋友关系、领导与被关系、同事关系、朋友关系、领导与被领导关系、整除关系、三角形相似关系、领导关系、整除关系、三角形相似关系、命题等价关系等命题等价关系等以上为二个客体之间的关系。祖孙关系祖孙关系等是三个客体之间的关系。5关系及其表示序偶序偶a，b实际上反映了二个元素之间的关系，关系反映了事物的结构关系反映了事物的结构。1.关系：指事物之间（客体之间）的相互联系。日常生活中的关系：父子关系、母子关父子关系、母子关系系等为二二个客体之间的关系。祖孙关系是三三个客体之间的关系（父子关系和父子关系的合成）。n元笛卡尔积A1A2An是n元关系。 5关系及其表示定义若|,22112121AxAxxxAA

18、则A1A2 的任何一个子集是一个二元关系二元关系。即：序偶作为元素的任何集合是一个即：序偶作为元素的任何集合是一个二元关系。二元关系。 ),(|)(RyxyxRdom设设ran(R)是所有客体是所有客体y的集合，对于一些的集合，对于一些X来说，若有来说，若有 Ryx ,，则称集合，则称集合ran(R)是是R的的值域值域,即：即： ),(|)(RyxxyRran例：例：X=1,2,3,4,5,6, R为为X到到Y的二元关系的二元关系, 4, 3, 2, 1dcbaR,fa,b,c,d,eY ，则，则 ,)(,4 , 3 , 2 , 1)(dcbaRranRdom2关系的定义域和值域：关系的定义域

19、和值域：定义定义：设：设R是一个二元关系，是一个二元关系，dom(R)是所有客体是所有客体x的集合，对于一些的集合，对于一些y来说，若有来说，若有 ，则称，则称dom(R)为为R的的定义域定义域，即，即 Ryx ,一般情况，称一般情况，称X为为R的的前域前域，称，称Y为为R的的陪域陪域。 5关系及其表示xRyRyx ,Ryx ,例：二元关系定义如图：, 4, 3, 2, 1dcbaR3关系表示方法关系表示方法（1）枚举法（直观法、列举法）枚举法（直观法、列举法）设R表示二元关系，用 表示特定的序偶， 若 ，则也可写成：x R y。可写成：5关系及其表示（2）谓词公式表示法）谓词公式表示法 前面

20、讲述，一个集合可用谓词公式来表达，所以关系也可用谓词公式来表达。例：实数集合R上的“”关系可表达为： 大于关系：“”= 父子关系：“F”=)( |,yxRyRxyx|,的父亲是yxyx（3）关系矩阵表示法）关系矩阵表示法 规定：(a)二元关系中的序偶中左元素表示行，右元素表示列；(b)若 ，则在对应位置记上“1”，否则为“0”。ijx Ry5关系及其表示5关系及其表示例 ：设并定义为1 , 22 , 31 , 33 , 42 , 41 , 41R10000100011001110RM的关系是R,4 , 3 , 2 , 1列出关系矩阵：例：设X=a,b,c,Y=1,2, R2是的关系， 2 ,1

21、 ,2 ,1 ,2 ,1 ,2ccbbaaYXR3R（4）关系图表示法）关系图表示法规定：(a)把、集合中的元素以点的形式全部画在平面上；(b)若 ，则xi和yj之间画一箭头弧线，反之不画任何联线。 ijx Ry1,4 , 3 , 2 , 1RX 1 , 22 , 31 , 33 , 42 , 41 , 41R用关系图表示：例： 是X中的二元关系，（4）关系图表示法）关系图表示法规定：(a)把、集合中的元素以点的形式全部画在平面上；(b)若 ，则xi和yj之间画一箭头弧线，反之不画任何联线。 ijx Ry（4）关系图表示法）关系图表示法规定：(a)把、集合中的元素以点的形式全部画在平面上；(b

22、)若 ，则xi和yj之间画一箭头弧线，反之不画任何联线。 1,| 2,13,13,24,14,2 Sx yxXyYxy 2 , 41 , 1|,22yxYyXxyxS2 , 21 , 1|,3yxYyXxyxS关系和笛卡尔乘积关系和笛卡尔乘积 笛卡尔乘积的任何子集都可以定义一笛卡尔乘积的任何子集都可以定义一种二元关系种二元关系。例：X=1,2,3,4，Y=1,2，则 2 , 4,1 , 4,2 , 3,1 , 3,2 , 2,1 , 2,2 , 1,1 , 1YX321,SSS均为二元关系。 ,|,XyxyxXXEiix空集也是 的一个子集，它也定义了一种关系，称为空关系空关系用 表示； XX

23、 X集合中的恒等关系恒等关系，|,XxxxIiiix特殊关系：全域关系，空关系，恒等关系特殊关系：全域关系，空关系，恒等关系定义定义：集合X2定义了X集合中集合中的一种关系，通称为X中的全域关系全域关系，用Ex表示：X在全域关系和恒等关系中：（1）前域=定义域（2）陪域=值域。 例：=，则 ,FFTFFTTTEx,xIT TF F 同一域上的关系同一域上的关系, ,可进行集合的所有运算。可进行集合的所有运算。 练习P110:（5）b)注意：要求写出关系矩阵和关系图6关系的性质自反性与反自反性：自反性与反自反性： 定义定义：设是集合中的二元关系，对于每一个（所有的） ，有 ，则称是自反自反关系关

24、系。XxxRx)(xRxXxx例：设 ,cbaX ,baccbbaaR是自反的关系。 R的关系矩阵 001010110RMX中R是自反的6关系的性质定义定义：设R是X中的二元关系，对于每一个 ，有x x，则称R是反自反反自反的关系，表示成：R是X中的反自反的关系。Xx(,)x xXx xR例：设X=1,2,3, 1 , 22 , 11S2 , 12S1 , 23S000100000,000000010,000100010321SSSMMM6关系的性质2 , 31 , 31 , 21 , 14S110100100RMS4既不是自反的，又不是反自反的6关系的性质小结：自反性与反自反性的不同组合：小

25、结：自反性与反自反性的不同组合：1自反的且不是反自反2反自反的且不是自反3既不是自反的，又不是反自反的?既是自反的，又是反自反的6关系的性质小结：自反性与反自反性的不同组合：小结：自反性与反自反性的不同组合：1自反的且不是反自反2反自反的且不是自反3既不是自反的，又不是反自反的4既是自反的，又是反自反的若 X，则X上的空关系 满足自反，反自反满足自反，反自反6关系的性质对称性与反对称性对称性与反对称性定义定义：设：设R R是是X X中的二元关系，对于每一个中的二元关系，对于每一个来讲，如果每当有来讲，如果每当有xRyxRy，则必有，则必有yRxyRx，则称，则称R R是是X X中的中的对称关系

26、对称关系，并表示成：并表示成：R R是是X X中的对称关系中的对称关系 Xyx,)(yRxxRyXyXxyx例：设X=1,2,3,R=, 则R是对称的关系010101110RM6关系的性质X上的全域关系全域关系： ,4bcaccbabcabaccbbaaR是自反的，对称的 例：X=a,b,c即当且仅当 )(yxyRxxRyXyXxyxX中的R才是反对称的。 讨论定义：（1）前件 yRxxRy 为“T”， 则x=y也为“T”,则为反对称的； （2） 前件 yRxxRy 为“F”， 则有三种情况：后件（x=y）不论是真还是假，命题公式为“T”。 下面举例说明：定义定义：设R是X集合中的二元关系，对

27、于每一个 来讲，如果每当xRy和yRx就必有x=y，则称R是反对称的关系反对称的关系。Xyx,问题二 北宋时，北宋时，皇帝两个亲戚平分财产时皇帝两个亲戚平分财产时发生了争执发生了争执，他们不断向皇帝告状。俗，他们不断向皇帝告状。俗话说：话说：“清官难断家务事。清官难断家务事。”皇帝对此皇帝对此事大伤脑筋，于是将此事交给大臣张齐事大伤脑筋，于是将此事交给大臣张齐贤处理。结果，张齐贤很快就处理了此贤处理。结果，张齐贤很快就处理了此事，当事人都很满意，皇帝也很满意。事，当事人都很满意，皇帝也很满意。 张齐贤用的什么方法？张齐贤用的什么方法？6关系的性质例：设X=a,b,c,1accbbaR,2ccb

28、baacaR,3accbaaR均是反对称反对称的100001100,001010101,100001010321RRRMMM6关系的性质010001101,00010101021RRMM例：X=a,b,c,1cbabbaR,2cabccbaaR关系R1、R2不是对称的，也不是反对称不是对称的，也不是反对称的小结：对称性与反对称性的不同组合：小结：对称性与反对称性的不同组合：1对称的且不是反对称2反对称的且不是对称3既不是对称的，又不是反对称的？既是对称的，又是反对称的6关系的性质0010101003RMX上的恒等关系恒等关系 ,3ccbbaaR是自反、对称、反对称自反、对称、反对称的。 例：X

29、=a,b,cX上的空关系空关系是反自反、对称、反对称的。 小结：对称性与反对称性的不同组合：小结：对称性与反对称性的不同组合：1对称的且不是反对称2反对称的且不是对称3既不是对称的，又不是反对称的4既是对称的，又是反对称的6关系的性质传递性：传递性： 定义定义：设R是X中的二元关系，对于每一个 Xzyx,来说，如果每当 yRzxRy ，就必有 xRz则称R是可传递可传递的，并表示成：X中R可传递 )(xRzyRzxRyXzXyXxzyx讨论定义：（1）前件 yRzxRy 为“T”， 则xRz也为“T”，R是可传递的； （2）前件为“F”，有三种情况后件不论是真还是假，命题为“T”，则R是可传递

30、的 6关系的性质 例：设X=a,b,c，则下列关系是否可传递的？,1cbcabaaaR,2baR,3cabaR4R6关系的性质下列关系是否可传递的：,4accaaaR,5accbbaR6关系的性质确定二元关系性质举例确定二元关系性质举例（1）设X=1,2,3，3 , 13 , 22 , 11R反自反，反对称，可传递的； 3 , 22 , 11 , 12R反对称的； 6关系的性质（2）若 X，则X上的空关系 自反的，反自反的，对称的，反对称的，可传递的。练习题P113:（1）注意：要求判断这些关系是否满足学过的5种性质7复合关系和逆关系关系的复合关系的复合定义定义：设 YX （R关系）， ZY

31、（S关系）， 于是可用 ZX （R S） 的关系，称 R S为R和S的复合关系，并规定为： ),(|,SzyRyxYyyZzXxzxSR7复合关系和逆关系,RSSR“ ”是不可交换的。讨论：（1）RS为新的二元关系（2） RSXZ（3）当R与S，才有 RS例：设A=1,2,3,4,5，R,S均为AA的关系，且R=,S=,则R S=,， S R=,7复合关系和逆关系定理定理：设 WZYXRRR321则有： 321321321)()(RRRRRRRRR可见合成关系图 下面定义关系R复合 的幂次7复合关系和逆关系定义定义给定集合X，R是X中的二元关系，设 Nn于是R的n次复合( )nR可以定义成：（

32、1） (0)R=X集合中的恒等关系 （2） (1)( )nnRRR例：设R,S是 I中的二元关系，且 |7 ,|2 ,IxxxSIxxxR则：|14,|14,IxxxRSIxxxSR7复合关系和逆关系(2),Ra cb ac b (2),4|RxxxI (2),49|SxxxI (3)(2),8|RRRxxxI ,accbbaR,cbaX 例：(3)(2),xRRRa ab bc cI (4)(3)RRRR若|X|=n，则X中的二元关系R的幂次值是有限的。一般不用求出超过X的基数次幂。 7复合关系和逆关系逆关系逆关系 定义定义：设X,Y是二个集合，若R是XY的关系，从YX的关系，称为R的逆关系

33、，用 表示。 ,|,cRy xx yR 讨论定义：（1）只要将R中每一个序偶中的元素全部调换位置， 就可得到R的逆关系（2）设 的关系矩阵为 的转置矩阵； cRRMM（3）在R的关系图中，只要把所有箭头改换方向就可得到的关系图。（自回路箭头改变与否无关） cRcRcR7复合关系和逆关系例：X=0,1,2，R=, cR=,110100001 ,100 ,001011cRRMM定理定理 设设R是集合是集合A上的二元关系，则上的二元关系，则(1) R是是自反自反的当且仅当的当且仅当IA R(2) R是是反反自反自反的当且仅当的当且仅当RIA=(3) R是是对称对称的当且仅当的当且仅当R=Rc(4)

34、R是是反对称反对称的当且仅当的当且仅当RRc IA(5) R是是传递传递的当且仅当的当且仅当R(2) R关系性质判断的充要条件8关系的闭包运算引例：设X=a,b,R=,，R 不是自反的，问题：是否可以加上一些序偶让R变成自反是R的一种运算？如：R=,R=, ,显然R比R更小些，如果这样的R具有唯一性，则R就具有一定的研究价值。8关系的闭包运算定义定义：给定集合X，R是X中的二元关系，若有另一R满足下列条件： （1）R是自反的（对称，可传递的）； （2） RR （3）对于任一自反（对称，传递的）关系R，若 RR ，则 RR 则称R是R的自反（对称，传递的）闭包自反（对称，传递的）闭包，并依次用r

35、(R),s(R),t(R)来表示之。8关系的闭包运算讨论定义： （1）已知一个集合中的二元关系R，则r(R),s(R),t(R)是唯一的，它是包含R的最小的自反（对称，传递）关系； （2）若R是自反（对称，传递）的，则r(R),s(R),t(R)就是R本身。 （3）若R不是自反（对称，传递）的，则我们可以补上最少序偶，使之变为自反、对称、传递关系，从而得到r(R),s(R),t(R)；8关系的闭包运算例：设X=a,b,R=,， 求r(R),s(R),t(R)r(R)=,s(R)=,t(R)=,=R 定理定理 设设R是集合是集合A上的二元关系，则上的二元关系，则(1) R是自反的，当且仅当是自反

36、的，当且仅当r( R )=R；(2) R是对称的，当且仅当是对称的，当且仅当s( R )=R；(3) R是传递的，当且仅当是传递的，当且仅当t( R )=R。 二二、闭包的、闭包的构造构造 定理定理 设设R是集合是集合A上的二元关系，上的二元关系，IA是是集合集合A上的恒等关系，则上的恒等关系，则 (1) r(R)=RIA (2) s(R)=RRc (3) t(R)= RR(2)R(3) 推论推论 设设A是元素个数为是元素个数为n的有限集合，的有限集合，R AA，则，则t(R)= RR(2)R(3)R(n)例：设X=a,b,c,R=,，求r(R),s(R),t(R)解：r(R)= ,xRIa

37、bb cc aa ab bc c s(R)= ,cRRa bb ab cc bc aa c t(R)= RR(2)R(3)R(n)=?(2),Ra cb ac b ,accbbaR(3)(2),xRRRa ab bc cI (4)(3)RRRRt(R) = RR(2)R(3)=,9集合的划分和覆盖集合的划分和覆盖9集合的划分和覆盖集合的划分和覆盖定义定义：给定一非空集合，又设 ,21mAAAA若（1） ),2 , 1( ,miSAi（2） miiSA1则称A为S的覆盖覆盖。 例：S=a,b,c，下面哪些是S的覆盖？ A=a,b,c， B=a,a,b,c， C=a,b,b， D=a,a,b,d,

38、c， E=a,b,c， F=a,b,a,c 9集合的划分和覆盖集合的划分和覆盖定义定义：给定一非空集合S，设非空集合 ,21mAAAA如果有： ),2 , 1( ,) 1 (miSAi(3)ijAA 或 jiAA 1(2)miiAS（i,j=1,2,m） 则称集合A是集合S的一个划分划分。例：S=a,b,c，下面哪些是S的划分？ A=a,b,c， B=a,a,b,c， C=a,b,b， D=a,a,b,d,c， E=a,b,c， F=a,b,a,c 9集合的划分和覆盖集合的划分和覆盖讨论定义： （1）划分和覆盖主要差别主要差别在第（3）条； （2）划分A中的元素，称为划分的类划分的类，在定义中

39、 均是A中的一个类，类的个数称为划分的秩划分的秩；（3）若A为有限集合，则A的秩是有限的，为|A|， 若A为无限集合，则划分的秩是无限的；（4）集合的划分必定是覆盖，而覆盖不一定是划分；（5）集合S上的秩最大的划分称最大划分最大划分，最小的称最小最小划分划分。mAAA21,9集合的划分和覆盖集合的划分和覆盖例：设S=a,b,c，下列 iA均为S的一个划分：,1cbaA 类有二个a,b,c, |1A=2（秩）； ,2cbaA 类有二个a ,b ,c, |2A=2（秩）； ,3bcaA 类有二个a,c,b, |3A=2（秩）； ,4cbaA 最大划分，秩为3=|S|； ,5cbaA 最小划分，秩为

40、1。 9集合的划分和覆盖集合的划分和覆盖定义定义：设A和A是非空集合S的二种划分，并可表示成： , 1miiAAnijAA1若A的每一个类 jA都是A的某一个类 iA的子集，则称划分A是划分A的加细，或讲A加细了A。 讨论定义： A加细了A，一定有|A|A|（秩）例：S=a,b,c,d,S的划分：A=a,b,c,d,A=abc,d，则A是A的加细 A=abcd,则A 是A的加细A 也是A的加细，A 也是A的加细。例：考虑下列关系的性质：（2）人类 中的同姓关系（3）命题集合上的等价关系 （1）实数（或I、N集上）集合上的 “=”关系（相等）10等价关系与等价类等价关系与等价类定义定义：设X是一

41、个集合，R是X中的二元关系，若R是自反的，对称的和可传递的自反的，对称的和可传递的，则称R是等等价关系价关系。例：下列关系均为等价关系（1）实数（或I、N集上）集合上的 “=”关系（相等）（2）人类 中的同姓关系（3）命题集合上的等价关系例：设X=1,2,3,4,5,6,7， 3,|,yxXyxyxR为整数10等价关系与等价类等价关系与等价类试验证R是等价关系。10等价关系与等价类等价关系与等价类(mod3)xy记作：333xyxyIxy实际上，故称作 与 模3同余，或模3相等,3xxxRI对任意，自反性成立,33xyyxxyRII对任意 ，若，则， 对称性成立, ,33333xyyzx y

42、zRIIxzxyyzI 对任意若，则传递性成立R满足自反、对称和可传递的，R是一等价关系画出R的关系图，列出R的关系矩阵 解：（1）R=,（2）R的关系矩阵 1001001001001001001001001001001001001001001001001RMR满足自反、对称和可传递的，R是一等价关系10等价关系与等价类等价关系与等价类定义定义：设R是X集合中的等价关系，对于任何的 Xx来讲，可把集合 XxR规定成： |yRxXyyxR并称是由 Xx生成的R等价类等价类。讨论定义： （1）等价类 Rx是一个集合，由定义中可见 XxR（2） Rx中的元素是在等价关系R中，所有与x 具有关系的元素

43、所组成的集合，且 Rx10等价关系与等价类等价关系与等价类例：设X=a,b,c,d,R是X中的等价关系，R=,则 RRddcc,RRbbaa,定理定理：设X是一个集合，R是X中的等价关系，则（1）若 Xx，则 Rxx（3）对于所有的 Xyx,，或者 RRyx或者 RRyx（2） XxRXx10等价关系与等价类等价关系与等价类例：设X=N，关系R= )(|,yxXyXxyx可被3整除 是一等价关系， 则R可以找出三个等价类：R0=0，3，6，9，此集合中的元素除以3的余数为“0”； R 1 =1，4，7，10，此集合中的元素除以3的余数为“1”；R2=2，5，8，11，此集合中的元素除以3的余数

44、为“2”。10等价关系与等价类等价关系与等价类定理定理：设X是一非空集合，R是X中的等价关系，R等价类的集合xR| x X是X的一个划分，且此集合称为X按R的商集，用 RX表示之。例：设X=x1,x2.xn （1）X集合中的全域关系， XXR1，它是一个等价关系， XxR1| |1XxRX按 R1的商集1|,|11RXXxxRXR它形成了X的一个最小划分 10等价关系与等价类等价关系与等价类（2）X中的恒等关系 xIR 2|22XxxRXR221RnRxx),(21Xxxxn它形成了X的一个最大划分 例：X为全班同学的集合，|X|=n, (nN)（1）同学关系R1是一个等价关系， 1XRX（2

45、）按指纹的相同关系R2是一个等价关系， 2212RnRxxRX它形成了全班同学的最大划分 （3）同姓关系R3是一等价关系3RX张 R3，李R3，它形成了全班同学的既不是最大，又不是最小划分定理定理：X是一非空集合， A为X的一个划分，且A=A1,A2,.An，则由A导出的X中的一个等价关系)(1iiniAAR例：Xa,b,c,d，A=a,b,c,d则 R(a,b a,b)(c,d c,d) =, 由此我们看到：集合X上的等价关系与X的划分之间有对应关系。10等价关系与等价类等价关系与等价类例：设X=1,2,3,4,5,6,7，A=1,4,7,2,5 ,3,6,求A对应的等价关系。讨论下列关系的

46、性质：兄弟关系兄弟关系同学关系同学关系同事关系同事关系朋友关系朋友关系三角形相似关系三角形相似关系命题等价关系等命题等价关系等11相容关系相容关系11相容关系相容关系定义定义：给定一个集合X，R是X中的二元关系，如果R是自反、对称自反、对称的，则称R是相容关系相容关系。 例：设X=ball,bed,dog,let,egg,5个英文单词定义X中一个二元关系：R= yxXyxyx,|,有相同的字母 则R是自反的，对称的，但不可传递(ball R bed) (bed R egg) (ball R egg) 则R=, , , 讨论下列关系的性质：领导与被领导关系领导与被领导关系正整数集上整除关系正整数

47、集上整除关系大于等于关系（小于等于关系）大于等于关系（小于等于关系）大于关系（小于关系）大于关系（小于关系）祖先关系（后代关系）祖先关系（后代关系）父子关系（母子关系）父子关系（母子关系）12序关系 12序关系 定义定义：设R是P中的二元关系，如果R是自反的，自反的，反对称和可传递的反对称和可传递的，则称R是P中的偏序关系（或称偏序），并用符号“”表示，而序偶P，则称为偏序集合偏序集合。下列关系哪些是偏序关系：领导与被领导关系领导与被领导关系正整数集上整除关系正整数集上整除关系大于等于关系（小于等于关系）大于等于关系（小于等于关系）大于关系（小于关系）大于关系（小于关系）祖先关系（后代关系）祖

48、先关系（后代关系）父子关系（母子关系）父子关系（母子关系）（3）R是集合P中的偏序关系，则 R也是P中的偏序关系，即R用“”表示， R则用“”表示； （4）若P，是一个偏序集合，则P，也一定是偏序集合，且偏序集合是一个序偶，左元素为集合P，右元素为偏序关系。（1）“”不单纯意味着在实数中的关系，而是代表更为普遍的关系（具有自反，反对称和可传递性的关系）；（2）若 Pyx,，“xy”读作： “x小于或等于y”“y包含x”“x在y的前面”等；讨论定义：12序关系例：8 , 6 , 3 , 24I4I中的“”（整除）=,而“”（整倍数）=,均是偏序关系。 12序关系定义定义：R是集合X中的二元关系，

49、若R是反自反的，反对称的和可传递的，则称R是拟序关系拟序关系（串序），并用符号“”表示。而X,称为拟序集合拟序集合。讨论：拟序关系也可用偏序关系来定义： yxyxyxyxyxyx大于关系、小于关系、祖先关系、后代关系等都大于关系、小于关系、祖先关系、后代关系等都是拟序关系是拟序关系12序关系定义定义：设P，是一个偏序集合，若对于每一个 Pyx,，或者xy，或者yx，即 )(xyyxPyPxyx，则“” 称为全序关系全序关系，而P，称为全序集合全序集合（线序集合线序集合）。 定义定义：在偏序集合P，中，若 Pyx,且具有xy或yx，则称x和y是可以比较可以比较的，否则称x,y是不可比较不可比较的。 推论推论：在偏序集合中，一般情