《离散数学知识点整理.doc》由会员分享，可在线阅读，更多相关《离散数学知识点整理.doc（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、. .离散数学一、 逻辑和证明1.1命题逻辑命题：是一个可以判断真假的陈述句。联接词：、。记住“p仅当q意思是“如果p，那么q，即p。记住“q除非p意思是“pq。会考察条件语句翻译成汉语。构造真值表pqpqpqpqpqpqpTTTTTTFFTFFTFFTFFTFTTFTTFFFFTTFT1.2语句翻译系统规X说明的一致性是指系统没有可能会导致矛盾的需求，即假设pq无论取何值都无法让复合语句为真，那么该系统规X说明是不一致的。1.3命题等价式逻辑等价：在所有可能情况下都有一样的真值的两个复合命题，可以用真值表或者构造新的逻辑等价式。证逻辑等价是通过p推导出q，证永真式是通过p推导出T。逻辑等价式
2、pT ppF p恒等律pF FpT T支配律pp p幂等律(P) p双否律pq qp交换律(pq)r p(qr)结合律p(qr) (pq)(pr)p(qr) (pq)(pr) 分配律(pq) pq (pq) pq德摩根律p(pq) pP(pq) p吸收律pp Fpp T否认律条件命题等价式pq pqpq qppq pqpq (pq)(pq) pq(pq)(pr) p(qr)(pr)(qr) (pq)r(pq)(pr) p(qr)(pr)(qr) (pq)r双条件命题等价式pq (pq)(qp)pq pqpq (pq)(pq)(pq) pq1.4量词谓词+量词变成一个更详细的命题，量词要说明论域
3、，否那么没有意义，如果有约束条件就直接放在量词后面，如x0P(x)。当论域中的元素可以一一列举，那么xP(x)就等价于P(x1)P(x2).P(xn)。同理，xP(x)就等价于P(x1)P(x2).P(xn)。两个语句是逻辑等价的，如果不管他们谓词是什么，也不管他们的论域是什么，他们总有一样的真值，如xP(x)Q(x)和(xP(x)(xQ(x)。量词表达式的否认：xP(x) xP(x)，xP(x) xP(x)。1.5量词嵌套我们采用循环的思考方法。量词顺序的不同会影响结果。语句到嵌套量词语句的翻译，注意论域。嵌套量词的否认就是连续使用德摩根定律，将否认词移入所有量词里。1.6推理规那么一个论证
4、是有效的，如果它的所有前提为真且蕴含着结论为真。但有效论证不代表结论正确，因为也许有的前提是假的。推理规那么，都是基于永真式的，用来证明一个前提蕴含一个结论。而基于可满足式的推理规那么叫谬误。ppq(p(pq)q假言推理qpqqr(pq)(qr)(pr)假言三段论prqpq(q(pq)p取拒式ppqp(pq)p)q析取三段论qpp(pq)附加律pqpq(pq)p化简律ppqpqpq合取律pqpqpr(pq)(pr)(qr)消解律qr量化推理规那么xP(x)全称实例P(c)P(c)，任意c全称引入P(x)xP(x)存在实例P(c)，对某个cP(c)，对某个c存在引入xP(x)命题和量化命题的组合
5、使用。二、 集合、函数、序列、与矩阵2.1集合说的是元素与集合的关系，说的是集合与集合的关系。常见数集有N=0,1,2,3.，Z整数集，Z+正整数集，Q有理数集，R实数集，R+正实数集，C复数集。A和B相等当仅当x(xAxB)；A是B的子集当仅当x(xAxB)；A是B的真子集当仅当x(xAxB)x(xAxB)。幂集：集合元素的所有可能组合，肯定有何它自身。如的幂集就是，而的幂集是，。笛卡尔积：AB，结果是序偶，其中的一个子集叫一个关系。带量词和集合符号如xRx20是真的，那么所有真值构成真值集。集合恒等式名称(AB)=AB(AB)=AB德摩根律A(AB)=AA(AB)=A吸收律2.3函数考虑A
6、B的函数关系，定义域、陪域实值函数、整数值函数、值域、像集定义域的一个子集在值域的元素集合。一对一或者单射：B可能有多余的元素，但不重复指向。映上或者满射：B中没有多余的元素，但可能重复指向。一一对应或者双射：符合上述两种情况的函数关系。反函数：如果是一一对应的就有反函数，否那么没有。合成函数：fg(a)=f(g(a)，一般来说交换律不成立。2.4序列无限集分为：一组是和自然数集合有一样基数，另一组是没有一样基数。前者是可数的，后者不可数。想要证明一个无限集是可数的只要证明它与自然数之间有一一对应的关系。如果A和B是可数的，那么AB也是可数的。如果存在一对一函数f从A到B和一对一函数g从B到A
7、，那么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+.+n3 = n2(n+1)2/42.6矩阵普通矩阵和、减、乘积，0-1矩阵还可以、和相乘类似，用代替+，用代替九、 关系9.1关系及其性质设A和B是集合，从A到B的二元关系是AB的子集。一个从A到B的二元关系是集合R，第一个元素取自A，第二个元素取自B，当(a,b)属于R时写作aRb。集合A上的关系是A到A的关系，有n个元素就有n2个有序对，n2个有序对就有2n2个关系
8、。考虑集合A到A的关系R：任意aA都有a，aR，那么R是集合A上的自反关系。任意a，bA，假设a，bR都有b，aR，那么R是对称关系。任意a，bA，假设a，bR且b，aR一定有a=b，那么R是反对称关系。任意a，b，cA，假设a，bR且b，cR一定有a，cR，那么R是传递关系。假设R是A到B的关系，S是B到C的关系，R与S的合成RS是有序数对a，c。其中aA，cC，且存在一个bB使得a，bR，b，cS。二元关系的5种复合要会翻译成汉语。9.3关系的表示0-1矩阵法：A有n个元素，B有m个元素，用一个nm的矩阵MR表示，mij=1表示有关系。自反关系的0-1矩阵主对角线全为1；对称关系的0-1矩
9、阵是对称阵；反对称关系的0-1矩阵关于主对角线反对称。MR1R2=MR1MR2，MR1R2=MR1MR2，MR1R2=MR1MR2。有向图法：A有n个元素，每一个关系是一条有向边。自反关系的图每一个顶点都有一个环；对称关系的图在不同顶点之间每一条边都存在与之对应的反方向边也可用无向图；反对称关系的图在不同顶点之间每一条边都不存在与之对应的反方向边；传递关系的图在3个不同顶点之间构成正确方向的三角形。9.4关系的闭包自反闭包：R，其中=a，a|aA对称闭包：R并R-1，其中R-1=b,a|a，bR传递闭包：R矩阵传递闭包=MRMR2MR3.MRn，了解沃舍尔算法9.5等价关系：自反、对称且传递的
10、关系集合A的元素a在R上的等价类a=s|(a,s)RsA。如A=1,2,3,4,5,6,7,8，R=(a,b)|a = b(mod 3)的等价类划分如下1=4=7=1,4,7,2=5=8=2,5,8,3=6=3,69.6偏序关系：自反、反对称且传递的的关系偏序集S，中如果既没有ab，也没有ba，那么a和b是不可比的。全序集：如果偏序集中每个元素都可比，那么为全序集，如Z，是全序集，但Z+，|不是，因为有5和7是不可比的。良序集：如果是全序集，而且S的每个非空机子都有一个最小元素，那么为良序集。哈塞图：对有穷偏序集，去掉环，去掉所有由传递性可以得到的边，排列所有的边使得方向向上。 极大元极小元：
11、图中的顶元素和底元素，可能有多个 最大元最小元：只有唯一的一个，比其他都或 上界下界：只有唯一的一个，比其他都或 格：每对元素都有最小上界和最大下界十、 图10.1图的概念简单图：每对顶点最多只有一条边多重图：每对顶点可以有多条边无向图：边没有方向有向图：边有方向10.2图的术语无向图中，点v的度为deg(v)，如果v是一个环，那么度为2。度为0的点是孤立的，度为1的点是悬挂的。有m条边的无向图那么2m=deg(v)。无向图有偶数个度为奇数的点，因为2m=deg(Vi)+deg(Vj)。 有向图中，点v的入度为deg-(v)，出度为deg+(v)，且deg-(v)=deg+(v)=边数。有向图
12、忽略边的方向后得到的图叫做根本无向图，它们有一样的边数。会画完全图Kn、圈图、轮图Wn。二分图，将点分成2局部，每条边都连着一局部和另一局部。用着色法判读是否是二分图。完全二分图Kn,m是边最多的二分图。10.3图的表示邻接表：无向简单图包括顶点和相邻顶点，不太好表示无向多重图因为边的数量不好表示。有向图包括起点和终点。邻接矩阵：无向简单图按顶点排列，如果vi和vj之间相邻那么aij是1，否那么是0。无向多重图这时aij是vi和vj之间的边数。可知无向图的邻接矩阵都是对称阵。有向简单图也按照顶点排列，如果vi，vj是边那么aij是1，否那么是0。有向多重图也按顶点排列，只不过aij是vi，vj
13、之间的边数。关联矩阵：将图G按v行e列排列，如果vi和ej关联，那么aij是1，否那么是0。图的同构：简单图G1和G2，如果存在一一对应的从V1到V2的函数f，且对V1的a和b来说，a与b相邻当仅当f(a)与f(b)在G2中相邻，那么G1和G2是同构的，f称为同构。图形不变量如顶点数、边数、度数，如果不同那么不同构，如果一样那么可能同构。当我们找到f后，还要比拟两个图的邻接矩阵，看f是否是保持边的。10.4图的连通性简单图中，用x0=u，x1.xn=v来表示一条通路，假设u=v且路长度大于0，那么是回路，如果不包含重复的边，那么这条通路是简单的。无向图中每对不同顶点之间都有通路那么这个图是连通
14、的，割点关节点、割边桥去掉后就会使图变得不连通，不含割点的图叫做不可割图。有向图中，任意一对顶点a和b，都有从a到b以及从b到a的通路，那么这个有向图是强连通的，如果只是根本无向图能保持联通那么叫做弱联通的，会求强连通分支。通路与同构：可以用长度为k2的简单回路的存在性来证不同构或者是潜在的同构映射f，同样找到f后还要验证f保持边。图G允许是有向和无向、多重边和环的vi到vj的长度为n的不同通路的条数等于Ani,j，A是G的邻接矩阵。10.5欧拉回路与哈密顿回路欧拉回路：包含G的每一条边的简单回路。欧拉通路：包含G的每一条边的简单通路。含有至少2个顶点的连通多重图有欧拉回路当仅当它的每个顶点度
15、都为偶数，有欧拉通路但无欧拉回路当仅当它恰有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-6。推论2：G中有度不超过5的顶点。推论3：v3且没有长度为3的回路，那么e2v-4。库拉兔斯基定理：假设G是平面图，那么删掉一条边u,v并添加一个新顶点w和两条边u,w和v,w得到的仍然是平面图。假设G1和G2都是这样得到的，那么G1和G2是同胚的。一个图是非平面图当仅当它包含一个同胚于K3,3或者K5的子图。10.8着色图地图转换为对偶图时，区域变顶点，相邻的区域那么顶点相连。图的着色数是指着色所需的最少颜色数(G)，这个值不超过4。(Kn)=n，(Km,n)=2，()=2当n为偶数且4；()=3当n为奇数且3。. .word.