再谈离散数学课件

DiscreteMath.离散数学研究离散对象及其相互间关系的一门数学学科。研究离散结构的数学分支。（辞海）离散数学的内容：基础——概念原理——方法应用——实践12/16/2022

1DiscreteMath.,DeRenChenDiscreteMath.12/11/20221Di基础部分:逻辑(Logic)集合(Sets)算法(Algorithms)数论(NumberTheory)原理部分:数学推理(Reasoning)计数原理(Counting)关系(Relations)应用部分:图(Graphs)树(Trees)代数系统：布尔代数(BooleanAlgebra)，群（Group）12/16/2022

2DiscreteMath.,DeRenChen基础部分:原理部分:应用部分:12/11/20222Dis逻辑（LOGIC）：命题逻辑PropositionLogic命题演算PropositionalEquivalences谓词和量词PredicatesandQuantifiers12/16/2022

3DiscreteMath.,DeRenChen逻辑（LOGIC）：12/11/20223Discrete

（1）命题的概念：定义、逻辑值、符号化表示（2）从简单命题到复合命题：

逻辑联接词：运算方法、运算优先级（3）从命题常量到命题变量，从复合命题到命题公式：命题公式的真值描述：真值表（4）命题公式的分类：

永真公式、永假公式、可满足公式

（5）命题公式的等价演算：基本等价定理；两种方法（6）命题公式的标准化描述：表达、判定、分类与应用（7）从命题到命题函数：N元谓词、个体、个体变量、个体域（8）从命题公式到谓词公式：存在量词、全称量词；变量的分类（9）谓词公式的演算：基本等价定理12/16/2022

4DiscreteMath.,DeRenChen12/11/20224DiscreteMathTable512/16/2022

5DiscreteMath.,DeRenChenTable512/11/20225DiscreteMaTable6p∨qTp∧qFp∨(p∧q)pAbsorptionLaws/吸收律p∧(p∨q)pp→qp∨qpq(p→q)∧(q→p)12/16/2022

6DiscreteMath.,DeRenChenTable6p∨qT12/11/2022判断命题公式逻辑等价的方法：1、真值表2、命题公式的演算

基本等值定理（基本等价定理）；公式的代入不变性；等值关系的传递性。12/16/2022

7DiscreteMath.,DeRenChen判断命题公式逻辑等价的方法：12/11/20227Disc命题公式逻辑等价关系的应用：1、判定是否逻辑等价；2、判断是否为永真公式或永假公式；3、命题公式的化简

12/16/2022

