《离散数学复习》课件

离散数学复习欢迎参加离散数学复习课程！本课程将系统地梳理离散数学的核心概念与重要定理，帮助大家建立完整的知识体系离散数学是计算机科学的理论基础，掌握好这门课程对于后续的专业学习至关重要我们将从集合论、关系、函数、代数结构、逻辑、组合数学到图论等方面进行全面的复习与巩固课程将注重理论与实践的结合，配合典型例题分析，帮助大家提高解题能力，为考试做好充分准备建议大家跟随课程节奏，及时完成习题，遇到问题随时提出，共同进步离散数学基本概念离散与连续的区别研究内容实用价值离散数学研究离散量，即不连续的、可离散数学主要研究集合论、关系、函离散数学在计算机网络、数据库设计、分离的数学结构连续数学则研究连续数、图论、组合数学、数理逻辑、代数密码学、人工智能等领域有着广泛应变化的量结构等内容用离散结构的特点是元素之间存在间隔这些内容构成了计算机科学的理论基掌握离散数学知识有助于培养逻辑思维或跳跃，如整数集合、图形结构等础，对算法设计、人工智能、编程语言能力和抽象思维能力，提高解决复杂问等领域有着重要影响题的能力集合论基础集合的定义集合的表示方法集合是具有某种特定性质的事列举法，通A={a,b,c,d}物的总体，集合中的事物称为过列举集合中的所有元素来表该集合的元素集合用大写字示集合描述法B={x|x母表示，如、、等集合是偶数且，通过描述A B C x10}中的元素用小写字母表示，如元素的性质来表示集合文氏、、等图用图形直观地表示集合之a b c间的关系基本符号∈属于，∈表示是集合的元素⊆子集，⊆表示是a Aa A A B A B的子集⊂真子集，⊂表示是的真子集或的补A BA BAĀA集集合的基数，即元素个数|A|A集合的基本运算并运算A∪B={x|x∈A或x∈B}交运算A∩B={x|x∈A且x∈B}差运算A-B={x|x∈A且x∉B}补运算A={x|x∈U且x∉A}德摩根定律是集合论中的重要定律，它描述了集合的并、交与补运算之间的关系A∪B=A∩B，A∩B=A∪B这两个等式表明两个集合的并集的补集，等于这两个集合各自补集的交集；两个集合的交集的补集，等于这两个集合各自补集的并集这些基本运算在计算机科学中有着广泛应用，如在数据库查询、算法设计和逻辑推理等方面掌握这些运算及其性质，对于理解更复杂的离散数学概念具有重要意义集合运算性质运算律表达式类比交换律A∪B=B∪A,A∩B=B∩A加法、乘法结合律A∪B∪C=A∪B∪C,A∩B∩C=加法、乘法A∩B∩C分配律A∩B∪C=A∩B∪A∩C,A∪B∩乘法对加法、加法对乘法C=A∪B∩A∪C幂等律A∪A=A,A∩A=A无类比吸收律A∪A∩B=A,A∩A∪B=A无类比证明示例证明分配律A∩B∪C=A∩B∪A∩C证明对于任意x∈A∩B∪C，有x∈A且x∈B∪C，即x∈A且x∈B或x∈C按照逻辑等价，得到x∈A且x∈B或x∈A且x∈C，即x∈A∩B或x∈A∩C，所以x∈A∩B∪A∩C同理可证A∩B∪A∩C⊆A∩B∪C，故A∩B∪C=A∩B∪A∩C幂集与笛卡尔积幂集定义幂集性质笛卡尔积集合的幂集是由的所有子集组成的集对于任意集合，，有⊆当且仅集合与的笛卡尔积是所有有序对组A AA B1A BA Ba,b合，记作PA或2^A例如，若A={a,当PA⊆PB；2PA∩PB=PA∩成的集合，其中a∈A，b∈B，记作A×，则；∪⊆∪∈∈b}PA={∅,{a},{b},{a,b}}B3PA PBPA BB={a,b|a A,b B}若集合有个元素，则其幂集有幂集的应用广泛，特别是在计算机科学中若有个元素，有个元素，则有A nPA2^n A m B n A×B个元素这是因为对于中的每个元素，我的算法设计、组合优化和布尔代数等领个元素笛卡尔积在关系、函数、坐标Am·n们都有取或不取两种选择域系统等概念中有重要应用集合应用题型容斥原理集合等式证明计算多个集合并集元素个数的方法运用集合运算性质证明集合之间的关系子集问题文氏图应用关于集合包含关系的判断与证明通过文氏图解决集合元素计数问题典型例题在一个班级中，有名学生学习数学，名学生学习物理，名学生学习化学有名学生同时学习数学和物理，名学生同时学习数学和3530251510化学，名学生同时学习物理和化学有名学生同时学习这三门课程求班级中至少学习一门课程的学生总数128解析设学习数学、物理、化学的学生集合分别为M、P、C根据容斥原理，|M∪P∪C|=|M|+|P|+|C|-|M∩P|-|M∩C|-|P∩C|+|M∩P∩C|=因此，班级中至少学习一门课程的学生总数为人35+30+25-15-10-12+8=90-37+8=6161关系定义与性质二元关系的定义从集合A到集合B的二元关系R是笛卡尔积A×B的子集自反性对任意a∈A，都有a,a∈R对称性若a,b∈R，则b,a∈R传递性若a,b∈R且b,c∈R，则a,c∈R在集合A上的二元关系是A×A的子集，也称为A上的关系关系可以通过不同方式表示关系集合、有向图、矩阵等反自反性指对任意a∈A，都有a,a∉R反对称性指若a,b∈R且b,a∈R，则a=b关系的性质组合产生不同类型的关系，如等价关系（自反、对称、传递）、偏序关系（自反、反对称、传递）等理解这些性质对于分析复杂系统中元素间的关系具有重要意义，广泛应用于计算机科学、数据结构和算法设计等领域等价关系等价关系定义同时具有自反性、对称性和传递性的关系称为等价关系等价类对于等价关系R，元素a的等价类是与a有关系的所有元素集合，记为[a]={x|a,x∈R}商集由等价关系R导出的所有等价类构成的集合称为商集，记为A/R划分定理集合上的等价关系与集合的划分一一对应例题设R是整数集Z上的关系，aRb当且仅当a-b是3的倍数证明R是等价关系，并求

