再谈离散数学

1、2/21/2022 4:24 PM Discrete Math. , DeRen Chen1再谈离散数学再谈离散数学Reviewing in Reviewing in Discrete Mathematics Discrete Mathematics 2/21/2022 4:24 PM Discrete Math. , DeRen Chen2 Discrete Math. 离散数学离散数学 研究离散对象及其相互间关系的一门数学学科。研究离散对象及其相互间关系的一门数学学科。 研究离散结构的数学分支。（辞海）研究离散结构的数学分支。（辞海）离散数学的内容离散数学的内容：基础：基础概念概念 原理原

2、理方法方法 应用应用实践实践2/21/2022 4:24 PM Discrete Math. , DeRen Chen3基础部分基础部分: 逻辑逻辑(Logic) 集合集合(Sets) 算法算法(Algorithms) 数论数论(Number Theory)原理部分原理部分: 数学推理数学推理(Reasoning) 计数原理计数原理(Counting) 关系关系(Relations)应用部分应用部分: 图图(Graphs) 树树(Trees) 代数系统：布尔代数代数系统：布尔代数(Boolean Algebra)，群（群（Group）2/21/2022 4:24 PM Discrete Mat

3、h. , DeRen Chen4逻辑（逻辑（LOGIC）：命题逻辑命题逻辑 Proposition Logic命题演算命题演算 Propositional Equivalences谓词和量词谓词和量词 Predicates and Quantifiers2/21/2022 4:24 PM Discrete Math. , DeRen Chen5 （1）命题的概念：）命题的概念：定义、逻辑值、定义、逻辑值、 符号化表示符号化表示（2）从简单命题到复合命题：）从简单命题到复合命题： 逻辑联接词：运算方法、运算优先级逻辑联接词：运算方法、运算优先级（3）从命题常量到命题变量，）从命题常量到命题变量，

4、 从复合命题到命题公式：从复合命题到命题公式： 命题公式的真值描述：命题公式的真值描述：真值表真值表（4）命题公式的分类：）命题公式的分类： 永真公式、永假公式、可满足公式永真公式、永假公式、可满足公式 （5）命题公式的等价演算：）命题公式的等价演算：基本等价定理；两种方法基本等价定理；两种方法（6）命题公式的标准化描述：）命题公式的标准化描述：表达、判定、分类与应用表达、判定、分类与应用（7）从命题到命题函数：）从命题到命题函数：N元谓词、个体、个体变量、个体域元谓词、个体、个体变量、个体域（8）从命题公式到谓词公式：）从命题公式到谓词公式：存在量词、全称量词；变量的分类存在量词、全称量词；

5、变量的分类（9）谓词公式的演算：）谓词公式的演算：基本等价定理基本等价定理2/21/2022 4:24 PM Discrete Math. , DeRen Chen62/21/2022 4:24 PM Discrete Math. , DeRen Chen7p q Tp q Fp (p q) p Absorption Laws/吸收律p (p q) pp q p qp q (p q) ( q p)2/21/2022 4:24 PM Discrete Math. , DeRen Chen8判断命题公式逻辑等价的方法：判断命题公式逻辑等价的方法： 1、真值表、真值表 2、命题公式的演算、命题公式的

6、演算 基本等值定理（基本等价定理）；基本等值定理（基本等价定理）； 公式的代入不变性；公式的代入不变性； 等值关系的传递性。等值关系的传递性。2/21/2022 4:24 PM Discrete Math. , DeRen Chen9命题公式逻辑等价关系的应用：命题公式逻辑等价关系的应用： 1、判定是否逻辑等价；、判定是否逻辑等价； 2、判断是否为永真公式或永假公式；、判断是否为永真公式或永假公式； 3、命题公式的化简、命题公式的化简 2/21/2022 4:24 PM Discrete Math. , DeRen Chen10定理定理2 （基本量词等值定律）（基本量词等值定律）量词分配律量词