8DiscreteMath.,DeRenChen命题公式逻辑等价关系的应用：12/11/20228Disc定理2（基本量词等值定律）量词分配律Vx（A(x)∧B(x)）VxA(x)∧VxB(x)x(A(x)∨B(x)）

xA(x)∨xB(x)另两种情况的思考：V与∨，与∧量词否定律12/16/2022

9DiscreteMath.,DeRenChen定理2（基本量词等值定律）12/11/20229Dis量词扩张/收缩律Vx(P∨B(x))P∨VxB(x)Vx(P∧B(x))P∧VxB(x)x(P∨B(x))P∨xB(x)x(P∧B(x))P∧x

B(x)这里A、B是任意包括个体变量x的谓词公式，P是不包括个体变量x的任意谓词公式。12/16/2022

10DiscreteMath.,DeRenChen量词扩张/收缩律12/11/202210Discrete

集合集合的表示集合间的关系：相等、包含集合间的运算一些特殊的集合：空集、全集、幂集、X集集合的分类：集合的基函数的概念函数的分类函数的运算一些特殊的应用函数：语言12/16/2022

11DiscreteMath.,DeRenChen集合12/11/202211DiscreteMath.Table112/16/2022

12DiscreteMath.,DeRenChenTable112/11/202212DiscreteM命题演算的基本等值定理12/16/2022

13DiscreteMath.,DeRenChen命题演算的基本等值定理12/11/202213Discre证明两个集合相等的方法：1、定义方法：谓词公式2、相等定理：互相包含3、集合相等运算：基本相等定理4、Venn图（文氏图）：图解5、位运算12/16/2022

14DiscreteMath.,DeRenChen证明两个集合相等的方法：12/11/202214Discr一对一，单函数，单射映上的，满函数，满射一一对应，双射逆函数函数的复合运算，积运算12/16/2022

15DiscreteMath.,DeRenChen一对一，单函数，单射映上的，满函数，满射一一对应，双射逆函数几个常用的函数：Eigenfunctionfloorfunctionceilingfunction关于集合的进一步讨论（基于函数）：SequencesstringLanguageCountableofelementsinsets12/16/2022

16DiscreteMath.,DeRenChen几个常用的函数：关于集合的进一步讨论（基于函数）：12/11DEFINITION2.

算法（Algorithm）是通过一个有限的指令序列集合对特定问题进行求解的一种计算执行描述。Analgorithmisafinitesetofpreciseinstructionsforperformingacomputationorforsolvingaproblem.12/16/2022

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

18DiscreteMath.,DeRenChen一个算法通常应具有下列特征：12/11/202218DisLetfandgbefunctionsfromthesetofRorItothesetofR.Callthatf(x)isO(g(x))ifthereareconstantsCandksuchthat|f(x)|<=C|g(x)|Whereverx>k.Readas“f(x)isbig-ohofg(x)”O:Landausymbol关于C和k的说明：1、不唯一2、是有序对作为元素的一个无限集3、尽可能小12/16/2022

19DiscreteMath.,DeRenChenLetfandgbefunctionsfromTheorem1

Iff(x)=anxn+an-1xn-1+…+a1x1+a0whereai

R,i=0,1,…,nThenf(x)isO(xn)Theorem2

Iff1(x)isO(g1(x)),f2(x)isO(g2(x)),Then(f1+

f2)(x)isO(max(g1(x),g2(x)))12/16/2022

20DiscreteMath.,DeRenChenTheorem1Theorem212/11/2022Corollary1

Iff1(x)isO(g(x)),f2(x)isO(g(x)),Then(f1+

f2)(x)isO(g(x))Theorem3

Iff1(x)isO(g1(x)),f2(x)isO(g2(x)),Then(f1f2)(x)isO(g1(x)g2(x))12/16/2022

21DiscreteMath.,DeRenChenCorollary1Theorem312/11/20常用的算法复杂性分类：O(1):constantcomplexityO(logn):logarithmiccomplexityO(n):linearcomplexityO(nlogn):nlogncomplexitylinearO(nb):polynomialcomplexitypolynomialO(bn):exponentialcomplexity(b>1)exponentialO(n!):factorialcomplexity12/16/2022

22DiscreteMath.,DeRenChen常用的算法复杂性分类：12/11/202222DiscreLetfandgbefunctionsfromthesetofRorItothesetofR.Callthatf(x)is(g(x))ifthereareconstantsCandksuchthat|f(x)|>=C|g(x)|Whereverx>k.Readas“f(x)isbig-omegaofg(x)”

12/16/2022

23DiscreteMath.,DeRenChenLetfandgbefunctionsfromLetfandgbefunctionsfromthesetofRorItothesetofR.Callthatf(x)is(g(x))

iff(x)isO(g(x))andf(x)is(g(x))Readas“f(x)isbig-thetaofg(x)”“f(x)isoforderg(x)”12/16/2022

24DiscreteMath.,DeRenChenLetfandgbefunctionsfrom数论（NumberTheory）1、算术基本定理2、同余关系3、密码学基础定义设m是一个正整数，对任意两个整数a、b，若a-b能被m整除，则称a与b是（模m）同余的，或（模m）合同的/congruentbymodulom，记为ab(modm)

在m确定的情况下，简记为ab。12/16/2022

25DiscreteMath.,DeRenChen数论（NumberTheory）1、算术基本定理定义1、整数的因子、公因子、GCD---EUCLID算法、GCD的线性组合2、质数、质因子、两两互质---整数分解3、同余关系、线性同余、中国同余定理4、费尔玛小定理、RSA算法12/16/2022

26DiscreteMath.,DeRenChen1、整数的因子、公因子、GCD12/11/202226D原理部分:数学推理(Reasoning)

3.1推理与证明方法3.2数学归纳方法3.3递推方法计数原理(Counting)关系(Relations)12/16/2022

27DiscreteMath.,DeRenChen原理部分:12/11/202227DiscreteMat蕴涵演算/logicalimplyingoperation对于任意的公式P和Q，如果P

→Q为T，则称P蕴涵Q，记为P

Q或P/Q蕴涵演算的推广表示：P1、P2、…、Pn

Q前提组/hypotheses结论/conclusion12/16/2022

28DiscreteMath.,DeRenChen蕴涵演算/logicalimplyingoperatioTable112/16/2022

29DiscreteMath.,DeRenChenTable112/11/202229Dis定理证明方法：1、直接证明/directproof:p→Q

2、间接证明/indirectproof:p→Q

¬Q→¬P3、空证明/vacuousproof:p→Q其中P为F4、平凡证明/trivialproof：p→Q其中Q为T12/16/2022

30DiscreteMath.,DeRenChen定理证明方法：12/11/202230DiscreteM定理证明方法：5、反证明/proofofcontradiction：P¬PS∧¬S6、分例证明/proofofcases：P1∨P2…

∨Pn→Q（P1→Q）

∧（P2→Q）…∧（Pn→Q）7、存在证明/existenceproof：

xP(x)constructive,nonconstructive8、归纳证明/inductionproof：

xP(x)

12/16/2022

31DiscreteMath.,DeRenChen定理证明方法：12/11/202231DiscreteM皮亚诺公理（1）0∈N；（2）对每一个n∈N，唯一定义了一个自然数n'，n'称为n的后邻；（3）不同的自然数，其后邻也不同；（4）没有一个自然数的后邻是0；（5）如果有一个子集MN满足：①

0∈M；②

n∈M时必n'∈M,则M=N自然数全体N通过皮亚诺公理的五条公理组成。这些公理缺一不可，其中性质（5）称为归纳公理，并指出了自然数是满足公理（1）~（4）的最小集合。

12/16/2022

32DiscreteMath.,DeRenChen皮亚诺公理（1）0∈N；12/11/202232Discr数学归纳法的一般公式表示：[P(k)∧m(m

k∧P(m)→P(m+1))]→nP(n)1、归纳基础：P(k)2、归纳步骤：m(m

k∧P(m)→P(m+1))第二数学归纳法：[P(n0)∧k(k>n0∧P(n0)∧P(n0+1)∧…∧P(k)→P(k+1))]→nP(n)1、归纳基础：P(n0)2、归纳步骤：k(k>n0∧P(n0)∧P(n0+1)∧…∧P(k)→P(k+1))Definition212/16/2022

33DiscreteMath.,DeRenChen数学归纳法的一般公式表示：Definition212/11有限数学归纳法：对于n0

nnk的P(n)有限数学归纳法的前推公式表示：[P(n0)∧n(n0

nnk-1

∧

P(n))→P(n+1))]→

