《《离散数学]》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《离散数学]》PPT课件.ppt（133页珍藏版）》请在三一办公上搜索。
1、集 合 论,由于集合论的语言适合于描述和研究离散对象及其关系，所以也是计算机科学与工程的理论基础，在程序设计、关系数据库、排队论、开关理论，形式语言和自动机理论等学科领域中都有重要的应用。本篇主要介绍：集合、二元关系和函数，以及集合的基数问题。,集 合 论,第三章集合与关系,1集合的概念和表示法2集合的运算4序偶与笛卡尔积5关系及其表示6关系的性质7复合关系和逆关系8关系的闭包运算,9集合的划分和覆盖10等价关系与等价类11相容关系12序关系,1集合的概念和表示法,1、集合与元素（1）集合：就是把人们直观的或想象中的某些确定的能够区分的对象汇合在一起组成的一个整体。讨论：一些不同的确定的对象之
2、全体。例：1000以内的素数的集合；这个班里高个子学生的集合；（不是集合）元素（成员）：组成集合的各个对象。符号：用大写英文字母表示集合，用小写英文字母或其它符号表示元素。集合：A，B.元素：a，b.,1集合的概念和表示法,元素与集合间的关系：若a是集合S中的元素，则可写成a S；若b不是集S合中的元素，则可写成b S。集合S的基数(势)：S中的元素个数。用|S|表示。有限集合：集合的基数（元素）是有限的。无限集合：集合的基数（元素）是无限的。,1集合的概念和表示法,本书中常用集合符:Im(m1)有限个正整数的集合1,2,3m Nm(m0)有限个自然数的集合0,1,2m 以上是有限集合,下面是
3、无限集合：N 自然数集合 0,1,2 I+正整数集合 1,2,3 I 整数集合-1,0,1,2 P 素数集合 大于1的正整数，只能被1和自己整除 Q 有理数集合 i/j.i、j均为整数且j0 R 实数集合 有理数、无理数 C 复数集合 a+bi，a、b可为实数,1集合的概念和表示法,(2)集合的表示方法:(a)枚举法(列举法)把集合的元素列于花括号内。例：命题的真假值组成的集合：S=T,F自然数0,1,2,3,4五个元素的集合：P=0,1,2,3,4(b)谓词公式描述法所有集合均可用谓词公式来表示：S=x|p(x),1集合的概念和表示法,例：大于10的整数的集合：S1=x|x I x10 偶整
4、数集合：S2=x|y(y I x=2y)有限个元素集合：S3=1,2,3,4,5=x|x I(1 x 5)S4=F,T=x|x=T x=F S5=1,4=x|(x-5x+4=0)(c)同一集合可以用多种不同的形式表示。(d)集合也可作为某一集合的元素。例：S=a,1,2,p,q,1集合的概念和表示法,(3)三个特殊集合：空集、全集合、集合族定义如果一个集合包含了所要讨论的每一个集合，则称该集合为全集合，简称全集，用E表示。E=x|p(x)p(x)p(x)为任何谓词公式定义不拥有任何元素的集合称为空集（或称零集），用表示=x|p(x)p(x)=注意：前者是空集，是没有元素的集合；后者是以作为元素
5、的集合。,1集合的概念和表示法,定义集合中的元素均为集合，称这样的集合为集合族。例A=a，b，c、d2、集合之间的关系公理给定二个集合A和B，当且仅当A和B具有同样的元素（成员），则A和B才是相等的，记作A=B并规定：（A=B）x(x A x B)例：a,b,c=b,a,a,c,c,1集合的概念和表示法,例：a,b,c=b,c,a例：设P=1,2,4，Q=1,2,4，则PQ定义设A、B是任意二个集合，如果集合A的每一个元素都是B的一个元素，则称A 是B的子集，或者说A包含于B，或者说B包含A，记作AB，或者BA。并规定：ABBAx(x A x B),1集合的概念和表示法,例：A1=1,2,3
6、A2=0 A3=1,2,3,0 B=1,2,3,0 则A1、A2、A3均为B的子集合，并记为 A1B，A2B，A3B定义设A、B是任意二个集合，若AB且AB，则称A是B的真子集，记作AB（A真包含于B）并规定：AB（AB AB）,1集合的概念和表示法,注意：区分“”和“”的关系：“”关系是指集合和该集合中元素之间的关系。例：S=a,b,c 则a S，bS，c S而“”关系是指二个集合之间的关系。例：S1=a,b S2=a,b,1,2 则S1 S2若A不包含于B，则也可表示成AB定理设E是全集，A是一个集合，则一定有AE。,1集合的概念和表示法,定理设A、B是任意二个集合，当且仅当A B和B A
7、才有A=B。证明：()充分性：（A=B）（A B B A）(A=B)x(x A xBxB xA)x(xA xB)x(xB xA)(AB)(BA)()必要性：ABBAA=B(AB)(BA)x(xA xB)x(xB xA)(A=B),1集合的概念和表示法,推论对于任一集合A，则有A A。定理设A、B、C是任意集合，如果AB和BC，则AC。推论若AB和BC，则AC。定理设有空集和任一集合A，则A证明：设xA，要证明A，只要证：x(x xA)为“T”中没有元素，x为假，x（x xA）为“T”定理 是唯一的。,1集合的概念和表示法,证明：设有二个空集合1和2 是任何集合的子集（1 22 1）(1=2)3
8、、幂集和索引集合（1）幂集：例：给定S1=a 则子集为，a S2=1，2 则子集为，1，2，1，2 S3=则子集有（而不是）,1集合的概念和表示法,定义 设A是集合，A的所有子集（作为元素）的集合称为A的幂集。记作(A)或2A 且有：(A)(=2A)=x|x A例：若A1=，则(A1)=若A2=a，则(A2)=，a 若A3=1，2，则(A3)=，1，2，1，2注：|(S)|=2|s|为幂集(S)的基数,1集合的概念和表示法,（2）索引集合 为了在计算机上表示集合，必须给每一个集合的元素加上标记，以用来表示元素在集合中的位置。例：S1=a，b 假设集合S1中，a,b的位置已经固定。则用二进制下标
9、法来表示S的所有子集：=B00，a=B10，b=B01，a，b=B11这样(S1)=B00，B01，B10，B11=Bi|iJ 而其中J=00，01，10，11（索引集合或指标集合）,1集合的概念和表示法,例：已知集合S=a1，a2，a3，a4，S的子集有24 个 可以分别表示成B0，B1B(24-1)则B7=B0111=a2，a3，a4 B15=B1111=a1，a2，a3，a4,2 集合的运算,1.交集（交运算）定义任何二个集合A和B的交集AB是由A和B所共有的全部元素构成的集合，即：AB=x|x A x B例：A=a，b B=a，c AB=a定理 集合的相交运算是可交换的和可结合的，即对
10、于任何集合A，B，C有 AB=BA，（AB）C=A（BC）证明：设x是AB中任一元素 则x ABx x|x A x B x x|x B x Ax BA AB=BA,2 集合的运算,定理设A是E的任一子集，则有（1）AA=A（2）A=（3）AE=A定义 A、B是二个集合，若AB=，则称A和B是不相交的，或者说A和B没有相同的元素。若C是一个集合族（集合族：元素均为集合的集合）且C的任何二个元素都不相交，则称C为不相交的集合族。例：A=a，b，c A为不相交的集合族,2 集合的运算,2.并集（并运算）定义 A、B是任意二个集合，A和B的并集AB是由A和B的所有元素构成的集合。即：AB=x xAxB
11、。例：A=a,b,c B=1,2,3 则AB=a,b,c,1,2,3 定理集合的并运算是可交换的和可结合的，即对任何A，B，C有 AB=BA和（AB）C=A（BC）,2 集合的运算,定理集合的并和交运算，每一个对另一个都是可分配的。即：(1)A（BC）=（AB）（AC）(2)A（BC）=（AB）（AC）定理设A、B、C是全集E的任意子集，则有：(1)AA=A(2)A=A(3)AE=E,2 集合的运算,3.相对补集：定义设A和B是二个任意集合，B对A的相对补集（A-B）是由属于A且不属于B的所有元素组成的集合。即：A-B=xxAxB=xxAxB。例：设A=0，1，2 B=2，3，4 则A-B=0
12、,1 B-A=3，4A-BB-A相对补集不满足交换律。,2 集合的运算,定理设A，B，C，D是E的子集，则有：(1)A-BA，(2)若AB和CD，则ACBD，(3)若AB和CD，则AC BD，(4)若AAB，则 BAB(5)若ABA，则ABB(6)若AB，则AB=B(7)若AB，则AB=A(8)A-=A(9)A(B-A)=(10)A(B-A)=AB,2 集合的运算,4、绝对补集（补运算）定义设E是全集，任一集合A对E的相对补集称为A的绝对补集（或称补集）记作A（或A）。即：A=E-A=x|xExA=x|xA例：设E=a，b，c，d A=a，b 则A=c，d 定理）A是E的任一子集，则有(1)A
13、A=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，6,2 集合的运算,5、环和(对称差)定义设A、B是任意二集合，A和B的环和记作AB。即：AB=(A-B)(B-A)=(AB)(BA)或者x(AB)xx|xAxB 例：设A=2，5，6，B=2，3，4 则AB=3，4，5，6,2 集合的运算,对称差的性质：(1)AB=BA 可交换的(2)(AB)C=A(BC)可结合的(3)AA=(4
14、)A=A(5)A(BC)=(AB)(AC)(对是可以分配的),2 集合的运算,6、文氏图(1)文氏图的画法规则：规定矩形表示E。子集用圆画在E中。(2)文氏图应用：（a）表示集合和运算的关系 可用文氏图画出各种运算：（b）证明集合恒等式例：A（BC）=（AB）（AC）,下图中的阴影部分表示了每个图下边所指出的集合。,AB,AB,A-B,AB,A,A,A,A,A,A,A,B,B,B,B,B,AB=,2 集合的运算,3 序偶与笛卡尔乘积,1.序偶：定义由二个具有给定次序的客体所组成的序列称为序偶。记作x，y 例：XY二维平面上的一个点的坐标x，y就是一个序偶。说明：在序偶中二个元素要有确定的排列次
15、序。即：若ab时，则a，bb，a 若x，y=a，b（x=ay=b）下面定义多重序元：三元组：x，y，z=x，y，zn元组：x1，x2，x3，xn=x1,xn,3 序偶与笛卡尔乘积,2.笛卡尔乘积定义设A，B为二个任意集合，若序偶的第一个成员（左元素）是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 即“”是不满足交换律。,3 序偶与笛卡尔乘积,例：设A=a，b，B=1，2，C=z 则(AB)C
16、=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（BC）“”不满足结合律。定理若A，B，C是三个集合，则有：A（BC）=（AB）（AC）A（BC）=（AB）（AC）（AB）C=（AC）（BC）（AB）C=（AC）（BC）,3 序偶与笛卡尔乘积,证明：（2）设x，y是A（BC）中的任一元素，则：x，yA（BC）x,y x,y|xAyBC|xAyByC|(xAyB)(xAyC)(AB)(AC)即 A(BC)=(AB)(AC)例：设A=1，B=1，2，C=2，3 则A（BC
17、）=11，2，3=1，1，1，2，1，3,3 序偶与笛卡尔乘积,（AB）（AC）=11，212，3=1，1，1，2，1，3 A（BC）=12=1，2（AB）（AC）=1,1,1，21,2,1,3=1，2 n个集合的笛卡儿乘积的定义：A2=AAA3=AAAAn=AAA,N个A,4关系及其表示,序偶a，b实际上反映了二个元素之间的关系。1.关系：指事物之间（客体之间）的相互联系。在数学上关系可表达集合中元素间的联系。日常生活中：父子关系，母子关系，兄弟关系等均为二个客体之间的关系。n元笛卡尔积A1A2An是n元关系。,4关系及其表示,定义若则是一个二元关系。即：以序偶作为元素的任何集合是一个二元关
18、系。关系表示方法（1）枚举法（直观法、列举法）设R表示二元关系，若 用 表示，若，则也可写成：x R y。,4关系及其表示,例：二元关系定义如图：可写成：由定义可见：关系是一个集合，定义集合的方法都可以来定义关系。（2）谓词公式表示法 前面讲述，一个集合可用谓词公式来表达，所以关系也可用谓词公式来表达。,4关系及其表示,例：实数集合R上的“”关系可表达为：大于关系：“”=父子关系：“F”=（3）关系矩阵表示法 规定：(a)二元关系中的左元素表示行，右元素表示列；(b)若，则在对应位置记上“1”，否则为“0”。,4关系及其表示,例1：设并定义为列出关系矩阵：,4关系及其表示例2：设X=a,b,c
19、,Y=1,2,R2是的关系，,是的全域关系，,4关系及其表示,（4）关系图表示法规定：(a)把、集合中的元素以点的形式全部画在平面上；(b)若，则xi和yi之间画一箭头弧线，其箭头指向yi。反之不画任何联线。,4关系及其表示,用关系图表示：,例：,是X中的二元关系，,4关系及其表示,关系的前域和值域：定义：设R是一个二元关系，由 的所有x组成的集合dom R称R的前域,即,R的前域和值域一起称做R的域,记做FLD R,即FLD R=dom R ran R,设R是一个二元关系，由 的所有y组成的集合ran R称R的值域,即,4关系及其表示,4关系及其表示,均为二元关系。,4关系及其表示,三个特殊
20、关系：空白关系，全域关系，恒等关系,定义：集合X2定义了X集合中的一种关系，通称为X中的全域关系，用Ex表示：,4关系及其表示,5关系的性质,自反性：,例：设,是自反的关系。,R的关系矩阵,5关系的性质,定义：设R是X中的二元关系，对于每一个，有x x，则称R是反自反的关系，表示成：R是X中的反自反的关系 x x。,例：设X=1,2,3,5关系的性质,S4既不是自反的，又不是反自反的,5关系的性质,例：设X=1,2,3,R=则R是对称的关系,5关系的性质,即当且仅当,X中的R才是反对称的。,5关系的性质,反对称的另一定义如下:,下面举例说明：,定义：设R是X集合中的二元关系，对于每一个,来讲，
21、如果xy且xRy,则yRx,称R是反对称的关系。,5关系的性质,例：设X=a,b,c,均是反对称的,5关系的性质,例：X=a,b,c,下列关系不是对称的，也不是反对称的,5关系的性质,5关系的性质,X上的全域关系：,是自反的，对称的,X上的空关系是反自反、对称、反对称的。,5关系的性质,传递性：,5关系的性质,例：设X=a,b,c，则下列关系均是可传递的,5关系的性质,下列关系是不可传递的：,5关系的性质,确定二元关系性质举例,（1）设X=1,2,3，,反自反，反对称，可传递的；,反对称的；,5关系的性质,自反，对称，反对称，可传递的；,自反，对称，可传递的；,反自反的，对称的，反对称的，可传
22、递的。,5关系的性质,（2）若,，则X上的空关系,自反的，反自反的，对称的，反对称的，可传递的。,6复合关系和逆关系,关系的复合,定义：设,（R关系），,（S关系），,于是可用,（RS）,的关系，称,RS,为R和S的复合关系，并规定为：,例：设A=1,2,3,4,5，R,S均为AA的关系，且R=,S=,则RS=，SR=,6复合关系和逆关系,“”是不可交换的。,讨论：（1）RS为新的二元关系（2）RSXZ,6复合关系和逆关系,定理：设,则有：,即:关系的复合运算满足结合律.,下面定义关系R 的幂次,6复合关系和逆关系,定义给定集合X，R是X中的二元关系，设,于是R的n次幂,可以定义成：,例：,6
23、复合关系和逆关系,复合关系的矩阵表示,设有三个集合：,而|X|=m,|Y|=n,|Z|=p，则关系矩阵,6复合关系和逆关系,例：设X=1,2,3,4,5,R,S均是X中的二元关系，R=,S=,3.6 复合关系和逆关系,逆关系,讨论定义：（1）只要将R中每一个序偶中的元素全部调换位置，就可得到R的逆关系。,3.6 复合关系和逆关系,例：X=0,1,2，R=,=,3.6 复合关系和逆关系,定理设,，则可有：,3.6 复合关系和逆关系,例：,，试求：,3.6 复合关系和逆关系,3.6 复合关系和逆关系,证明：充分性：R是对称的,3.6 复合关系和逆关系,定理给定集合X,Y,，于是可有,7关系的闭包运
24、算,定义：给定集合X，R是X中的二元关系，若有另一R满足下列条件：（1）R是自反的（对称，可传递的）；（2）,（3）对于任一自反（对称，传递的）关系R，若,，则,则称R是R的自反（对称，传递的）闭包，并依次用r(R),s(R),t(R)来表示之。,7关系的闭包运算,讨论定义：（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)；,7
25、关系的闭包运算,定理：给定集合X，R是X中的二元关系，于是可有：（1）当且仅当r(R)=R，则R是自反的；（2）当且仅当s(R)=R，则R是对称的；（3）当且仅当t(R)=R，则R是可传递的。,例：设X=a,b,c,R=，求r(R),解：r(R)=,7关系的闭包运算,7关系的闭包运算,定理：给定集合X，R是X中的二元关系，则有,定理：设X是一集合，R是X中的二元关系，则：,例：设X=a,b,c,R=，求s(R),s(R)=,7关系的闭包运算,例：X=a,b,c,R=，|X|=3,则,定理：设|X|=n，R是X中的二元关系，则,7关系的闭包运算,例：X=a,b,c,d,R=,则,例：设X=a,b
26、,R=，求r(R),s(R),t(R)r(R)=,s(R)=,t(R)=R,定理：设X是一集合，R是X中的二元关系，则有：,（1）r(S(R)=S(r(R);（2）r(t(R)=t(r(R);（3）t(S(R),7关系的闭包运算,S(t(R)。,7关系的闭包运算,证明：（1）r(S(R),常用下列符号表示一些闭包：,“R加”：,，传递闭包，,“R星”：,，自反可传递闭包，,7关系的闭包运算,例：设X=a,b,c,R=（1）rS(R)=r=Sr(R)=s=（2）rt(R)=r=tr(R)=t=（3）tS(R)=t=St(R)=S=t(S(R),St(R),8集合的划分和覆盖,定义：给定一非空集合
27、，又设,若（1）,（2）,则称A为S的覆盖。,例：S=a,b,c，A=a,b,b,c，B=a,a,b,c，C=a,b,c，D=a,b,a,c,均为S的覆盖。,8集合的划分和覆盖,定义：给定一非空集合S，设非空集合,如果有：,（i,j=1,2,m）,则称集合A是集合S的一个划分。,8集合的划分和覆盖,讨论定义：,（1）划分和覆盖主要差别在第（2）条；,（3）若A为有限集合，则A的秩是有限的，为|A|，若A为无限集合，则划分的秩是无限的；,（4）集合的划分必定是一个覆盖，而覆盖不一定是划分；,（5）集合S上的秩最大的划分称最大划分，最小的称最小划分。,8集合的划分和覆盖,例：设S=a,b,c，下列
28、,均为S的一个划分：,类有二个a,b,c,=2（秩）；,类有二个a,b,c,=2（秩）；,类有二个a,c,b,=2（秩）；,最大划分，秩为3；,最小划分，秩为1。,8集合的划分和覆盖,定义：设A和A是非空集合S的二种划分，并可表示成：,若A的每一个类,都是A的某一个类,的子集，则称划分A是划分A的加细，,或讲A加细了A，若A加细了A且,则称A是A的真加细。,8集合的划分和覆盖,例：S=a,b,c,d,S的划分：A=a,b,c,d,A=abc,d，则A是A的真加细,A=abcd,则A 是A的真加细,9等价关系与等价类,定义：设X是一个集合，R是X中的二元关系，若R是自反的，对称的和可传递的，则称
29、R是等价关系。,例：设X=1,2,3,4,5,6,7，,为整数,9等价关系与等价类,试验证R是等价关系，画出R的关系图，列出R的关系矩阵,解：（1）R=,（2）R的关系矩阵,9等价关系与等价类,R满足自反、对称和可传递的，R是一等价关系,例：设A=0，1，2，3，6，R=x,y|xy(x,yA)yx(mod 3)，则domR=_，ranR=_。,9等价关系与等价类,9等价关系与等价类,定义：设R是X集合中的等价关系，对于任何的,来讲，可把集合,规定成：,并称是由,生成的R等价类。,讨论定义：,（2）,9等价关系与等价类,例：设X=a,b,c,d,R是X中的等价关系，R=,则,9等价关系与等价类
30、,例：设X=N，关系R=,是一等价关系，,则R可以找出三个等价类：,=0，3，6，9，此集合中的元素除以3的余数为“0”；,=1，4，7，10，此集合中的元素除以3的余数为“1”；,=2，5，8，11，此集合中的元素除以3的余数为“2”。,9等价关系与等价类,定理：设X是一非空集合，R是X中的等价关系，R等价类的集合xR|x X是X的一个划分，且此集合称为X关于R的商集，用,表示之。,9等价关系与等价类,（2）X中的恒等关系,它形成了X的一个最大划分,9等价关系与等价类,定理：X是一非空集合，A为X的一个划分，且A=A1,A2,.An，则由A导出的X中的一个等价关系,例：Xa,b,c,d，A=
31、a,b,c,d则 R(a,b a,b)(c,d c,d)=,由此我们看到：集合X上的等价关系与X的划分之间有对应关系。,定义：设X是一个集合，R是X中的二元关系，若R是自反的，对称的，则称R是相容关系。由定义知,等价关系是具有传递性的相容关系;相容关系是一个比等价关系更为普遍的关系。因为相容关系是自反和对称的,其关系矩阵是对称的且主对角线元素全为1,因此我们可仅用下三角矩阵T来表示和存储就够了,即关系矩阵可以简化为“阶梯形”。,10相容关系,EX：设A=cat,teacher,cold,desk,knife,byR=x,y|x,yA 且 x和y至少有一个相同的字母R 是 A上的一个相容关系,简
32、记 A 中元素依次为x1,x2,x3,x4,x5,x6,则R的关系矩阵MR和对应简化的下三角矩阵TR为：,catteacher cold desk knife by,cat teacher cold desk knife by,EX：在相容关系的关系图上，每个顶点都有自环且每两个顶点间的弧线都是成对出现的。为简化相容关系的关系图,不画自环,并用无箭头的单线段代替来回弧线,使之成为无向图。上例的关系图如下:,定义1：设R是集合A上的相容关系,若CA,若任意a,bC,有aRb,则称C是由R产生的相容类。例如上例的相容关系R可产生相容类x1,x2，x1,x3，x2,x3，x6，x2,x4,x5，等等
33、。对于前三个相容类，都能加进新的元素组成新的相容类，而后两个相容类，加入任一新元素，就不能组成相容类，我们称它为最大相容类。,x3,x2,x1,也可以这样理解最大相容类CR：对CR中的任意元素x,x必与CR中所有元素有相容关系,而在差集A CR中没有任何元素与CR中所有元素都是相容的。,求最大相容类的方法：,关系图法：确定最大完全多边形 即:每个顶点都与其他所有顶点相联结的多边形。,(1)孤立结点是最大的完全多边形；,(2)二个相互联结的结点是最大完全多边形；,(3)三角形是三个结点的最大完全多边形；,(4)四个结点；,(5)五个结点;,画出简化相容关系的关系图后，先确定结点最多的完全多边形，
34、以后逐次减少。,例：已知相容关系图，求出最大相容类,最大相容类集合为,完全覆盖：设有 集合 A 上的相容关系 R，其中最大相容类的集合，称作集合 A 的完全覆盖。定理：A 上的每个相容关系，唯一的定义一个完全覆盖。,g,最大相容类：b,g,f,e，b,a,e，b,c，d,该集合的完全覆盖为：b,g,f,e，b,a,e，b,c，d,1、偏序关系的定义：设 A 是一个集合，如果A上的一个关系 R，满足自反性，反对称性和传递性，则称 R 是 A上的一个偏序关系，记作“”.EX1：在实数集 Z上，证明小于等于关系是偏序关系EX2：在实数集Z上，小于关系是偏序关系？EX3：设A=1，2，3，则定义在(A
35、)上的关系“”是偏序关系吗？EX4：设A=2，3，6，8，则定义在A上的整除关系R=(2，2)，(3，3)，(6，6)，(8，8)，(2，6)，(2，8)，(3，6)是偏序关系吗？,偏序关系,设为偏序关系,如果,则记作x y,读作“小于或等于”.注意:这里的“小于或等于”不是指数的大小,而是在偏序关系中的顺序性.x“小于或等于”y的含义是:依照这个序,x排在y的前边或者x就是y.不同偏序的定义有不同的序解释.例如整除关系是偏序关系,3 6的含义是3整除6;大于或等于关系也是偏序关系,针对这个关系写5 4是说大于或等于关系中5排在4的前边,也就是5比4大.,偏序关系,偏序关系,定义 集合A和A上
36、的偏序关系一起叫做偏序集,记作.例如:整数集合Z和数的小于等于关系构成偏序集,集合A的幂集P(A)和包含关系R构成偏序集.,利用偏序关系的自反性、反对称性和传递性可简化偏序关系的关系图,该关系图称为哈斯图(Hasse Diagram).为了说明哈斯图的画法,先定义偏序集中顶点之间的覆盖关系.,偏序关系,定义:对于任意 R 且a=b,则 IR,令R1=R-IR,则R1-(R1 o R1)为盖住集。以上所给的等价定义是立足于集合的观点,应用此等价定义判定偏序关系的盖住集,不仅有条理,而且步骤清晰。可从以下几步求盖住集:(1)首先从R 中找出所有a=b 的序对集合IR。(2)计算集合R 和IR 的差
37、R1,即R1=R-IR。(3)将R1 与其自身复合,得集合R2。(4)计算集合R1 和R2 的差,则R1-R2 为盖住集。,偏序关系,例 设集合A=a,b,c,d,e,R 是A 上的偏序关系。R=,试判定R 上的盖住集COVR。解:IR=,R1=R-IR=,R1 o R1=,COVR=R1-(R1 o R1)=,偏序关系,在画偏序集的哈斯图时,首先适当排列顶点的顺序,使得:x,yA,1)若x y,则将x画在y的下方.2)对于A中的两个不同元素x和y,如果y覆盖x,就用一条线段连接x和y.,给定偏序集A，它的盖住集是唯一的。我们可以画出盖住集的关系图，称为A，的哈斯图。,偏序关系,则P1，是一偏
38、序集合，全序集合，良序集合其哈斯图为：,偏序关系,例：设X=a,b,(X)=,是一偏序关系，,其哈斯图为：,偏序关系,下面考虑偏序集中的一些特殊元素.定义 设为偏序集,BA,yB.(1)若x(xByx)成立,则称y为B的最小元;(2)若x(xBxy)成立,则称y为B的最大元;(3)若在B中找不到一个y 使y y，则称y为B的极小元；(4)若在B中找不到一个y 使y y，则称y为B的极大元。,偏序关系,最大元、最小元举例：例：设有集合A=1,2,3,4,5,6,9,10,15上的整除关系 R，B1=1,2,3，B2=3,5,15，B3=AB1的最大元是，B1的最小元是1；B2的最大元是15，B2
39、的最小元是；B3的最大元是，B3的最小元是1；,1,偏序关系,极大元、极小元举例：例：设有集合A=1,2,3,4,5,6,9,10,15上的整除关系 R，B1=1,2,3，B2=3,5,15，B3=AB1的极大元是2,3，B1的极小元是1；B2的极大元是15，B2的极小元是3,5；B3的极大元是4,6,9,10,15，B3的极小元是1；,1,偏序关系,讨论定义：(1)yB，B的极大元，极小元，最大元，最小元，若有的话，必定在B中。(2)最大，最小元与B中所有元素都可以比较,极大，极小元不一定与B中所有元素都可以比较.(3)B中最大，最小元不一定存在,如果有最大，最小元则一定是唯一的，极大，极小
40、元一定存在，且不一定是唯一的。(4)极大元是哈斯图中最顶层的元素,极小元是哈斯图中最低层的元素,偏序关系,定义 设为偏序集,BA,yA.(1)若x(xBxy)成立,则称y为B的上界;(2)若x(xByx)成立,则称y为B的下界;(3)令C=y|y为B的上界,若 C 有最小元素，则称该最小元素为 B 的最小上界或上确界,记为LUB(上确界)(4)令D=y|y为B的下界,若 D 有最大元素，则称该最大元素为为B的最大下界或下确界,记为GLB(下确界),偏序关系,上界、下界举例：例：设有集合A=1,2,3,4,5,6,9,10,15上的整除关系 R，B1=1,2,3，B2=3,5,15，B3=A。B
41、1的上界是6，B1的下界是1；B2的上界是15，B2的下界是1；B3的上界是，B3的下界是1；,1,偏序关系,上确界（最小上界）、下确界（最大下界举例）：例：设有集合A=1,2,3,4,5,6,9,10,15上的整除关系 R，B1=1,2,3，B2=3,5,15，B3=A。B1的最小上界是6，B1的最大下界是1；B2的最小上界是15，B2的最大下界是1；B3的最小上界是，B3的最大下界是1；,1,偏序关系,例：设X=a,b,c,是一偏序集合，,其哈斯图如右，,求下列子集的上界、下界、最小上界和最大下界,讨论定义：(1)上，下界是对B中所有元素比较而言的。(2)B的上界,下界都可能不存在,如果存
42、在,则不一定是唯一的。(3)B的最小上界(LUB),最大下界(GLB)都可能不存在.如果存在,最小上界与最大下界是唯一的.(4)若 B只有一个上界和下界，则该上界和下界一定是最小上界与最大下界,偏序关系,偏序关系,定义 设R为非空集合A上的偏序关系,如果x,yA,x与y都是可比较的,则称R为A上的全序关系(或线序关系).例如:数集上的小于等于关系是全序关系,因为任何两个数总是可比大小的.一般来说,整除关系不是全序关系.如:集合 1,2,3 上的整除关系就不是全序关系,因为2和3不可整除.,全序关系的定义：,偏序关系,定义 若集合X上的二元关系R是全序关系，且X的任一非空子集，都有一个最小元素，则称R为良序关系，并称为良序集合。,讨论定义：,（1）良序关系比全序关系多了一个条件，即在全序关系中，X集合的任一非空子集均有一个最小元素；,（2）每一个有限集合X上的全序关系必定是良序关系。,良序关系的定义：,偏序关系,拟序关系的定义：设 A 是一个集合，如果A上的一个关系 R，满足反自反性，反对称性和传递性，则称 R 是 A上的一个拟序关系，或称 R 在 A 上是拟序的，记作“”；例：由集合 A 所组成的幂集(A)上的关系“”是是拟序关系？例：在整数集 Z 上小于关系是拟序关系？,偏序关系,
