离散数学知识点整理

1、离散数学一、逻辑和证明1.1命题逻辑命题：是一个可以判断真假的陈述句。联接词：八、V、一、？、？。记彳i“p仅当q”意思是“如果p,则q，即p-。记住“q除非p”意思是“？p-q”。会考察条件语句翻译成汉语。构造真值表pqpAqpVqp一qp?qpOq?pTTTTTTFF1TFFTFFTFFTFTTFTTFFFFTTFT1.2语句翻译系统规范说明的一致性是指系统没有可能会导致矛盾的需求，即若pq无论取何值都无法让复合语句为真，则该系统规范说明是不一致的。1.3命题等价式逻辑等价：在所有可能情况下都有相同的真值的两个复合命题，可以用真值表或者构造新的逻辑等价式。证逻辑等价是通过p推导出q,证永真

2、式是通过p推导出T逻辑等价式pAT?p恒等律pVF?ppAF?FpVT?T支配律pAp?p幕等律?(?P)?p双否律pAq?qAp交换律(pAq)Ar?pA(qAr)结合律pV(qAr)?(pVq)A(pVr)分配律pA(qVr)?(pAq)V(pAr)?(pAq)?pV?q德摩根律?(pVq)?pA?qpV(pAq)?p吸收律PA(pVq)?ppA?p?FpV?p?T否定律条件命题等价式p-q?pVqp-q?q一？ppVq?p-qpAq?(p-?q)?(p-q)?pA?q(p-q)A(p-r)?p一(qAr)(p-r)A(qr)？(pVq)-r(p-q)V(pr)？p一(qVr)(p-r)V