n(n0

nnk→P(n))1、归纳基础：P(n0)2、归纳步骤：n(n0

nnk-1

∧

P(n))→P(n+1))]有限数学归纳法：对于n0

nnk的P(n)有限数学归纳法的后推公式表示：[P(nk)∧n(n0+1nnk∧

P(n))→P(n-1))]→

n(n0

nnk→P(n))1、归纳基础：P(nk)2、归纳步骤：n(n0+1nnk∧

P(n))→P(n-1))12/16/2022

34DiscreteMath.,DeRenChen有限数学归纳法：对于n0nnk的P(n)有定义1 如果一个对象部分地由自己所组成，或者按它自己定义，则称为是递归的（Recursion）。递归定义的函数f：f的定义域：非负整数集1、递归基础：f(0)2、递归步骤：f(n)=g(f(k)),k<n,n>=0菲波那契数/Fibonacci

F(0)=0，F(1)=1 F(n)=F(n–1)+F(n–2) n>112/16/2022

35DiscreteMath.,DeRenChen定义1 如果一个对象部分地由自己所组成，或者按它自己定义，则4、计数原理/Counting

4.1基本计数原理:加法原理和乘法原理TheBasicofCounting4.2包含与排斥原理:有限集的基的运算TheInclusion-ExclusionPrinciple4.3鸽洞原理:有限集的基的比较ThePigeonholePrinciple4.4排列与组合:排列、组合、二项式PermutationsandCombinations4.5排列与组合的生成：排列生成、组合生成GeneratingPermutationsandCombinations12/16/2022

36DiscreteMath.,DeRenChen4、计数原理/Counting12/11/202236Di求和规则/TheSumRuleIfafirsttaskcanbedoneinnwaysandasecondtaskinmways,andiftherethesetaskscannotbedoneatthesametime,thentherearen+mwaystobeeithertask.|A1

A2|=|A1|+|A2|其中A1

A2=

求和规则的推广|A1

A2…

An|=|A1|+|A2|+…+|An|其中Ai

Aj=

ij,i,j=1,2,…,n12/16/2022

37DiscreteMath.,DeRenChen求和规则/TheSumRule12/11/202237求积规则/TheProductRuleSupposethataprocedurecanbebrokendownintotwotasks.Iftherearenwaystodothefirsttaskandmwaystodothesecondtaskafterthefirsttaskhasbeendone,thentherearenmwaystodotheprocedure.|A1

A2|=|A1||A2|求积规则的推广|A1

A2

…

An|=|A1||A2|…|An|12/16/2022

38DiscreteMath.,DeRenChen求积规则/TheProductRule12/11/202TheoremofInclusion-Exclusion对任意有限集A1、A2，成立|A1

