1、离散数学1、逻辑和证明1.1 命题逻辑命题：是一个可以判断真假的陈述句。联接词：、。记住“p 仅当 q”意思是“如果 p，则 q”，即 p。记住“q 除非 p”意思是“pq”。会考察条件语句翻译成汉语。构造真值表p q pq pq pq pq pq pT T T T T T F FT F F T F F T FF T F T T F T TF F F F T T F T1.2 语句翻译系统规范说明的一致性是指系统没有可能会导致矛盾的需求，即若 pq 无论取何值都无法让复合语句为真，则该系统规范说明是不一致的。1.3 命题等价式逻辑等价：在所有可能情况下都有相同的真值的两个复合命题，可以用真值表
2、或者构造新的逻辑等价式。证逻辑等价是通过 p 推导出 q，证永真式是通过 p 推导出 T。逻辑等价式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) pqp(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)(
3、qp)pq pqpq (pq)(pq)(pq) pq1.4 量词谓词+量词变成一个更详细的命题，量词要说明论域，否则没有意义，如果有约束条件就直接放在量词后面，如x0P(x)。当论域中的元素可以一一列举，那么xP(x)就等价于 P(x1)P(x2).P(xn)。同理，xP(x)就等价于 P(x1)P(x2).P(xn)。两个语句是逻辑等价的，如果不论他们谓词是什么，也不论他们的论域是什么，他们总有相同的真值，如x（P(x)Q(x) 和( xP(x)(xQ(x)。量词表达式的否定：xP(x) xP(x)，xP(x) xP(x)。1.5 量词嵌套我们采用循环的思考方法。量词顺序的不同会影响结果。语
4、句到嵌套量词语句的翻译，注意论域。嵌套量词的否定就是连续使用德摩根定律，将否定词移入所有量词里。1.6 推理规则一个论证是有效的，如果它的所有前提为真且蕴含着结论为真。但有效论证不代表结论正确，因为也许有的前提是假的。推理规则，都是基于永真式的，用来证明一个前提蕴含一个结论。而基于可满足式的推理规则叫谬误。ppqq(p(pq)q 假言推理pqqrpr(pq)(qr)(pr) 假言三段论qpqp(q(pq)p 取拒式pqpq(pq)p)q 析取三段论ppqp(pq) 附加律pqp(pq)p 化简律pqpq（pq）（pq） 合取律pqprqr(pq)(pr)(qr) 消解律量化推理规则xP(x)P
5、(c)全称实例P(c)，任意 cP(x)全称引入xP(x)P(c)，对某个 c存在实例P(c)，对某个 cxP(x)存在引入命题和量化命题的组合使用。2、集合、函数、序列、与矩阵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，结果是序偶，其中的一个
6、子集叫一个关系。带量词和集合符号如xR（x 20）是真的，则所有真值构成真值集。集合恒等式 名称(AB)=AB (AB)=AB德摩根律A(AB)=AA(AB)=A吸收律2.3 函数考虑 AB 的函数关系，定义域、陪域（实值函数、整数值函数）、值域、像集（定义域的一个子集在值域的元素集合）。一对一或者单射：B 可能有多余的元素，但不重复指向。映上或者满射：B 中没有多余的元素，但可能重复指向。一一对应或者双射：符合上述两种情况的函数关系。反函数：如果是一一对应的就有反函数，否则没有。合成函数：fg(a)=f(g(a)，一般来说交换律不成立。2.4 序列无限集分为：一组是和自然数集合有相同基数，另
7、一组是没有相同基数。前者是可数的，后者不可数。想要证明一个无限集是可数的只要证明它与自然数之间有一一对应的关系。如果 A 和 B 是可数的，则 AB 也是可数的。如果存在一对一函数 f 从 A 到 B 和一对一函数 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+.+n3 = n2(n+1)2/42.6 矩阵普通矩阵和、减、乘积，0-1 矩阵还可以、（和相乘类似，用代替+，用代替）9、关系9.
8、1 关系及其性质设 A 和 B 是集合，从 A 到 B 的二元关系是 AB 的子集。一个从 A 到 B 的二元关系是集合 R，第一个元素取自 A，第二个元素取自 B，当(a,b)属于 R 时写作 aRb。集合 A 上的关系是 A 到 A 的关系，有 n 个元素就有 n2个有序对，n 2个有序对就有 2n2个关系。考虑集合 A 到 A 的关系 R：任意 aA 都有（a，a）R，则 R 是集合 A 上的自反关系。任意 a，bA，若（a，b）R 都有（b，a）R，则 R 是对称关系。任意 a，bA，若（a，b）R 且（b，a）R 一定有 a=b，则 R 是反对称关系。任意 a，b，cA，若（a，b）
9、R 且（b，c）R 一定有（a，c）R，则R 是传递关系。若 R 是 A 到 B 的关系，S 是 B 到 C 的关系，R 与 S 的合成 RS 是有序数对（a，c）。其中 aA，cC，且存在一个 bB 使得（a，b）R，（b，c）S。二元关系的 5 种复合要会翻译成汉语。9.3 关系的表示0-1 矩阵法：A 有 n 个元素，B 有 m 个元素，用一个 nm 的矩阵 MR表示，mij=1 表示有关系。自反关系的 0-1 矩阵主对角线全为 1；对称关系的 0-1 矩阵是对称阵；反对称关系的 0-1 矩阵关于主对角线反对称。MR1R2 =MR1M R2，M R1R2 =MR1M R2，M R1 R2
10、=MR1M R2。 有向图法：A 有 n 个元素，每一个关系是一条有向边。自反关系的图每一个顶点都有一个环；对称关系的图在不同顶点之间每一条边都存在与之对应的反方向边（也可用无向图）；反对称关系的图在不同顶点之间每一条边都不存在与之对应的反方向边；传递关系的图在 3 个不同顶点之间构成正确方向的三角形。9.4 关系的闭包自反闭包：R，其中 =（a，a）|aA对称闭包：R 并 R-1，其中 R-1=（b,a）|（a，b）R传递闭包：R 矩阵传递闭包=M RM R2M R3.M Rn，了解沃舍尔算法9.5 等价关系：自反、对称且传递的关系集合 A 的元素 a 在 R 上的等价类a=s|(a,s)R
11、sA。如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 的每个非空机子都有一个最小元素，则为良序集。哈塞图：对有穷偏序集，去掉环，去掉所有由传递性可以得到的边，排列所有的边使得方向向上。极大元极小元：图中的顶元素和底元素
12、，可能有多个最大元最小元：只有唯一的一个，比其他都或上界下界：只有唯一的一个，比其他都或格：每对元素都有最小上界和最大下界10、图10.1 图的概念简单图：每对顶点最多只有一条边多重图：每对顶点可以有多条边无向图：边没有方向有向图：边有方向10.2 图的术语无向图中，点 v 的度为 deg(v)，如果 v 是一个环，则度为 2。度为 0 的点是孤立的，度为 1 的点是悬挂的。有 m 条边的无向图则 2m=deg(v)。无向图有偶数个度为奇数的点，因为 2m=deg(V i)+deg(V j)。 有向图中，点 v 的入度为 deg-(v)，出度为 deg+(v)，且 deg-(v)=deg+(v
13、)=边数。有向图忽略边的方向后得到的图叫做基本无向图，它们有相同的边数。会画完全图 Kn、圈图 Cn、轮图 Wn。二分图，将点分成 2 部分，每条边都连着一部分和另一部分。用着色法判读是否是二分图。完全二分图 Kn,m是边最多的二分图。10.3 图的表示邻接表：无向简单图包括顶点和相邻顶点，不太好表示无向多重图因为边的数量不好表示。有向图包括起点和终点。邻接矩阵：无向简单图按顶点排列，如果 vi和 vj之间相邻则 aij是 1，否则是 0。无向多重图这时 aij是 vi和 vj之间的边数。可知无向图的邻接矩阵都是对称阵。有向简单图也按照顶点排列，如果v i，v j是边则 aij是 1，否则是
14、0。有向多重图也按顶点排列，只不过 aij是v i，v j之间的边数。关联矩阵：将图 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.x n=v 来表示一条通
15、路，若 u=v 且路长度大于 0，则是回路，如果不包含重复的边，则这条通路是简单的。无向图中每对不同顶点之间都有通路则这个图是连通的，割点（关节点）、割边（桥）去掉后就会使图变得不连通，不含割点的图叫做不可割图。有向图中，任意一对顶点 a 和 b，都有从 a 到 b 以及从 b 到 a 的通路，则这个有向图是强连通的，如果只是基本无向图能保持联通则叫做弱联通的，会求强连通分支。通路与同构：可以用长度为 k2 的简单回路的存在性来证不同构或者是潜在的同构映射 f，同样找到 f 后还要验证 f 保持边。图 G（允许是有向和无向、多重边和环）的 vi到 vj的长度为 n 的不同通路的条数等于 Ani
16、,j，A 是 G 的邻接矩阵。10.5 欧拉回路与哈密顿回路欧拉回路：包含 G 的每一条边的简单回路。欧拉通路：包含 G 的每一条边的简单通路。含有至少 2 个顶点的连通多重图有欧拉回路当仅当它的每个顶点度都为偶数，有欧拉通路但无欧拉回路当仅当它恰有 2 个度为奇数的顶点。哈密顿回路：包含 G 的每一个顶点恰好一次的简单回路。哈密顿通路：包含 G 的每一个顶点恰好一次的简单通路。含有至少 3 个顶点的简单图，若每个顶点的度都(n/2)，或者每一对不相邻的顶点 u 和 v 都有 deg(u)+deg(v)n，则有哈密顿回路。最短通路算法：迪克斯特拉算法和旅行商问题（枚举）10.7 平面图欧拉公式
17、：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。(K n)=n，(K m,n)=2，(C n)=2 当 n 为偶数且4；(C n)=3 当 n 为奇数且3。
