再談離散數(shù)學(xué)課件

DiscreteMath.離散數(shù)學(xué)研究離散對象及其相互間關(guān)系的一門數(shù)學(xué)學(xué)科。研究離散結(jié)構(gòu)的數(shù)學(xué)分支。（辭海）離散數(shù)學(xué)的內(nèi)容：基礎(chǔ)——概念原理——方法應(yīng)用——實踐12/16/2022

1DiscreteMath.,DeRenChenDiscreteMath.12/11/20221Di基礎(chǔ)部分:邏輯(Logic)集合(Sets)算法(Algorithms)數(shù)論(NumberTheory)原理部分:數(shù)學(xué)推理(Reasoning)計數(shù)原理(Counting)關(guān)系(Relations)應(yīng)用部分:圖(Graphs)樹(Trees)代數(shù)系統(tǒng)：布爾代數(shù)(BooleanAlgebra)，群（Group）12/16/2022

2DiscreteMath.,DeRenChen基礎(chǔ)部分:原理部分:應(yīng)用部分:12/11/20222Dis邏輯（LOGIC）：命題邏輯PropositionLogic命題演算PropositionalEquivalences謂詞和量詞PredicatesandQuantifiers12/16/2022

3DiscreteMath.,DeRenChen邏輯（LOGIC）：12/11/20223Discrete

（1）命題的概念：定義、邏輯值、符號化表示（2）從簡單命題到復(fù)合命題：

邏輯聯(lián)接詞：運算方法、運算優(yōu)先級（3）從命題常量到命題變量，從復(fù)合命題到命題公式：命題公式的真值描述：真值表（4）命題公式的分類：

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

（5）命題公式的等價演算：基本等價定理；兩種方法（6）命題公式的標(biāo)準(zhǔn)化描述：表達(dá)、判定、分類與應(yīng)用（7）從命題到命題函數(shù)：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、命題公式的演算

基本等值定理（基本等價定理）；公式的代入不變性；等值關(guān)系的傳遞性。12/16/2022

7DiscreteMath.,DeRenChen判斷命題公式邏輯等價的方法：12/11/20227Disc命題公式邏輯等價關(guān)系的應(yīng)用：1、判定是否邏輯等價；2、判斷是否為永真公式或永假公式；3、命題公式的化簡

12/16/2022

8DiscreteMath.,DeRenChen命題公式邏輯等價關(guān)系的應(yīng)用：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量詞擴(kuò)張/收縮律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量詞擴(kuò)張/收縮律12/11/202210Discrete

集合集合的表示集合間的關(guān)系：相等、包含集合間的運算一些特殊的集合：空集、全集、冪集、X集集合的分類：集合的基函數(shù)的概念函數(shù)的分類函數(shù)的運算一些特殊的應(yīng)用函數(shù)：語言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一對一，單函數(shù)，單射映上的，滿函數(shù)，滿射一一對應(yīng)，雙射逆函數(shù)函數(shù)的復(fù)合運算，積運算12/16/2022

15DiscreteMath.,DeRenChen一對一，單函數(shù)，單射映上的，滿函數(shù)，滿射一一對應(yīng)，雙射逆函數(shù)幾個常用的函數(shù)：Eigenfunctionfloorfunctionceilingfunction關(guān)于集合的進(jìn)一步討論（基于函數(shù)）：SequencesstringLanguageCountableofelementsinsets12/16/2022

16DiscreteMath.,DeRenChen幾個常用的函數(shù)：關(guān)于集合的進(jìn)一步討論（基于函數(shù)）：12/11DEFINITION2.

算法（Algorithm）是通過一個有限的指令序列集合對特定問題進(jìn)行求解的一種計算執(zhí)行描述。Analgorithmisafinitesetofpreciseinstructionsforperformingacomputationorforsolvingaproblem.12/16/2022

17DiscreteMath.,DeRenChenDEFINITION2.算法（Alg一個算法通常應(yīng)具有下列特征：（1）輸入：一個算法具有零個或多個取自指定集合的輸入值；（2）輸出：對算法的每一次輸入，算法具有一個或多個與輸入值接聯(lián)系的輸出值；（3）確定性：算法的每一個指令步驟都是明確的；（4）有限性：對算法的每一次輸入，算法都必須在有限步驟（即有限時間）內(nèi)結(jié)束；（5）正確性：對每一次輸入，算法應(yīng)產(chǎn)生出正確的輸出值；（6）通用性：算法的執(zhí)行過程可應(yīng)用于所有同類求解問題，而不是僅適用于特殊的輸入。12/16/2022