A2|=|A1|+|A2|-|A1

A2|推广：|A1

A2…

An|=12/16/2022

39DiscreteMath.,DeRenChenTheoremofInclusion-Exclusio

ThePigeonholePrincipleIfk+1ormoreobjectsareplacedintokboxes,thenthereisatleastoneboxcontainingtwoormoreoftheobjects.TheGeneralizedPigeonholePrincipleIfNobjectsareplacedintokboxes,thenthereisatleastoneboxcontainingatleastN/kobjects.12/16/2022

40DiscreteMath.,DeRenChenThePigeonholePrinciple12/4.4排列与组合/Permutations

andCombinations(1)排列：r-排列、全排列、r-可重排列、r-限重排列、r-循环排列(2)组合：r-组合、r-可重组合(3)二项式定理与二项式系数：4.5排列与组合的生成GeneratingPermutations

andCombinations12/16/2022

41DiscreteMath.,DeRenChen4.4排列与组合/Permutations12/11/2定义1：n个元素的集合A中任意选择r个（rn）进行排列称为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的一个全排列排列/Permutations12/16/2022

42DiscreteMath.,DeRenChen定义1：n个元素的集合A中任意选择r个（rn）进行排列排列的函数表示：|A|=n，B={1,2,…,r}，F:BA（1）F是一个单射A的一个r-排列（2）B到A的所有单射总数P(n,r)排列的球盒模型表示：|A|=nn个盒子B={1,2,…,r}r个不同的球F:BA且是单射每个盒子最多放一个球A的一个r-排列B到A的所有单射总数球放入盒子的放法总数P(n,r)排列/Permutations12/16/2022

43DiscreteMath.,DeRenChen排列的函数表示：排列/Permutations12/11/2定义2：n个元素的集合A中任意选择r个（rn）称为A的一个r-组合/r-Combination定理2：n个元素的集合A的r-组合数为n(n-1)(n-2)…(n-r+1)/r!记为C(n,r)组合的球盒模型表示：B={0，1}两个盒子An个不同的球F:BA且使得A中的r个元素的象为1指定一个盒子恰好放r个球A的一个r-组合满足条件的F总数=C(n,r)=满足条件的球的放法总数组合/Combinations12/16/2022

44DiscreteMath.,DeRenChen定义2：n个元素的集合A中任意选择r个（rn）称为A的定理6（BinomialTheorem/二项式定理）：对任意正整数n和变量x、y

（x+y）n=nj=0

C（n，j）xn-jyj二项式系数与二项式定理12/16/2022

45DiscreteMath.,DeRenChen定理6（BinomialTheorem/二项式定理）：二项定义3n个不同元素的集合A，每个元素可重复选取，则A中任意选择r个（rn）进行排列称为A的一个r-可重排列/r-Permutationwithrepetition。排列与组合的推广定理7n个不同元素的集合A，每个元素可重复选取，则A的r-可重排列总数为nr。12/16/2022

46DiscreteMath.,DeRenChen定义3n个不同元素的集合A，每个元素可重复选取，则定义6n个不同元素的集合A，每个元素可重复选取，则A中任意选择r个（rn）的方式称为A的一个r-可重组合/r-Combinationwithrepetition。排列与组合的推广定理10n个不同元素的集合A，每个元素可重复选取，则A的r-可重组合总数为C（n-1+r，r）12/16/2022

47DiscreteMath.,DeRenChen定义6n个不同元素的集合A，每个元素可重复选取，则Relations关系（1）二元关系的概念：集合、关系、函数多元关系（2）二元关系的表示:集合、图形、矩阵（3）二元关系的性质：分类（4）二元关系的运算：集合运算、函数运算、闭包运算12/16/2022

48DiscreteMath.,DeRenChenRelations关系（1）二元关系的概念：集合、关系、（5）等价关系的概念、等价关系与划分（6）半序关系与半序集、全序关系与全序集半序集中的极小/大元素、最小/大元素、上/下界、上/下确界良序关系与良序集、拓扑排序12/16/2022

49DiscreteMath.,DeRenChen（5）等价关系的概念、等价关系与划分12/11/202247、图/Graph7.1图的概念/IntroductionofGraph7.2图的术语/GraphTerminology7.3图的表示与同构/RepresentingGraphandGraphIsomorphism表示:集合、表、矩阵图的转换、图的包含、图的运算、图的同构7.4连通性/Connectivity12/16/2022

50DiscreteMath.,DeRenChen

