《数学集合论》ppt课件

1、1 集合论集合论(Set Theory)是现代数学的基础它的起源可是现代数学的基础它的起源可追溯到追溯到16世纪末，但集合论实际发展是由世纪末，但集合论实际发展是由 19世纪世纪 70年代德国数学家康托尔年代德国数学家康托尔(G . Cantor) 在无穷序列和分在无穷序列和分析的有关课题的理论研究中创立的析的有关课题的理论研究中创立的. 集合论在计算机科学、人工智能领域、逻辑学及语言集合论在计算机科学、人工智能领域、逻辑学及语言学等方面都有着重要的应用对于从事计算机科学的学等方面都有着重要的应用对于从事计算机科学的工作者来说，集合论是不可缺少的理论知识，熟悉和工作者来说，集合论是不可缺少的理

2、论知识，熟悉和掌握它是十分必要的掌握它是十分必要的第第3章章 集合、关系与映射集合、关系与映射23.1 集合的基本概念集合的基本概念一、集合的概念一、集合的概念 把具有相同性质的所有对象汇集在一起就称为一个把具有相同性质的所有对象汇集在一起就称为一个集合集合. 把组成集合的对象称为把组成集合的对象称为元素元素。例如：例如：方程方程x210的实数解集合；的实数解集合；26个英文字母的集合；个英文字母的集合；坐标平面上所有点的集合；坐标平面上所有点的集合；3二、集合的表示二、集合的表示 一般用带下角标或不带下角标的大写字母表示集合，如一般用带下角标或不带下角标的大写字母表示集合，如 A, B, P

3、1, P2, Q1, Q2等等;一般用带标号或不带标号的小写字母表示集合，如一般用带标号或不带标号的小写字母表示集合，如 a, b, c, a1, a2,等等;3.1 集合的基本概念集合的基本概念4三、说明集合的方法三、说明集合的方法（1）列举法）列举法：如：如A=1,2,3,4，B0,2,4,6,8,10,（2）描述法）描述法：如：如A=x|P(x),P(x)是元素是元素x所具有的性质。所具有的性质。例：例：A=x|x2-5x+6=0（3）特定的字符集：）特定的字符集：在集合中常约定：在集合中常约定： N表示自然数集合；表示自然数集合；I(或或Z)表示整数集合；表示整数集合； Q表示有理数集

4、合；表示有理数集合；R表示实数集合；表示实数集合； E表示偶数集合；表示偶数集合； O表示奇数集合；表示奇数集合； P表示素数集合；表示素数集合； F表示分数集合；表示分数集合； C表示复数集合；表示复数集合； R表示正实数集合表示正实数集合； R*表示非零实数，即表示非零实数，即R*=x|xRx0; （4）图示法）图示法：用封闭曲线表示集合，封闭曲线内的点：用封闭曲线表示集合，封闭曲线内的点 表示集合中的元素表示集合中的元素3.1 集合的基本概念集合的基本概念5注意：注意：(1)集合的元素是确定的，即对集合集合的元素是确定的，即对集合A，任一元素，任一元素a或属于此集合或属于此集合(aA)或

5、不属于此集合或不属于此集合(a A) ，两者必居其一。两者必居其一。(2)集合中的每个元素均不相同。集合中的每个元素均不相同。 即集合即集合 1,2,2,3,4,4 = 1,2,3,4 (3) 集合中的元素是无序的。集合中的元素是无序的。 例：例：4,3=3,43.1 集合的基本概念集合的基本概念6包含关系：包含关系：若集合若集合B中的每个元素都是中的每个元素都是A中的元素，称中的元素，称B包含于包含于A或或A包含包含B，称集合，称集合B是集合是集合A的一个的一个子集子集记为记为B A : ( x)(xBxA) 如果如果B不被不被A包含，则记作包含，则记作B A。 例如：例如：N Z Q R