18DiscreteMath.,DeRenChen一個算法通常應(yīng)具有下列特征：12/11/202218DisLetfandgbefunctionsfromthesetofRorItothesetofR.Callthatf(x)isO(g(x))ifthereareconstantsCandksuchthat|f(x)|<=C|g(x)|Whereverx>k.Readas“f(x)isbig-ohofg(x)”O(jiān):Landausymbol關(guān)于C和k的說明：1、不唯一2、是有序?qū)ψ鳛樵氐囊粋€無限集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常用的算法復(fù)雜性分類：O(1):constantcomplexityO(logn):logarithmiccomplexityO(n):linearcomplexityO(nlogn):nlogncomplexitylinearO(nb):polynomialcomplexitypolynomialO(bn):exponentialcomplexity(b>1)exponentialO(n!):factorialcomplexity12/16/2022

22DiscreteMath.,DeRenChen常用的算法復(fù)雜性分類：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數(shù)論（NumberTheory）1、算術(shù)基本定理2、同余關(guān)系3、密碼學(xué)基礎(chǔ)定義設(shè)m是一個正整數(shù)，對任意兩個整數(shù)a、b，若a-b能被m整除，則稱a與b是（模m）同余的，或（模m）合同的/congruentbymodulom，記為ab(modm)

在m確定的情況下，簡記為ab。12/16/2022

25DiscreteMath.,DeRenChen數(shù)論（NumberTheory）1、算術(shù)基本定理定義1、整數(shù)的因子、公因子、GCD---EUCLID算法、GCD的線性組合2、質(zhì)數(shù)、質(zhì)因子、兩兩互質(zhì)---整數(shù)分解3、同余關(guān)系、線性同余、中國同余定理4、費爾瑪小定理、RSA算法12/16/2022

26DiscreteMath.,DeRenChen1、整數(shù)的因子、公因子、GCD12/11/202226D原理部分:數(shù)學(xué)推理(Reasoning)

3.1推理與證明方法3.2數(shù)學(xué)歸納方法3.3遞推方法計數(shù)原理(Counting)關(guān)系(Relations)12/16/2022

27DiscreteMath.,DeRenChen原理部分:12/11/202227DiscreteMat蘊(yùn)涵演算/logicalimplyingoperation對于任意的公式P和Q，如果P

→Q為T，則稱P蘊(yùn)涵Q，記為P

Q或P/Q蘊(yùn)涵演算的推廣表示：P1、P2、…、Pn

Q前提組/hypotheses結(jié)論/conclusion12/16/2022

28DiscreteMath.,DeRenChen蘊(yùn)涵演算/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，唯一定義了一個自然數(shù)n'，n'稱為n的后鄰；（3）不同的自然數(shù)，其后鄰也不同；（4）沒有一個自然數(shù)的后鄰是0；（5）如果有一個子集MN滿足：①

0∈M；②

n∈M時必n'∈M,則M=N自然數(shù)全體N通過皮亞諾公理的五條公理組成。這些公理缺一不可，其中性質(zhì)（5）稱為歸納公理，并指出了自然數(shù)是滿足公理（1）~（4）的最小集合。

12/16/2022

32DiscreteMath.,DeRenChen皮亞諾公理（1）0∈N；12/11/202232Discr數(shù)學(xué)歸納法的一般公式表示：[P(k)∧m(m

k∧P(m)→P(m+1))]→nP(n)1、歸納基礎(chǔ)：P(k)2、歸納步驟：m(m

k∧P(m)→P(m+1))第二數(shù)學(xué)歸納法：[P(n0)∧k(k>n0∧P(n0)∧P(n0+1)∧…∧P(k)→P(k+1))]→nP(n)1、歸納基礎(chǔ)：P(n0)2、歸納步驟：k(k>n0∧P(n0)∧P(n0+1)∧…∧P(k)→P(k+1))Definition212/16/2022