一些特殊的简单无向图：（1）CompleteGraphs/完全图Kn（2）Cycles/环图Cn（3）Wheels/轮图Wn（4）n-Cubes/n-立方图Qn（5）BipartiteGraphs/二分图Kn,m12/16/2022

51DiscreteMath.,DeRenChen一些特殊的简单无向图：12/11/202251Discre一些特殊的其他图：（1）有向完全图（2）零图（3）平凡图（4）正则图：若图Ｇ＝（Ｖ，Ｅ）中每个顶点的次均为n，称此图Ｇ是n-正则的/n-regular。12/16/2022

52DiscreteMath.,DeRenChen一些特殊的其他图：12/11/202252Discrete7.5欧拉道路与哈密尔顿道路/EulerandHamiltonPaths7.6最短道路问题/ShortestPathProblem7.7平面图/PlanarGraphs

平面图的概念：无向、简单、有限、非交叉边/区域平面图的欧拉公式：必要条件平面图判定的库氏定理：关键点：极大非平面图7.8图的着色/GraphColoring12/16/2022

53DiscreteMath.,DeRenChen7.5欧拉道路与哈密尔顿道路/12/11/20225树/Trees8.1树的概念/IntroductionofTrees8.2树的应用/ApplicationsofTrees8.3树的遍历/TreeTraversal8.4树和分类/TreesandSorting8.5生成树和最小生成树/SpanningTreesandminimumSpanningTrees12/16/2022

54DiscreteMath.,DeRenChen12/11/202254DiscreteMath.,1、树的概念：无向/有向树的层、树中顶点的道路长度2、树的分类：M元树、正规M元树、完全M元树3、树的应用：前缀码、二元树的遍历问题4、生成树：存在的充分必要条件

最小生成树的求法Ｋｒｕｓｋａｌ算法12/16/2022

55DiscreteMath.,DeRenChen1、树的概念：无向/有向12/11/202255Discr

布尔代数的抽象定义：半序集（A，）格/Lattics:半序集（A，）对任意a,bA,a,b的上确界c和下确界d存在，记ab=c,ab=d有界格：格中存在最大元素1和最小元素0。有界格中元素的余元：aA，若存在bA使得ab=1,ab=0，称b是a的一个余元。12/16/2022

56DiscreteMath.,DeRenChen布尔代数的抽象定义：1有余格：有界格中每一个元素都存在余元。分配格：有界格中上确界和下确界运算满足分配律。定理：分配格中任意元素若有余元，则必唯一。布尔格：至少有两个元素的有余分配格。布尔代数：布尔格对应的代数系统（A，，，¯）12/16/2022

57DiscreteMath.,DeRenChen有余格：有界格中每一个元素都存在余元。12/11/20布尔表达式与布尔函数BooleanExpressionsandBooleanFunctionsB={0,1},xi:布尔变量,i=1,2,…,nF:BnB,布尔函数，n:布尔函数的维数布尔表达式的表示

布尔表达式的图示方法：卡诺图/KarnaughMaps布尔表达式的标准化描述表达、分类、判定、应用12/16/2022

58DiscreteMath.,DeRenChen布尔表达式与布尔函数12/11/202258Discret精品课件！12/16/202259DiscreteMath.,DeRenChen精品课件！12/11/202259DiscreteMath精品课件！12/16/202260DiscreteMath.,DeRenChen精品课件！12/11/202260DiscreteMathThat’sall!12/16/2022

61DiscreteMath.,DeRenChenThat’sall!12/11/202261Discr

DiscreteMath.离散数学研究离散对象及其相互间关系的一门数学学科。研究离散结构的数学分支。（辞海）离散数学的内容：基础——概念原理——方法应用——实践12/16/2022

62DiscreteMath.,DeRenChenDiscreteMath.12/11/20221Di基础部分:逻辑(Logic)集合(Sets)算法(Algorithms)数论(NumberTheory)原理部分:数学推理(Reasoning)计数原理(Counting)关系(Relations)应用部分:图(Graphs)树(Trees)代数系统：布尔代数(BooleanAlgebra)，群（Group）12/16/2022

63DiscreteMath.,DeRenChen基础部分:原理部分:应用部分:12/11/20222Dis逻辑（LOGIC）：命题逻辑PropositionLogic命题演算PropositionalEquivalences谓词和量词PredicatesandQuantifiers12/16/2022

64DiscreteMath.,DeRenChen逻辑（LOGIC）：12/11/20223Discrete

（1）命题的概念：定义、逻辑值、符号化表示（2）从简单命题到复合命题：

逻辑联接词：运算方法、运算优先级（3）从命题常量到命题变量，从复合命题到命题公式：命题公式的真值描述：真值表（4）命题公式的分类：