[1]和

[2]证明1自反性对任意a∈Z，a-a=0是3的倍数，所以aRa；2对称性若aRb，则a-b是3的倍数，所以b-a=-a-b也是3的倍数，故bRa；3传递性若aRb且bRc，则a-b和b-c都是3的倍数，所以a-b+b-c=a-c也是3的倍数，故aRc因此R是等价关系

[1]={...,-5,-2,1,4,7,...}，

[2]={...,-4,-1,2,5,8,...}偏序关系偏序关系是同时具有自反性、反对称性和传递性的关系若集合A上的关系R是偏序关系，则称序偶A,R为偏序集偏序集中，若任意两个元素a,b∈A，要么aRb，要么bRa，则称R为全序关系，A,R为全序集哈斯图是表示偏序集的一种图形方法，它省略了自反性和传递性导出的边，仅保留了覆盖关系（即不存在z使得xRz且zRy）的边在哈斯图中，如果x比y小，则x画在y的下方，并用一条线段连接偏序关系的典型例子包括1集合间的包含关系⊆；2整数间的整除关系|；3自然数集上的小于等于关系≤偏序关系在计算机科学中有广泛应用，如任务调度、依赖分析、拓扑排序等理解偏序集的性质对于解决这类问题具有重要意义关系的矩阵与图表示关系矩阵有向图表示设是从有限集到有限集的关关系可以表示为有向图，其中顶点集（在上R A={a₁,a₂,...,aₘ}B={b₁,b₂,...,bₙ}R G=V,E V=AA系，的关系矩阵是一个的矩阵，其中的关系）；边集∈R M_R m×n0-1E={a,b|a,b R}，如果∈；，如果有向图直观地表现了元素间的关系自反性表现为顶点上的自M_Ri,j=1a_i,b_j RM_Ri,j=0∉环；对称性表现为两顶点间有一对相反的有向边；传递性则体现a_i,b_j R在如果有从到和从到的路径，则存在从到的有向边a bbca c关系矩阵便于进行关系的运算，如关系的并、交、复合等例如，关系∘的矩阵是（布尔积）R SM_R·M_S通过有向图分析关系性质时，特别要注意环路和传递路径的存在关系的复合与逆关系的复合关系的逆关系的对偶设是从到的关系，关系的逆是关系的对偶是R AB S R R^-1=R R*=是从到的关系，则与∈若∉关系BCR{b,a|a,b R}R{b,a|a,b R}的复合是从到的关系是从到的关系，则的对偶与逆的区别在于，S AC AB∘∈存是从到的关对偶改变了关系的成员关R S={a,c A×C|R^-1BA在∈使得∈且系系b Ba,b R∈b,c S}关系复合的性质关系复合一般不满足交换律∘∘；关系复合满足1R S≠S R2结合律∘∘∘∘；关系复合对并运算的分配律∘∪R S T=R ST3R ST=∘∪∘，∪∘∘∪∘R SR TST R=SRTR关系逆的性质；∪∪；1R^-1^-1=R2R S^-1=R^-1S^-1；∘∘逆关系在分析3R∩S^-1=R^-1∩S^-14R S^-1=S^-1R^-1关系结构和性质时非常有用，特别是在证明关系性质时函数概念回顾111单射函数满射函数双射函数对任意，有，保持元素唯一性对任意∈，存在∈使得，覆盖所有既是单射又是满射的函数，形成一一对应关系x₁≠x₂fx₁≠fx₂y Yx X fx=y目标元素函数（映射）是一种特殊的二元关系，是从集合到集合的对应关系，满足中每个元素都有唯一的像∈与之对应，记为集合称为定X Y f Xx fxYf:X→Y X义域，称为陪域，∈称为值域，记为Y{fx|x X}fX复合函数给定函数和，它们的复合是∘，定义为∘逆函数若函数是双射，则存在唯一的函数f:X→Y g:Y→Z gf:X→Z gfx=gfx f:X→Y，使得∘且∘，其中和分别是和上的恒等函数这个函数称为的逆函数，记为g:Y→X gf=I_Xfg=I_Y I_X I_Y XY gf f^-1常见离散函数常量函数形式，其中为常数特点对于定义域中的任何值，函数值都是常数fx=c c例如，对任意，都等于c fx=5x fx5恒等函数形式特点函数值等于自变量本身在关系的矩阵表示中，恒等fx=x关系的矩阵是单位矩阵恒等函数在函数复合中具有特殊地位，类似于乘法中的1阶乘函数形式，其中为非负整数特点，，fn=n!n f0=1fn=n·n-1!n阶乘函数在组合计数中有广泛应用，如排列数公式、组合数公式等0指数函数与对数函数指数函数，且对数函数，fx=aˣa0a≠1gx=log_ax a且这两类函数互为逆函数，在离散数学和计算复杂性分析中有0a≠1重要应用函数题型及解法函数计数问题从n个元素的集合X到m个元素的集合Y，不同函数的个数为m^n其中，单射函数（要求n≤m）的个数为m!/m-n!；满射函数（要求n≥m）的个数为m!·Sn,m，其中Sn,m是第二类斯特林数一一对应问题证明两个集合之间存在一一对应关系，常用方法是构造一个双射函数另一种方法是证明两个集合具有相同的基数（有限集合）或可数无限性（无限集合）函数性质问题证明函数的单射、满射或双射性质证明单射若fx₁=fx₂，则x₁=x₂证明满射对任意y∈Y，找到x∈X使得fx=y证明双射证明函数既是单射又是满射示例题证明函数f:Z→Z，fn=n+3是双射证明1证明f是单射若fn₁=fn₂，则n₁+3=n₂+3，所以n₁=n₂2证明f是满射对任意m∈Z，取n=m-3∈Z，有fn=n+3=m-3+3=m因此，f是双射其逆函数为f⁻¹n=n-3代数结构基础二元运算在集合A上的二元运算是从A×A到A的映射，记为*对任意a,b∈A，a*b∈A，即运算结果仍在集合A中（封闭性）常见的二元运算有加法、乘法、模运算等半群若代数系统S,*满足1在S上的二元运算*是封闭的；2*满足结合律对任意a,b,c∈S，a*b*c=a*b*c；则称S,*为半群幺半群若半群S,*中存在单位元e，使得对任意a∈S，有e*a=a*e=a，则称S,*为幺半群（或含幺半群）群若幺半群G,*中每个元素a都有逆元a⁻¹，使得a*a⁻¹=a⁻¹*a=e，则称G,*为群子群判定设G,*是群，H是G的非空子集若对任意a,b∈H，有a*b⁻¹∈H，则H是G的子群这个判定定理简化了证明子群的过程，只需验证一个条件，而不是逐一验证群的所有性质代数结构的研究在现代数学和计算机科学中有重要地位，特别是在密码学、编码理论、量子计算等领域理解这些基本概念有助于更深入地学习抽象代数和其应用群的基本性质群G,*的基本性质包括1结合律对任意a,b,c∈G，a*b*c=a*b*c；2单位元存在e∈G，使得对任意a∈G，e*a=a*e=a；3逆元对任意a∈G，存在a⁻¹∈G，使得a*a⁻¹=a⁻¹*a=e群的其他重要性质1消去律若a*b=a*c或b*a=c*a，则b=c；2方程解的存在唯一性对任意a,b∈G，方程a*x=b和y*a=b分别有唯一解x=a⁻¹*b和y=b*a⁻¹；3单位元的唯一性群中单位元是唯一的；4逆元的唯一性群中每个元素的逆元是唯一的示例证明证明群中的单位元是唯一的证明假设e和e都是群G中的单位元，则对任意a∈G，有a*e=a和a*e=a特别地，取a=e，有e*e=e；取a=e，有e*e=e由单位元定义，e*e=e，所以e=e，即单位元是唯一的同构与同余同构定义同余关系同余算术设和⊙是两个群，如果存在双射在整数集上，定义关系在中，定义加法和乘G,*H,Z≡mod m Z_m[a]+[b]=[a+b]，使得对任意∈，都有对任意∈，当且仅当法这些运算满足封闭性和f:G→H a,b Ga,b Za≡b modm[a]·[b]=[a·b]⊙，则称是从到的同，即是的倍数这是一个等结合律是一个模的加法群，fa*b=fa fbf G H m|a-b a-b mZ_m,+m构映射，记为≅同构的群在代数结构价关系，其等价类为，构而当是素数时，是一个模GH

