离散数学重要公式定理汇总.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,大一上,离散数学主要公式定理汇总,第1页,2026/7/26 周日,2,基本等价公式,对合律,P,P,幂等律 P,P,P P,P,P,结合律 P,(,Q,R),(,P,Q),R,P,(,Q,R),(,P,Q),R,交换律 P,Q,Q,P P,Q,Q,P,分配律 P,(,Q,R),(,P,Q),(,P,R),P,(,Q,R),(,P,Q),(,P,R),吸收律 P,(,P,Q),P P,(,P,Q),P,德摩根定律,(,P,Q),P,Q,(,P,Q),P,Q,Formula,第2页,2026/7/26 周日,3,同一律 P,F,P P,T,P,零律 P,T,T P,F,F,互补律 P,P,T,P,P,F,附加：,P,Q,P,Q,P,Q,Q,P,P,Q(,P,Q),(Q,P),P,Q(,P,Q),(P,Q),P,Q(,P,Q),(,P,Q),Formula,第3页,2026/7/26 周日,4,等价公式(前10个)与集合论公式比较,：,对合律 A,A A表示A绝对补集,幂等律 A,A,A A,A,A,结合律,A,(,B,C),(,A,B),C；,A,(,B,C),(,A,B),C,交换律 A,B,B,A A,B,B,A,分配律 A,(,B,C),(,A,B),(,A,C),A,(,B,C),(,A,B),(,A,C),吸收律 A,(,A,B),A A,(,A,B),A,Formula,第4页,2026/7/26 周日,5,德摩根定律 ,(,A,B),A,B,(,A,B),A,B,同一律 A,A;A,E,A E表示全集,零律 A,E,E A,否定律 A,A,E,A,A,Formula,第5页,2026/7/26 周日,6,Definition,永真(重言)式（Tautology）,公式中命题变量元论怎样指派，公式对应真值恒为T。,永假（矛盾）式（Contradiction),公式中命题变量不论怎样代入，公式对应真值恒为F。,可满足公式（Satisfaction）,公式中命题变量不论怎样代入，公式对应真值总有一个情况为T。,普通命题公式（Contingency）,既不是永真公式也不是永假公式。,第6页,2026/7/26 周日,7,3.,主要重言蕴含式,(如教材第43页所表示),I,1,.P,Q,P,I,2,.P,Q,Q,I,3,.P,P,Q I,4,.Q,P,Q,I,5,.,P,P,Q I,6,.Q,P,Q,I,7,.,(,P,Q),P I,8,.,(,P,Q),Q,I,9,.P,Q,P,Q I,10,.,P,(P,Q),Q,I,11,.P,(P,Q),Q I,12,.,Q,(P,Q),P,I,13,.(P,Q),(Q,R),P,R,I,14,.(P,Q),(P,R),(QR),R,I,15,.A,B,(,A,C),(,B,C),I,16,.A,B,(A,C),(,B,C),Formula,第7页,2026/7/26 周日,8,蕴含性质,*若,A,B且A为重言式，则B必为重言式,*,若A,B且BC，则AC,(,传递性,),*,若A,B且,A,C，则A,(,B,C,),*,若A,B且C B，则,(,A,C,),B,证实见书P22,Formula,第8页,2026/7/26 周日,9,conjunction,一、全功效真值表,P,Q,C1,C2,C3,C4,C5,C6,C7,C8,T,T,T,F,T,T,F,F,T,F,T,F,T,F,T,F,F,T,F,T,F,T,T,F,F,T,T,F,F,T,F,F,T,F,F,F,T,T,F,T,P,Q,C9,C1,0,C11,C12,C13,C14,C15,C16,T,T,T,F,T,F,T,F,T,F,T,F,T,F,F,T,F,T,T,F,F,T,T,F,T,F,F,T,F,T,F,F,F,T,T,F,T,F,T,F,P,Q,Q,P,第9页,2026/7/26 周日,10,3.析取范式与合取范式化法,化成限定性公式,。,公式E,16,P,Q,P,Q,公式E,21,P,Q(,P,Q),(,P,Q),公式E,20,P,Q(,P,Q),(Q,P),公式E,16,P,Q(,P,Q),(P,Q),将否定联结词移到命题变量前面。,A(P,1,P,2,P,n,),A*(,P,1,P,2,P,n,),(,P,Q),P,Q、,(,P,Q),P,Q,用分配律、幂等律等公式进行整理，使之成为所要求形式。,normal form,第10页,2026/7/26 周日,11,主析取范式定义,析取范式 A,1,A,2,.A,n,其中每个A,i,(i=1,2.n)都是小项，称之为,主析取范式,。,思索：主析取范式与析取范式区分是什么？,主析取范式写法,方法：,列真值表,列出给定公式真值表。,找出真值表中每个“T”对应真值指派再对应小项。,用“,”,联结上述小项，即可。,normal form,第11页,2026/7/26 周日,12,主合取范式定义,合,取范式 A,1,A,2,.A,n,其中每个A,i,(i=1,2.n)都是大项，称之为,主合取范式。,主合取范式写法,方法：,列真值表,列出给定公式真值表。,找出真值表中每个“F”对应真值指派再对应大项。,用“,”联结上述大项，即可。,normal form,第12页,2026/7/26 周日,13,Brief Summary,第一章 小结,命题,原子命题,复合命题,联结词,命题公式,永真式,永真蕴涵式,等价公式,范式,命题逻辑推理,直接推理,间接推理,条件论证,反证法,析取,合取,主析取,主合取,知识网络：,第13页,2026/7/26 周日,14,假如,是个不含客体变元x谓词公式,，且不在,x和,x辖域内，能够将放入,x和,x辖域内。即得以下公式：,1.,xA(x)B,x(A(x)B),2.,xA(x)B,x(A(x)B),3.,xA(x)B,x(A(x)B),4.,xA(x)B,x(,A,(x)B),5.B,xA(x),x(BA(x),6.B,xA(x),x(BA(x),7,.,xA(x)B,x(A(x)B),8,.,xA(x)B,x(A(x)B),量词辖域扩充公式,第14页,2026/7/26 周日,15,1.,x(A(x)B(x),xA(x),xB(x),2.,x(A(x)B(x),xA(x),xB(x),3.,x(A(x)B(x),xA(x)xB(x),4.,xA(x),xB(x),x(A(x)B(x),证实,：设论域为a,1,a,2,.,a,n,，,x(A(x)B(x),(A(a,1,)B(a,1,)(A(a,2,)B(a,2,),(A(a,n,)B(a,n,),(A(a,1,)A(a,2,).A(a,n,),(B(a,1,)B(a,2,).B(a,n,),xA(x),xB(x),量词分配公式,第15页,2026/7/26 周日,16,其它公式,1,.,x(A(x)B(x),x,A(x),x,B(x),2.,xA(x),x,B(x),x(,A(x),B(x),证实1：,x,A(x),x,B(x),x,A(x),x,B(x),xA(x),x,B(x),x(,A(x),B(x),x(A(x),B(x),证实2,：,xA(x),x,B(x),xA(x),x,B(x),x,A(x),x,B(x),x(,A(x),B(x),x(,A(x),B(x),第16页,2026/7/26 周日,17,量词之间有以下公式：,1.,x,yA(x,y),y,xA(x,y),2.,x,yA(x,y),y,xA(x,y),3.,y,xA(x,y),x,yA(x,y),4.,x,yA(x,y),x,yA(x,y),5.,y,xA(x,y),x,yA(x,y),6.,x,yA(x,y),y,xA(x,y),7.,y,xA(x,y),x,yA(x,y),8.,x,yA(x,y),y,xA(x,y),注意：下面式子不成立,x,yA(x,y),y,xA(x,y),第17页,2026/7/26 周日,18,x,yA(x,y),y,xA(x,y),x,yA(x,y),y,xA(x,y),x,yA(x,y),y,xA(x,y),y,xA(x,y),x,yA(x,y),为了便于记忆，用图形表示上面八个公式。,第18页,2026/7/26 周日,19,第二章 小结,第19页,集合,性质,幂等律,对任何集合A，有AA=A。,交换律,对任何集合A、B，有AB=BA。,结合律,对任何集合A、B、C，有,(AB)C=A(BC)。,同一律,对任何集合A，有AEA。,零律,对任何集合A，有A=。,A,B,AB=A。,第20页,交、并,性质,幂等律,对任何集合A，有AA=A。,交换律,对任何集合A、B，有AB=BA。,结合律,对任何集合A、B、C，有,(AB)C=A(BC)。,同一律,对任何集合A，有A=A。,零律,对任何集合A，有AE=E。,分配律,对任何集合A、B、C，有,A(BC)=(AB)(AC)。,A(BC)=(AB)(AC)。,第21页,吸收律,对任何集合A、B，有,A(AB)=A A(AB),=A,证实:,A(AB),=(AE)(AB)(同一),=A(EB)(分配),=AE=A (零律)(同一),A,B,AB=B,第22页,差集,性质,设A、B、C是任意集合，则,A-=A -A=,A-A=A-B,A,A,B,A-B=,(A-B)-C=(A-C)-(B-C),A-(BC)=(A-B)(A-C),A-(BC)=(A-B)(A-C),A,(B-,C)=(AB)-(AC),注意：,对-是不可分配，如A(A-B)=A,而(AA)-(AB)=,第23页,相关绝对补集,性质,设A、B、C是任意集合，则,E=E,(A)=A,AA=AA=E,A-B=AB,(AB)=AB (AB)=AB,A,B,B,A,A=B 当且仅当AB=E且 AB=,第24页,相关对称差,性质,交换律,对任何集合A、B，有A,B=B,A。,结合律,对任何集合A、B、C，有A,B),C=A,(B,C)。教材里有证实。,同一律,对任何集合A，有A,=A。,对任何集合A，有,A,A,=。,对,可分配,A,(B,C)=(AB),(AC),第25页,一.自反性,定义:,设R是集合A中关系，假如对于任意xA都有R(xRx)，则称R是A中自反关系。,即 R是A中自反关系,x(x,A,xRx),比如：,在实数集合中,“,”是自反关系，因为，对任意实数x，有x,x.,关系性质,从关系有向图看自反性:每个结点都有环。,从关系矩阵看自反性：主对角线都为1。,第26页,二.反自反性,定义：,设R是集合A中关系，假如对于任意xA都有,R，则称R为A中反自反关系。,即 R是A中反自反x(x,A,R),从关系有向图看反自反性:每个结点都无环。,从关系矩阵看反自反性：主对角线都为0。,如,实数大于关系，父子关系是反自反。,注意：,一个不是自反关系，不一定就是反自反,。,第27页,三.对称性,定义:,R是集合A中关系,若对任何x,yA,假如有xRy,必有yRx,则称R为A中对称关系。,R是A上对称,x,y(x,A,y,A,xRy),yRx),从关系有向图看对称性:在两个不一样结点之间，若有边话，则有方向相反两条边。,从关系矩阵看对称性：以主对角线为对称矩阵。,例 邻居关系和朋友关系是对称关系。,第28页,四.反对称性,定义:,设R为集合A中关系,若对任何x,yA,假如有xRy和yRx,就,有x=y,则称R为A中反对称关系,。,R,R是A上反对称,x,y(x,A,y,A,xRy,yRx),x=y),x,y(x,A,y,A,x,y,xRy),y x,)(P112),由R关系图看反对称性：两个不一样结点之间最多有一条边。,从关系矩阵看反对称性：以主对角线为对称两个元素中最多有一个1。,另外对称与反对称不是完全对立，有些关系它既是对称也是反对称，如空关系和恒等关系。,第29页,五.,传递性,定义:,R是A中关系，对任何x,y,zA,假如有xRy,和yRz,就,有xRz,则称R为A中传递关系。,即R在A上传递,x,y,z(x,A,y,A,z,A,xRy,yRz),xRz)例,实数集中、，集合,、,是传递。,从关系关系图和关系矩阵中不易看清是否有传递性。必须直接依据传递定义来检验。,检验时要尤其注意使得传递定义表示式前件为F时候此表示式为T，即是传递。,即若,R与R有一个是F时(即定义前件为假)，R是传递。,第30页,本节要求：,1.准确掌握这五个性质定义。,2.熟练掌握五个性质判断和证实。,R是A中自反,x(x,A,xRx),R是A中反自反,x(x,A,R),R是A上对称,x,y(x,A,y,A,xRy),yRx),R是A上反对称,x,y(x,A,y,A,xRy,yRx),x=y),x,y(x,A,y,A,x,y,xRy),y x,),R在A上传递,x,y,z(x,A,y,A,z,A,xRy,yRz),xRz),注意,性质,表示式前件为F时此表示式为T，即R是满足此性质。(自反和反自反性除外),第31页,自反性,反自反性,对称性,传递性,反对称性,每个结点都有环 主对角线全是1,每个结点都无环 主对角线全是0,不一样结点间假如有边,则有方向相反两条边.,是以对角线为对称矩阵,不一样结点间,最多有一条边.,以主对角线为对称位置不会同时为1,假如有边,则也有边.,或前件为假,假如a,ij,=1,且,a,jk,=1,则,a,ik,=1,性质判定,从关系有向图,从关系矩阵,第32页,若,R,AB S,BC,T,BC,则有,证实,任取,R,(ST),b(bB,R,ST),b(bB,R,(,ST),）,b(bB,R,S),(bB,R,T),b(bB,R,S),b(bB,R,T),R,SR,T,(R,S)(R,T),所以R,(ST)=(R,S),(R,T),第33页,R是从A到B关系，则,2.R,C,有向图：是将,R,有向图全部边方向颠倒一下即可。,3.,R,C,矩阵,M=(M,R,),T,即为R矩阵转置。如,1 0 1 0,0 0 0 1,1 0 1 1,M,R,=,34,0 0 0,1 0 1,0 1 1,43,1 0 1,=,M,R,c,第34页,三.性质,令R、S都是从X到Y关系，则,1.(R,C,),C,=R,2.(RS),C,=R,C,S,C,。,3.(RS),C,=R,C,S,C,。,4.(RS),C,=R,C,S,C,。,第35页,5.RS R,C,S,C,。,6.(R),C,=R,C,7.令R是从X到Y关系，S是Y到 Z关系，则,(R,S),C,=S,C,R,C,。(,注意,R,C,S,C,),8.R是A上关系，则,R是对称，当且仅当 R,C,=R,R是反对称，当且仅当 RR,C,I,A,。,第36页,四.性质,定理5.,R是A上关系，则,R是自反，当且仅当 r(R)=R.,R是对称，当且仅当 s(R)=R.,R是传递，当且仅当 t(R)=R.,定理6,.,R是A上关系，则,R是自反，则s(R),和,t(R),也自反。R是对称，则r(R),和,t(R),也对称。,R是传递，则r(R),也传递。,第37页,定理7：,设R,1,、R,2,是A上关系，假如R,1,R,2,，则,r(R,1,),r(R,2,)s(R,1,),s(R,2,)t(R,1,),t(R,2,),证实,r(R,1,)=I,A,R,1,I,A,R,2,=,r(R,2,),，类似可证。,定理8：,设R是A上关系，则,sr(R)=rs(R)tr(R)=rt(R)st(R),ts(R),证实：,sr(R)=r(R)(r(R),c,=(RI,A,)(RI,A,),c,=(RI,A,)(R,c,I,A,c,)=RI,A,R,c,I,A,=(RR,c),I,A,=s(R)I,A,=rs(R),证实用前边证实结论：,(,R,I,A,),k,=I,A,RR,2,.R,k,可证，这里从略。,第38页,六.函数类型,1,2,3,4,a,b,c,1,2,3,4,a,b,c,1,2,3,d,a,b,c,2,3,b,c,a,1,一对一,一对一,满射,映内,入射,单射,一对一,双射,一一对应,第39页,函数复合性质,1,.定理5-2.1,满足可结合,性,f,:X,Y,g:Y,Z,h,:Z,W,是函数,则(,h,g),f,=,h,(g,f,),2,.定理5-2.2,f:X,Y,g:Y,Z,是两个函数,则,假如f,和,g,是,满,射，则,g,f,也是,满,射；,假如f,和,g,是,入,射，则,g,f,也是,入,射；,假如f,和,g,是,双,射，则,g,f,也是,双,射。,第40页,3.,定理5-2.3,假如 g,f,是,满,射，则,g,是,满,射；,假如g,f,是,入,射，则,f,是,入,射；,假如 g,f,是,双,射，则,f,是,入,射,和,g,是,满,射。,4.,定理5-2.4,f:X,Y,是函数,则,f,I,X,=f 且 I,Y,f=,f,。,第41页,性质,1,.,定理5-3.1,设f:XY是双射函数，则(f,-1,),-1,=f。,2.,定理5-3.2,设f:XY是双射函数，则有,f,-1,f=I,X,且 f,f,-1,=I,Y,。,证实,先证,明定义域、陪域相等。,因为,f:XY是双射，f,-1,:YX也是双射，所以,f,-1,f,:,X,X;I,X,:X,X,可见,f,-1,f 与I,X,含有相同定义域和陪域。,再证,它们对应规律相同：,xX,因,f:XY,yY,使得,y=f(x),又f,可逆，故,f,-1,(y)=x，,于是,f,-1,f,(x)=f,-1,(f(x)=f,-1,(y)=x=,I,X,(x),同理可证,f,f,-1,=I,Y,。,第42页,3,.定理5-3.3 令,f:X,Y,g:Y,X,是两个函数,假如,g,f=I,X,且 f,g=I,Y,则 g=,f,-1,。,证实,：,证f,和,g,都可逆。因为,g,f=I,X,，I,X,是双射，由关系复合性质3得，f,是,入,射,和,g,是,满,射。同理由,f,g=I,Y,，得g,是,入,射,和,f,是,满,射。所以,f,和,g,都可逆。,显然,f,-1,和,g含有相同定义域和陪域。,证实它们对应规律相同。,任取yY，f,-1,(y)=f,-1,I,Y,(y),=,f,-1,(f,g),(y),=(,f,-1,f),g,(y),=(,I,X,g),(y)=g(y),所以,f,-1,=g,第43页,顺便说明,：,f,-1,=g,两个条件必须同时满足，缺一不可。,比如,X,Y,。,。,。,。,1,2,a,b,。,c,f,。,。,1,2,X,g,。,。,12,X,。,。,1,2,X,I,X,此例只满足,g,f=,I,X,但 f与 g都非双射，不可逆。,4.,定理5-3.4,令,f:X,Y,g:Y,X,是两个,双射,函数,则,(g,f),-1,=f,-1,g,-1,此定理与关系复合求逆(R,S),C,=S,C,R,C,类似,.,第44页,2.性质,令A,B是全集E子集,1),A=,x(,A,(x)=0),2),A=E,x(,A,(x)=1),3),A,Bx(,A,(x),B,(x),证实:,任取xE,从下表看出,A,Bx(,A,(x),B,(x),),x,A,x,B,x,A,x,B,A,(x),B,(x),A,(x),B,(x),F F,T,00,T,F T,T,0,1 T,T F,F,1,0,F,T T,T,1,1 T,第45页,9),A-B,(x)=,A,(x)-,AB,(x),证实,:,任取xE,A-B,(x)=,AB,(x)=,A,(x),B,(x),=,A,(x)(1-,B,(x)=,A,(x)-,A,(x),B,(x),=,A,(x)-,AB,(x),应用上述公式能够得到一些集合公式。比如证实吸收律：A(AB)=A,证实,:,任取xA,A(AB),(x)=,A,(x)+,AB,(x)-,A(AB),(x),=,A,(x)+,AB,(x)-,AB,(x)=,A,(x),第46页,3.计算公式,KA,1,=KA,2,=.=KA,n,=,则,K,A,1,A,2,.A,n,=,KA=KB=,则 K,AB,=,KA=,KB=,0,(,或,KB=n),(B是,多可数集,)则 K,AB,=,第47页,定理5-6.2,假如集合A到B存在入射函数,则KAKB。,定理5-6.3,(Zermelo定理)A和B是任何集合,则以下 三条,之一必有一个成立:,a)KAKB.,b)KBKA,c)KA=KB.,第48页,定理5-6.4,(Contor-Schroder-Bernstein定理)A和B是任何集合,假如 KAKB 且 KBKA 则KA=KB。,定理5-6.5,设A是有限集合,则KA,0,定理5-6.6,设A是无限集合,则,0,KA,连续统假设:,是大于,0,最小基数,不存在集合A使得,0,KA ,第49页,