离散数学章节总结
第一章
[命题逻辑]
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 /
B
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
=
A
i
1≤i ≤n ∑-
A i
?A
j
1≤i n 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) R Reflexive relations: 含有所有(a,a)元素的关系 6.对称关系:symmetric 对所有(a,b) R 就有(b,a) R 非对称关系:Antisymmetric: 只有当a=b 时(a,b) (b,a)才会同时R 。 即 a ≠ b , (a ,b )R → (b ,a )R Asymmetric: 只要(a,b) R 那么(b,a) R 三者两两互不矛盾 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 kj 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