[0],

[1],...,[m-1]mZ_m\{

[0]},·上是相同的，仅在元素的标记上可能不成了剩余类环的乘法群Z_m m同代数结构综合题型结构判定判断给定的代数系统是否为半群、幺半群、群、阿贝尔群等需要逐一验证相应的性质子群判定判断给定的集合是否为某个群的子群可以使用子群判定定理非空集合H是群G的子群当且仅当对任意a,b∈H，有a*b⁻¹∈H运算表分析根据给定的有限群的运算表（凯莱表），分析群的性质、元素的阶等同构证明证明两个群是同构的，需要构造一个保持运算的双射例题证明集合G={0,1,2,3,4}上定义的运算a*b=a+b mod5构成一个群，并证明该群是循环群解答1封闭性对任意a,b∈G，a*b=a+b mod5∈G；2结合律a*b*c=a+b mod5+cmod5=a+b+c mod5=a*b*c；3单位元0是单位元，因为a*0=a+0mod5=a mod5=a；4逆元对任意a∈G，其逆元为5-a mod5，因为a*5-a mod5=a+5-a mod5=5mod5=0所以G,*是群该群是循环群，因为G可以由元素1生成1,1*1=2,1*1*1=3,1*1*1*1=4,1*1*1*1*1=0命题逻辑基础命题的概念逻辑联结词命题是一个陈述句，它要么为真，命题之间可以通过逻辑联结词连接要么为假，不能既真又假例如，成复合命题否定为假1¬p p是命题（真命题），时为真，为真时为假；合取2+3=5p2是命题（假命题），而∧和都为真时为真，否则53p q p q不是命题（因为真假取决为假；析取∨和至少一x+y=103p q p q于和的值）个为真时为真，都为假时为假；x y4蕴含为真且为假时为p→qp q假，其他情况为真；双蕴含5和真值相同时为真，不p↔qp q同时为假真值表真值表是表示命题公式在所有可能赋值下真值的表格对于包含个命题变元的公n式，其真值表有行通过真值表可以判断命题公式是否为重言式（永真式，所2^n有赋值下都为真）、矛盾式（永假式，所有赋值下都为假）或可满足式（存在使其为真的赋值）常用逻辑等价关系名称逻辑等价式双重否定律¬¬p≡p德摩根律¬p∧q≡¬p∨¬q,¬p∨q≡¬p∧¬q交换律p∧q≡q∧p,p∨q≡q∨p结合律p∧q∧r≡p∧q∧r,p∨q∨r≡p∨q∨r分配律p∧q∨r≡p∧q∨p∧r,p∨q∧r≡p∨q∧p∨r蕴含等价式p→q≡¬p∨q双蕴含等价式p↔q≡p→q∧q→p≡p∧q∨¬p∧¬q对偶律将∧与∨互换，将0与1互换，保持¬不变，公式真值不变等价式举例证明逻辑公式p→q→r和p→q→r不等价证明方法构造一个赋值，使得两个公式的真值不同例如，取p=真，q=假，r=假则p→q→r=真→假→假=假→假=真；而p→q→r=真→假→假=真→真=真这个例子不能说明不等价我们再取p=假，q=真，r=假，则p→q→r=假→真→假=真→假=假；而p→q→r=假→真→假=假→假=真此时两公式真值不同，所以它们不等价命题公式化简识别公式类型应用等价关系判断是否为重言式、矛盾式或可满足式使用逻辑等价律进行变换2验证结果化简表达式用真值表或等价推导检查消除冗余、合并相似项逻辑恒真与悖论重言式（逻辑恒真）是在所有可能的赋值下都为真的命题公式，如p∨¬p；矛盾式（悖论）是在所有可能的赋值下都为假的命题公式，如p∧¬p化简技巧1利用吸收律p∨p∧q≡p，p∧p∨q≡p；2利用分配律展开或合并；3利用蕴含等价式将p→q转化为¬p∨q；4利用德摩根律处理否定；5利用对偶性质例如，化简p∧q∨¬p∧r∨q∧r p∧q∨¬p∧r∨q∧r≡p∧q∨¬p∧r∨q∧r∧p∨¬p≡p∧q∨¬p∧r∨q∧r∧p∨q∧r∧¬p≡p∧q∨¬p∧r∨p∧q∧r∨¬p∧q∧r≡p∧q∨¬p∧r∨p∧q∧r∨¬p∧r∧q≡p∧q∨p∧q∧r∨¬p∧r∨¬p∧r∧q≡p∧q∧1∨r∨¬p∧r∧1∨q≡p∧q∨¬p∧r谓词逻辑谓词与命题函数谓词是包含变量的命题函数，只有当变量被赋予具体值时，才能判断真假例如，Px:x5是一个谓词，当x=6时为真，当x=3时为假全称量词全称量词∀表示对所有∀x Px表示对于定义域中的所有x，谓词Px都为真例如，∀x x0→x²0表示对于所有实数x，如果x大于0，则x²大于0存在量词存在量词∃表示存在∃x Px表示定义域中存在至少一个x使谓词Px为真例如，∃x x²=4表示存在实数x使得x²等于4量词的否定全称量词和存在量词的否定符合以下等价关系¬∀x Px≡∃x¬Px，¬∃x Px≡∀x¬Px这意味着并非所有x都满足Px等价于存在x不满足Px；不存在x满足Px等价于所有x都不满足Px量词的换序含有多个量词的谓词公式，如果量词类型相同全是∀或全是∃，则可以交换顺序；如果量词类型不同，一般不能交换顺序例如，∀x∀y Px,y≡∀y∀x Px,y，∃x∃y Px,y≡∃y∃xPx,y，但∀x∃y Px,y与∃y∀x Px,y一般不等价数理逻辑题型命题证明谓词应用给定前提和结论，证明结论是否从前提逻辑推出常用方法包括谓词逻辑题型通常要求•真值表法适用于命题变元较少的情况，列出所有可能的赋值，•将自然语言表述转换为谓词公式，如所有学生都喜欢至少一门检查在前提为真的情况下，结论是否也为真课程表示为∀∃∧xSx→yCy Lx,y•等价变换法利用逻辑等价关系，将复杂表达式转化为更简单的•求谓词公式的否定，如¬∀x∃y Px,y≡∃x∀y¬Px,y形式证明谓词公式的等价性或蕴含关系•推演法使用推理规则（如肯定前件、否定后件、假言推理等）•使用量词的性质解决实际问题•从前提推导出结论解题思路明确题目要求和已知条件；对于命题逻辑，可以使用等价变换化简或真值表验证；对于谓词逻辑，注意量词的作用域和变123量的约束关系；复杂问题可以先转化为标准形式，如合取范式或析取范式4例题证明∧∨p→r q→r≡p q→r证明∧∨∧∨∧∨∨∨∨p→r q→r≡¬p r¬q r≡¬p¬q r≡¬pqr≡pq→r证明基本方法直接证明从已知条件出发，通过逻辑推理，直接得出结论适用于形如如果p，则q的命题如证明如果n是奇数，则n²也是奇数假设n是奇数，则n=2k+1（k为整数），计算n²=2k+1²=4k²+4k+1=22k²+2k+1，所以n²是奇数逆否证明2证明逆否命题如果¬q，则¬p，等价于原命题如果p，则q如证明如果n²是偶数，则n是偶数证明其逆否命题如果n是奇数，则n²是奇数（见上一个例子）反证法假设结论不成立（即假设结论的否定为真），推导出矛盾，从而证明原结论成立如证明√2是无理数假设√2是有理数，则存在最简分数p/q使得√2=p/q，推导出矛盾，所以√2是无理数数学归纳法证明关于自然数n的命题Pn对所有n≥n₀成立1证明基础情况Pn₀成立；2假设Pk成立，证明Pk+1也成立如证明1+2+...+n=nn+1/2数学归纳法应用一般归纳法步骤强归纳法常见应用场景第一步证明基础情况（或）成强归纳法与普通归纳法的区别在于归纳假数学归纳法广泛应用于证明求和公式、不P1Pn₀立第二步归纳假设，假设对某个设普通归纳法假设成立，强归纳法等式、整除性质、算法正确性和复杂度分Pk Pk成立第三步归纳证明，在归纳假假设都成立强归纳法析等在离散数学中，它是证明递归定义k≥1P1,P2,...,Pk设的基础上，证明成立通过这三适用于后一项依赖于前多项的情况，如证的数列性质、图论性质和组合问题的强大Pk+1个步骤，可以证明对所有（或明斐波那契数列性质、证明每个大于的整工具如证明对的整数成Pn n≥112^nn²n≥5）成立数都可以分解为素数的乘积等立n≥n₀典型证明题详解多变量归纳法1适用于含有多个变量的命题证明分层归纳法2对不同范围的变量使用不同的归纳策略嵌套归纳法在归纳证明中嵌套另一个归纳证明例题一（分层归纳法）证明对任意n≥1，有1²+2²+...+n²=nn+12n+1/6证明1基础情况当n=1时，左边为1²=1，右边为1·2·3/6=1，相等，成立2归纳假设假设对于某个k≥1，有1²+2²+...+k²=kk+12k+1/63归纳步骤考虑n=k+1的情况，左边为1²+2²+...+k²+k+1²=kk+12k+1/6+k+1²=kk+12k+1/6+k+1²·6/6=k+1/6·[k2k+1+6k+1]=k+1/6·[2k²+k+6k+6]=k+1/6·[2k²+7k+6]=k+1/6·[k+22k+3]=k+1k+22k+3/6=k+1k+1+12k+1+1/6，符合公式，得证例题二（多变量归纳法）证明对任意自然数m和n，有Cm+n,n=Cm+n-1,n+Cm+n-1,n-1证明使用双重归纳法，先对n归纳，再对m归纳，或采用组合意义直接证明组合数学基础加法原理乘法原理如果一个事件可以通过种方式实现，另一个事件可以通过种方式如果一个事件可以通过种方式实现，对于每一种方式，另一个事件n m n实现，且这两个事件不能同时发生，则这两个事件中的一个发生的可以通过种方式实现，则两个事件按此顺序实现的方式有种mn·m方式有n+m种形式化表示若A∩B=∅，则|A∪B|=|A|+|B|形式化表示|A×B|=|A|·|B|有序选取无序选取从个不同元素中有序地选取个元素，排列数为从个不同元素中无序地选取个元素，组合数为n rPn,r=n!/n-n rCn,r=n!/[r!n-这表示从个不同元素中选取个不同的元素，并考虑它们的顺这表示从个不同元素中选取个不同的元素，不考虑它们的顺r!n rr!]n r序，共有多少种不同的选法序，共有多少种不同的选法排列与组合问题二项式定理123基本公式二项式系数性质帕斯卡恒等式a+b^n=∑k=0to n Cn,ka^n-Cn,k=Cn,n-k,Cn,0+Cn,1+...Cn,k=Cn-1,k-1+Cn-1,kkb^k+Cn,n=2^n二项式定理是组合数学中的重要定理，描述了多项式的展开式它的一般形式是a+b^n a+b^n=∑k=0to nCn,ka^n-kb^k其中是二项式系数，表示从个元素中选取个的组合数=Cn,0a^n+Cn,1a^n-1b+...+Cn,nb^nCn,k n k复杂系数求解技巧求展开式中项的系数找出所有中项的系数，然后按二项式公式加权求和；对于1a+b^n x^k a^n-ib^i x^k2形式的表达式，可以先将其改写为，然后应用二项式定理；利ax^m+by^n^r ax^m+by^n^r=ax^m^r1+by^n/ax^m^r3用生成函数方法求解复杂系数；对于特殊的二项式展开，如，其特点是系数简单，可以直接套用公式41+x^n鸽笼原理基本原理推广形式应用举例鸽笼原理的基本形式如果个物体放入鸽笼原理的推广形式如果个物体放入个鸽笼原理在组合数学、数论和计算机科学中n+1nk个盒子中，则至少有一个盒子包含至少两盒子中，则至少有一个盒子包含至少有广泛应用经典例题证明任意个n113个物体数学化表述若，则存个物体（表示大于或等于的不同的整数中，必定存在两个数，它们的差|X||Y|·k n/k xx⌈⌉⌈⌉在∈，使得，其中最小整数）这意味着如果平均每个盒子要能被整除；证明在平面上任取个点，y Y|f^-1y|k f:X→Y1225是一个函数，表示的原像集合放入个物体，那么必然存在一个盒子的必有两点之间的距离不超过直径为的圆的f^-1y yn/k1物体数量不少于这个平均值的上取整直径；证明在任意个不超过的正3n+12n整数中，必定存在两个数，其中一个整除另一个组合数学典型题型复杂计数组合应用归纳应用型问题这类题型通常涉及多重约束条件下的计数问题解决策略包括这类题型要求利用数学归纳法证明组合恒等式或不等式常见题型包括分解问题将复杂问题分解为简单子问题，应用加法原理和乘法