6、C，但，但Z N。 3.1 集合的基本概念集合的基本概念四、集合间的关系：相等关系和包含关系四、集合间的关系：相等关系和包含关系 结论：结论：对任何集合对任何集合A都有都有A AA。 例如：例如： Aa，a和和a的关系为的关系为 a A ，又有，又有 aA 7若若B是是A的子集且在的子集且在A中存在不属于中存在不属于B的元素，则称的元素，则称集合集合B是集合是集合A的一个的一个真子集真子集，记为，记为B A : B A( x)(xAx B ，称，称A真包含于真包含于B。3.1 集合的基本概念集合的基本概念例如：例如：N Z Q R C8相等关系：相等关系：若集合若集合A的任一元素都是集合的任一

7、元素都是集合B中的元素并且集合中的元素并且集合B中的元素也是集合中的元素也是集合A中元素，则称这两个集合中元素，则称这两个集合相等相等，记为记为AB :( x)(aA aB) 或或 AB : (A B)(B A)否则称这两个集合否则称这两个集合不相等不相等，记为，记为A B 3.1 集合的基本概念集合的基本概念9五、子集具有的性质：五、子集具有的性质： A A 自反性自反性 A BB AAB 反对称性反对称性 A BB CA C 传递性传递性证明证明: 这里仅给出的证明这里仅给出的证明, 余下类似可证余下类似可证 A BB A ( x)(x Ax B)( x)(x Bx A)( x)(x Ax

8、 B)(x Bx A)( x)(x Ax B) AB 3.1 集合的基本概念集合的基本概念10不包含任何元素的集合称为不包含任何元素的集合称为空集空集。记为。记为例如：例如：A=x|x2-1, xR对任何集合对任何集合A， A全集全集U：所有集合都是所有集合都是U的子集。的子集。3.1 集合的基本概念集合的基本概念11六、集合的运算六、集合的运算交运算：交运算： AB := x|x Ax B 3.1 集合的基本概念集合的基本概念12并运算：并运算： AB: x|x Ax B 3.1 集合的基本概念集合的基本概念13两个集合的并和交运算可以推广成两个集合的并和交运算可以推广成n个集合的并和交：个

9、集合的并和交：A1A2Anx|xA1xA2xAnA1A2Anx|xA1xA2xAn六、集合的运算六、集合的运算3.1 集合的基本概念集合的基本概念并和交运算还可以推广到无穷多个集合的情况：并和交运算还可以推广到无穷多个集合的情况：A1A2A1A2 14差运算：差运算： BA : x|x Bx A3.1 集合的基本概念集合的基本概念15全集全集U：所有集合都是所有集合都是U的子集。的子集。补集：补集：全集全集U与集合与集合A的差集称为的差集称为A的补集，的补集， 记为记为 UA=x|x A A AUA3.1 集合的基本概念集合的基本概念16对称差运算：对称差运算： AB:= x|x (AB)x

10、(BA) A B3.1 集合的基本概念集合的基本概念显然：显然： A A A B B A ABA A UAB17图形表示集合间的关系文氏图图形表示集合间的关系文氏图(Venn Digram表示表示)UA, B3.1 集合的基本概念集合的基本概念 AB181. 交换律交换律 ABBA ； ABBA2. 结合律结合律 A(BC)=(AB)C A(BC)=(AB)C3. 分配律分配律 A(BC)=(AB) (AC) A(BC)=(AB)(AC)4. 吸收律吸收律 A(AB)=A ； A(AB)=A5. De Mergam律律 6. 幂等律幂等律 AAA ; AAA7. 补余律补余律 8. 零律零律

11、A AUU9. 壹律壹律 AUA AA10. 互补律互补律 11. 重非律重非律 集合运算的算律：设集合运算的算律：设A,B,C是任意三个集合。是任意三个集合。BABA;BABA UAA;AA U;UAA 19定理：设定理：设A, B, C, D是任意三个集合。是任意三个集合。（1） 若若A B，则，则ABA ；ABB； (BA)AB（2） AB A, B; A, B AB（3） 若若A B且且C D；则；则AC BD ； AC BD （4） 若若AB ；则称；则称A，B不相交；若还有不相交；若还有ABU， 则称则称A，B为互补。为互补。 （5）若）若A B，则，则 （6） A(BC)(AB)

12、(AC) ； A(B C) (AB) (AC) (7) A (BC)(A B) (A C) 但但 A (BC) (AB) (AC) UAB,BA,AB幂集：幂集：由集合由集合A的所有子集组成的集合称为的所有子集组成的集合称为A的幂集。的幂集。 记为记为P(A)或或2A 即即P(A):B|B A例如：例如：Aa P(A)=,a A=a,b P(A)=,a,b,a,b A=,a P(A)=,a,a设设Aa1,a2,an,则则A的子集的子集B的的二进制编码二进制编码为：为：若若ai B，则，则ai记为记为1，否则记为，否则记为0，i1,2,n.按此规定得到的一个二进制数称为集合按此规定得到的一个二进

13、制数称为集合B的编码。的编码。设设|A|=n,则则P(A)= 2n21集合的应用求若干有限集合并的元素个数。集合的应用求若干有限集合并的元素个数。定理：定理：设设A1，A2是两个有限集合，是两个有限集合， 记记|A1|, |A2|为它们所含的元素个数，为它们所含的元素个数， 则则|A1A2|= |A1|+|A2| A1A2|in1i1nnkji1kjinji1jin1iin1iiA) 1(.AAAAAAA 推广：推广：例例1：假设某班有假设某班有50名学生，其中英语成绩为优的名学生，其中英语成绩为优的25名，名，数学成绩为优的数学成绩为优的20名，又有名，又有15名学生数学和英语成绩均名学生数

14、学和英语成绩均为优。问这两门课都不是优的学生有几名？为优。问这两门课都不是优的学生有几名？解：解：英语成绩为优的学生组成的集合是英语成绩为优的学生组成的集合是A；|A|=25 数学成绩为优的学生组成的集合是数学成绩为优的学生组成的集合是B；|B|=20 因此这两门可成绩均为优的学生组成的集合是因此这两门可成绩均为优的学生组成的集合是AB； | AB |=15 所以所以 | AB |=|A| +|B| AB |=25201530， 这说明两门课中至少有一门课为优的学生是这说明两门课中至少有一门课为优的学生是30名，名， 所以这两门课都不是优的学生有所以这两门课都不是优的学生有503020名名例例

15、2 2：求出在求出在1 1和和9090之间之间( (包括包括90)90)能被能被2 2，3 3，5 5 任一任一 数整除的整数个数。数整除的整数个数。解：设解：设A1，A2，A3分别为表示分别为表示1和和90之间能被之间能被2，3，5 任一数整除的整数集合。任一数整除的整数集合。 6636915183045|AAA|AA|AA|AA|A|A|A|AAA|353290|AAA|65390|AA|95290|AA|153290|AA|18590|A|30390|A|45290|A|321313221321321321323121321可可得得 所以所以 在在1和和90之间之间(包括包括90)能被能

16、被2，3，5 任一数整除任一数整除的整数个数为的整数个数为66。243.2 关关 系系定义定义1 1（笛卡尔积或直乘积）（笛卡尔积或直乘积） 设设A，B是任意两个集合，是任意两个集合， AB|xA, yB 称为集合称为集合A和和B的笛卡尔积或直乘积。的笛卡尔积或直乘积。 称为有序对或序偶对，称为有序对或序偶对，x称为序偶对的第一称为序偶对的第一 个元素，个元素，y称为序偶对的第二个元素。称为序偶对的第二个元素。 = iff a=x且且b=y25例：例：A=a,b，B=1,2,3，C=x则则 AB, BA, , , , 结论：设结论：设 |A|=n, |B|=m, 则则 | AB |=nm3.2

17、 关关 系系 (AB)C,x,x,x, ,x,x,x结论：结论： (AB)C A(BC)A(BC)a,a,a, b,b,b,26笛卡儿积运算的性质笛卡儿积运算的性质: 1. 若若A，B中有一个空集中有一个空集,则它们的笛卡儿积是空集则它们的笛卡儿积是空集, 即即 AA A 2. 当当AB且且A,B都不是空集时都不是空集时,有有 ABBA。 所以所以,笛卡儿积运算不满足交换律笛卡儿积运算不满足交换律。 3. 当当A,B,C都不是空集时都不是空集时,有有 (AB)CA(BC). 所以所以,笛卡儿积运算不满足结合律笛卡儿积运算不满足结合律。27定理定理1(笛卡儿积笛卡儿积运算运算对对或或运算运算满足

18、分配律满足分配律,即即) 设设A, B, C是任意三个集合；则是任意三个集合；则 A(BC) = (AB)(AC) /对对具有左分配律具有左分配律 A(BC) = (AB)(AC) /对对具有左分配律具有左分配律 (AB)C= (AB)(AC) /对对具有右分配律具有右分配律 (AB)C= (AB)(AC) /对对具有右分配律具有右分配律3.2 关关 系系28证明：证明： A(BC)=(AB)(AC) /对对具有左分配律具有左分配律令令x, y为分别属于集合为分别属于集合A和集合和集合BC的任意元素的任意元素, 则则 A(BC)x Ay (BC) x A(y By C)(x Ay B)(x A

19、y C) AB AC (AB)(AC) 所以：所以： A(BC)=(AB)(AC)3.2 关关 系系29定理定理2：设设A, B, C，D是任意四个集合；则是任意四个集合；则 若若A B且且C D，则，则AC BD规定：规定： AAA A,记为记为AnAn-1A例：例：A1,2 A3=A2A= 1,22 1,2 = ,1, ,2, ,1,2, ,1, ,2, ,1, ,2 3.2 关关 系系30定义定义2（二元关系）（二元关系） 设设A, B是任意两个集合，则是任意两个集合，则AB的任一子集称为从的任一子集称为从A到到B的的 二元关系二元关系(简称关系简称关系)，记为，记为R，显然，显然R A

20、B， 若若R，则称，则称x和和y有关系有关系R，记为，记为xRy; 否则否则 R，则称，则称x, y没有关系，记为没有关系，记为xRy 若若AB，则称关系，则称关系R是集合是集合A上的一个二元关系，即上的一个二元关系，即R A2； R| xA, 称称R为为A上的恒等关系，记为上的恒等关系，记为IA； 若若R，则称，则称R为空关系，记为为空关系，记为A； 若若RAAA2，则称，则称R为全域关系，记为为全域关系，记为UA； 设设|A|=n, 则则A2的序偶对一共有的序偶对一共有n2个，个，A上的二元关系一共有上的二元关系一共有 2n23.2 关关 系系31例例1：A=a,b, B=1,2,3则则R

21、1,是一个从是一个从A到到B的的(二元二元)关系。关系。同理同理 R2, 也是一个从也是一个从A到到B的的(二元二元)关系。关系。例例2：A=a, b, c,则则 IA,是一个是一个A上的恒等关系。上的恒等关系。UA ,是一个是一个A上的全域关系。上的全域关系。3.2 关关 系系32定理：定理：若若R1和和R2是是A上的关系，则上的关系，则 R1R2， R1R2， R1R2也是也是A上的关系。上的关系。1A1RUR 3.2 关关 系系证明：因为证明：因为R1和和R2是是A上的关系，则上的关系，则R1 A2， R2 A2 所以所以R1R2 A2； R1R2 A2； R1R2 A2； 故故 ，R1

22、R2， R1R2， R1R2， 也是也是A上的关系。上的关系。21A1ARUR 1R33定义定义3 设设R是从集合是从集合A到到B的一个关系，称的一个关系，称 domRx|( y)( R) 为为R的的定义域定义域。 romRy|( x)( R) 为为R的的值域值域。3.2 关关 系系例：例：R,的的 domR=a,b romR=1,2,334关系的表示关系的表示矩阵法矩阵法图形法图形法3.2 关关 系系35矩阵法：矩阵法：设两个有限集合设两个有限集合 A=x1, x2, , xm, B=y1, y2, , yn, R AB. 则对应于二元关系则对应于二元关系R有一个有一个关系矩阵关系矩阵: M

23、R=(rij)mn, 其中其中 R 否则否则这里这里i1, 2, , m， j=1, 2, , n.01ijr3.2 关关 系系36 例如例如, Ax1,x2,x3, B=y1, y2, R=, 则则: 23101001RM矩阵法矩阵法:37 例如：例如：Ax1,x2,x3,x4, A上的一个关系上的一个关系R为为 R=, 矩阵法矩阵法:0010000011000011RM38图形表示：图形表示：设设R AB。用小圆圈分别表示集合用小圆圈分别表示集合A、B中的元素，中的元素，若若R，则由，则由x向向y引一条有向边引一条有向边(或称为弧或称为弧)。关系的表示：矩阵法和图形法关系的表示：矩阵法和图

24、形法例例1: Ax1,x2,x3, B=y1, y2, R=,x3x2x1y1y239 例例2: A1,2,3,4, A上的一个关系上的一个关系R为为 R=, ,关系的表示：矩阵法和图形法关系的表示：矩阵法和图形法设设R A2。用小圆圈表示集合。用小圆圈表示集合A中的元素，中的元素，若若R，则由，则由x向向y引一条有向边引一条有向边(或称为弧或称为弧)。40关系的性质关系的性质、合成和逆合成和逆定义定义(关系的性质关系的性质)：设：设R是是A上的一个二元关系。上的一个二元关系。 R在在A中中自反自反:=( x)(x AxRx) R在在A中中非自反非自反: =( x)(x A(xRx) R在在A

25、中中对称对称:= ( x)( y) (x,y AxRyyRx) R在在A中中反对称反对称: =( x)( y)(x,y AxRyxy(yRx) R在在A中中传递传递: =( x)( y)( z)(x,y,z AxRyyRzxRy)41而而实数集合上的实数集合上的小于小于关系和集合上的关系和集合上的真包含真包含关系关系都是反自反关系。都是反自反关系。 例如例如:A上的全域关系上的全域关系UA，恒等关系，恒等关系IA 实数集合上的实数集合上的小于等于小于等于关系关系 正整数集合上的正整数集合上的整除整除关系关系 包含包含关系关系R 是给定集合族是给定集合族A上的上的自反、反自反关系举例自反、反自反

26、关系举例都是自反关系。都是自反关系。例例: 设设A=1,2,3，R1，R2，R3是是A上的关系，其中上的关系，其中R1,R2 R3, 说明说明R1，R2和和R3是否为是否为A上的自反关系和反自反关系上的自反关系和反自反关系解解: R1是自反的是自反的,R2是反自反的是反自反的,R3既不是自反的也不是既不是自反的也不是 反自反的。反自反的。结论：不自反的关系未必反自反；结论：不自反的关系未必反自反； 不反自反的关系未必自反不反自反的关系未必自反；43例如例如: A上的全域关系上的全域关系UA，恒等关系，恒等关系IA和空关系和空关系都是都是A上的对称关系。上的对称关系。恒等关系恒等关系IA和空关系

27、也是和空关系也是A上的反对称关系。上的反对称关系。但全域关系但全域关系UA一般不是一般不是A上的反对称关系，除非上的反对称关系，除非A为单元集或空集。为单元集或空集。 对称、反对称关系举例对称、反对称关系举例A44 设设A1,2,3，R1，R2，R3和和R4都是都是A上的关系，其中上的关系，其中 R1, R2, R3, R4,说明说明R1，R2，R3和和R4是否为是否为A上对称和反对称的关系。上对称和反对称的关系。 解解: R1既是对称也是反对称的。既是对称也是反对称的。 R2是对称的但不是反对称的。是对称的但不是反对称的。 R3是反对称的但不是对称的。是反对称的但不是对称的。 R4既不是对称

28、的也不是反对称的。既不是对称的也不是反对称的。 结论：结论：不对称的关系未必反对称；不对称的关系未必反对称；不反对称的关系未必对称；不反对称的关系未必对称；二元关系既可对称也可反对称；二元关系既可对称也可反对称；对称、反对称关系举例对称、反对称关系举例45反对称的另一种定义：反对称的另一种定义：R在在A中中反对称反对称: = ( x)( y)(xRyxy (yRx) /x,y A= ( x)( y)( (xRy)x=y (yRx) = ( x)( y)( (xRyyRx )x=y) = ( x)( y)(xRyyRxx=y)关系的性质关系的性质R4, 不是反对称的不是反对称的46例如例如: A

29、上的全域关系上的全域关系UA,恒等关系恒等关系IA和空关系和空关系 都是都是A上的上的传递关系传递关系。小于等于关系，整除关系和包含关系小于等于关系，整除关系和包含关系也是相应集合上的也是相应集合上的传递关系传递关系。小于关系和真包含关系是相应集合上的小于关系和真包含关系是相应集合上的传递关系。传递关系。传递关系举例传递关系举例A47设设A1,2,3，R1，R2，R3是是A上的关系，其中上的关系，其中R1,R2,R3说明说明R1，R2和和R3是否为是否为A上的传递关系。上的传递关系。解解: R1和和R3是是A上的传递关系，上的传递关系，R2不是不是A上的传递关系。上的传递关系。 传递关系举例传

30、递关系举例48利用关系的表示来判断关系的性质利用关系的表示来判断关系的性质49关系的运算：逆和合成关系的运算：逆和合成定义定义(逆运算逆运算) 设设R是从集合是从集合A到集合到集合B的二元关系的二元关系 R-1:= | xA, yB且且xRy 称为关系称为关系R的逆关系。的逆关系。 显然显然R-1是从集合是从集合B到集合到集合A的二元关系的二元关系.例：例：A1,2,3, B=a,b R=,从集合从集合A到集合到集合B的二元关系的二元关系则：则： R-1,从集合从集合B到集合到集合A 的二元关系的二元关系50定理：设定理：设R和和S是从集合是从集合A到集合到集合B的关系。的关系。 R-1是一个

31、关系是一个关系 xR-1y iff yRx (R-1)-1=R (RS)-1=R-1S-1 (RS)-1=R-1S-1 (R S)-1 =R-1 S-1证明证明 ：令：令x, y分别为集合分别为集合A和集合和集合B中的任何元素，则中的任何元素，则 若若 x(RS)-1y y(RS)x yRx ySx xR-1y xS-1y x(R-1S-1)y 根据定义知根据定义知, (RS)-1=R-1S-1关系的运算：逆和合成关系的运算：逆和合成51令令x, y分别为集合分别为集合A和集合和集合B中的任何元素，中的任何元素，则若则若x(R S)-1yy(R S)x yRx (ySx) xR-1y (xS-

32、1y) x(R-1- S-1)y 由定义知由定义知, (R S)-1=R-1- S-1.关系的运算：逆和合成关系的运算：逆和合成52定义定义 (合成运算合成运算)设设R是从集合是从集合A到集合到集合B的二元关系，的二元关系， S是从集合是从集合B到集到集合合C的二元关系，则称的二元关系，则称 R o S:=| (xAzC( y)(yB) xRyySz 为关系为关系R和关系和关系S的从的从A到到C二元关系。二元关系。例：例：令令R=, , S=, 则则 R o S =,. S o R=. R o S S o R关系的运算：逆和合成关系的运算：逆和合成53结论：结论： 关系合成运算满足结合律，不满

33、足交换律关系合成运算满足结合律，不满足交换律.特别特别, 当当 R=S时时, 记记 Rn=Rn-1 o R.关系的运算：逆和合成关系的运算：逆和合成定理定理3.2.1 设设R ，R1和和R2 是从是从A到到B的二元关系，的二元关系，(p84) S是从是从B到到C的二元关系，则有下列结论：的二元关系，则有下列结论： (1) (R o S)-1 = S-1 o R-1 (2) (R1 R2 ) -1= R1-1 R2 -1 ; /书上错书上错 (R1 R2 ) -1= R1-1 R2 -1 (3) (AB) -1= BA (4) (R1R2 ) -1= R1-1 R2 -1 ; (5) R1 R2

34、 iff R1-1 R2-1 (6) (7) (R1R2) o S = (R1 o S) (R2 o S) 练习练习 (R1R2) o S (R1 o S)(R2 o S)1111RABRRRRBAR，这里，这里，则，则若若 55利用两个关系的关系矩阵求它们的合成关系利用两个关系的关系矩阵求它们的合成关系.例：例：R,是从是从A=1,2,3到到B=a,b,c的关系的关系 S=,是从是从B=a,b,c到到C=x,y,z的关系的关系 求求 R o SR o S,56 关系的闭包运算关系的闭包运算 现在来讨论另一种重要关系现在来讨论另一种重要关系闭包闭包. 所谓闭包是指，所谓闭包是指，对于给定的关系

35、对于给定的关系R和一种性质和一种性质P, 把包含把包含R并且满足性质并且满足性质P的最小关系称为的最小关系称为R对于对于P的闭包的闭包, 记为记为P(R). 若若P是自反是自反的的, 则称则称R是是自反闭包自反闭包, 记为记为r(R), 若若P是对称的，则称是对称的，则称R是是对称闭包对称闭包, 记为记为s(R); 若若P是传递的是传递的, 则称则称R是是传递闭传递闭包包,记为记为t(R).57关系的闭包运算关系的闭包运算定义定义3.2.1设设R和和R是集合是集合A上的一个二元关系，若满足下列条件：上的一个二元关系，若满足下列条件：(1) R是自反是自反(对称对称,传递传递)关系；关系；(2)

36、 R R ；(3) 若若R也是也是A上的自反上的自反(对称对称,传递传递) 关系且关系且R R ， 则则R R , 称称R是是R的自反的自反(对称对称,传递传递) 闭包关系，闭包关系， 记为为记为为r(R)(s(R)和和t(R).结论：结论： R是包含是包含R的最小的自反的最小的自反(对称对称,传递传递) 关系。关系。58定理定理1 设设R是集合是集合A上的一个二元关系，则上的一个二元关系，则 R是自反的是自反的 iff r(R) = R R是对称的是对称的 iff s(R) = R R是传递的是传递的 iff t(R) = R关系的闭包运算关系的闭包运算59证明：证明： 只证明只证明设设R为

37、自反为自反. 由于由于R R, 取取R 为为R,以及任何包含以及任何包含R的自反关系的自反关系 R , 有有RR R, 可见可见R满足自反满足自反闭包定义闭包定义, 即即r(R) = R. 下面再给出关于闭包的三个构造性定理下面再给出关于闭包的三个构造性定理. 关系的闭包运算关系的闭包运算定理定理3.2.2 设设R是集合是集合A上的任一二元关系，则上的任一二元关系，则 r(R) = R IA s(R) = RR-1 t(R) = Ri1i 关系的闭包运算关系的闭包运算61证明证明 只证明和只证明和令令R R IA, 显然显然R R . 则则R 在在A中自反中自反. 又因又因为对于任意包含为对于

38、任意包含R的自反关系的自反关系R, 显然有显然有IA R, 因此有因此有R IA R, 即即R R. 由自反闭包定义知由自反闭包定义知, r(R) =R , 即即r(R) =R IA.首先证明首先证明 Ri t(R). 用归纳法证明如下用归纳法证明如下: 当当i1时，根据传递闭包定义时，根据传递闭包定义, R t(R); 假设当假设当i1时时Ri t(R), 欲欲证证Ri+1 t(R)。 x,y,zA, 若若 Ri+1,因为因为Ri+1 Ri o R 所以所以 y A,使得使得 Ri且且 R 由假设知由假设知 , t(R), 则则 t(R) 因此因此, Ri+1 t(R). 于是于是, Ri

39、t(R).1i1i 次证次证 t(R) Ri, 由于包含由于包含 R的传递关系都包含的传递关系都包含t(R)，且且R Ri, 因此只需证明因此只需证明Ri是传递即可是传递即可. x, y, z A, 则则 设设 Ri, Ri, 则必则必 s,t N+ 使得使得 Rs， Rt 因此因此, Rs+t ,故故 Ri 所以所以 Ri是传递的是传递的. 综上可知综上可知, t(R) = Ri.1i1i1i1i1i1i1i64推论推论 t(R) Ri，其中其中kn例例. 设设R=, 试求试求r(R), s(R)和和t(R).解解: r(R)=R IA =, s(R)=RR-1 =,1i 关系的闭包运算关系

40、的闭包运算65下面求下面求t(R), 因因A只含有只含有3个元素个元素 ，所以，所以k3. R= ,R2=R o R=,R3=R2 o R= ,于是于是 t(R)=RR2R3 =, , , 关系的闭包运算关系的闭包运算例：设例：设Aa,b,c,d, R, 则则 r(R),s(R),t(R) 为为解解: (1) r(R)=R IA =, =,., (2) s(R)=RR-1 =, =, (3) t(R)=RR2R3 =, , =, 67关系矩阵为关系矩阵为:证明证明 只给出的证明只给出的证明 因为因为r(R)=R IA, 已知已知R为对称为对称, 而而IA显然也是对称的显然也是对称的, 因此因此

41、r(R)是对称的是对称的. t(R)=RR2R3, 用归纳法证明用归纳法证明t(R)对称对称. 当当 i1时，时， R是对称的。是对称的。定理定理 R为自反为自反s(R)和和t(R)为自反为自反 R为对称为对称r(R)和和t(R)为对称为对称 R为传递为传递r(R)为传递为传递假设对于假设对于i1时时, Ri是对称是对称, 欲证欲证Ri+1是对称是对称. 令令 x, y A, 则则: xRi+1y x(Ri o R)y ( z)(xRizzRy) ( z)(zRixyRz) ( z)(yRzzRix) y(R o Ri)x yRi+1x 故故Ri+1是对称的是对称的, 于是于是t(R)是对称的

42、是对称的.70证明证明 sr(R)=s(R IA )= (R IA ) (R IA )-1 = (R IA ) (R-1(IA )-1) = RR-1 IA = s(R) IA =rs(R) (其中其中 IA = (IA )-1)闭包运算律：闭包运算律： rs(R)=sr(R) (自反对称闭包自反对称闭包等于等于对称自反闭包对称自反闭包) rt(R)=tr(R) (自反传递闭包自反传递闭包等于等于传递自反闭包传递自反闭包) st(R) ts(R) (对称传递闭包对称传递闭包包含于包含于传递对称闭包传递对称闭包)71若若R S, 则显然有则显然有s(R) s(S), t(R) t(S). 根据对

43、称闭根据对称闭包的定义包的定义, R s(R), 于是于是 t(R) ts(R) st(R) sts(R) 由于由于s(R)对称，则对称，则ts(R)亦对称亦对称, sts(R)=ts(R). 所以所以, 可得可得, st(R) ts(R) 72 注意：注意： ts(R) 不一定包含于不一定包含于st(R)例如：若例如：若R, 则则 s(R)=, ; t(R)= ts(R)=, st(R)=,73Warshall算法：求传递闭包的新方法算法：求传递闭包的新方法设设R是具有是具有n个元素的集合个元素的集合A上的任一二元关系，上的任一二元关系，由由MR 求求Mt(R)如下：如下：(1) MR M；

44、1i(2) 对于对于j1,n, 若有若有wji=1,则则wjkwjkwik (k=1,n)(3) i+(4) 若若in，则转，则转(2), 否则结束，此时否则结束，此时M即为即为R的传递闭包的传递闭包 矩阵矩阵Mt(R) 。例例: 设设Aa, b, c, d, R, 问问t(R)？练习：练习：p92(11)75 等价关系与划分等价关系与划分定义（定义（ 等价关系特殊的关系）等价关系特殊的关系）设设R是非空集合是非空集合A上的一个二元关系，上的一个二元关系，若关系若关系R自反、对称和传递，则称自反、对称和传递，则称R为为A上的等价关系上的等价关系例如：例如：实数中的实数中的等于关系等于关系；直线

45、间的；直线间的平行关系平行关系；在一群人的集合上在一群人的集合上年龄相等的关系年龄相等的关系是等价关系；是等价关系； 而而朋友关系朋友关系不一定是等价关系不一定是等价关系,因为它可能不是传递的因为它可能不是传递的. 例：例：设设A=1,2,8，如下定义，如下定义A上的关系上的关系R：R=|x，yAxy(mod 3) /模模3同余关系同余关系其中其中xy(mod 3)称作称作x与与y模模3相等相等(即即x除以除以3的余数与的余数与y除除以以3的余数相等的余数相等), 则则R为为A上的等价关系上的等价关系，因为，因为 xA，有，有xx(mod 3) x, yA，若，若xy(mod 3)，则有，则有

46、yx(mod 3) x, y, zA，若，若xy(mod 3)，yz(mod 3)，则有则有xz(mod 3)一般，若一般，若R|x,yZxy(mod k)，kN+则则R是等价关系是等价关系。定义定义: 设设R是非空集合是非空集合A上的等价关系上的等价关系,对对 xA,令令xR=y| yAxRy 则称则称xR为为x关于关于R的等价类的等价类,简称为简称为x等价类等价类.在上例中有在上例中有 0R =3R =-3R =,-6,-3,0,3,6,; 1R =4R =-2R =,-5,-2,1,4,7,; 2R =5R =-1R =,-4,-1,2,5,8,; 集合集合A=1,2,8上等价关系的关系

47、图上等价关系的关系图79商集：商集：设设R为非空集合为非空集合A上的等价关系上的等价关系, 称称 xRxA 为为A关于关于R的的商集商集,记作记作A/R 即即 A/R xRxA如上例如上例 A/R= 0R,1R,2R = ,6,-3,0,3,6,; ,5,-2,1,4,7,; ,-4,-1,2,5,8,; 80定理定理(等价类的性质等价类的性质) 设设R是非空集合是非空集合A上的等价关系，则上的等价关系，则（1） xA，xR是是A的非空子集。的非空子集。（2） x,yA，如果，如果xRy，则，则xR=yR。（3） x,yA，如果，如果 (xRy)，则，则xRyR=.（4）x|xA=A证明：证明

48、：(1) xA，xR是是A的非空子集。的非空子集。 由等价类的定义可知由等价类的定义可知, xR=y| yAxRy A。 又由于等价关系的自反性有又由于等价关系的自反性有xxR，即，即xR非空。非空。 (2) x,yA，如果，如果xRy，则，则xR=yR。 任取任取zA ，若有，若有zxR = R = R 因此有因此有RR =R = R 从而证明了从而证明了zyR. 则则 xR yR。 同理可证同理可证 yR xR，从而得到了，从而得到了xR=yR。 （3） x,yA，如果，如果 (xRy) ，则，则xRyR=. 假设假设xRyR ，则存在则存在zxRyR，从而有，从而有zxRzyR，即，即R

49、R成立。根据成立。根据R的对称性和传递性必有的对称性和传递性必有R，与，与 (xRy) 矛盾，矛盾，即假设错误，原命题成立。即假设错误，原命题成立。 （4）xR|xA=A 先证先证xR|xA A 任取任取y，yxR|xA = x(xAyxR) = yA (因为因为x A) 从而有从而有xR|xA A 再证再证A xR|xA 任取任取x，xA, xxRxA =xxR|xA 从而有从而有A xR|xA成立。成立。 综上所述得综上所述得xR|xA=A。84定义定义3.2.2 设设A是非空集合是非空集合,如果存在一个如果存在一个A的子集族的子集族 S=A1,A2,Am满足以下条件满足以下条件:(1)

50、Ai(i=1,2,m)非空非空；(2) S中任意两个不同元素交集为空；中任意两个不同元素交集为空；(3) S中中所有元素的并集等于所有元素的并集等于A；则称则称S为为A的一个划分的一个划分，且称，且称S中的元素中的元素Ai为为划分块划分块.划分划分85例例. 考虑集合考虑集合Aa, b, c, d的下列子集族的下列子集族(1) a,b,c,d 又称最大划分又称最大划分(块最多块最多)(7) ,a,b,c,d(6) a,b,c,a,d (5) a,b,c(4) a,b,c,d(3) a,b,c,d(2) a,b,c,d 又称最小划分又称最小划分(块最少块最少)86交叉划分交叉划分设设S1和和S2

51、是集合是集合A的两个划分，由的两个划分，由S1和和S2元素间元素间所有非空交集作为元素的集合称为所有非空交集作为元素的集合称为S1和和S2的的交叉划分交叉划分。例例 S1 a,b,c,d ,S2a,c,b,d的的交叉划分交叉划分为为 a,b,c,d87加细划分加细划分设设S1和和S2分别是集合分别是集合A的两个划分的两个划分,若对于若对于S1中的任一元中的任一元素素S1i，在，在S2中都存在元素中都存在元素S2j,使得使得S1i S2j,则称则称S1是是S2的的加细划分加细划分。若还有。若还有S1S2,则称则称S1是是S2的的真加细划分真加细划分。例例 S1a,b,c,d是是S2 a,b,c,

52、d的的 加细划分加细划分且为且为真加细划分真加细划分。88定理：交叉划分是原来集合的加细划分。定理：交叉划分是原来集合的加细划分。因为因为S1iS2j S1i且且S1iS2j S2j89定理：等价关系与划分的关系相互确定定理：等价关系与划分的关系相互确定把等价类的性质和划分的定义相比较，易见把等价类的性质和划分的定义相比较，易见商集就是商集就是A的一个划分的一个划分，并且不同的商集将对应于不同的划分。反，并且不同的商集将对应于不同的划分。反之任给之任给A的一个划分的一个划分S，如下定义，如下定义A上的关系上的关系R：R=|x,yAx与与y在在S的同一划分块中的同一划分块中则不难证明则不难证明R

53、为为A上的等价关系，且该等价关系所确定上的等价关系，且该等价关系所确定的商集就是的商集就是S。由此可见，由此可见，A上的等价关系与上的等价关系与A的划分是一一对应的。的划分是一一对应的。 90例：设例：设Aa,b,c,d,e,R= , , ,则集合则集合A上等价关系上等价关系R的商集为的商集为A/R=a,b,c,d,e,即为集合即为集合A的一个划分。的一个划分。反之，由划分反之，由划分a,b,c,d,e确定的集合确定的集合A上的等上的等价关系为价关系为a,ba,b,c,dc,d,ee = , , ,等价关系与划分的关系相互确定等价关系与划分的关系相互确定91例例 设设Aa1,a2,a3, 求出

54、求出A上所有的等价关系上所有的等价关系解解:R=URR=,R=IRR=, R=,92 对于对于n元集合元集合A上的全部划分个数可转化为上的全部划分个数可转化为将将n个不同个不同球放入球放入r(rn)个相同的盒中，无空盒的不同放法数，个相同的盒中，无空盒的不同放法数，由由第二类第二类Stirling数求得，记为数求得，记为S(n,r)，此递归公式为：，此递归公式为： S(n,r)=rS(n-1,r)+S(n-1,r-1). 其中：其中： S(n,0)=0, S(n,1)=1, S(n,2)=2n-1-1, S(n,n-1)= , S(n,n)=1是递归计算的基础。是递归计算的基础。例如例如,求求

55、4元集元集A上全部等价关系数上全部等价关系数,通过求通过求A的全部划分数而给出的全部划分数而给出解解:第二类第二类Stirling个数为个数为=S(4,1)+S(4,2)+S(4,3)+S(4,4) =1+(23-1)+6+1=15. 等价关系与划分等价关系与划分2nC练习：计算练习：计算5个元素个元素A上的全部等价关系数上的全部等价关系数93 定义定义(偏序关系与偏序集偏序关系与偏序集) 设设R是集合是集合A上的一个二元关上的一个二元关系系, 如果如果R具有具有自反性自反性, 反对称性和传递性反对称性和传递性, 那么称那么称R为为一个偏序关系一个偏序关系(或部分序或部分序, 或半序关系或半序

56、关系); 记为记为，并称，并称 为偏序集。为偏序集。偏序关系偏序关系94例如例如: 1.实数集合实数集合R上的小于等于关系是一个偏序关系，上的小于等于关系是一个偏序关系， 偏序集为偏序集为。2.正整数集正整数集I+关于整除关系关于整除关系D是一个偏序关系，是一个偏序关系， 偏序集为偏序集为。偏序关系偏序关系954.集合集合A=a,b,c,d,e上的关系上的关系R是一个偏序关系，偏序是一个偏序关系，偏序集集, 这里这里 R=, , , 。偏序关系偏序关系3. 集合的包含关系是一个偏序关系，集合全体集合的包含关系是一个偏序关系，集合全体S作成一作成一个偏序集个偏序集.96相容关系与覆盖相容关系与覆

57、盖定义（定义（ 相容关系特殊的关系）相容关系特殊的关系）设设R是非空集合是非空集合A上的一个二元关系，上的一个二元关系，若关系若关系R自反、对称，则称自反、对称，则称R为为A上的相容关系上的相容关系例如：例如：实数中的实数中的等于关系等于关系；直线间的；直线间的平行关系平行关系；在一群人的集合上在一群人的集合上年龄相等的关系年龄相等的关系是相容关系；是相容关系； 而而朋友关系也是朋友关系也是相容关系。相容关系。结论：等价关系是相容关系，反之不真。结论：等价关系是相容关系，反之不真。97定义定义(覆盖覆盖) 设设A是非空集合是非空集合,如果存在一个如果存在一个A的子集族的子集族 S=A1,A2,

58、Am满足以下条件满足以下条件:(1) Ai(i=1,2,m)非空非空；(2) S中中所有元素的并集等于所有元素的并集等于A；则称则称S为为A的一个覆盖的一个覆盖。结论：划分是覆盖，反之不真。结论：划分是覆盖，反之不真。相容关系与覆盖相容关系与覆盖98例例. 考虑集合考虑集合Aa, b, c, d的下列子集族的下列子集族(1) a,b,c,d(7) ,a,b,c,d(6) a,b,c,a,d (5) a,b,c(4) a,b,c,d(3) a,b,c,d(2) a,b,c,d99例：设集合例：设集合=a1,a2,a3,a4,a5,a6,a7R=, , , a1 a2 a3 a4 a5 a6 a7

59、 相容关系与覆盖相容关系与覆盖100相容关系与覆盖相容关系与覆盖定义（相容类）定义（相容类）设设R为为A上的相容关系若上的相容关系若C A，如果对于，如果对于C中任中任意两个元素意两个元素a，b，都有，都有aRb，则称，则称C是有相容关系是有相容关系R产生的相容类。产生的相容类。相容类为相容类为a1,a2,a3,a3,a4 a3,a5,a6,a5,a6,a7101相容关系与覆盖相容关系与覆盖定义（最大相容类）定义（最大相容类） 设设R为为A上的相容关系不能真包含在任何其它相上的相容关系不能真包含在任何其它相容类中的相容类，称为最大相容类。容类中的相容类，称为最大相容类。最大相容类为最大相容类为

60、a1,a2,a3,a3,a4,a5 a3,a5,a6,a7102相容关系与覆盖相容关系与覆盖定义（完全覆盖）定义（完全覆盖） 设设R为为A上的相容关系其所有最大相容类的集合上的相容关系其所有最大相容类的集合称为集合称为集合A的完全覆盖。的完全覆盖。完全覆盖为完全覆盖为a1,a2,a3,a3,a4,a5 a3,a5,a6,a7103相容关系与覆盖相容关系与覆盖定理（最大相容类）定理（最大相容类） 集合集合A上的相容关系上的相容关系R与完全覆盖存在一一对应与完全覆盖存在一一对应由完全覆盖由完全覆盖a1,a2,a3,a3,a4,a5,a3,a5,a6,a7可得可得 集合集合A上的相容关系上的相容关系