7、分配律 Vx（A(x)B(x)）VxA(x)VxB(x) x(A(x)B(x)） xA(x) xB(x)另两种情况的思考：另两种情况的思考：V与与， 与与量词否定律量词否定律2/21/2022 4:24 PM Discrete Math. , DeRen Chen11量词扩张量词扩张/收缩律收缩律Vx(PB(x)PVxB(x)Vx(PB(x)PVxB(x) x(PB(x)P xB(x) x(PB(x)P x B(x)这里这里A、B是任意包括个体变量是任意包括个体变量x的谓词公式，的谓词公式，P是不包括是不包括个体变量个体变量x的任意谓词公式。的任意谓词公式。2/21/2022 4:24 PM

8、Discrete Math. , DeRen Chen12 集合集合1.集合的表示集合的表示2.集合间的关系：相等、包含集合间的关系：相等、包含3.集合间的运算集合间的运算4.一些特殊的集合：空集、全集、幂集、一些特殊的集合：空集、全集、幂集、X集集5.集合的分类：集合的基集合的分类：集合的基6.函数的概念函数的概念7.函数的分类函数的分类8.函数的运算函数的运算9.一些特殊的应用函数：语言一些特殊的应用函数：语言2/21/2022 4:24 PM Discrete Math. , DeRen Chen132/21/2022 4:24 PM Discrete Math. , DeRen Che

9、n142/21/2022 4:24 PM Discrete Math. , DeRen Chen15证明两个集合相等的方法：证明两个集合相等的方法：1、定义方法：谓词公式、定义方法：谓词公式2、相等定理：互相包含、相等定理：互相包含3、集合相等运算：基本相等定理、集合相等运算：基本相等定理4、Venn 图（文氏图）：图解图（文氏图）：图解5、位运算、位运算2/21/2022 4:24 PM Discrete Math. , DeRen Chen16一对一，单函数，单射一对一，单函数，单射映上的，满函数，满射映上的，满函数，满射一一对应，双射一一对应，双射逆函数逆函数函数的复合运算，积运算函数的

10、复合运算，积运算2/21/2022 4:24 PM Discrete Math. , DeRen Chen17几个常用的函数：几个常用的函数：Eigenfunctionfloor functionceiling function关于集合的进一步讨论（基于函数）：关于集合的进一步讨论（基于函数）： Sequences string Language Countable of elements in sets2/21/2022 4:24 PM Discrete Math. , DeRen Chen18 算法（算法（Algorithm）是通过一个有限的指是通过一个有限的指令序列集合对特定问题进行求解

11、的一种计算执令序列集合对特定问题进行求解的一种计算执行描述。行描述。 An algorithm is a finite set of precise instructions for performing a computation or for solving a problem.2/21/2022 4:24 PM Discrete Math. , DeRen Chen19一个算法通常应具有下列特征：一个算法通常应具有下列特征：（1）输入：一个算法具有零个或多个取自指定集合的输入）输入：一个算法具有零个或多个取自指定集合的输入值；值；（2）输出：对算法的每一次输入，算法具有一个或多个与）输出

12、：对算法的每一次输入，算法具有一个或多个与输入值接联系的输出值；输入值接联系的输出值；（3）确定性：算法的每一个指令步骤都是明确的；）确定性：算法的每一个指令步骤都是明确的；（4）有限性：对算法的每一次输入，算法都必须在有限步）有限性：对算法的每一次输入，算法都必须在有限步骤（即有限时间）内结束；骤（即有限时间）内结束；（5）正确性：对每一次输入，算法应产生出正确的输出值；）正确性：对每一次输入，算法应产生出正确的输出值；（6）通用性：算法的执行过程可应用于所有同类求解问题，）通用性：算法的执行过程可应用于所有同类求解问题，而不是仅适用于特殊的输入。而不是仅适用于特殊的输入。2/21/2022

13、 4:24 PM Discrete Math. , DeRen Chen20Let f and g be functions from the set of R or I to the set of R. Call that f(x) is O(g(x) if there are constants C and k such that |f(x)| k. Read as “f(x) is big-oh of g(x)” O:Landau symbol关于关于C和和k 的说明：的说明： 1、 不唯一不唯一 2、是有序对作为元素的一个无限集、是有序对作为元素的一个无限集 3、尽可能小、尽可能小2/

14、21/2022 4:24 PM Discrete Math. , DeRen Chen21Theorem 1 If f(x)=an xn +an-1 xn-1+a 1 x1+a0 where ai R, i=0,1,nThen f(x) is O(xn)Theorem 2 If f1(x) is O(g1(x), f2(x) is O(g2(x),Then (f1 + f2 )(x) is O(max(g1(x), g2(x) )2/21/2022 4:24 PM Discrete Math. , DeRen Chen22Corollary 1 If f1(x) is O(g(x), f2(x

15、) is O(g(x),Then (f1 + f2 )(x) is O(g(x) )Theorem 3 If f1(x) is O(g1(x), f2(x) is O(g2(x),Then (f1 f2 )(x) is O(g1(x)g2(x) )2/21/2022 4:24 PM Discrete Math. , DeRen Chen23常用的算法复杂性分类：常用的算法复杂性分类： O(1): constant complexity O(log n): logarithmic complexity O(n): linear complexity O(n log n): n log n com

16、plexity linear O(nb) : polynomial complexity polynomial O(bn) : exponential complexity(b1) exponential O(n!): factorial complexity2/21/2022 4:24 PM Discrete Math. , DeRen Chen24Let f and g be functions from the set of R or I to the set of R. Call that f(x) is (g(x) if there are constants C and k suc

17、h that |f(x)| = C|g(x)|Wherever x k. Read as “f(x) is big-omega of g(x)” 2/21/2022 4:24 PM Discrete Math. , DeRen Chen25Let f and g be functions from the set of R or I to the set of R. Call that f(x) is (g(x) if f(x) is O(g(x) and f(x) is (g(x)Read as “f(x) is big-theta of g(x)” “f(x) is of order g(

18、x)”2/21/2022 4:24 PM Discrete Math. , DeRen Chen26数论数论 （Number Theory）1、算术基本定理、算术基本定理2、同余关系、同余关系3、密码学基础、密码学基础定义定义 设设m是一个正整数，对任意两个整数是一个正整数，对任意两个整数a、b，若，若a-b能被能被m整除，则称整除，则称a与与b是是（模（模m）同余的）同余的，或，或（模（模m）合）合同的同的/congruent by modulo m ，记为，记为 a b ( mod m) 在在m确定的情况下，简记为确定的情况下，简记为 a b 。2/21/2022 4:24 PM Disc

19、rete Math. , DeRen Chen271、整数的因子、公因子、整数的因子、公因子、GCD -EUCLID算法、算法、 GCD的线性组合的线性组合2、质数、质因子、两两互质、质数、质因子、两两互质 -整数分解整数分解3、同余关系、线性同余、中国同余定理、同余关系、线性同余、中国同余定理4、费尔玛小定理、费尔玛小定理、RSA算法算法2/21/2022 4:24 PM Discrete Math. , DeRen Chen28原理部分原理部分: 数学推理数学推理(Reasoning) 3.1 推理与证明方法推理与证明方法 3.2 数学归纳方法数学归纳方法 3.3 递推方法递推方法 计数原

20、理计数原理(Counting) 关系关系(Relations)2/21/2022 4:24 PM Discrete Math. , DeRen Chen29蕴涵演算蕴涵演算/logical implying operation 对于任意的公式对于任意的公式P和和Q，如果，如果P Q 为为T，则称，则称P蕴涵蕴涵Q， 记为记为P Q 或或P/Q蕴涵演算的推广表示：蕴涵演算的推广表示： P1、 P2 、 、Pn Q 前提组前提组/hypotheses 结论结论/conclusion2/21/2022 4:24 PM Discrete Math. , DeRen Chen30Rule of Infe

21、rence NameP P QAddition/析取附加式析取附加式P Q P Simplification/合取化简式合取化简式P、Q P Q Conjunction/并发式并发式P、 P Q QModus ponens/分离式分离式 Q、 P Q PModus tollens/拒取式拒取式 p、P Q QDisjunctive syllogism/析取三段式析取三段式P Q、 Q R P R Hypothetical syllogism/假言三段式假言三段式2/21/2022 4:24 PM Discrete Math. , DeRen Chen31定理证明方法：定理证明方法：1、直接证明

22、、直接证明/direct proof: p Q 2、间接证明、间接证明/indirect proof : p Q Q P3、空证明、空证明/vacuous proof: p Q 其中其中 P为为 F4、平凡证明、平凡证明/trivial proof： p Q 其中其中 Q 为为T2/21/2022 4:24 PM Discrete Math. , DeRen Chen32定理证明方法：定理证明方法：5、反证明、反证明/proof of contradiction： P P S S6、分例证明、分例证明/proof of cases： P1 P2 Pn Q （P1 Q） （P2 Q） （Pn Q

23、）7、存在证明、存在证明/existence proof： x P(x) constructive, nonconstructive8、归纳证明、归纳证明/induction proof ： x P(x) 2/21/2022 4:24 PM Discrete Math. , DeRen Chen33（1）0N；（2）对每一个）对每一个nN，唯一定义了一个自然数，唯一定义了一个自然数n，n 称为称为n的后邻；的后邻；（3）不同的自然数，其后邻也不同；）不同的自然数，其后邻也不同；（4）没有一个自然数的后邻是）没有一个自然数的后邻是0；（5）如果有一个子集）如果有一个子集M N满足：满足： 0M；

24、 nM时必时必n M, 则则M = N自然数全体自然数全体N通过皮亚诺公理的五条公理组成。通过皮亚诺公理的五条公理组成。 这些公理缺一不可，其中性质（这些公理缺一不可，其中性质（5）称为归纳公理，并指）称为归纳公理，并指出了自然数是满足公理（出了自然数是满足公理（1）（4）的最小集合。）的最小集合。 2/21/2022 4:24 PM Discrete Math. , DeRen Chen34数学归纳法的一般公式表示：数学归纳法的一般公式表示：P(k) m(m k P(m) P(m+1) n P(n) 1、归纳基础：、归纳基础： P(k) 2、归纳步骤：、归纳步骤： m (m k P(m) P

25、(m+1)第二数学归纳法：第二数学归纳法：P(n0) k ( k n0 P(n0) P(n0+1) P(k) P(k+1) n P(n) 1、归纳基础：、归纳基础： P(n0) 2、归纳步骤：、归纳步骤： k ( k n0 P(n0) P(n0+1) P(k) P(k+1) 2/21/2022 4:24 PM Discrete Math. , DeRen Chen35有限数学归纳法：对于有限数学归纳法：对于 n0 n nk 的的 P(n)有限数学归纳法的前推公式表示：有限数学归纳法的前推公式表示：P(n0) n(n0 n nk-1 P(n) P(n+1) n (n0 n nk P(n) 1、归

26、纳基础：、归纳基础： P(n0) 2、归纳步骤：、归纳步骤： n(n0 n nk-1 P(n) P(n+1) 有限数学归纳法：对于有限数学归纳法：对于 n0 n nk 的的 P(n)有限数学归纳法的后推公式表示：有限数学归纳法的后推公式表示：P(nk ) n(n0 +1 n nk P(n) P(n-1) n (n0 n nk P(n) 1、归纳基础：、归纳基础： P(nk ) 2、归纳步骤：、归纳步骤： n(n0 +1 n nk P(n) P(n-1)2/21/2022 4:24 PM Discrete Math. , DeRen Chen36定义定义1如果一个对象部分地由自己所组成，如果一个

27、对象部分地由自己所组成，或 者 按 它 自 己 定 义 ， 则 称 为 是或 者 按 它 自 己 定 义 ， 则 称 为 是 递 归递 归 的的（Recursion）。）。f的定义域：非负整数集的定义域：非负整数集 1、递归基础：、递归基础： f(0) 2、递归步骤：、递归步骤： f(n)=g(f(k), k=0菲波那契数菲波那契数/FibonacciF(0) = 0，F(1) = 1F(n) = F (n1) + F (n2)n12/21/2022 4:24 PM Discrete Math. , DeRen Chen374、计数原理、计数原理/Counting 4.1 基本计数原理基本计数

28、原理:加法原理和乘法原理加法原理和乘法原理 The Basic of Counting 4.2 包含与排斥原理包含与排斥原理:有限集的基的运算有限集的基的运算 The Inclusion-Exclusion Principle 4.3 鸽洞原理鸽洞原理:有限集的基的比较有限集的基的比较 The Pigeonhole Principle4.4 排列与组合排列与组合:排列、组合、二项式排列、组合、二项式 Permutations and Combinations4.5 排列与组合的生成：排列与组合的生成：排列生成、组合生成排列生成、组合生成 Generating Permutations and

29、Combinations2/21/2022 4:24 PM Discrete Math. , DeRen Chen38求和规则求和规则/The Sum RuleIf a first task can be done in n ways and a second task in m ways, and if there these tasks cannot be done at the same time, then there are n+m ways to be either task.|A1 A2| = |A1| + |A2| 其中其中A1 A2 = 求和规则的推广求和规则的推广|A1 A

30、2 An | = |A1| + |A2| + + |An| 其中其中A i A j = i j, i,j =1,2,n2/21/2022 4:24 PM Discrete Math. , DeRen Chen39求积规则求积规则/The Product RuleSuppose that a procedure can be broken down into two tasks. If there are n ways to do the first task and m ways to do the second task after the first task has been done,

31、 then there are nm ways to do the procedure. |A1 A2 | = |A1| |A2|求积规则的推广求积规则的推广|A1 A2 An | = |A1| |A2| |An| 2/21/2022 4:24 PM Discrete Math. , DeRen Chen40对任意有限集对任意有限集A1、A2，成立成立 |A1 A2| = |A1| + |A2| - |A1 A2| 推广：推广：|A1 A2 An | =2/21/2022 4:24 PM Discrete Math. , DeRen Chen41The Pigeonhole Principle

32、If k+1 or more objects are placed into k boxes, then there is at least one box containing two or more of the objects.The Generalized Pigeonhole PrincipleIf N objects are placed into k boxes, then there is at least one box containing at least N/k objects.2/21/2022 4:24 PM Discrete Math. , DeRen Chen4

33、24.4 排列与组合排列与组合/Permutations and Combinations(1) 排列：排列：r-排列、全排列、排列、全排列、 r-可重排列、可重排列、r-限重排列、限重排列、r-循环排列循环排列(2) 组合：组合：r-组合、组合、 r-可重组合可重组合(3) 二项式定理与二项式系数：二项式定理与二项式系数：4.5 排列与组合的生成排列与组合的生成 Generating Permutations and Combinations2/21/2022 4:24 PM Discrete Math. , DeRen Chen43定义定义1：n个元素的集合个元素的集合A中任意选择中任意选

34、择r个（个（r n）进行排列称为进行排列称为A的一个的一个r-排列排列/r-Permutation定理定理1： n个元素的集合个元素的集合A的的r-排列数为排列数为 n(n-1)(n-2)(n-r+1) =P(n,r)特别地，当特别地，当r = n 时，记时，记P(n,r)=n! 称为称为A的一个的一个全排列全排列2/21/2022 4:24 PM Discrete Math. , DeRen Chen44排列的函数表示：排列的函数表示： |A| = n，B=1,2,r，F:BA（1）F是一个单射是一个单射 A的一个的一个r-排列排列（2）B到到A的所有的所有单射总数单射总数 P(n,r)排列

35、的球盒模型表示：排列的球盒模型表示： |A| = n n个盒子个盒子 B=1,2,r r个不同的球个不同的球F:BA且是单射且是单射 每个盒子最多放一个球每个盒子最多放一个球 A的一个的一个r-排列排列B到到A的所有的所有单射总数单射总数 球放入盒子的放法总数球放入盒子的放法总数 P(n,r)2/21/2022 4:24 PM Discrete Math. , DeRen Chen45定义定义2：n个元素的集合个元素的集合A中任意选择中任意选择r个（个（r n）称为）称为A的一个的一个r-组合组合/r-Combination定理定理2： n个元素的集合个元素的集合A的的r-组合数为组合数为 n

36、(n-1)(n-2)(n-r+1)/r! 记为记为C(n,r)组合的球盒模型表示：组合的球盒模型表示： B=0，1 两个盒子两个盒子 A n个不同的球个不同的球F:BA且使得且使得A中的中的r个元素的象为个元素的象为1 指定一个盒子恰好放指定一个盒子恰好放r个球个球 A的一个的一个r-组合组合满足条件的满足条件的F总数总数 = C(n,r) = 满足条件的球的放法总数满足条件的球的放法总数2/21/2022 4:24 PM Discrete Math. , DeRen Chen46定理定理6（Binomial Theorem/二项式定理）：二项式定理）： 对任意正整数对任意正整数n和变量和变量

37、x、y （x+y）n= nj=0 C（n，j）xn-j yj2/21/2022 4:24 PM Discrete Math. , DeRen Chen47定义定义3 n个不同元素的集合个不同元素的集合A，每个元素可重复，每个元素可重复选取，则选取，则A中任意选择中任意选择r个（个（r n）进行排列称为）进行排列称为A的一个的一个r-可重排列可重排列/r-Permutation with repetition。定理定理7 n个不同元素的集合个不同元素的集合A，每个元素可重复，每个元素可重复选取，则选取，则A的的r-可重排列总数为可重排列总数为nr。 2/21/2022 4:24 PM Discr

38、ete Math. , DeRen Chen48定义定义6 n个不同元素的集合个不同元素的集合A，每个元素可重复，每个元素可重复选取，则选取，则A中任意选择中任意选择r个（个（r n）的方式称为）的方式称为A的的一个一个r-可重组合可重组合/r-Combination with repetition。定理定理10 n个不同元素的集合个不同元素的集合A，每个元素可重，每个元素可重复选取，则复选取，则A的的r-可重组合总数为可重组合总数为 C（n-1+r，r） 2/21/2022 4:24 PM Discrete Math. , DeRen Chen49Relations 关系关系（1）二元关系的

39、概念：集合、关系、函数）二元关系的概念：集合、关系、函数 多元关系多元关系（2）二元关系的表示）二元关系的表示:集合、图形、矩阵集合、图形、矩阵（3）二元关系的性质：分类）二元关系的性质：分类（4）二元关系的运算：集合运算、函数运算、闭包运算）二元关系的运算：集合运算、函数运算、闭包运算2/21/2022 4:24 PM Discrete Math. , DeRen Chen50（5）等价关系的概念、等价关系与划分等价关系的概念、等价关系与划分（6）半序关系与半序集、全序关系与全序集半序关系与半序集、全序关系与全序集 半序集中的极小半序集中的极小/大元素、最小大元素、最小/大元素、大元素、 上

40、上/下界、上下界、上/下确界下确界 良序关系与良序集、拓扑排序良序关系与良序集、拓扑排序2/21/2022 4:24 PM Discrete Math. , DeRen Chen51 7、图、图/Graph7.1 图的概念图的概念/Introduction of Graph7.2 图的术语图的术语/Graph Terminology7.3 图的表示与同构图的表示与同构/ Representing Graph and Graph Isomorphism 表示表示:集合、表、矩阵集合、表、矩阵 图的转换、图的包含、图的转换、图的包含、 图的运算、图的同构图的运算、图的同构7.4 连通性连通性/Co

41、nnectivity2/21/2022 4:24 PM Discrete Math. , DeRen Chen52一些特殊的简单无向图：一些特殊的简单无向图： （1）Complete Graphs/完全图完全图Kn （2）Cycles/环图环图Cn （3）Wheels/轮图轮图Wn （4）n-Cubes/n-立方图立方图Qn （5）Bipartite Graphs/二分图二分图Kn,m2/21/2022 4:24 PM Discrete Math. , DeRen Chen53一些特殊的其他图：一些特殊的其他图： （1）有向完全图）有向完全图 （2）零图）零图 （3）平凡图）平凡图 （4）正则图：若图（，）中每正则图：若图（，）中每个顶点的次均为个顶点的次均为n n，称此图是，称此图是n-n-正则的正则的/n-/n-regularregular。2/21/2022 4:24 PM Discrete Math. , DeRen Chen547.5 欧拉道路与哈密尔顿道路欧拉道路与哈密尔顿道路/ Euler and Hamilton Paths7.6 最短道路问题最短道路问题/Shortest Path Problem7.7 平面图平面图/Planar Graphs 平面图的概念：无向、简单、有限、非交叉边平面图的概念：无向、简单、有限、非交叉边/区域区域 平