1.原理组合恒等式证明如证明

1.∑k=0to nCn,k²=C2n,n直接计数与间接计数有时候计算补集更简单，即总情况数不组合不等式证明如证明

2.-

2.C2n,n≥2^n n≥1符合条件的情况数求和公式证明如证明

3.∑k=0to nk·Cn,k=n·2^n-1递推关系建立递推方程，如卡特兰数满足递推式

3.Cn Cn=组合解释法通过不同的组合解释，建立恒等式的证明

4.C0·Cn-1+C1·Cn-2+...+Cn-1·C0特殊计数技巧如球盒模型、隔板法等

4.例题分析证明恒等式Cn,0-Cn,1+Cn,2-...+-1^n·Cn,n=0n≥1证明考虑二项式的展开式根据二项式定理，1-1^n1-1^n=∑k=0to nCn,k·1^n-k·-1^k=Cn,0-Cn,1+Cn,2-...+-而当时因此，这个证明方法简洁有力，展1^n·Cn,n1-1^n=0^n=0n≥1Cn,0-Cn,1+Cn,2-...+-1^n·Cn,n=0n≥1示了代数与组合的结合递归关系基础递归关系定义线性递推关系经典递推序列递归关系（递推关系）是一种表达数列中如果递推关系可以表示为经典的递推序列包括斐波那契数列an=c1·an-1+1的项与其前面的项之间关系的方程形式，其中c2·an-2+...+ck·an-k+gn c1,F0=0,F1=1,Fn=Fn-1+Fn-2上，如果一个数列满足形如是常数，是的函数，则称；等比数列{an}an=c2,...,ck gn n n≥22a1=c,an=r·an-的方程，则称该方它为阶线性递推关系当恒为时，；等差数列fan-1,an-2,...,an-k kgn01n≥23a1=a,an=an-1程为这个数列的递归关系称为齐次线性递推关系；否则，称为非齐；卡特兰数+d n≥24C0=1,Cn=次线性递推关系∑k=0to n-1Ck·Cn-1-k n≥1解决递归关系问题的基本方法包括特征方程法、生成函数法、差分方程法等在实际应用中，递归关系广泛存在于算法分析、组合计数和概率模型中例如，归并排序的时间复杂度满足递推关系；二分查找的时间复杂度满足递推关系Tn=2Tn/2+On Tn=Tn/2+O1初值条件在递归关系中至关重要，它们决定了递归关系的唯一解对于阶线性递推关系，需要个初值条件才能唯一确定数列例k k如，斐波那契数列需要和两个初值，才能递推出整个数列F0F1线性递归关系解法特征方程法1求解齐次线性递推关系的主要方法特解法2求解非齐次线性递推关系的通用策略生成函数法3求解复杂递推关系的强大工具特征方程法是求解齐次线性递推关系的标准方法对于阶齐次线性递推关系，其特征方程为k an=c1·an-1+c2·an-2+...+ck·an-k r^k-c1·r^k-如果特征方程有个不同的根，则通解形式为，其中系数由初1-c2·r^k-2-...-ck=0k r1,r2,...,rk an=α1·r1^n+α2·r2^n+...+αk·rk^nαi值条件确定如果特征方程有重根，则通解需要调整常数系数的例子考虑斐波那契数列的递推关系，其特征方程为，解得，通解形式为Fn=Fn-1+Fn-2r^2-r-1=0r1=1+√5/2r2=1-√5/2代入初值和，解得，因此，，这就Fn=α1·r1^n+α2·r2^n F0=0F1=1α1=1/√5α2=-1/√5Fn=1/√5·1+√5/2^n-1/√5·1-√5/2^n是斐波那契数列的闭公式，也称为比内公式复杂递归模型分段递归模型递归嵌套模型1根据变量不同范围定义不同的递推式递推公式中参数也通过递归定义分治递归模型树形递归模型将问题分解为规模更小的子问题每一步递归产生多个子问题分段递归模型在实际问题中非常常见，例如Ackermann函数Am,n=n+1m=0；Am,n=Am-1,1n=0；Am,n=Am-1,Am,n-1m0,n0这是一个双参数递归函数，且增长极其迅速，超过了任何原始递归函数递归嵌套模型的典型例子是汉诺塔问题T1=1；Tn=2·Tn-1+1n1这描述了将n个盘子从一根柱子移动到另一根柱子所需的最少步数解得Tn=2^n-1在算法分析中，快速排序的平均时间复杂度也是通过递归方程Tn=Tk+Tn-k-1+On来分析的，其中k是随机选择的枢轴元素的位置递归关系典型题目算法复杂度递归分析组合问题递归模型数学归纳证明在算法分析中，许多分治算法的时间复杂许多组合计数问题可以建立递推关系例对于由递推关系定义的数列，可以用数学度都可以用递推关系表示对于形如如，用的多米诺骨牌铺满的棋盘的归纳法证明其性质例如，证明斐波那契Tn1×22×n的递推关系，可以使用主方法数满足，，数列满足=aTn/b+fn FnF1=1F2=2Fn+m=Fn-1·Fm+Fn·Fm+1定理（）求解当这实际上首先验证基础情况，然后假设结论对某个Master Theoremfn=Fn=Fn-1+Fn-2n≥3n时，若，则是斐波那契数列类似地，卡特兰数表和所有成立，证明对和所有也成On^c clog_ba Tn=Cn mn+1m；若，则示对括号的合法排列数，满足递推关系立这种技巧在证明递归定义的数列的各Θn^log_ba c=log_ba n；若，则，种恒等式中十分有用Tn=Θn^c·log nclog_ba C0=1Cn=∑i=0to n-1Ci·Cn-1-iTn=Θfn图论基础与基本概念图的定义子图图G=V,E由顶点集V和边集E组成，其中边连接图H是图G的子图，如果H的顶点集是G的顶点集2顶点对如果边有方向，则为有向图；否则为无的子集，且H的边集是G中这些顶点之间边的子向图集度数完全图顶点的度数是与该顶点相关联的边的数量对于完全图是每对不同顶点之间都有边的无向图n个有向图，区分入度和出度顶点的完全图记为Kn，有nn-1/2条边图论的其他基本概念1路径从一个顶点到另一个顶点的边的序列；2回路（环）起点和终点相同的非平凡路径；3连通图任意两个顶点之间都存在路径的无向图；4连通分支图的极大连通子图；5双射图顶点集可以划分为两个子集，使得每条边连接的两个顶点分别属于这两个子集；6平面图可以在平面上绘制而没有边交叉的图无向图的一个重要性质是握手定理所有顶点的度数之和等于边数的两倍，即∑v∈V degv=2|E|这是因为每条边对两个顶点的度数各贡献1对于有向图，所有顶点的入度之和等于所有顶点的出度之和，且等于边数∑v∈V in-degv=∑v∈V out-degv=|E|图的矩阵表示邻接矩阵关联矩阵对于具有个顶点的图，其邻接矩阵是一个的矩阵，其中对于具有个顶点和条边的图，其关联矩阵是一个的n GA n×n nm GBn×m如果顶点和之间有边，否则对于带权图，矩阵对于无向图，如果顶点与边关联，否则A[i,j]=1i jA[i,j]=0B[i,j]=1i jB[i,j]=可以是边的权值邻接矩阵的特点对于有向图，如果边从顶点发出，则；如果边指A[i,j]0j i B[i,j]=1j向顶点，则；否则关联矩阵的特点iB[i,j]=-1B[i,j]=0无向图的邻接矩阵是对称的；

