当前位置：文档视界 › 离散数学章节总结

离散数学章节总结

第一章

[命题逻辑]

1.逻辑运算

1.否定:Negation? NOT

2.交:Conjunction AND

3.并:Disjunction OR

4.蕴含:Implication IMPLIES

5. Biconditional ? IFF

XOR

2.逆/否/逆否

1.逆:converse

2.否:inverse

3.逆否:conytrapositive

3.问题的一致性

[逻辑等价]

→q 等价于?p q 等价于? q→?p

2. p q 等价于?p→q

p q 等价于?( p→?q)

3.(p→q)(p→r) 等价于p→(q r)

(p→r)(q→r) 等价于(p q)→r

(p→r)(q→r)等价于(p q) →r

4.证明等价: 真值表逻辑符号证明找反例

(假设左为假右必为假假设右为假左必为假)

[ 谓词逻辑]

1.量词存在

任意

量词顺序不能随机改变

不全为真:(p1p2…p n) (p1p2…p n) x P(x ) x P(x )

没有一个为真:(p1p2…p n) (p1p2…p n) x P(x ) x P(x )

[ 推理]

[ 证明]

1.证明方法:直接证明间接证明反证列举证明(列举所有情况) 构造证明(构造出满足结论的元素)

2.证明步骤:正向证明反向证明

第二章

[ 集合及运算]

1.特殊集合: R Q Z 无穷/有限集

2.集合表述方法: 列举法描述法图表法

3.集合运算: 交/并/补/差/取子集P(S)/元素数|S|/乘积P ×Q /

A B A B A B A ?=??=? n i i

A 1

= X A A ∈ n

i i

A 1= X

A A

∈

容斥原理

A i i =1n

1≤i ≤n ∑-

A i

1≤i

A i

i =1n

4.证明集合相等:1.证明互为子集 2.从属表 3.逻辑证明

[ 函数]

1.函数的定义

2.术语：定义域，值域，象，原象，范围， (a)/f(A)

第五章

[序、归纳]

1.序：在某种关系下存在最小元素则为well-ordered

2.第一数学归纳法：basic step P(C)成立and inductive step P(k)→P(k+1)

3.第二数学归纳法:basic step:P(c)成立 and inductive step: 任意k小于等于nP(k) 成立→P(n+1)

[递归]

1.递归：以相同形式用小的项来定义的大的项

不能一直递归下去（存在初始项）必须存在可以直接解决问题的一项

①basic step:原有元素

② recursive step:原有元素如何产生新元素

2.字符串的定义：空字符，回文

3.结构归纳：用于证明递归结构对所有元素都成立：

①basic step:原有元素成立

②recursive step:用递归式导出的新元素成立

[递归算法]

1.定义：把问题转化为相同形式但值更小的算法

2.递归算法有初始步骤（是可终止的）并且递归时至少改变一个参数值使之

向初始步骤靠拢

3.递归时间复杂度高，可以用非递归（loop或 stack）来代替

[程序的正确性]

1.测试与证明：证明更有说服力

2.证明：①程序会终止②（部分正确）程序只要可以终止得出的结论都是正

确的

正确的程序：对任意可能的输入都有正确的输出

部分正确，完全正确

triple：P{S}Q

P: precondition S: assertion Q:postcondition

P{S}Q:当PQ正确时为部分正确

当证明了S的可终止性为完全正确

4.程序的基本语句：赋值，命题，条件，循环

5.弱化结论：P{S}R R→Q：P{S}Q

强化条件Q→R R{S}P：Q{S}P

复合：P{S1}R R{S2}Q: P{S1;S2}Q

第六章

[加法乘法原理]

1.加法乘法原理：方法不重复，互不影响，做1or2 m+n 做1and2 mn

2.容斥原理：方法有重叠：|A B |=|A ||B ||A B |

3.包含条件的问题。

[分类原理]

1.抽屉原理。

2.抽屉原理推论：n 插入k 个抽屉：至少有一个抽屉含有[n/k]个元素（上取整）

[排列组合]

1.排列：选择的元素只出现一次r-permutation of S