永真公式、永假公式、可满足公式

（5）命题公式的等价演算：基本等价定理；两种方法（6）命题公式的标准化描述：表达、判定、分类与应用（7）从命题到命题函数：N元谓词、个体、个体变量、个体域（8）从命题公式到谓词公式：存在量词、全称量词；变量的分类（9）谓词公式的演算：基本等价定理12/16/2022

65DiscreteMath.,DeRenChen12/11/20224DiscreteMathTable512/16/2022

66DiscreteMath.,DeRenChenTable512/11/20225DiscreteMaTable6p∨qTp∧qFp∨(p∧q)pAbsorptionLaws/吸收律p∧(p∨q)pp→qp∨qpq(p→q)∧(q→p)12/16/2022

67DiscreteMath.,DeRenChenTable6p∨qT12/11/2022判断命题公式逻辑等价的方法：1、真值表2、命题公式的演算

基本等值定理（基本等价定理）；公式的代入不变性；等值关系的传递性。12/16/2022

68DiscreteMath.,DeRenChen判断命题公式逻辑等价的方法：12/11/20227Disc命题公式逻辑等价关系的应用：1、判定是否逻辑等价；2、判断是否为永真公式或永假公式；3、命题公式的化简

12/16/2022

69DiscreteMath.,DeRenChen命题公式逻辑等价关系的应用：12/11/20228Disc定理2（基本量词等值定律）量词分配律Vx（A(x)∧B(x)）VxA(x)∧VxB(x)x(A(x)∨B(x)）

xA(x)∨xB(x)另两种情况的思考：V与∨，与∧量词否定律12/16/2022

70DiscreteMath.,DeRenChen定理2（基本量词等值定律）12/11/20229Dis量词扩张/收缩律Vx(P∨B(x))P∨VxB(x)Vx(P∧B(x))P∧VxB(x)x(P∨B(x))P∨xB(x)x(P∧B(x))P∧x

B(x)这里A、B是任意包括个体变量x的谓词公式，P是不包括个体变量x的任意谓词公式。12/16/2022

71DiscreteMath.,DeRenChen量词扩张/收缩律12/11/202210Discrete

集合集合的表示集合间的关系：相等、包含集合间的运算一些特殊的集合：空集、全集、幂集、X集集合的分类：集合的基函数的概念函数的分类函数的运算一些特殊的应用函数：语言12/16/2022

72DiscreteMath.,DeRenChen集合12/11/202211DiscreteMath.Table112/16/2022

73DiscreteMath.,DeRenChenTable112/11/202212DiscreteM命题演算的基本等值定理12/16/2022

74DiscreteMath.,DeRenChen命题演算的基本等值定理12/11/202213Discre证明两个集合相等的方法：1、定义方法：谓词公式2、相等定理：互相包含3、集合相等运算：基本相等定理4、Venn图（文氏图）：图解5、位运算12/16/2022

75DiscreteMath.,DeRenChen证明两个集合相等的方法：12/11/202214Discr一对一，单函数，单射映上的，满函数，满射一一对应，双射逆函数函数的复合运算，积运算12/16/2022

76DiscreteMath.,DeRenChen一对一，单函数，单射映上的，满函数，满射一一对应，双射逆函数几个常用的函数：Eigenfunctionfloorfunctionceilingfunction关于集合的进一步讨论（基于函数）：SequencesstringLanguageCountableofelementsinsets12/16/2022

77DiscreteMath.,DeRenChen几个常用的函数：关于集合的进一步讨论（基于函数）：12/11DEFINITION2.

算法（Algorithm）是通过一个有限的指令序列集合对特定问题进行求解的一种计算执行描述。Analgorithmisafinitesetofpreciseinstructionsforperformingacomputationorforsolvingaproblem.12/16/2022

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

79DiscreteMath.,DeRenChen一个算法通常应具有下列特征：12/11/202218DisLetfandgbefunctionsfromthesetofRorItothesetofR.Callthatf(x)isO(g(x))ifthereareconstantsCandksuchthat|f(x)|<=C|g(x)|Whereverx>k.Readas“f(x)isbig-ohofg(x)”O:Landausymbol关于C和k的说明：1、不唯一2、是有序对作为元素的一个无限集3、尽可能小12/16/2022

80DiscreteMath.,DeRenChenLetfandgbefunctionsfromTheorem1

Iff(x)=anxn+an-1xn-1+…+a1x1+a0whereai

R,i=0,1,…,nThenf(x)isO(xn)Theorem2

Iff1(x)isO(g1(x)),f2(x)isO(g2(x)),Then(f1+

f2)(x)isO(max(g1(x),g2(x)))12/16/2022

81DiscreteMath.,DeRenChenTheorem1Theorem212/11/2022Corollary1

Iff1(x)isO(g(x)),f2(x)isO(g(x)),Then(f1+

f2)(x)isO(g(x))Theorem3

Iff1(x)isO(g1(x)),f2(x)isO(g2(x)),Then(f1f2)(x)isO(g1(x)g2(x))12/16/2022

82DiscreteMath.,DeRenChenCorollary1Theorem312/11/20常用的算法复杂性分类：O(1):constantcomplexityO(logn):logarithmiccomplexityO(n):linearcomplexityO(nlogn):nlogncomplexitylinearO(nb):polynomialcomplexitypolynomialO(bn):exponentialcomplexity(b>1)exponentialO(n!):factorialcomplexity12/16/2022

83DiscreteMath.,DeRenChen常用的算法复杂性分类：12/11/202222DiscreLetfandgbefunctionsfromthesetofRorItothesetofR.Callthatf(x)is(g(x))ifthereareconstantsCandksuchthat|f(x)|>=C|g(x)|Whereverx>k.Readas“f(x)isbig-omegaofg(x)”

12/16/2022

84DiscreteMath.,DeRenChenLetfandgbefunctionsfromLetfandgbefunctionsfromthesetofRorItothesetofR.Callthatf(x)is(g(x))

iff(x)isO(g(x))andf(x)is(g(x))Readas“f(x)isbig-thetaofg(x)”“f(x)isoforderg(x)”12/16/2022

85DiscreteMath.,DeRenChenLetfandgbefunctionsfrom数论（NumberTheory）1、算术基本定理2、同余关系3、密码学基础定义设m是一个正整数，对任意两个整数a、b，若a-b能被m整除，则称a与b是（模m）同余的，或（模m）合同的/congruentbymodulom，记为ab(modm)

在m确定的情况下，简记为ab。12/16/2022

86DiscreteMath.,DeRenChen数论（NumberTheory）1、算术基本定理定义1、整数的因子、公因子、GCD---EUCLID算法、GCD的线性组合2、质数、质因子、两两互质---整数分解3、同余关系、线性同余、中国同余定理4、费尔玛小定理、RSA算法12/16/2022

87DiscreteMath.,DeRenChen1、整数的因子、公因子、GCD12/11/202226D原理部分:数学推理(Reasoning)

3.1推理与证明方法3.2数学归纳方法3.3递推方法计数原理(Counting)关系(Relations)12/16/2022

88DiscreteMath.,DeRenChen原理部分:12/11/202227DiscreteMat蕴涵演算/logicalimplyingoperation对于任意的公式P和Q，如果P

→Q为T，则称P蕴涵Q，记为P

Q或P/Q蕴涵演算的推广表示：P1、P2、…、Pn

Q前提组/hypotheses结论/conclusion12/16/2022

89DiscreteMath.,DeRenChen蕴涵演算/logicalimplyingoperatioTable112/16/2022

90DiscreteMath.,DeRenChenTable112/11/202229Dis定理证明方法：1、直接证明/directproof:p→Q

2、间接证明/indirectproof:p→Q

¬Q→¬P3、空证明/vacuousproof:p→Q其中P为F4、平凡证明/trivialproof：p→Q其中Q为T12/16/2022

91DiscreteMath.,DeRenChen定理证明方法：12/11/202230DiscreteM定理证明方法：5、反证明/proofofcontradiction：P¬PS∧¬S6、分例证明/proofofcases：P1∨P2…

∨Pn→Q（P1→Q）

∧（P2→Q）…∧（Pn→Q）7、存在证明/existenceproof：

xP(x)constructive,nonconstructive8、归纳证明/inductionproof：

xP(x)

12/16/2022

92DiscreteMath.,DeRenChen定理证明方法：12/11/202231DiscreteM皮亚诺公理（1）0∈N；（2）对每一个n∈N，唯一定义了一个自然数n'，n'称为n的后邻；（3）不同的自然数，其后邻也不同；（4）没有一个自然数的后邻是0；（5）如果有一个子集MN满足：①

0∈M；②

n∈M时必n'∈M,则M=N自然数全体N通过皮亚诺公理的五条公理组成。这些公理缺一不可，其中性质（5）称为归纳公理，并指出了自然数是满足公理（1）~（4）的最小集合。

12/16/2022

93DiscreteMath.,DeRenChen皮亚诺公理（1）0∈N；12/11/202232Discr数学归纳法的一般公式表示：[P(k)∧m(m

k∧P(m)→P(m+1))]→nP(n)1、归纳基础：P(k)2、归纳步骤：m(m

k∧P(m)→P(m+1))第二数学归纳法：[P(n0)∧k(k>n0∧P(n0)∧P(n0+1)∧…∧P(k)→P(k+1))]→nP(n)1、归纳基础：P(n0)2、归纳步骤：k(k>n0∧P(n0)∧P(n0+1)∧…∧P(k)→P(k+1))Definition212/16/2022

94DiscreteMath.,DeRenChen数学归纳法的一般公式表示：Definition212/11有限数学归纳法：对于n0

nnk的P(n)有限数学归纳法的前推公式表示：[P(n0)∧n(n0

nnk-1

∧

P(n))→P(n+1))]→