1.每列恰好有两个非零元素（对于无向图）或者一个和一个表示没有自环；

1.1-

12.A[i,i]=0（对于有向图）；邻接矩阵的次幂中的元素表示从顶点到顶点

3.A k A^kA^k[i,j]i j关联矩阵适合分析图的一些代数性质；

2.的长度为的路径数；k关联矩阵需要的存储空间，对于稀疏图更为有利邻接矩阵需要的存储空间，不管图的边数多少

3.Onm

4.On²图的其他表示方法包括邻接表和边集数组邻接表对于稀疏图（边数远小于顶点数的平方）更为有效，空间复杂度为，适用On+m于大多数图算法边集数组适合某些特定的图算法，如最小生成树算法Kruskal路径与连通性路径与回路欧拉图哈密顿图路径是从一个顶点到另一个顶点的边的序列，欧拉路径是指通过图中每条边恰好一次的路哈密顿路径是指经过图中每个顶点恰好一次的其中相邻的边共享一个顶点简单路径是指不径欧拉回路是指通过图中每条边恰好一次并路径哈密顿回路是指经过图中每个顶点恰好重复经过顶点的路径回路（环）是起点和终回到起点的回路如果图存在欧拉回路，则一次并回到起点的回路如果图存在哈密顿G G点相同的非平凡路径简单回路是除起点和终称为欧拉图无向图是欧拉图的充要条件回路，则称为哈密顿图判断一个图是否为G G点外不重复经过顶点的回路是图连通且所有顶点的度数都是偶数有向哈密顿图是完全问题，没有已知的充要条NP图是欧拉图的充要条件是图连通且所有顶点件，但有一些充分条件，如定理如果Dirac G的入度等于出度是个顶点的无向图，且每个顶点的度数n≥3至少为，则是哈密顿图n/2G树及树的性质树的定义树的类型树是一个无环连通的无向图树具有以下等价特性根据结构和用途，树可以分为不同类型任意两个顶点之间有唯一的路径；有根树指定了一个特殊顶点作为根的树；••是无环连通的无向图；二叉树每个顶点最多有两个子节点（左子节点和右子节点）的••有根树；连通且边数等于顶点数减（）；•1|E|=|V|-1满二叉树除了叶节点外，每个节点都有两个子节点的二叉树；无环且边数等于顶点数减；••1完全二叉树除了最后一层外，每一层都被填满，且最后一层的删除任何一条边后图不再连通；••节点都靠左排列；添加任何一条边后图中会形成一个环•二叉查找树具有特定排序性质的二叉树；•平衡树任意节点的左右子树高度差不超过的二叉树；•1森林多棵树的集合•树的重要性质具有个顶点的树有条边；任何两个顶点之间有且仅有一条路径；是极小连通图和极大无环图；树中删除一条边后形成两棵n n-1树；树中添加一条边后形成一个环；对于有根树，除根节点外，每个节点有且仅有一个父节点；个顶点的无根树有种不同的带标记的nn^n-2树最小生成树问题2普利姆算法克鲁斯卡尔算法应用场景普利姆算法是一种求解最小生成树的贪心算克鲁斯卡尔算法也是一种求解最小生成树的贪最小生成树问题在网络设计、电路布线、集群法，从单个顶点开始，逐步扩展算法流程心算法，从边的角度出发算法流程1将所分析等领域有广泛应用例如，在通信网络设1选择任意起始顶点，加入当前生成树；2有边按权值从小到大排序；2按排序后的顺序计中，顶点代表通信站点，边代表连接站点的在连接当前生成树和未加入树的顶点的所有边遍历边，如果当前边连接的两个顶点不在同一通信线路，边的权值代表建设成本，最小生成中，选择权值最小的边加入；3重复步骤2，个连通分量中，则将该边加入最小生成树；3树给出了连接所有站点的最小成本方案直到所有顶点都加入生成树优点是实现简重复步骤2，直到生成树的边数为n-1优点是单，尤其适合稠密图；缺点是需要维护顶点的对于稀疏图效率高；缺点是需要维护顶点的连最小边权值信息通性信息，通常使用并查集实现树的遍历方式先序遍历对于二叉树，先访问根节点，然后递归地先序遍历左子树和右子树遍历序列总是以根节点开始，适合用于创建树的副本或前缀表达式中序遍历对于二叉树，先递归地中序遍历左子树，然后访问根节点，最后递归地中序遍历右子树对于二叉搜索树，中序遍历会产生一个有序的序列后序遍历对于二叉树，先递归地后序遍历左子树和右子树，然后访问根节点适用于删除树或计算后缀表达式，因为它会先处理子节点再处理父节点层序遍历按照从上到下、从左到右的顺序逐层访问树的节点通常使用队列实现，适用于需要按层次处理的场景，如计算树的宽度或查找最近的节点遍历树的应用举例1建立表达式树根据中序和后序/先序遍历结果，可以唯一确定一棵二叉树；2计算目录大小使用后序遍历，先计算所有子目录的大小，再计算当前目录的大小；3复制树结构使用先序遍历，先创建根节点，再递归复制左右子树；4判断两棵树是否同构比较它们的先序/中序/后序遍历结果树的遍历算法可以使用递归或迭代实现递归实现简洁易懂，但对于大规模树可能导致栈溢出；迭代实现通常使用栈（先序、中序、后序）或队列（层序），效率更高且不受调用栈限制图的典型算法广度优先搜索深度优先搜索应用场景广度优先搜索是一种图遍历算法，从深度优先搜索是另一种图遍历算法，图的遍历算法在各种实际问题中有广泛应BFS DFS起始顶点开始，先访问所有相邻顶点，然后从起始顶点开始，尽可能深地探索每一条路用网络路由查找网络中的最短路径；1再访问这些顶点的邻居通常使用队列实径，遇到死胡同则回溯通常使用递归或栈社交网络分析找出朋友关系、社区结2现，具有的时间复杂度的特实现，具有的时间复杂度的构；爬虫遍历互联网页面；解OV+E BFSOV+E DFS3Web4点是可以找到从起点到任意可达顶点的特点是可以方便地检测环和拓扑排序；决迷宫和谜题寻找路径或解决方案；115最短路径（以边数计）；适合解决最短适合解决连通性、路径存在性等问题；检测循环依赖在编译系统中检查模块间的22路径、连通分量等问题；适用于无权图在解决迷宫类问题时非常有效循环依赖；拓扑排序安排有依赖关系336或权值相同的图的任务的执行顺序图论典型题型欧拉路径与回路问题判断图是否存在欧拉路径或欧拉回路，以及如何构造它们无向图存在欧拉回路的充要条件是图连通且所有顶点的度数都是偶数；存在欧拉路径但不存在欧拉回路的充要条件是图连通且恰好有两个顶点的度数是奇数有向图存在欧拉回路的充要条件是图强连通且所有顶点的入度等于出度；存在欧拉路径的条件类似，允许起点和终点的入度出度有差异哈密顿圈问题判断图是否存在哈密顿路径或哈密顿回路，这是一个NP完全问题，没有已知的有效算法但有一些充分条件，如Dirac定理和Ore定理，可以用于判断特定类型的图实际应用中常使用启发式算法或近似算法图着色问题为图的顶点分配颜色，使得相邻顶点颜色不同，且使用的颜色数最少图的色数是图的一个重要指标平面图的四色定理指出，任何平面图都可以用至多四种颜色着色，使得相邻区域不同色图着色问题在调度安排、寄存器分配、地图着色等领域有重要应用离散概率基础概率定义随机变量离散概率空间是一个三元组S,F,随机变量是从样本空间S到实数集R的P，其中S是样本空间（所有可能结函数X:S→R离散随机变量的值域果的集合），F是事件集合（S的子集是有限集或可数无限集随机变量的的集合），P是概率函数（将事件映分布是指随机变量取各个可能值的概射到[0,1]的实数）概率函数满足率常见的离散分布包括1伯努利1对任何事件A，0≤PA≤1；分布单次试验成功或失败；2二项2PS=1；3对于互不相容的事件分布n次独立重复试验中成功的次序列A₁,A₂,...,P∪Aᵢ=∑PAᵢ数；3几何分布首次成功所需的试验次数；4泊松分布单位时间/空间内事件发生的次数期望与方差离散随机变量X的期望（或均值）是X的可能值的加权平均，权重是相应的概率EX=∑x·PX=x随机变量X的方差是X偏离其期望的平方的期望VarX=EX-EX²=EX²-EX²方差表示随机变量分布的离散程度期望和方差具有一些重要性质，如期望的线性性质EaX+bY=aEX+bEY概率与组合应用1/68/10单个骰子的点数为6的概率考试通过的条件概率对应于样本空间中单一结果的概率给定已读书的条件下通过考试的概率1-1/e非空集合的概率随机放置n个球到n个盒子至少有一个盒子为空的概率极限事件独立性是概率论中的重要概念如果事件A和B满足PA∩B=PA·PB，则称A和B是独立的这意味着一个事件的发生与否不影响另一个事件的概率独立性可以推广到多个事件事件A₁,A₂,...,Aₙ是相互独立的，如果对于任意子集I⊆{1,2,...,n}，都有P∩ᵢ∈ᵢAᵢ=∏ᵢ∈ᵢPAᵢ经典抽取问题是概率与组合的结合例如，从52张扑克牌中随机抽取5张，求得到同花的概率同花是指5张牌都是同一花色概率计算为P同花=4·C13,5/C52,5=4·C13,5/C52,5=4·1287/2598960=