P(n,r) = n(n ?1)…(n ?r+1) = n!/(n ?r)!

2.组合：

)!(!!!)!/(!),(),(),(r n r n r r n n r r P r n P r n r n C -=-==???? ??= [二项式系数]

1.杨辉三角：C(n+1, k) = C(n, k-1) + C(n, k)

第九章

[关系]

1.关系：函数的推广

2.二元关系：

①.定义：A binary relation from A to B is a set R where

a R

b denotes (a, b) R 包含于A X B . a is said to be

related to b by R.

②.数量：with |A| = m and |B| = n 共有2mn

relations from

A to B, including the empty relation as well as the relation

A X B. 3.关系图

4.自身关系：A on A ： A ×A relation on A

5.反身关系：reflexive ：a A (a,a)

Reflexive relations: 含有所有(a,a)元素的关系

6.对称关系：symmetric 对所有(a,b)

R 就有(b,a)

非对称关系：Antisymmetric: 只有当a=b 时(a,b) (b,a)才会同时R 。

即

a ≠

b , (a ,b )R → (b ,a )R

Asymmetric: 只要(a,b)

R 那么(b,a)

三者两两互不矛盾

7.传递：有(a,b)和(b,c)就有(a,c) 8.组合关系：A 交并补B

复合关系：S ：A→B R：B→C R S ：A→C ((4,2);(2,3)→(4,3)) 若A1，A2是可传递的，则A1并A2不一定可传递但A1A2与 A2A1是可传递的 R n = R R … R

[ n 元关系]

1.度，定义域

[ 关系的表示]

1.关系的表示方法: 1.元素组列表

2.函数关系

3.零一矩阵

4.图 2.零一矩阵:

|A |×|B | 0-1 matrix 对角线全为1:自反性

对称矩阵:对称性 antisymmetric:

M ij = 0 or M ji = 0 for all i≠j 3.零一矩阵的运算: 交: join M 1∨M 2 补: meet M 1∧M 2

复合: composition M 1⊙M 2

ik n k M M )()(211∧∨==

[ 关系的闭集]

1.反身闭集：原来的关系加上所有的(a,a) 在矩阵中则把对角线元素变为1

2.对称闭集：原来有的关系(a,b)加上所有的(b,a)即R U R -1其中R -1 代表R 的转置

表示补集

3.路：长度大于等于1(长度指边的条数) 从同一顶点开始、结束的路径：回路

4.传递闭集:两个顶点可由某一路径到达,用一条路直接连接这两个顶点.传递闭集包含所有这样的路

R n 代表所有长度为n 的可以连接两个顶点的路 R *代表所有任意长度的可以连接两个顶点的路 R *为传递闭集

路径的最大长度:元素总数n

零一矩阵:

]

[]3[]2[*n R R R R R M M M M M ∨∨∨∨=

[ 等价关系]

1.等价关系满足自反性,对称性,传递性.即f(x)=f(x) f(a)=f(b)则f(b)=f(a) f(a)=f(b) f(b)=f(c) 则f(a)=f(c)

满足以上三个条件的关系,若二者在关系R 下值相等,则称二者等价

2.等价集:

[a ]R 所有与a 在关系R 下等价的元素不混淆的情况下写作[R] 不同的等价集是互斥的(因具有对称性)

3.集合的划分:把集合S 划分为非空互斥的子集,所有子集的并为S 等价集可作为集合S 的划分依据

[ 偏序]

1.偏序是自反的,非对称的(antisymmetric),可传递的. (A , ?).偏序集

2.哈希图解:简化图1.箭头朝上2.去自反

3.去传递

4.去箭头

3.最小,最大元素(可能不只一个):a 比min 在关系?下大:b 比max 在关系?下小

4.字典顺序:在某一偏序关系下排序

5.全序: 在关系?下,并不一定两两元素均可比较

6.拓扑排序

易错点： 1..S D 顺序

D maps an element a to the element (5 – a), and afterwards S maps (5 – a) to all elements larger than (5 – a), resulting in S D = {(a,b) | 5 – a

?????=????????????????????==111010111011010101 011010101 ]

2[R R R M M M