33DiscreteMath.,DeRenChen數(shù)學(xué)歸納法的一般公式表示：Definition212/11有限數(shù)學(xué)歸納法：對于n0

nnk的P(n)有限數(shù)學(xué)歸納法的前推公式表示：[P(n0)∧n(n0

nnk-1

∧

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

n(n0

nnk→P(n))1、歸納基礎(chǔ)：P(n0)2、歸納步驟：n(n0

nnk-1

∧

P(n))→P(n+1))]有限數(shù)學(xué)歸納法：對于n0

nnk的P(n)有限數(shù)學(xué)歸納法的后推公式表示：[P(nk)∧n(n0+1nnk∧

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

n(n0

nnk→P(n))1、歸納基礎(chǔ)：P(nk)2、歸納步驟：n(n0+1nnk∧

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

34DiscreteMath.,DeRenChen有限數(shù)學(xué)歸納法：對于n0nnk的P(n)有定義1 如果一個對象部分地由自己所組成，或者按它自己定義，則稱為是遞歸的（Recursion）。遞歸定義的函數(shù)f：f的定義域：非負(fù)整數(shù)集1、遞歸基礎(chǔ)：f(0)2、遞歸步驟：f(n)=g(f(k)),k<n,n>=0菲波那契數(shù)/Fibonacci

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

35DiscreteMath.,DeRenChen定義1 如果一個對象部分地由自己所組成，或者按它自己定義，則4、計數(shù)原理/Counting

4.1基本計數(shù)原理:加法原理和乘法原理TheBasicofCounting4.2包含與排斥原理:有限集的基的運算TheInclusion-ExclusionPrinciple4.3鴿洞原理:有限集的基的比較ThePigeonholePrinciple4.4排列與組合:排列、組合、二項式PermutationsandCombinations4.5排列與組合的生成：排列生成、組合生成GeneratingPermutationsandCombinations12/16/2022

36DiscreteMath.,DeRenChen4、計數(shù)原理/Counting12/11/202236Di求和規(guī)則/TheSumRuleIfafirsttaskcanbedoneinnwaysandasecondtaskinmways,andiftherethesetaskscannotbedoneatthesametime,thentherearen+mwaystobeeithertask.|A1

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

A2=

求和規(guī)則的推廣|A1

A2…

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

Aj=

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

37DiscreteMath.,DeRenChen求和規(guī)則/TheSumRule12/11/202237求積規(guī)則/TheProductRuleSupposethataprocedurecanbebrokendownintotwotasks.Iftherearenwaystodothefirsttaskandmwaystodothesecondtaskafterthefirsttaskhasbeendone,thentherearenmwaystodotheprocedure.|A1

A2|=|A1||A2|求積規(guī)則的推廣|A1

A2

…

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

38DiscreteMath.,DeRenChen求積規(guī)則/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-循環(huán)排列(2)組合：r-組合、r-可重組合(3)二項式定理與二項式系數(shù)：4.5排列與組合的生成GeneratingPermutations

andCombinations12/16/2022

41DiscreteMath.,DeRenChen4.4排列與組合/Permutations12/11/2定義1：n個元素的集合A中任意選擇r個（rn）進(jìn)行排列稱為A的一個r-排列/r-Permutation定理1：n個元素的集合A的r-排列數(shù)為n(n-1)(n-2)…(n-r+1)=P(n,r)特別地，當(dāng)r=n時，記P(n,r)=n!稱為A的一個全排列排列/Permutations12/16/2022

42DiscreteMath.,DeRenChen定義1：n個元素的集合A中任意選擇r個（rn）進(jìn)行排列排列的函數(shù)表示：|A|=n，B={1,2,…,r}，F(xiàn):BA（1）F是一個單射A的一個r-排列（2）B到A的所有單射總數(shù)P(n,r)排列的球盒模型表示：|A|=nn個盒子B={1,2,…,r}r個不同的球F:BA且是單射每個盒子最多放一個球A的一個r-排列B到A的所有單射總數(shù)球放入盒子的放法總數(shù)P(n,r)排列/Permutations12/16/2022

43DiscreteMath.,DeRenChen排列的函數(shù)表示：排列/Permutations12/11/2定義2：n個元素的集合A中任意選擇r個（rn）稱為A的一個r-組合/r-Combination定理2：n個元素的集合A的r-組合數(shù)為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總數(shù)=C(n,r)=滿足條件的球的放法總數(shù)組合/Combinations12/16/2022

44DiscreteMath.,DeRenChen定義2：n個元素的集合A中任意選擇r個（rn）稱為A的定理6（BinomialTheorem/二項式定理）：對任意正整數(shù)n和變量x、y

（x+y）n=nj=0

C（n，j）xn-jyj二項式系數(shù)與二項式定理12/16/2022

45DiscreteMath.,DeRenChen定理6（BinomialTheorem/二項式定理）：二項定義3n個不同元素的集合A，每個元素可重復(fù)選取，則A中任意選擇r個（rn）進(jìn)行排列稱為A的一個r-可重排列/r-Permutationwithrepetition。排列與組合的推廣定理7n個不同元素的集合A，每個元素可重復(fù)選取，則A的r-可重排列總數(shù)為nr。12/16/2022

46DiscreteMath.,DeRenChen定義3n個不同元素的集合A，每個元素可重復(fù)選取，則定義6n個不同元素的集合A，每個元素可重復(fù)選取，則A中任意選擇r個（rn）的方式稱為A的一個r-可重組合/r-Combinationwithrepetition。排列與組合的推廣定理10n個不同元素的集合A，每個元素可重復(fù)選取，則A的r-可重組合總數(shù)為C（n-1+r，r）12/16/2022

47DiscreteMath.,DeRenChen定義6n個不同元素的集合A，每個元素可重復(fù)選取，則Relations關(guān)系（1）二元關(guān)系的概念：集合、關(guān)系、函數(shù)多元關(guān)系（2）二元關(guān)系的表示:集合、圖形、矩陣（3）二元關(guān)系的性質(zhì)：分類（4）二元關(guān)系的運算：集合運算、函數(shù)運算、閉包運算12/16/2022

48DiscreteMath.,DeRenChenRelations關(guān)系（1）二元關(guān)系的概念：集合、關(guān)系、（5）等價關(guān)系的概念、等價關(guān)系與劃分（6）半序關(guān)系與半序集、全序關(guān)系與全序集半序集中的極小/大元素、最小/大元素、上/下界、上/下確界良序關(guān)系與良序集、拓?fù)渑判?2/16/2022

49DiscreteMath.,DeRenChen（5）等價關(guān)系的概念、等價關(guān)系與劃分12/11/202247、圖/Graph7.1圖的概念/IntroductionofGraph7.2圖的術(shù)語/GraphTerminology7.3圖的表示與同構(gòu)/RepresentingGraphandGraphIsomorphism表示:集合、表、矩陣圖的轉(zhuǎn)換、圖的包含、圖的運算、圖的同構(gòu)7.4連通性/Connectivity12/16/2022

50DiscreteMath.,DeRenChen

一些特殊的簡單無向圖：（1）CompleteGraphs/完全圖Kn（2）Cycles/環(huán)圖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

平面圖的概念：無向、簡單、有限、非交叉邊/區(qū)域平面圖的歐拉公式：必要條件平面圖判定的庫氏定理：關(guān)鍵點：極大非平面圖7.8圖的著色/GraphColoring12/16/2022

53DiscreteMath.,DeRenChen7.5歐拉道路與哈密爾頓道路/12/11/20225樹/Trees8.1樹的概念/IntroductionofTrees8.2樹的應(yīng)用/ApplicationsofTrees8.3樹的遍歷/TreeTraversal8.4樹和分類/TreesandSorting8.5生成樹和最小生成樹/SpanningTreesandminimumSpanningTrees12/16/2022

54DiscreteMath.,DeRenChen12/11/202254DiscreteMath.,1、樹的概念：無向/有向樹的層、樹中頂點的道路長度2、樹的分類：M元樹、正規(guī)M元樹、完全M元樹3、樹的應(yīng)用：前綴碼、二元樹的遍歷問題4、生成樹：存在的充分必要條件

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

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

布爾代數(shù)的抽象定義：半序集（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布爾代數(shù)的抽象定義：1有余格：有界格中每一個元素都存在余元。分配格：有界格中上確界和下確界運算滿足分配律。定理：分配格中任意元素若有余元，則必唯一。布爾格：至少有兩個元素的有余分配格。布爾代數(shù)：布爾格對應(yīng)的代數(shù)系統(tǒng)（A，，，ˉ）12/16/2022

57DiscreteMath.,DeRenChen有余格：有界格中每一個元素都存在余元。12/11/20布爾表達(dá)式與布爾函數(shù)BooleanExpressionsandBooleanFunctionsB={0,1},xi:布爾變量,i=1,2,…,nF:BnB,布爾函數(shù)，n:布爾函數(shù)的維數(shù)布爾表達(dá)式的表示

布爾表達(dá)式的圖示方法：卡諾圖/KarnaughMaps布爾表達(dá)式的標(biāo)準(zhǔn)化描述表達(dá)、分類、判定、應(yīng)用12/16/2022

58DiscreteMath.,DeRenChen布爾表達(dá)式與布爾函數(shù)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.離散數(shù)學(xué)研究離散對象及其相互間關(guān)系的一門數(shù)學(xué)學(xué)科。研究離散結(jié)構(gòu)的數(shù)學(xué)分支。（辭海）離散數(shù)學(xué)的內(nèi)容：基礎(chǔ)——概念原理——方法應(yīng)用——實踐12/16/2022

62DiscreteMath.,DeRenChenDiscreteMath.12/11/20221Di基礎(chǔ)部分:邏輯(Logic)集合(Sets)算法(Algorithms)數(shù)論(NumberTheory)原理部分:數(shù)學(xué)推理(Reasoning)計數(shù)原理(Counting)關(guān)系(Relations)應(yīng)用部分:圖(Graphs)樹(Trees)代數(shù)系統(tǒng)：布爾代數(shù)(BooleanAlgebra)，群（Group）12/16/2022

63DiscreteMath.,DeRenChen基礎(chǔ)部分:原理部分:應(yīng)用部分:12/11/20222Dis邏輯（LOGIC）：命題邏輯PropositionLogic命題演算PropositionalEquivalences謂詞和量詞PredicatesandQuantifiers12/16/2022

64DiscreteMath.,DeRenChen邏輯（LOGIC）：12/11/20223Discrete

（1）命題的概念：定義、邏輯值、符號化表示（2）從簡單命題到復(fù)合命題：

邏輯聯(lián)接詞：運算方法、運算優(yōu)先級（3）從命題常量到命題變量，從復(fù)合命題到命題公式：命題公式的真值描述：真值表（4）命題公式的分類：

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

（5）命題公式的等價演算：基本等價定理；兩種方法（6）命題公式的標(biāo)準(zhǔn)化描述：表達(dá)、判定、分類與應(yīng)用（7）從命題到命題函數(shù)：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、命題公式的演算

基本等值定理（基本等價定理）；公式的代入不變性；等值關(guān)系的傳遞性。12/16/2022

68DiscreteMath.,DeRenChen判斷命題公式邏輯等價的方法：12/11/20227Disc命題公式邏輯等價關(guān)系的應(yīng)用：1、判定是否邏輯等價；2、判斷是否為永真公式或永假公式；3、命題公式的化簡

12/16/2022

69DiscreteMath.,DeRenChen命題公式邏輯等價關(guān)系的應(yīng)用：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量詞擴(kuò)張/收縮律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量詞擴(kuò)張/收縮律12/11/202210Discrete

集合集合的表示集合間的關(guān)系：相等、包含集合間的運算一些特殊的集合：空集、全集、冪集、X集集合的分類：集合的基函數(shù)的概念函數(shù)的分類函數(shù)的運算一些特殊的應(yīng)用函數(shù)：語言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一對一，單函數(shù)，單射映上的，滿函數(shù)，滿射一一對應(yīng)，雙射逆函數(shù)函數(shù)的復(fù)合運算，積運算12/16/2022

76DiscreteMath.,DeRenChen一對一，單函數(shù)，單射映上的，滿函數(shù)，滿射一一對應(yīng)，雙射逆函數(shù)幾個常用的函數(shù)：Eigenfunctionfloorfunctionceilingfunction關(guān)于集合的進(jìn)一步討論（基于函數(shù)）：SequencesstringLanguageCountableofelementsinsets12/16/2022

77DiscreteMath.,DeRenChen幾個常用的函數(shù)：關(guān)于集合的進(jìn)一步討論（基于函數(shù)）：12/11DEFINITION2.

算法（Algorithm）是通過一個有限的指令序列集合對特定問題進(jìn)行求解的一種計算執(zhí)行描述。Analgorithmisafinitesetofpreciseinstructionsforperformingacomputationorforsolvingaproblem.12/16/2022

78DiscreteMath.,DeRenChenDEFINITION2.算法（Alg一個算法通常應(yīng)具有下列特征：（1）輸入：一個算法具有零個或多個取自指定集合的輸入值；（2）輸出：對算法的每一次輸入，算法具有一個或多個與輸入值接聯(lián)系的輸出值；（3）確定性：算法的每一個指令步驟都是明確的；（4）有限性：對算法的每一次輸入，算法都必須在有限步驟（即有限時間）內(nèi)結(jié)束；（5）正確性：對每一次輸入，算法應(yīng)產(chǎn)生出正確的輸出值；（6）通用性：算法的執(zhí)行過程可應(yīng)用于所有同類求解問題，而不是僅適用于特殊的輸入。12/16/2022

79DiscreteMath.,DeRenChen一個算法通常應(yīng)具有下列特征：12/11/202218DisLetfandgbefunctionsfromthesetofRorItothesetofR.Callthatf(x)isO(g(x))ifthereareconstantsCandksuchthat|f(x)|<=C|g(x)|Whereverx>k.Readas“f(x)isbig-ohofg(x)”O(jiān):Landausymbol關(guān)于C和k的說明：1、不唯一2、是有序?qū)ψ鳛樵氐囊粋€無限集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常用的算法復(fù)雜性分類：O(1):constantcomplexityO(logn):logarithmiccomplexityO(n):linearcomplexityO(nlogn):nlogncomplexitylinearO(nb):polynomialcomplexitypolynomialO(bn):exponentialcomplexity(b>1)exponentialO(n!):factorialcomplexity12/16/2022

83DiscreteMath.,DeRenChen常用的算法復(fù)雜性分類：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數(shù)論（NumberTheory）1、算術(shù)基本定理2、同余關(guān)系3、密碼學(xué)基礎(chǔ)定義設(shè)m是一個正整數(shù)，對任意兩個整數(shù)a、b，若a-b能被m整除，則稱a與b是（模m）同余的，或（模m）合同的/congruentbymodulom，記為ab(modm)

在m確定的情況下，簡記為ab。12/16/2022

86DiscreteMath.,DeRenChen數(shù)論（NumberTheory）1、算術(shù)基本定理定義1、整數(shù)的因子、公因子、GCD---EUCLID算法、GCD的線性組合2、質(zhì)數(shù)、質(zhì)因子、兩兩互質(zhì)---整數(shù)分解3、同余關(guān)系、線性同余、中國同余定理4、費爾瑪小定理、RSA算法12/16/2022

87DiscreteMath.,DeRenChen1、整數(shù)的因子、公因子、GCD12/11/202226D原理部分:數(shù)學(xué)推理(Reasoning)

3.1推理與證明方法3.2數(shù)學(xué)歸納方法3.3遞推方法計數(shù)原理(Counting)關(guān)系(Relations)12/16/2022

88DiscreteMath.,DeRenChen原理部分:12/11/202227DiscreteMat蘊(yùn)涵演算/logicalimplyingoperation對于任意的公式P和Q，如果P

→Q為T，則稱P蘊(yùn)涵Q，記為P

Q或P/Q蘊(yùn)涵演算的推廣表示：P1、P2、…、Pn

Q前提組/hypotheses結(jié)論/conclusion12/16/2022

89DiscreteMath.,DeRenChen蘊(yùn)涵演算/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，唯一定義了一個自然數(shù)n'，n'稱為n的后鄰；（3）不同的自然數(shù)，其后鄰也不同；（4）沒有一個自然數(shù)的后鄰是0；（5）如果有一個子集MN滿足：①

0∈M；②

n∈M時必n'∈M,則M=N自然數(shù)全體N通過皮亞諾公理的五條公理組成。這些公理缺一不可，其中性質(zhì)（5）稱為歸納公理，并指出了自然數(shù)是滿足公理（1）~（4）的最小集合。

12/16/2022

93DiscreteMath.,DeRenChen皮亞諾公理（1）0∈N；12/11/202232Discr數(shù)學(xué)歸納法的一般公式表示：[P(k)∧m(m

k∧P(m)→P(m+1))]→nP(n)1、歸納基礎(chǔ)：P(k)2、歸納步驟：m(m

k∧P(m)→P(m+1))第二數(shù)學(xué)歸納法：[P(n0)∧k(k>n0∧P(n0)∧P(n0+1)∧…∧P(k)→P(k+1))]→nP(n)1、歸納基礎(chǔ)：P(n0)2、歸納步驟：k(k>n0∧P(n0)∧P(n0+1)∧…∧P(k)→P(k+1))Definition212/16/2022

94DiscreteMath.,DeRenChen數(shù)學(xué)歸納法的一般公式表示：Definition212/11有限數(shù)學(xué)歸納法：對于n0

nnk的P(n)有限數(shù)學(xué)歸納法的前推公式表示：[P(n0)∧n(n0

nnk-1

∧

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

n(n0

nnk→P(n))1、歸納基礎(chǔ)：P(n0)2、歸納步驟：n(n0

nnk-1

∧

P(n))→P(n+1))]有限數(shù)學(xué)歸納法：對于n0

nnk的P(n)有限數(shù)學(xué)歸納法的后推公式表示：[P(nk)∧n(n0+1nnk∧

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

n(n0

nnk→P(n))1、歸納基礎(chǔ)：P(nk)2、歸納步驟：n(n0+1nnk∧

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

95DiscreteMath.,DeRenChen有限數(shù)學(xué)歸納法：對于n0nnk的P(n)有定義1 如果一個對象部分地由自己所組成，或者按它自己定義，則稱為是遞歸的（Recursion）。遞歸定義的函數(shù)f：f的定義域：非負(fù)整數(shù)集1、遞歸基礎(chǔ)：f(0)2、遞歸步驟：f(n)=g(f(k)),k<n,n>=0菲波那契數(shù)/Fibonacci

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

96DiscreteMath.,DeRenChen定義1 如果一個對象部分地由自己所組成，或者按它自己定義，則4、計數(shù)原理/Counting

4.1基本計數(shù)原理:加法原理和乘法原理TheBasicofCounting4.2包含與排斥原理:有限集的基的運算TheInclusion-ExclusionPrinciple4.3鴿洞原理:有限集的基的比較ThePigeonholePrinciple4.4排列與組合:排列、組合、二項式PermutationsandCombinations4.5排列與組合的生成：排列生成、組合生成GeneratingPermutationsandCombinations12/16/2022

97DiscreteMath.,DeRenChen4、計數(shù)原理/Counting12/11/202236Di求和規(guī)則/TheSumRuleIfafirsttaskcanbedoneinnwaysandasecondtaskinmways,andiftherethesetaskscannotbedoneatthesametime,thentherearen+mwaystobeeithertask.|A1

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

A2=

求和規(guī)則的推廣|A1

A2…

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

Aj=

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

98DiscreteMath.,DeRenChen求和規(guī)則/TheSumRule12/11/202237求積規(guī)則/TheProductRuleSupposethataprocedurecanbebrokendownintotwotasks.Iftherearenwaystodothefirsttaskandmwaystodothesecondtaskafterthefirsttaskhasbeendone,thentherearenmwaystodotheprocedure.|A1

A2|=|A1||A2|求積規(guī)則的推廣|A1

A2

…

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

99DiscreteMath.,DeRenChen求積規(guī)則/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-循環(huán)排列(2)組合：r-組合、r-可重組合(3)二項式定理與二項式系數(shù)：4.5排列與組合的生成GeneratingPermutations

andCombinations12/16/2022

102DiscreteMath.,DeRenChen4.4排列與組合/Permutations12/11/2定義1：n個元素的集合A中任意選擇r個（rn）進(jìn)行排列稱為A的一個r-排列/r-Permutation定理1：n個元素的集合A的r-排列數(shù)為n