(完整word版)离散数学知识点整理

.

. 离散数学

一、逻辑和证明

1.1命题逻辑

命题：是一个可以判断真假的陈述句。

联接词：∧、∨、→、↔、¬。记住“p仅当q”意思是“如果p，则q”，即p→。记住“q除非p”意思是“¬p→q”。会考察条件语句翻译成汉语。

构造真值表

p q p∧q p∨q p→q p↔q p⊙q ¬p

T T T T T T F F

T F F T F F T F

F T F T T F T T

F F F F T T F T

1.2语句翻译

系统规范说明的一致性是指系统没有可能会导致矛盾的需求，即若pq无论取何值都无法让复合语句为真，则该系统规范说明是不一致的。

1.3命题等价式

逻辑等价：在所有可能情况下都有相同的真值的两个复合命题，可以用真值表或者构造新的逻辑等价式。

证逻辑等价是通过p推导出q，证永真式是通过p推导出T。

逻辑等价式

p∧T ⇔ p

p∨F ⇔ p 恒等律

p∧F ⇔ F

p∨T ⇔ T 支配律

p∧p ⇔ p 幂等律

¬(¬P) ⇔ p 双否律

p∧q ⇔ q∧p 交换律

(p∧q)∧r ⇔ p∧(q∧r) 结合律

p∨(q∧r) ⇔ (p∨q)∧(p∨r)

p∧(q∨r) ⇔ (p∧q)∨(p∧r) 分配律

¬(p∧q) ⇔ ¬p∨¬q

¬(p∨q) ⇔ ¬p∧¬q 德摩根律

p∨(p∧q) ⇔ p

P∧(p∨q) ⇔ p 吸收律

p∧¬p ⇔ F

p∨¬p ⇔ T 否定律

条件命题等价式

p→q ⇔ ¬p∨q

p→q ⇔ ¬q→¬p

p∨q ⇔ ¬p→q

p∧q ⇔ ¬(p→¬q)

¬(p→q) ⇔ p∧¬q

(p→q)∧(p→r) ⇔ p→(q∧r) .

. (p→r)∧(q→r)

⇔ (p∨q)→r

(p→q)∨(p→r) ⇔ p→(q∨r)

(p→r)∨(q→r) ⇔ (p∧q)→r

双条件命题等价式

p↔q ⇔ (p→q)∧(q→p)

p↔q ⇔ ¬p↔¬q

p↔q ⇔ (p∧q)∨(¬p∧¬q)

¬(p↔q) ⇔ p↔¬q

1.4量词

谓词+量词变成一个更详细的命题，量词要说明论域，否则没有意义，如果有约束条件就直接放在量词后面，如∀x>0P(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) ⇔ ∃x¬P(x)，¬∃xP(x) ⇔ ∀x¬P(x)。

1.5量词嵌套

我们采用循环的思考方法。量词顺序的不同会影响结果。语句到嵌套量词语句的翻译，注意论域。嵌套量词的否定就是连续使用德摩根定律，将否定词移入所有量词里。

1.6推理规则

一个论证是有效的，如果它的所有前提为真且蕴含着结论为真。但有效论证不代表结论正确，因为也许有的前提是假的。

推理规则，都是基于永真式的，用来证明一个前提蕴含一个结论。而基于可满足式的推理规则叫谬误。

p

p→q (p∧(p→q))→q 假言推理

q

p→q

q→r ((p→q)∧(q→r))→(p→r) 假言三段论

p→r

¬q

p→q (¬q∧(p→q))→¬p 取拒式

¬p

p∨q

¬p ((p∨q)∧¬p)→q 析取三段论

q

p p→(p∨q) 附加律

p∨q

p∧q (p∧q)→p 化简律

p

p

q （p∧q）→（p∧q） 合取律 .

. p∧q

p∨q

¬p∨r (p∨q)∧(¬p∨r)→(q∨r) 消解律

q∨r

量化推理规则

∀xP(x) 全称实例

P(c)

P(c)，任意c 全称引入

∀P(x)

∃xP(x) 存在实例

P(c)，对某个c

P(c)，对某个c 存在引入

∃xP(x)

命题和量化命题的组合使用。

二、集合、函数、序列、与矩阵

2.1集合

∈说的是元素与集合的关系，⊆说的是集合与集合的关系。常见数集有N={0,1,2,3...}，Z整数集，Z+正整数集，Q有理数集，R实数集，R+正实数集，C复数集。

A和B相等当仅当∀x(x∈A↔x∈B)；A是B的子集当仅当∀x(x∈A→x∈B)；

A是B的真子集当仅当∀x(x∈A→x∈B)∧∃x(x∉A∧x∈B)。

幂集：集合元素的所有可能组合，肯定有∅何它自身。如∅的幂集就是{∅}，而{∅}的幂集是{∅，{∅}}。

