离散数学2（课堂PPT）

1,二元关系的性质,设R是A上的关系,R的性质主要有以下5种：自反性反自反性对称性反对称性传递性,2,二元关系的性质,设是上的二元关系，=(rij)n*n(1)自反性:对，（，），则称为自反的二元关系。显然，rii1（，n)反自反性:对，（，），则称为反自反的二元关系。即rii（，n),3,注:自反和反自反性互斥，但不互补。如：rii中既有0又有1，则R既不是自反的也不是反自反的。,对应于关系图：自反性：每个顶点都有自回路反自反性：每个顶点都没有自回路,4,(2）对称性：若,（，）,必有（，），称为对称的二元关系即的关系矩阵为对称阵，ijji,关系图对称性：任二个顶点间或没有边，或有二条方向相对的有向边.（例2.4.2）,5,反对称性：若，（，）,则（，），称为反对称的二元关系。,注意:（1）的相关矩阵是反对称的，即rijrji（）（2）若rij，则rji，但rij时，不要求rji，即rijrji是允许的。(3)对称性与反对称性既不互斥，又不互补,关系图：任二个顶点至多只有一条有向边；（例2.4.3）,6,7,注:rij，rjk中有一个不是,则=1,rik就可以任意。,即若(，),(b，c)中有1个不属于R，则讨论（a,c)是否属于R，无意义。即没有传递的条件，就不需讨论传递的结果。如:a,b,c,d，（，）,（，）,8,传递性：若到有边，到有边，则到必有边。,9,二元关系的性质对应于关系图，有：（1）自反性：每个顶点都有自回路，（2）反自反性：每个顶点都没有自回路；（3）对称性：任二个顶点间或没有边，或有二条方向相反的有向边；（4）反对称性：任二个顶点至多只有一条有向边；（也即：或没有边，或只有一条有向边）（5）传递性：若到有边，到有边，则到必有边。,10,11,定理2.4.1设R是集合A上的二元关系，则(1)是自反的当且仅当I(2)是对称的当且仅当=-1(3)是反对称的当且仅当-1I,(4)是传递的当且仅当,12,例：分析集合A=1,2,3上的下述四个关系，判断是否自反、对称、反对称、传递：(1)R=(1,1),(1,2),(1,3),(3,3);反对称、可传递(2)S=(1,1),(1,2),(2,1),(2,2),(3,3);自反、对称、可传递(3)T=(1,1),(1,2),(2,2),(2,3);反对称(4)AA自反、对称、可传递,13,判断A上关系的性质：,全域关系自反的、对称的和传递的恒等关系自反的、对称的和传递的整除关系自反的、反对称的和传递的小于等于关系自反的、反对称的和传递的幂集上的包含关系自反的、反对称的和传递的,14,举出A=1,2,3上关系R的例子，使其具有下述性质：A)既是对称的,又是反对称的；B)R既不是对称的,又不是反对称的；C)R是可传递的。解：A)R=(1,1),(2,2),(3,3)B)R=(1,2),(2,1),(2,3)C)R=(1,2),(2,1),(1,1),(2,2),(3,3),15,设R1,R2是A上的关系,如果经过某种运算后仍保持原来的性质,则划,否则划。,16,例：设R1,R2为A上的对称关系,证明R1R2也是A上的对称关系。证明：对于任意的R1R2()R1)(R2)(R1)(R2)R1R2所以,R1R2在A上是对称的。,17,作业：设X=1,2,3,4,R是X上的二元关系，R=(1,1),(1,2),(1,3),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3)(1)画出R的关系图(2)写出R的关系矩阵(3)说明R是否是自反、反自反、对称、传递的,18,关系的闭包,定义：设R是非空集合A上的关系,R的自反闭包(对称闭包或传递闭包)是A上的关系R,且R满足以下条件:(1)R是自反的(对称的或传递的)；(2)RR；(3)对A上的任何包含R的自反关系(对称或传递关系)S都有RS.即满足（1）（2）的最小者；一般将R的自反闭包reflexive记作r(R),对称闭包symmetric记作s(R),传递闭包transitive记t(R)。,19,教材P43例2.5.1例：设Aa,b,c,d,R,则R和r(R),s(R),t(R)的关系图如图所示,例P43,20,A上关系R的闭包,定理2.5.2设R为A上的二元关系,则(1)r(R)IR；(2)s(R)RR-1；(3)t(R)=RR2R3(4)A是含有n个元素的集合t(R)=RR2R3Rn闭包的矩阵表示,21,例:设Aa,b,c,d,R,则r(R),s(R),t(R)有解:(1)r(R)IR=,=,.,(2)s(R)RR-1=,=,22,(3)t(R)=RR2R3R4=,R4=,23,闭包的矩阵表示,MrMEMs=M+MMt=M+M2+M3+其中E表示同阶的单位矩阵(主对角线元素为1,其他元素都是0)M表示M的转置,而+均表示矩阵中对应元素的逻辑加（即：或运算）。Mt中的幂数不超过集合A中的元素数,24,在上例中3个结果矩阵是:,25,求传递闭包-Warshall算法,设集合基数为n，构造n+1个矩阵W0,W1,W2,Wn,W0为t(R)的关系矩阵,Wn即为t(R)的关系矩阵(1)令W0=MR(2)设Wi-1已求出，现求Wi考虑Wi-1的第i列，列中为1的元素分别位于P1,P2行，同时考虑第i行，该行中为1的元素位于q1,q2列，则：把Wi中第PS行qt列的元素改为1；(3)重复(2)过程，直到求出Wn(4)根据Wn写出t(R)（见书上例2.5.3）,26,定理2.5.3设A为集合，R1,R2AA.若R1R2则(1)r(R1)r(R2);(2)s(R1)s(R2);(3)t(R1)t(R2)等价关系,27,作业：,1.集合A=1,2,10上的关系R=(x,y)|x+y=10,xA,yA,则R的性质为().A.自反的B.对称的C.传递的,对称的D.反自反的，传递的2.设A=a,b,c上的关系如下，有传递性的有().A.P1=(a,c),(c,a),(a,b),(b,a)B.P2=(a,c),(c,a)C.P3=(a,b),(c,c),(b,a),(b,c)D.P4=(a,a),28,3.设集合A=a,b,c,d上关系R=(a,b),(a,c),(d,c),(b,c),(c,d)1)用矩阵运算求出R的自反、对称、传递闭包;2)用warshall算法，求出R的传递闭包,29,2.6等价关系,定义1等价关系:上的二元关系，如果是(1）自反的(2）对称的(3)传递的称为等价关系。（，），称与等价，记作。,30,恒等关系、全关系、三角形的全等关系以及三角形的相似关系均为等价关系。例：设集合A=1,2,3,4,R=(1,1),(1,4),(4,1),(4,4),(2,2),(2,3),(3,2),(3,3)验证关系R是A上的等价关系。,31,例：设R为计算机系所有学生构成的集合上的“同住一个宿舍关系”，则R为等价关系。,32,例2.6.2A1,2,8,R|x,yAxy(mod3),其中xy(mod3)的含义就是x-y可以被3整除.R为A上的等价关系,它的关系图如下所示：,33,把模3的等价关系推广,设Z为整数集合，取一个固定的整数m0,规定Z的元素间的一个关系R：(a,b)R当且仅当m|(a-b)，这个关系称为模m的同余关系.我们用ab(modm)来表示，同余关系为等价关系。,34,定义2.6.2若把一个非空集合A分成若干个叫做类的子集，使得A的每个元素属于而且只属于一个类，那么这些类的全体叫做集合A的一个分类（或划分）.,A1,A2,A3,A4,35,定理2.6.1集合A上的一个等价关系R决定A的一个分类.,定理2.6.2集合A上的一个分类决定A上的一个等价关系.例：设集合A中有4个元素，则A上的不同的等价关系的个数为（）A.12个B.14个C.15个D.17个,36,等价类：设R为集合A上的等价关系。对任何aA，称集合aR=xxA,xRa为a关于R的等价类，a称为aR的代表元素。,等价类aR是所有与a具有R关系的元素构成的集合。,设A=1,2,3,4,5，R是A上的“模3同余”关系，求其等价类。解：R=(1,1),(1,4),(4,1),(4,4),(2,2),(2,5),(5,2),(3,3),(5,5)A上关于R有三个等价类：1R=1,4=4R2R=2,5=5R3R=3,37,例：设N是自然数集合，定义N上的二元关系R：R=(x,y)|xN,yN,x+y是偶数证明R是一个等价关系；,38,等价类的性质,定理设R是非空集合A上的等价关系,对任意的x,yA,下面的结论成立.（1）任取xA,xR；（2）若x,yA,或者xR=yR,或者xRyR；（3）=A.,39,商集,定义2.6.3设R为集合A上的等价关系,以R的所有的等价类为元素的集合叫做A关于R的商集,记作AR,ARxA.在上例中,A在R下的商集是A/R=1,2,3=1,4,2,5,3,40,在整数集合z上关于模m同余的等价关系,其等价类是00,m,2m,=mz|zZmZ,11,m1,2m1,=mz1zZmZ122,m2,2m十2,mz2zZmZ2,m1m1,m+m1,2mm1,=mz+m1zZ=mZ+m1.商集为0,1,m1,41,例2.6.6设A1,2,3,求出A上所有的等价关系.,解:先求A的各种划分:只有1个划分块的划分1,具有两个划分块的划分2,3和4,具有3个划分块的划分5,请看下图,42,设对应于划分i的等价关系为Ri,i1,2,5.则有R1(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)IAEA；R2(2,3),(3,2)IA；.R3(1,3),(3,1)IA；R4(1,2),(2,1)IA.R5(1,1),(2,2),(3,3)IA；,43,2.7偏序关系,定义2.7.1设R为集合A上的二元关系,如果R是自反的、反对称的和传递的,则称R是A上的偏序关系.简称偏序,记作.具有偏序关系的集合A称为偏序集，记作(A,)例：判断下列集合是否是偏序集合:(a)(I,),其中是整数集合上的小于等于关系；(b)(P(A),),其中是集合上的包含关系;(c)(I,|),其中|是整除关系;(d)(I,),其中是小于关系.,44,设(A,)为偏序集,对于任意的x,yA可比:如果xy或者yx成立,则称x与y是可比的.盖住（覆盖关系）:如果xy,xy,且不存在zA使得xzy,则称y盖住x.并且记COVA=(x,y)|x,yA;y盖住x例1:设A=2,3,6,12,24,36,“|”是A上的整除关系,COVA=?COVA=(2,6),(3,6),(6,12),(12,24),(12,36)例2：集合A=a,b,c,偏序集合(P(A),)中,判断A的以下子集是否盖住a.（1）（2）b,c（3）a,b（4）a,b,c,45,偏序关系的图形表示哈斯图,哈斯图画法如下：,（1）用小圆圈代表元素。（2）如果xy且xy，则将代表y的小圆圈画在代表x的小圆圈之上。（3）如果(x,y)COVA,则在x与y之间用直线连接。,练习:A=a,b,画出偏序集合(P(R),)的哈斯图：,46,画偏序集的哈斯图,47,例如：画A=a,b,c,(P(R),)的哈斯图：,48,例:设偏序集的哈斯图如图所示,求出集合A的偏序.,解Aa,b,c,d,e,f,g,h.(a,c),(a,d),(a,e),(b,c),(b,d),(b,e),(c,e),(d,e),(f,g)IA.,e,c,d,a,b,g,f,h,49,最大元,最小元,极大元,极小元,设(A,)为偏序集合,BA.最大元:如果aB,若xB,都有xa,则称a为集合B的最大元；最小元:如果aB,若xB,都有ax,则称a为集合B的最小元；极大元：若xB，且由ax可推出a=x,则称a为B的极大元；极小元：若xB，且由xa可推出x=a,则称a为B的极小元；(区别见P57）,50,上界,下界,上确界,下确界,定义2.7.4设为偏序集,BA,B,aA(1)若xB,都有xa,则称a为B的上界.(2)若xB,都有ax,则称a为B的下界.(3)若a是B的上界，且对B的任意上界b均有ab，则称a为B的最小上界或上确界(4)若a是B的下界，且对B的任意下界b均有ba，则称a为B的最大下界或下确界（例2.7.6）,51,1、对于有穷集，极小元和极大元一定存在，还可能存在多个。2、最小元和最大元不一定存在，如果存在一定唯一。3、最小元一定是极小元；最大元一定是极大元。4、孤立结点既是极小元，也是极大元。,最小元、最大元、极小元、极大元具有下述性质：,52,上界、下界、最大上界与最小上界存在下述性质：,1、下界、上界、最大下界、最小上界不一定存在。2、如果下界、上界存在，也不一定是唯一的。3、最大下界、最小上界如果存在，则是唯一的。4、子集B的最小元就是它的最大下界，最大元就是它的最小上界；反之不对(最大下界、最小上界可能不在集合B中)。,53,例：整数集上的整除关系不是全序关系，但大小关系是全序关系。集合,a,a,b,a,b,c,a,b,c,d上的包含关系就是全序关系自然数集N大小元关系是良序集。,54,作业：设集合P=x1,x2,x3,x4,x5上的偏序关系如图，找出P的最大元、最小元、极大元、极小元。找出x2,x3,x4、x3,x4,x5和x1,x2,x3的上界、下界、上确界、下确界。,x2,x4,x3,x5,x1,55,2.8映射,定义2.8.1设A、B是任意两个非空集合，fAB，若对于A中的每个元素a都存在唯一的元素bB，使（a,b)f,则称f为A到B的映射(函数).x为y在f下的原象，y为x在f下的象.集合A称为定义域，记作Domf,即Domf=A.而f(A)=f(a)|aA称为f的值域，记作Ranf,由定义有RanfB.,56,例:设A=x1,x2,x3，B=y1,y2，如下关系F1(x1,y1),(x2,y1),(x3,y2)是不是映射？是映射F2(x1,y1),(x1,y2),(x2,y1),(x3,y2)呢？不是映射,因为对于x1domF有x1Fy1,x1Fy2同时成立.,57,例：判断下列关系中哪些能构成映射（函数）？(a)f=(x1,x2)|x1,x2N，x1+x2xC.R3是自然数集合Q上的关系，且xR3y当且仅当y=x+2B.R4是自然数集合N上的关系，且xR4y当且仅当x*y=4,70,4.A=1,2,3,B=4,5,6,8,R与S是从A到B的关系，且XRY当且仅当gcd(x,y)=1,即x与y的最大公约数等于1，xRy当且仅当x+y为偏序集，其中A=1,2,3,4,6,9,24,54,R是A上的整除关系.(1)画出的哈斯图；(2)求A中的极大元；(3)令B=4,6,9，求B的上确界和下确界.6.设A=a,b,c,R=,(1)给出R的关系矩阵；(2)说明具有的性质（自反性、反自反性、对称性、反对称性、传递性）,71,7、考虑下列实数集上的函数：f(x)=2x2+1，g(x)=-x+7，h(x)=2x，k(x)=sinx求gf，fg，ff，gg，fh，fk，kh的解析式。,72,第3章集合的基数,73,集合的基数,希尔伯特饭店(“无穷饭店”)关于无穷大悖论的故事“无穷饭店”是我们银河系中心的一家巨大的旅馆。它拥有无穷多个房间，这些房间通过黑洞伸展到更高级的时空领域。房间号从1开始，无限制地排下去。旅店每个房间恰能住一位旅客，并已经客满。当日又有一位旅客投宿，店主欣然接纳,希尔伯特（18621943),1,2,3,74,无穷集的概念定义3.1.1设A,B为两个集合，如果存在A到B的一个双射函数f：AB，则称A与B等势(等基数)，记作AB例：对集合A和B，构造一个从A到B的双射，以说明A和B具有相同的势.(1)A=(0,1),B=(0,2)f:AB,使得f(x)=2x,xA(2)A=R,B=(0,)f:AB,使得f(x)=ex,xR(3)A=0,1),B=(1/4,1/2f:AB,使得f(x)=-(1/4)x+1/2,x0,1),75,有限集与无限集,定义3.1.2设n为一个正整数，若集合A是空集或A与集合1，2，3,，n等势，称集合A为有限集；否则称A为无限集。即：若A为空集或存在集合1，2，3,，n到A，或A到该集合的双射，称集合A为有限集；否则称A为无限集。自然数集是无限集。证明正整数集合与自然数集合等势定义函数：f：NI+，f(x)=x+1,76,等势（等基数）的相关概念,定义：集合A与集合B等势(等基数)，当且仅当，A与B之间存在双射（一一对应）。在此意义下，刻画了两个无穷集合比较“多少”的一种办法。但这里的“多少”概念只是一种直观的解释，已经和有限集合比较多少的情况发生了变化。在有限集合中，一个集合不可能与其真子集等势。但在无限集合的比较，则不同。比如，自然数集和偶数集之间，可以通过双射f(n)=2n建立一一对应的关系。所以自然数集和偶数集是等势的，虽然偶数集是自然数的真子集。集合论认为，这种与其某一真子集等势的性质，恰好反映了无穷集合的本质，反映出了有限集和无穷集之间的一个重大区别。,77,任何有限集的任何子集为有限集。任何含有无限子集的集合必定是无限集。对无限集还