n(n0

nnk→P(n))1、归纳基础：P(n0)2、归纳步骤：n(n0

nnk-1

∧

P(n))→P(n+1))]有限数学归纳法：对于n0

nnk的P(n)有限数学归纳法的后推公式表示：[P(nk)∧n(n0+1nnk∧

P(n))→P(n-1))]→

n(n0

nnk→P(n))1、归纳基础：P(nk)2、归纳步骤：n(n0+1nnk∧

P(n))→P(n-1))12/16/2022

95DiscreteMath.,DeRenChen有限数学归纳法：对于n0nnk的P(n)有定义1 如果一个对象部分地由自己所组成，或者按它自己定义，则称为是递归的（Recursion）。递归定义的函数f：f的定义域：非负整数集1、递归基础：f(0)2、递归步骤：f(n)=g(f(k)),k<n,n>=0菲波那契数/Fibonacci

F(0)=0，F(1)=1 F(n)=F(n–1)+F(n–2) n>112/16/2022

96DiscreteMath.,DeRenChen定义1 如果一个对象部分地由自己所组成，或者按它自己定义，则4、计数原理/Counting

4.1基本计数原理:加法原理和乘法原理TheBasicofCounting4.2包含与排斥原理:有限集的基的运算TheInclusion-ExclusionPrinciple4.3鸽洞原理:有限集的基的比较ThePigeonholePrinciple4.4排列与组合:排列、组合、二项式PermutationsandCombinations4.5排列与组合的生成：排列生成、组合生成GeneratingPermutationsandCombinations12/16/2022