笛卡尔积：A×B，结果是序偶，其中的一个子集叫一个关系。

带量词和集合符号如∀x∈R（x2>0）是真的，则所有真值构成真值集。

集合恒等式 名称

(A∪B)'=A'∩B'

(A∩B)'=A'∪B' 德摩根律

A∪(A∩B)=A

A∩(A∪B)=A 吸收律

2.3函数

考虑A→B的函数关系，定义域、陪域（实值函数、整数值函数）、值域、像集（定义域的一个子集在值域的元素集合）。

一对一或者单射：B可能有多余的元素，但不重复指向。

映上或者满射：B中没有多余的元素，但可能重复指向。

一一对应或者双射：符合上述两种情况的函数关系。

反函数：如果是一一对应的就有反函数，否则没有。

合成函数：fοg(a)=f(g(a))，一般来说交换律不成立。

2.4序列

无限集分为：一组是和自然数集合有相同基数，另一组是没有相同基数。前者是可数的，后者不可数。想要证明一个无限集是可数的只要证明它与自然数之间有一一对应的关系。

如果A和B是可数的，则A∪B也是可数的。 .

. 如果存在一对一函数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)/2

1+22+32+...+n2 = n(n+1)(2n+1)/6

1+23+33+...+n3 = n2(n+1)2/4

2.6矩阵

普通矩阵和、减、乘积，0-1矩阵还可以∧、∨、⊙（和相乘类似，用∨代替+，用∧代替×）

九、关系

9.1关系及其性质

设A和B是集合，从A到B的二元关系是A×B的子集。一个从A到B的二元关系是集合R，第一个元素取自A，第二个元素取自B，当(a,b)属于R时写作aRb。

集合A上的关系是A到A的关系，有n个元素就有n2个有序对，n2个有序对就有2n2个关系。

考虑集合A到A的关系R：

任意a∈A都有（a，a）∈R，则R是集合A上的自反关系。

任意a，b∈A，若（a，b）∈R都有（b，a）∈R，则R是对称关系。

任意a，b∈A，若（a，b）∈R且（b，a）∈R一定有a=b，则R是反对称关系。

任意a，b，c∈A，若（a，b）∈R且（b，c）∈R一定有（a，c）∈R，则R是传递关系。

若R是A到B的关系，S是B到C的关系，R与S的合成RοS是有序数对（a，c）。其中a∈A，c∈C，且存在一个b∈B使得（a，b）∈R，（b，c）∈S。二元关系的5种复合要会翻译成汉语。

9.3关系的表示

0-1矩阵法：A有n个元素，B有m个元素，用一个n×m的矩阵MR表示，mij=1表示有关系。自反关系的0-1矩阵主对角线全为1；对称关系的0-1矩阵是对称阵；反对称关系的0-1矩阵关于主对角线反对称。

MR1∪R2=MR1∨MR2，MR1∩R2=MR1∧MR2，MR1οR2=MR1⊙MR2。

有向图法：A有n个元素，每一个关系是一条有向边。自反关系的图每一个顶点都有一个环；对称关系的图在不同顶点之间每一条边都存在与之对应的反方向边（也可用无向图）；反对称关系的图在不同顶点之间每一条边都不存在与之对应的反方向边；传递关系的图在3个不同顶点之间构成正确方向的三角形。

9.4关系的闭包

自反闭包：R∪Δ，其中Δ={（a，a）|a∈A}

对称闭包：R并R-1，其中R-1={（b,a）|（a，b）∈R}

传递闭包：R矩阵传递闭包=MR∨MR[2]∨MR[3]...∨MR[n]，了解沃舍尔算法

9.5等价关系：自反、对称且传递的关系

集合A的元素a在R上的等价类[a]={s|(a,s)∈R∧s∈A}。如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,6}

9.6偏序关系：自反、反对称且传递的的关系

偏序集（S，≤）中如果既没有a≤b，也没有b≤a，则a和b是不可比的。

全序集：如果偏序集中每个元素都可比，则为全序集，如（Z，≤）是全序集，但（Z+，|）不是，因为有5和7是不可比的。

良序集：如果是全序集，而且S的每个非空机子都有一个最小元素，则为良序集。

哈塞图：对有穷偏序集，去掉环，去掉所有由传递性可以得到的边，排列所有的边使得方向向上。

极大元极小元：图中的顶元素和底元素，可能有多个

最大元最小元：只有唯一的一个，比其他都＞或＜

上界下界：只有唯一的一个，比其他都≥或≤

格：每对元素都有最小上界和最大下界

十、图

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)=边数。有向图忽略边的方向后得到的图叫做基本无向图，它们有相同的边数。

会画完全图Kn、圈图Cn、轮图Wn。

二分图，将点分成2部分，每条边都连着一部分和另一部分。用着色法判读