3、(qr)？(pAq)一r双条件命题等价式p？q？(p一q)A(qp)p？q？p？qp？q？(pAq)V(？pA？q)？(p？q)？|p？q1.4量词谓词+量词变成一个更详细的命题，量词要说明论域，否则没有意义，如果有约束条件就直接放在量词后面，如？x0P(x)。当论域中的元素可以列举，那么？xP(x)就等价于P(x1)AP(x2)AP(xn)。同理，？xP(x)就等价于P(x1)VP(x2)VP(xn)。两个语句是逻辑等价的，如果不论他们谓词是什么，也不论他们的论域是什么，他们总有相同的真值，如？x(P(x)AQ(x)和(？xP(x)A(?xQ(x)。量词表达式的否定：？xP(x)？x？P(x

4、),?？xP(x)？x？P(x)。1.5量词嵌套我们采用循环的思考方法。量词顺序的不同会影响结果。语句到嵌套量词语句的翻译，注意论域。嵌套量词的否定就是连续使用德摩根定律，将否定词移入所有量词里。1.6推理规则一个论证是有效的，如果它的所有前提为真且蕴含着结论为真。但有效论证不代表结论正确，因为也许有的前提是假的。推理规则，都是基于永真式的，用来证明一个前提蕴含一个结论。而基于可涉足式的推理规则叫谬误。pp-q(pA(p-q)一q假百推理qp-qq-r(p-q)A(q-r)(pr)假百二段论p-r？qp-q(？qA(pq)一?p取拒式？ppVq？p(pVq)A？p)-q析取三段论qpp一(pV

5、q)附加律pVqpAq(pAq)p化简律ppq(pAq)(pAq)合取律pAqpVq?pVr(pVq)A(?pVr)一(qVr)消解律qVr量化推理规则?xP(x)全称实例P(c)P(c),任意c全称引入?P(x)?xP(x)存在实例P(c),对某个cP(c),对某个c存在引入?xP(x)命题和量化命题的组合使用二、集合、函数、序列、与矩阵2.1集合e说的是元素与集合的关系，？说的是集合与集合的关系。常见数集有N=0,1,2,3,Z整数集，Z+正整数集，Q有理数集，R实数集，R+正实数集,C复数集。A和B相等当仅当？x(xCA?xCB)；A是B的子集当仅当？x(xCA-xCB)；A是B的真子集

6、当仅当？x(xZxCB)A?x(x?AAxCB)。募集：集合元素的所有可能组合，肯定有？何它自身。如？的募集就是?,而?的募集是?,?。笛卡尔积：AXB,结果是序偶，其中的一个子集叫一个关系。带量词和集合符号如？xCR(x20)是真的，则所有真值构成真值集。集合恒等式名称(AUB)=AAB(AAB)=AUB德摩根律AU(AnB)=AAn(AUB)=A吸收律2.3函数考虑2B的函数关系，定义域、陪域(实信函数、整数值函数)、值域、像集(定义域的一个子集在值域的元素集合)。一对一或者单射：B可能有多余的元素，但不重复指向。映上或者满射：B中没有多余的元素，但可能重复指向。一一对应或者双射：符合上述

7、两种情况的函数关系。反函数：如果是一一对应的就有反函数，否则没有。合成函数：fog(a)=f(g(a),一般来说交换律不成立。2.4序列无限集分为：一组是和自然数集合有相同基数，另一组是没有相同基数。前者是可数的，后者不可数。想要证明一个无限集是可数的只要证明它与自然数之间有对应的关系。如果A和B是可数的，则AUB也是可数的。如果存在一对一函数f从A至UB和一对一函数g从B到A,那么A和B之间是一一对应的。求和公式：a+ar+ar2+ar3+.+arn=(arn+1-a)/(r-1)1+2+3+.+n=n(n+1)/21+22+32+.+n2=n(n+1)(2n+1)/61+23+33+.+n

8、3=n2(n+1)2/42.6矩阵普通矩阵和、减、乘积，0-1矩阵还可以A、V、O(和相乘类似，用V代替+,用A代替X)九、关系9.1 关系及其性质设A和B是集合，从A到B的二元关系是AXB的子集。一个从A到B的二元关系是集合R,第一个元素取自A,第二个元素取自B,当(a,b)属于R时写作aRb。集合A上的关系是A到A的关系，有n个元素就有n2个有序对，n2个有序对就有2n2个关系。考虑集合A到A的关系R任意aCA都有(a,a)R,则R是集合A上的自反关系。任意a,bCA,若(a,b)R都有(b,a)R,则R是对称关系。任意a,bCA,若(a,b)CR且(b,a)CR一定有a=b,则R是反对称

9、关系。任意a,b,cCA,若(a,b)CR且(b,c)R一定有(a,c)R,则R是传递关系。若R是A到B的关系，S是B到C的关系，R与S的合成RoS是有序数对(a,c)o其中aA,cCC,且存在一个bCB使得(a,b)CR,(b,c)CS。二元关系的5种复合要会翻译成汉语。9.3 关系的表示0-1矩阵法：A有n个元素，B有m个元素，用一个nXm的矩阵MR表示，m=1表示有关系。自反关系的0-1矩阵主对角线全为1；对称关系的0-1矩阵是对称阵；反对称关系的0-1矩阵关于主对角线反对称。MRwr2=MRiVMR2,Minr尸MiAM2,MR10R2=MliOMR20有向图法：A有n个元素，每一个关

10、系是一条有向边。自反关系的图每一个顶点都有一个环；对称关系的图在不同顶点之间每一条边都存在与之对应的反方向边(也可用无向图)；反对称关系的图在不同顶点之间每一条边都不存在与之对应的反方向边；传递关系的图在3个不同顶点之间构成正确方向的三角形。9.4 关系的闭包自反闭包：RUA,其中A=(a,a)|aCA对称闭包：R并R1,其中R1=(b,a)|(a,b)R传递闭包：R矩阵传递闭包=MVM2VMR3VMRn,了解沃舍尔算法9.5 等价关系：自反、对称且传递的关系集合A的元素a在R上的等价类a=s(a,s)CRAsCA。如A=1,2,3,4,5,6,7,8，R=(a,b)|a=b(mod3)的等价

11、类划分如下1=4=7=1,4,7,2=5=8=2,5,8,3=6=3,69.6 偏序关系：自反、反对称且传递的的关系偏序集(S,)中如果既没有ab,也没有ba,则a和b是不可比的。全序集：如果偏序集中每个元素都可比，则为全序集，如(Z,或2的简单回路的存在性来证不同构或者是潜在的同构映射f，同样找到f后还要验证f保持边。图G（允许是有向和无向、多重边和环）的Vi到Vj的长度为n的不同通路的条数等于Ani,j,A是G的邻接矩阵。10.5 欧拉回路与哈密顿回路欧拉回路：包含G的每一条边的简单回路。欧拉通路：包含G的每一条边的简单通路。含有至少2个顶点的连通多重图有欧拉回路当仅当它的每个顶点度都为偶

12、数，有欧拉通路但无欧拉回路当仅当它恰有2个度为奇数的顶点。哈密顿回路：包含G的每一个顶点恰好一次的简单回路。哈密顿通路：包含G的每一个顶点恰好一次的简单通路。含有至少3个顶点的简单图，若每个顶点的度都（n/2）,或者每一对不相邻的顶点u和v都有deg（u）+deg（v）n,则有哈密顿回路。最短通路算法：迪克斯特拉算法和旅行商问题（枚举）10.7 平面图欧拉公式：G是有e条边和v个顶点的平面连通简单图，r是G的平面图表示中的面数，则有r=e-V+2。根据上述条件，有3个推论，可以用来判断不是平面图：推论1:若v3,则e3v-6o推论2:G中有度不超过5的顶点。推论3:Q3且没有长度为3的回路，则e02V-4。库拉兔斯基定理：若G是平面图，则删掉一条边u,v并添加一个新顶点w和两