97DiscreteMath.,DeRenChen4、计数原理/Counting12/11/202236Di求和规则/TheSumRuleIfafirsttaskcanbedoneinnwaysandasecondtaskinmways,andiftherethesetaskscannotbedoneatthesametime,thentherearen+mwaystobeeithertask.|A1

A2|=|A1|+|A2|其中A1

A2=

求和规则的推广|A1

A2…

An|=|A1|+|A2|+…+|An|其中Ai

Aj=

ij,i,j=1,2,…,n12/16/2022

98DiscreteMath.,DeRenChen求和规则/TheSumRule12/11/202237求积规则/TheProductRuleSupposethataprocedurecanbebrokendownintotwotasks.Iftherearenwaystodothefirsttaskandmwaystodothesecondtaskafterthefirsttaskhasbeendone,thentherearenmwaystodotheprocedure.|A1

A2|=|A1||A2|求积规则的推广|A1

A2

…

An|=|A1||A2|…|An|12/16/2022

99DiscreteMath.,DeRenChen求积规则/TheProductRule12/11/202TheoremofInclusion-Exclusion对任意有限集A1、A2，成立|A1

A2|=|A1|+|A2|-|A1

A2|推广：|A1

A2…

An|=12/16/2022

100DiscreteMath.,DeRenChenTheoremofInclusion-Exclusio

ThePigeonholePrincipleIfk+1ormoreobjectsareplacedintokboxes,thenthereisatleastoneboxcontainingtwoormoreoftheobjects.TheGeneralizedPigeonholePrincipleIfNobjectsareplacedintokboxes,thenthereisatleastoneboxcontainingatleastN/kobjects.12/16/2022

101DiscreteMath.,DeRenChenThePigeonholePrinciple12/4.4排列与组合/Permutations

andCombinations(1)排列：r-排列、全排列、r-可重排列、r-限重排列、r-循环排列(2)组合：r-组合、r-可重组合(3)二项式定理与二项式系数：4.5排列与组合的生成GeneratingPermutations

andCombinations12/16/2022

102DiscreteMath.,DeRenChen4.4排列与组合/Permutations12/11/2定义1：n个元素的集合A中任意选择r个（rn）进行排列称为A的一个r-排列/r-Permutation定理1：n个元素的集合A的r-排列数为n