0.00198这个例子展示了如何使用组合数计算概率将有利结果数除以可能结果总数类似地，可以计算得到顺子、同花顺、四条等特定牌型的概率复习重点总结一集合论核心掌握集合的基本运算（并、交、补、差）及其性质（交换律、结合律、分配律等）；熟练应用德摩根定律和其他等价变换；理解幂集和笛卡尔积的概念；能应用容斥原理解决集合计数问题易错点德摩根定律的应用，集合相等的证明，复杂集合表达式的化简关系要点理解二元关系的定义和性质（自反性、对称性、传递性等）；掌握等价关系、等价类和商集的概念；理解偏序关系和全序关系的区别；熟悉关系的图示法和矩阵表示易错点关系的复合运算，等价类的构造，偏序集的哈斯图绘制函数重点掌握函数（单射、满射、双射）的定义和判定方法；理解复合函数和逆函数的性质；能分析有限集合间函数的计数问题易错点函数的单射和满射性质的证明，复合函数的性质，逆函数的存在条件复习重点总结二代数结构理解群、环、域的定义和基本性质组合数学2掌握排列组合计数原理和重要公式图论熟悉图的基本概念和常用算法代数结构考点梳理1掌握半群、幺半群、群的定义和判定方法；2理解子群的概念和子群判定定理；3掌握循环群的性质及其生成元的特点；4理解同构的概念及其在代数结构中的意义；5熟悉同余关系及其在模运算中的应用组合数学考点梳理1熟练应用加法原理和乘法原理解决复杂计数问题；2掌握排列组合公式及其变式（如重复排列、重复组合、圆排列等）；3理解二项式定理及其在组合计数中的应用；4掌握鸽笼原理及其在组合问题中的应用；5了解特殊计数问题（如卡特兰数、斯特林数）的递推关系和应用图论考点梳理1掌握图的基本概念（顶点、边、度数、路径、连通性等）；2理解特殊图类型（如完全图、二部图、平面图等）的性质；3掌握树的定义和基本性质，能够分析树的应用问题；4理解欧拉图和哈密顿图的判定条件和构造方法；5掌握图的基本算法（如BFS、DFS、最小生成树、拓扑排序等）及其应用场景真题与模拟题选讲51085%近五年真题分析经典题型高频考点覆盖率总结近年考试重点和趋势归纳总结常见题型和解法本讲义覆盖主要考点比例近年试题精选1集合论证明集合等式A∩B∪A∩C∪B∩C=A∪B∩A∪C∩B∪C，解法要点是运用分配律和德摩根定律；2关系判断给定的关系是否为等价关系，并求其商集，关键是验证自反性、对称性和传递性；3图论判断给定的图是否为欧拉图，并构造欧拉回路，解题要点是检查顶点的度数是否全为偶数；4组合计数求解从10本不同的书中选择4本放在5个不同书架上的方法数，关键是分析放置方案的特点和约束解题策略与思路分析1集合问题常用元素分析法或分类讨论法；2关系问题注重定义的应用和性质的验证；3函数问题关注映射的本质特性；4组合计数问题重视加法原理和乘法原理的合理应用；5图论问题强调图的结构特点和相关算法的应用；6代数结构问题需要理解抽象概念并灵活应用定义总体而言，离散数学题目要求既有理论基础，又有实际运用能力，需要在复习中注重概念理解和方法掌握的结合复习建议与答疑有效复习策略学习资源推荐应试技巧系统梳理知识点将离散数学各部分内容系统化，教材《离散数学》（耿素云），《离散数学及其考前调整保持充足的睡眠和良好的身体状态，调建立完整的知识框架，理清各概念之间的联系应用》（Kenneth H.Rosen）整心态，以平常心对待考试多做习题通过大量习题练习加深对概念的理解，网络资源中国大学MOOC离散数学课程，国外名答题策略先易后难，确保基础题得分；答题清晰提高解题能力和速度尤其注重典型例题和历年真校公开课（如MIT的离散数学课程），各大论坛的规范，特别是证明题要层次分明，逻辑严密题的分析专题讨论和题库离散数学是一门需要理解和应用并重的课程，不仅要掌握基本概念和定理，更要培养抽象思维和逻辑推理能力在复习过程中，建议采用理解→应用→提升的学习路径首先理解基本概念和原理，然后通过例题应用这些知识，最后通过综合性题目提升解决复杂问题的能力学习离散数学遇到困难是正常的，关键是找到适合自己的学习方法可以尝试小组讨论、绘制思维导图、编写简化版解题笔记等方式辅助学习同时，保持积极的学习态度，相信通过持续的努力和合理的复习，一定能够取得良好的学习成果最后，欢迎随时提出问题，共同交流和探讨离散数学的奥秘。