《数学分析1(1).ppt》由会员分享，可在线阅读，更多相关《数学分析1(1).ppt（84页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、R e v i e wR e v i e w DiscreteMath.离散数学离散数学研究离散对象及其相互间关系的一门数学学科。研究离散对象及其相互间关系的一门数学学科。研究离散结构的数学分支。（辞海）研究离散结构的数学分支。（辞海）离散数学的内容离散数学的内容：基础、原理、应用：基础、原理、应用1/5/2023 1Discrete Math.,DeRen ChenR e v i e wR e v i e w基础部分基础部分:逻辑逻辑(Logic)集合集合(Sets)算法算法(Algorithms)数论数论(NumberTheory)1/5/2023 2Discrete Math.,DeRe
2、n ChenR e v i e wR e v i e w原理部分原理部分:数学推理数学推理(Reasoning)计数原理计数原理(Counting)关系关系(Relations)1/5/2023 3Discrete Math.,DeRen ChenR e v i e wR e v i e w应用部分应用部分:图图(Graphs)树树(Trees)布尔代数布尔代数(BooleanAlgebra)1/5/2023 4Discrete Math.,DeRen ChenR e v i e wR e v i e w逻辑（逻辑（LOGIC）：1.命题逻辑命题逻辑PropositionLogic2.命题演算
3、命题演算PropositionalEquivalences3.谓词和量词谓词和量词PredicatesandQuantifiers1/5/2023 5Discrete Math.,DeRen ChenR e v i e wR e v i e w（1）命题的概念：）命题的概念：定义、逻辑值、定义、逻辑值、符号化表示符号化表示（2）从简单命题到复合命题：）从简单命题到复合命题：逻辑联接词：运算方法、运算优先级逻辑联接词：运算方法、运算优先级（3）从命题常量到命题变量，）从命题常量到命题变量，从复合命题到命题公式：从复合命题到命题公式：命题公式的真值描述：命题公式的真值描述：真值表真值表（4）命题公
4、式的分类：）命题公式的分类：永真公式、永假公式、可满足公式永真公式、永假公式、可满足公式、一般公式、一般公式（5）命题公式的判定、分类与标准化描述）命题公式的判定、分类与标准化描述（6）从命题到命题函数：）从命题到命题函数：N元谓词、个体、个体变量、个体域元谓词、个体、个体变量、个体域（7）从命题公式到谓词公式：）从命题公式到谓词公式：存在量词、全称量词存在量词、全称量词1/5/2023 6Discrete Math.,DeRen ChenR e v i e wR e v i e w命题公式：命题公式：1、原子命题是命题公式；、原子命题是命题公式；2、设、设P是命题公式，则是命题公式，则P也是
5、命题公式；也是命题公式；3、设、设P、Q是命题公式，则（是命题公式，则（PQ）、（）、（PQ）、）、（PQ）、（）、（PQ）也是命题公式；也是命题公式；4、有限次地使用、有限次地使用1、2、3所得到的也是命题公式。所得到的也是命题公式。PropositionFormulas,Well-FormedFormulas(wff)1/5/2023 7Discrete Math.,DeRen ChenR e v i e wR e v i e w永真命题公式（永真命题公式（Tautology）公式中的命题变量无论怎样代入，公式对应的真值恒为公式中的命题变量无论怎样代入，公式对应的真值恒为T。永假命题公式（
6、永假命题公式（Contradiction)公式中的命题变量无论怎样代入，公式对应的真值恒为公式中的命题变量无论怎样代入，公式对应的真值恒为F。可满足命题公式（可满足命题公式（Satisfaction）公式中的命题变量无论怎样代入，公式对应的真值总有一公式中的命题变量无论怎样代入，公式对应的真值总有一种情况为种情况为T。一般命题公式（一般命题公式（Contingency）既不是永真公式也不是永假公式。既不是永真公式也不是永假公式。1/5/2023 8Discrete Math.,DeRen ChenR e v i e wR e v i e wTable 5Table 51/5/2023 9Dis
7、crete Math.,DeRen ChenR e v i e wR e v i e wTable 6Table 6p q Tp q Fp (p q)p Absorption Laws/吸收律p (p q)pp q p qp q (p q)(q p)1/5/2023 10Discrete Math.,DeRen ChenR e v i e wR e v i e w判断命题公式逻辑等价的方法：判断命题公式逻辑等价的方法：1、真值表、真值表2、命题公式的演算、命题公式的演算基本等值定理；基本等值定理；公式的代入不变性；公式的代入不变性；等值关系的传递性。等值关系的传递性。1/5/2023 11Di
8、screte Math.,DeRen ChenR e v i e wR e v i e w命题公式逻辑等价关系的应用：命题公式逻辑等价关系的应用：1、判定是否逻辑等价；、判定是否逻辑等价；2、判断是否为永真公式或永假公式；、判断是否为永真公式或永假公式；3、命题公式的化简、命题公式的化简命题公式的标准化描述：命题公式的标准化描述：表达、分类、判定、应用表达、分类、判定、应用1/5/2023 12Discrete Math.,DeRen ChenR e v i e wR e v i e w文字（文字（literal）/符号（符号（symbol）：）：原子命题或其否定原子命题或其否定小项（小项（s
9、mallitem）/合取式（合取式（conjunctiveform）:若干个文字的合取。若干个文字的合取。大项（大项（largeitem）/析取式（析取式（disjunctiveform）:若干个文字的析取。若干个文字的析取。1/5/2023 13Discrete Math.,DeRen ChenR e v i e wR e v i e w合取范式（合取范式（conjunctivenormalform):若干个大项的合取。若干个大项的合取。析取范式（析取范式（disjunctivenormalform):若干个小项的析取。若干个小项的析取。标准句标准句(standardsentence)：合取
10、范式或析取范式合取范式或析取范式子句（子句（clause）:合取范式中的大项或合取范式中的大项或析取范式中的小项。析取范式中的小项。1/5/2023 14Discrete Math.,DeRen ChenR e v i e wR e v i e w令令A（a1、a2、an）包含有包含有n个变量的公式，个变量的公式，极小项极小项(extremal):小项中恰包含小项中恰包含n个变量或其否定。个变量或其否定。极大项极大项(extremal):大项中恰包含大项中恰包含n个变量或其否定。个变量或其否定。主合取范式（主合取范式（Uniqueconjunctivenormalform):若干个极大项的合取
11、。若干个极大项的合取。主析取范式（主析取范式（Uniquedisjunctivenormalform):若干个极小项的析取。若干个极小项的析取。1/5/2023 15Discrete Math.,DeRen ChenR e v i e wR e v i e w定理：令定理：令A（a1、a2、an）包含有包含有n个变量的公式，个变量的公式，则有：则有：1、如果、如果A存在与之等价的主析取范式，则必唯一；存在与之等价的主析取范式，则必唯一；2、如果、如果A存在与之等价的主合取范式，则必唯一；存在与之等价的主合取范式，则必唯一；3、A是永真公式当且仅当与是永真公式当且仅当与A等价的主析取范式恰有等价
12、的主析取范式恰有2n个个极小项或没有主合取范式；极小项或没有主合取范式；4、A是永假公式当且仅当与是永假公式当且仅当与A等价的主合取范式恰有等价的主合取范式恰有2n个个极大项或没有主析取范式；极大项或没有主析取范式；5、两个命题公式等价当且仅当它们有相同的主合取范式或、两个命题公式等价当且仅当它们有相同的主合取范式或相同的主析取范式。相同的主析取范式。1/5/2023 16Discrete Math.,DeRen ChenR e v i e wR e v i e w定义定义 一个谓词一个谓词P连同相关的连同相关的n（n0）个个体变量组成的表个个体变量组成的表达式称为达式称为n元谓词元谓词（n-
13、predicate），），记记P（x1,x2,xn），），其中其中n是该表达式中不同个体变量的数目。是该表达式中不同个体变量的数目。n元谓词也称元谓词也称简单简单命题函数命题函数，将简单命题函数视为命题，按，将简单命题函数视为命题，按1.1.1节定义节定义10得到得到的递归定义的表达式称为的递归定义的表达式称为复合命题函数复合命题函数。简单命题函数和复。简单命题函数和复合命题函数，统称为合命题函数，统称为命题函数命题函数（proposition function）。）。DEFINITION.DEFINITION.1/5/2023 17Discrete Math.,DeRen ChenR e v
14、 i e wR e v i e w为为了了进进一一步步讨讨论论命命题题函函数数P(x)的的真真值值情情况况，首首先先需需要要指指定定个个体体变变量量x可可选选择择的的范范围围，即即个个体体域域（universe of discourse,or domain）。每每一一个个个个体体变变量量x都都有有自自己己的的个个体体域域。如如果果没没有有特特别别指指定定的的个个体体域域，则则缺缺省省为为一一个个全全个个体体域域（total universe of discourse）即任意个体均可以作为常量对即任意个体均可以作为常量对x代入。代入。1/5/2023 18Discrete Math.,DeRen
15、 ChenR e v i e wR e v i e w定定义义2命命题题函函数数P(x)的的全全称称量量化化（universalquanification）是是一一个个按按如如下下规规则则确确定定真真值值的的命命题题：如如果果对对每每一一个个个个体体a代代入入得得到到的的P(a)均均为为T。则则该该命命题题为为T。记记为为VxP(x)。这这里里V是是全全称称量量词词（universalquantifier），表表示示为为“对对任任意意的的”、“所所有有的的”、“对每一个对每一个”等等。等等。DEFINITION 2.DEFINITION 2.1/5/2023 19Discrete Math.,
16、DeRen ChenR e v i e wR e v i e w定定 义义 3 命命 题题 函函 数数 P(x)的的 存存 在在 量量 化化（existential quantification）是是一一个个按按如如下下规规则则确确定定真真值值的的命命题题：如如果果个个体体域域中中存存在在一一个个个个体体a代代入入后后得得到到P(a)为为T，则则该该命命题题为为T，否否则则 为为 F。记记 或或 。这这 里里 称称 为为 存存 在在 量量 词词（existential quantification）。表表示示为为“有有一一个个”、“某某些些”、“某某个个”等等。等等。DEFINITION 3.
17、DEFINITION 3.1/5/2023 20Discrete Math.,DeRen ChenR e v i e wR e v i e w定义定义4 谓词公式定义为谓词公式定义为（1）n元谓词是一个谓词公式；元谓词是一个谓词公式；（2）若）若A是谓词公式，则（是谓词公式，则（A）也是谓词公式；也是谓词公式；（3）若若A，B是是谓谓词词公公式式，则则（AB）、（AB）、（AB）、（AB）也是谓词公式；也是谓词公式；（4）若）若A是谓词公式且含有未被量化的个体变量是谓词公式且含有未被量化的个体变量x，则则VxA(x)，XA(x)也是谓词公式。也是谓词公式。（5）有限次地使用（）有限次地使用（1
18、）（4）所得到的也是谓词公式。）所得到的也是谓词公式。DEFINITION 4.DEFINITION 4.1/5/2023 21Discrete Math.,DeRen ChenR e v i e wR e v i e w定理定理2 （基本量词等值定律）（基本量词等值定律）E14：量词分配律量词分配律Vx（A(x)B(x)）VxA(x)VxB(x)x(A(x)B(x)）xA(x)xB(x)另两种情况的思考：另两种情况的思考：V与与，与与1/5/2023 22Discrete Math.,DeRen ChenR e v i e wR e v i e wE15：量词扩张量词扩张/收缩律收缩律Vx(
19、PB(x)PVxB(x)Vx(PB(x)PVxB(x)x(PB(x)P xB(x)x(PB(x)P xB(x)这这里里A、B是是任任意意包包括括个个体体变变量量x的的谓谓词词公公式式，P是是不不包包括括个个体变量体变量x的任意谓词公式。的任意谓词公式。1/5/2023 23Discrete Math.,DeRen ChenR e v i e wR e v i e w1.2集合（集合（Sets）1.2.1集合的概念集合的概念ConceptsofSets1.2.2集合的运算集合的运算OperatingofSets1.2.3函数函数Functions1.2.4语言语言Language1/5/2023
20、 24Discrete Math.,DeRen ChenR e v i e wR e v i e wTheobjectsinasetarealsocalledtheelements,ormembers,oftheset.Asetissaidtocontainitselements.A=a,b,c,n枚举法枚举法A=x|x P(x)谓词公式法谓词公式法NullSet:Therearenoanythingintheset.=x|x P(x)(x P(x)1/5/2023 25Discrete Math.,DeRen ChenR e v i e wR e v i e wDEFINTION 2.DEF
21、INTION 2.Twosetsareequalifandonlyiftheyhavethesameelements.PresentedasA=BotherwiseA BA=B x(x A x B)ThesetAissaidtobeasubsetofBifandonlyifeveryelementofAisalsoanelementofB.WeusethenotationA BtoindicatethatAisasubsetofthesetB.ThesetAissaidtobeapropersubsetofBifA Bandthereisa Banda A1/5/2023 26Discrete
22、 Math.,DeRen ChenR e v i e wR e v i e w定理定理1：A=B当且仅当当且仅当A B B A定理定理2：对任意的集合：对任意的集合A，A A定理定理3：对任意的集合对任意的集合A、B、C，如果如果A B，B C，则则A C定理定理4：对任意的集合：对任意的集合A，A定理定理5：空集：空集是唯一的是唯一的1/5/2023 27Discrete Math.,DeRen ChenR e v i e wR e v i e wThesetUissaidtobeauniversalset:U=x|x P(x)V(x P(x)全集全集GivenasetS,thepowers
23、etofSisthesetofallsubsetsofthesetS.ThepowersetofSisdenotedbyP(S).1/5/2023 28Discrete Math.,DeRen ChenR e v i e wR e v i e wLetAandBbesets.TheCartesianproductofAandB,denotedbyAB,isthesetofallorderedpairs(a,b)whereaAandbB.Hence,AB=(a,b)aAbB.Theorderedn-tuple(a1,a2,an)istheorderedcollectionthathasa1asi
24、tsfirstelement,a2asitssecondelement,andanasitsnthelement.有序有序n元组元组或或n元元有序组有序组(a1,a2,an)1/5/2023 29Discrete Math.,DeRen ChenR e v i e wR e v i e wLetAandBbesets.TheunionofthesetsAandB,denotedbyAB,isthesetthatcontainsthoseelementsthatareeitherinAorinB,orinboth.集合的并集合的并LetAandBbesets.Theintersectionoft
25、hesetsAandB,denotedbyAB,isthesetcontainingthoseelementsinbothAandB.集合的交集合的交LetAandBbesets.ThedifferenceofAandB,denotedbyA B,isthesetcontainingthoseelementsthatareinAbutnotinB.ThedifferenceofAandBisalsocalledthecomplementofBwithrespecttoA.差集、补集、余集差集、补集、余集1/5/2023 30Discrete Math.,DeRen ChenR e v i e
26、wR e v i e wTable 1Table 11/5/2023 31Discrete Math.,DeRen ChenR e v i e wR e v i e w命题演算的基本等值定理命题演算的基本等值定理命题演算的基本等值定理命题演算的基本等值定理1/5/2023 32Discrete Math.,DeRen ChenR e v i e wR e v i e w证明两个集合相等的方法：证明两个集合相等的方法：1、定义方法：谓词公式、定义方法：谓词公式2、相等定理：互相包含、相等定理：互相包含3、集合相等运算：基本相等定理、集合相等运算：基本相等定理4、Venn图（文氏图）：图解图（文氏
27、图）：图解5、特征函数、特征函数1/5/2023 33Discrete Math.,DeRen ChenR e v i e wR e v i e wIffisafunctionfromAtoB,wesaythatAisthedomainoffandBisthecodomainoff.Iff(a)=b,wesaythatbistheimageofaandaisapre-imageofb.TherangeoffisthesetofallimagesofelementsofA.Also,iffisafunctionfromAtoB,wesaythatfmapsAtoB.A：定义域/domain of
28、 f a:b 的原象/pre-imageB：陪域/codomain of f b:a的象/imagef（A）：值域/range of f函数函数/映射映射/Functions/Mapping1/5/2023 34Discrete Math.,DeRen ChenR e v i e wR e v i e wAfunctionfissaidtobeone-to-one,orinjective,ifandonlyf(x)=f(y)impliesthatx=yforallxandyinthedomainoff.Afunctionissaidtobeaninjectionifitisone-to-one
29、.一对一，单函数，单射一对一，单函数，单射AfunctionffromAtoBiscalledonto,orsurjective,ifandonlyifforeveryelementbBthereisanelementaAwithf(a)=b.Afunctionfiscalledasurjectionifitisonto.映上的，满函数，满射映上的，满函数，满射Thefunctionfisaone-onecorrespondence,orabijection,ifitisbothone-to-oneandonto.一一对应，双射一一对应，双射1/5/2023 35Discrete Math.,
30、DeRen ChenR e v i e wR e v i e wDEFINITION 9.DEFINITION 9.Letfbeaone-to-onecorrespondenceffromthesetAtothesetB.TheinversefunctionoffisthefunctionthatassignstoanelementbbelongingtoBtheuniqueelementainAsuchthatf(a)=b.Theinversefunctionoffisdenotedbyf1.Hence,f1(b)=awhenf(a)=b.逆函数逆函数Letgbeafunctionfromt
31、hesetAtothesetBandletfbeafunctionfromthesetBtothesetC.Thecompositionofthefunctionsfandg,denotedbyfog,isdefinedby(fo g)(a)=f(g(a).函数的复合运算，积运算函数的复合运算，积运算1/5/2023 36Discrete Math.,DeRen ChenR e v i e wR e v i e w定理定理2设设f:AB,g:BC。（1）若若f,g都是满射，则都是满射，则gf也是满射；也是满射；（2）若）若f,g都是单射，则都是单射，则gf也是单射；也是单射；（3）若）若f,g
32、都是双射，则都是双射，则gf也是双射；也是双射；定理定理3 设设f:AB，g:BC，h:CD则积运算满足结合律，即则积运算满足结合律，即 h(gf)=(hg)f 1/5/2023 37Discrete Math.,DeRen ChenR e v i e wR e v i e w几个常用的函数：几个常用的函数：Eigenfunctionfloorfunctionceilingfunction关于集合的进一步讨论（基于函数）：关于集合的进一步讨论（基于函数）：SequencesstringLanguageCountableofelementsinsets1/5/2023 38Discrete Ma
33、th.,DeRen ChenR e v i e wR e v i e wSequences（序列、顺序）序列、顺序）:Asequenceisafunctionfromasubsetofthesetofintegers(0、1、2、or1、2、3、)toasetV.an denotetheimageoftheintegerncallan atermofthesequencea1，a2，a3，anString（串）串）a1a2 a3 an n=0thelengthofthestringn=0:emptystringv:symbollistset、alphabetset1/5/2023 39Disc
34、rete Math.,DeRen ChenR e v i e wR e v i e wClosureofV（V的闭包）的闭包）V*=a|a=a1a2 a3 an 是是V上的串且上的串且n=0PositiveClosureofV（V的的正闭包）正闭包）V+=a|a=a1a2 a3 an 是是V上的串且上的串且n0Language（语言）语言）L V*1/5/2023 40Discrete Math.,DeRen ChenR e v i e wR e v i e w 从集合的基（Cardinality)进行集合的分类 A是有限集：A的基为n（n=0)或 f:1,2,nA且f是一一对应 A是可数无限
35、集：f:NA且f是一一对应 A是可数集（countable)：A是有限集或A是可数无限集 A是不可数集(uncountable)：A不是可数集1/5/2023 41Discrete Math.,DeRen ChenR e v i e wR e v i e w基础部分二：基础部分二：1、算法、算法2、数论、数论1/5/2023 42Discrete Math.,DeRen ChenR e v i e wR e v i e wDEFINITION 2.DEFINITION 2.算法（算法（Algorithm）是通过一个有限的指是通过一个有限的指令序列集合对特定问题进行求解的一种计算执令序列集合对特
36、定问题进行求解的一种计算执行描述。行描述。Analgorithmisafinitesetofpreciseinstructionsforperformingacomputationorforsolvingaproblem.1/5/2023 43Discrete Math.,DeRen ChenR e v i e wR e v i e w一个算法通常应具有下列特征：一个算法通常应具有下列特征：（1）输输入入：一一个个算算法法具具有有零零个个或或多多个个取取自自指指定定集集合合的的输输入入值；值；（2）输输出出：对对算算法法的的每每一一次次输输入入，算算法法具具有有一一个个或或多多个个与与输入值接
37、联系的输出值；输入值接联系的输出值；（3）确定性：算法的每一个指令步骤都是明确的；）确定性：算法的每一个指令步骤都是明确的；（4）有有限限性性：对对算算法法的的每每一一次次输输入入，算算法法都都必必须须在在有有限限步步骤（即有限时间）内结束；骤（即有限时间）内结束；（5）正确性：对每一次输入，算法应产生出正确的输出值；）正确性：对每一次输入，算法应产生出正确的输出值；（6）通通用用性性：算算法法的的执执行行过过程程可可应应用用于于所所有有同同类类求求解解问问题题，而不是仅适用于特殊的输入。而不是仅适用于特殊的输入。1/5/2023 44Discrete Math.,DeRen ChenR e
38、v i e wR e v i e w算法的概念与程序十分相似，但实际上有很大不算法的概念与程序十分相似，但实际上有很大不同。程序并不都满足算法所要求的上述特征，例如有同。程序并不都满足算法所要求的上述特征，例如有限性特征。算法代表了对特定问题的求解，而程序则限性特征。算法代表了对特定问题的求解，而程序则是算法在计算机上的实现。因此算法也常常称为是一是算法在计算机上的实现。因此算法也常常称为是一个个能行过程能行过程。一个函数如果可以用一个算法来计算，。一个函数如果可以用一个算法来计算，那么我们称该函数是那么我们称该函数是能行可计算能行可计算的。的。算法的计算量问题算法的计算量问题1/5/2023
39、 45Discrete Math.,DeRen ChenR e v i e wR e v i e wLetfandgbefunctionsfromthesetofRorItothesetofR.Callthatf(x)isO(g(x)ifthereareconstantsCandksuchthat|f(x)|k.Readas“f(x)isbig-ohofg(x)”O:Landausymbol关于关于C和和k的说明：的说明：1、不唯一不唯一2、是有序对作为元素的一个无限集、是有序对作为元素的一个无限集3、尽可能小、尽可能小1/5/2023 46Discrete Math.,DeRen ChenR
40、 e v i e wR e v i e wTheorem1Iff(x)=anxn+an-1xn-1+a1x1+a0whereai R,i=0,1,nThenf(x)isO(xn)Theorem2Iff1(x)isO(g1(x),f2(x)isO(g2(x),Then(f1+f2)(x)isO(max(g1(x),g2(x)1/5/2023 47Discrete Math.,DeRen ChenR e v i e wR e v i e wCorollary1Iff1(x)isO(g(x),f2(x)isO(g(x),Then(f1+f2)(x)isO(g(x)Theorem3Iff1(x)isO
41、(g1(x),f2(x)isO(g2(x),Then(f1f2)(x)isO(g1(x)g2(x)1/5/2023 48Discrete Math.,DeRen ChenR e v i e wR e v i e w常用的算法复杂性分类：常用的算法复杂性分类：O(1):constantcomplexityO(logn):logarithmiccomplexityO(n):linearcomplexityO(nlogn):nlogncomplexitylinearO(nb):polynomialcomplexitypolynomialO(bn):exponentialcomplexity(b1)e
42、xponentialO(n!):factorialcomplexity1/5/2023 49Discrete Math.,DeRen ChenR e v i e wR e v i e w数论数论（NumberTheory）1、算术基本定理、算术基本定理2、同余关系、同余关系3、密码学基础、密码学基础定定义义设设m是是一一个个正正整整数数，对对任任意意两两个个整整数数a、b，若若a-b能能被被m整整除除，则则称称a与与b是是（模模m）同同余余的的，或或（模模m）合合同的同的/congruentbymodulom，记为记为a b(modm)在在m确定的情况下，简记为确定的情况下，简记为a b。1/
43、5/2023 50Discrete Math.,DeRen ChenR e v i e wR e v i e w1、整数的因子、公因子、整数的因子、公因子、GCD-EUCLID算法、算法、GCD的线性组合的线性组合2、质数、质因子、两两互质质数、质因子、两两互质-整数分解整数分解3、同余关系、线性同余、中国同余定理、同余关系、线性同余、中国同余定理4、费尔玛小定理、费尔玛小定理、RSA算法算法1/5/2023 51Discrete Math.,DeRen ChenR e v i e wR e v i e w原理部分原理部分:数学推理数学推理(Reasoning)3.1推理与证明方法推理与证明方
44、法3.2数学归纳方法数学归纳方法3.3递推方法递推方法计数原理计数原理(Counting)关系关系(Relations)1/5/2023 52Discrete Math.,DeRen ChenR e v i e wR e v i e w蕴涵演算蕴涵演算/logicalimplyingoperation对对于于任任意意的的公公式式P和和Q，如如果果PQ为为T，则则称称P蕴涵蕴涵Q，记为记为PQ或或P/Q蕴涵演算的推广表示：蕴涵演算的推广表示：P1、P2、PnQ前提组前提组/hypotheses结论结论/conclusion1/5/2023 53Discrete Math.,DeRen ChenR
45、 e v i e wR e v i e wTable 1 Table 1 RuleofInferenceNamePPQAddition/析取附加式析取附加式PQPSimplification/合取化简式合取化简式P、QPQConjunction/并发式并发式P、PQQModusponens/分离式分离式 Q、PQ PModustollens/拒取式拒取式 p、PQQDisjunctivesyllogism/析取三段式析取三段式PQ、QRPRHypotheticalsyllogism/假言假言三段式三段式1/5/2023 54Discrete Math.,DeRen ChenR e v i e
46、wR e v i e w定理证明方法：定理证明方法：1、直接证明、直接证明/directproof:pQ2、间接证明间接证明/indirectproof:pQ Q P3、空证明空证明/vacuousproof:pQ其中其中P为为F4、平凡证明平凡证明/trivialproof：pQ其中其中Q为为T1/5/2023 55Discrete Math.,DeRen ChenR e v i e wR e v i e w定理证明方法：定理证明方法：5、反证明反证明/proofofcontradiction：P PS S6、分例证明分例证明/proofofcases：P1P2PnQ（P1Q）（P2Q）（P
47、nQ）7、存在证明存在证明/existenceproof：xP(x)constructive,nonconstructive8、归纳证明归纳证明/inductionproof：xP(x)1/5/2023 56Discrete Math.,DeRen ChenR e v i e wR e v i e w皮亚诺公理皮亚诺公理皮亚诺公理皮亚诺公理（1）0N；（2）对对每每一一个个nN，唯唯一一定定义义了了一一个个自自然然数数n，n称称为为n的后邻；的后邻；（3）不同的自然数，其后邻也不同；）不同的自然数，其后邻也不同；（4）没有一个自然数的后邻是）没有一个自然数的后邻是0；（5）如果有一个子集）如果
48、有一个子集M N满足：满足：0M；nM时必时必nM,则则M=N自然数全体自然数全体N通过皮亚诺公理的五条公理组成。通过皮亚诺公理的五条公理组成。这些公理缺一不可，其中性质（这些公理缺一不可，其中性质（5）称为归纳公理，并指）称为归纳公理，并指出了自然数是满足公理（出了自然数是满足公理（1）（4）的最小集合。）的最小集合。1/5/2023 57Discrete Math.,DeRen ChenR e v i e wR e v i e w数学归纳法的一般公式表示：数学归纳法的一般公式表示：P(k)m(m kP(m)P(m+1)nP(n)1、归纳基础：归纳基础：P(k)2、归纳步骤：归纳步骤：m(m
49、 kP(m)P(m+1)第二数学归纳法：第二数学归纳法：P(n0)k(kn0P(n0)P(n0+1)P(k)P(k+1)nP(n)1、归纳基础：归纳基础：P(n0)2、归纳步骤：归纳步骤：k(kn0P(n0)P(n0+1)P(k)P(k+1)Definition 2Definition 21/5/2023 58Discrete Math.,DeRen ChenR e v i e wR e v i e w有限数学归纳法：对于有限数学归纳法：对于n0 n nk的的P(n)有限数学归纳法的前推公式表示：有限数学归纳法的前推公式表示：P(n0)n(n0 n nk-1P(n)P(n+1)n(n0 n n
50、kP(n)1、归纳基础：归纳基础：P(n0)2、归纳步骤：归纳步骤：n(n0 n nk-1P(n)P(n+1)有限数学归纳法：对于有限数学归纳法：对于n0 n nk的的P(n)有限数学归纳法的后推公式表示：有限数学归纳法的后推公式表示：P(nk)n(n0+1 n nkP(n)P(n-1)n(n0 n nkP(n)1、归纳基础：归纳基础：P(nk)2、归纳步骤：归纳步骤：n(n0+1 n nkP(n)P(n-1)1/5/2023 59Discrete Math.,DeRen ChenR e v i e wR e v i e w定义定义1如如果果一一个个对对象象部部分分地地由由自自己己所所组组成成