《选修离散复习》课件

DISCRETEMATHEMATICS选修离散复习期末总复习课件·35页完整版∑∀x∞∃CONTENTS目录CourseReviewRoadmap01复习策略与高频考点导引05代数系统：群环域02数理逻辑：命题与推理06图论：连通性与特殊图03集合论：运算与计数07组合数学初步04二元关系与函数08综合练习与备考建议CHAPTER00复习策略导引高频考点与复习方法论R离散数学复习STRATEGY复习策略与高频考点构建体系·专项突破·错题回溯01构建知识图谱串联概念以核心概念为节点绘制思维导图，从命题联结词延伸到范式与推理证明，建立模块内纵向关联跨模块横向连接，如将等价关系与划分对应、偏序关系与哈斯图对应，形成结构化记忆网络02高频考点专项突破模板主析取范式、关系闭包、群同构判定、欧拉图判别四大题型整理固定解题步骤，考前反复演练针对每个考点准备2-3道典型例题，标注易错环节与验证方法，形成可复用的解题清单03错题分类回溯防重复按模块建立错题档案，区分概念理解偏差与计算疏忽两类错误，针对性补强薄弱环节每周回顾一次错题本，对反复出错的知识点重新推导定义与定理，确保底层逻辑清晰抓住「建体系→练题型→补漏洞」三个关键动作，高效完成离散数学期末复习CHAPTER01数理逻辑命题符号化范式推理证明DISCRETEMATHEMATICS01LOGICFUNDAMENTALSPROPOSITIONS命题与联结词基础Propositions&LogicalConnectives五个联结词的优先级与蕴涵式真值规定是命题逻辑的基石。联结词优先级：否定¬、合取∧、析取∨、蕴涵→、等价↔五个联结词优先级依次降低，括号可改变运算顺序蕴涵式真值：p→q仅当p真q假时为假，其余情况均为真，这一规定与自然语言直觉存在差异需特别记忆符号化步骤：识别原子命题并赋值符号，分析语句逻辑结构，用联结词按优先级组合成公式常见错误：将"除非q否则p"误译为p→q，正确应为¬q→p或等价的p∨q形式五个基本联结词的真值表H高校课程复习DISCRETEMATH等值演算与范式求解EquivalenceCalculus&NormalForms主析取范式与主合取范式具有唯一性，是判断公式类型与等价关系的可靠工具。德摩根律¬(p∧q)⇔¬p∨¬q¬(p∨q)⇔¬p∧¬q等值演算中最常用的变形规则分配律p∧(q∨r)⇔(p∧q)∨(p∧r)用于展开公式，是构造析取范式的核心步骤求主析取范式1化为析取范式2缺变元用(p∨¬p)补全3合并相同极小项4写成Σm形式公式类型判别重言式含全部极小项矛盾式不含任何极小项可满足式含部分极小项H离散数学REASONING命题逻辑推理证明PropositionalLogic—MethodsofProof三种推理方法的选择取决于结论形式。01直接证明法步骤要点从给定前提出发，依次运用假言推理、拒取式、析取三段论等规则推导新公式每一步注明所用规则与依据的前提编号，保持推导链清晰可追溯，直至推出目标结论02附加前提法适用场景当待证结论为A→B形式时，将A作为临时前提加入已知条件集，转而证明B成功推出B后即得A→B成立，将蕴涵式证明转化为更简单的直接推导问题03归谬法反向突破技巧假设结论的否定¬C为真，与原有前提一起推导，若能得出矛盾式则原结论C成立适用于直接证明路径不明显的情形，关键是找到能快速导出矛盾的中间推导步骤LOGICFIRST-ORDERLOGIC一阶逻辑量词与前束范式量词·辖域·前束范式转化量词辖域规则是前束范式转化的关键。量词基础全称量词∀xP(x)表示论域中所有个体满足P，存在量词∃xP(x)表示至少一个个体满足P辖域扩张若B不含x的自由出现，则∀xA→B⇔∀x(A→B)，∃xA→B⇔∃x(A→B)改名规则更换量词指导变元及其辖域内所有同名变元，新名不得与公式中已有自由变元重名前束范式转化01消去多余联结词02将否定深入至原子公式03约束变元改名04量词逐一提至前端Summary数理逻辑模块小结核心公式速查·五组关键方法覆盖80%考题类别核心公式/方法易错提醒蕴涵等值式p→q⇔¬p∨q勿与p∨q混淆，前件假时蕴涵恒真德摩根律¬(p∧q)⇔¬p∨¬q否定号分配时联结词互换主析取范式Σm(i₁,i₂,...)补全变元后用幂等律去重推理规则假言推理/拒取式/归谬每步注明依据，避免跳步量词辖域∀x(A→B)⇔∀xA→B（B无x）改名避免自由变元冲突备考提示：掌握以上五组核心公式与方法，即可覆盖数理逻辑80%以上的考题类型CHAPTER02集合论运算·恒等式·包含排斥原理D离散数学复习SETTHEORYCONCEPTS集合基本运算与恒等式集合恒等式证明的三种方法各有优势。五种基本运算并∪、交∩、差−、补~、对称差⊕，其中对称差A⊕B=(A−B)∪(B−A)成员资格表法列出所有元素归属情况组合，逐行验证等式两边结果一致即证恒等逻辑演算法将x∈A∪B转化为x∈A∨x∈B，利用命题等值式推导后再转回集合语言对称差性质满足交换律与结合律，但对交和并不满足分配律，即A⊕(B∩C)≠(A⊕B)∩(A⊕C)H离散数学CountingPrinciple包含排斥原理与计数包含排斥原理的本质是先加后减再补的容斥思想。两集合容斥：|A∪B|=|A|+|B|−|A∩B|，减去交集避免重复计数三集合容斥：单集之和减去两两交集之和再加上三集交集，符号交替正负整除计数应用：1到n中能被k整除的数个数为⌊n/k⌋，能同时被a,b整除即被lcm(a,b)整除推广形式：恰好满足k个性质的元素数可用广义容斥公式计算，涉及组合系数与交集大小三集合容斥原理·文氏图示意D离散数学复习SETTHEORYCHAPTERREVIEW幂集与笛卡尔积幂集的元素个数2ⁿ体现了子集的指数级增长。幂集P(A)幂集P(A)包含A的全部子集，当|A|=n时|P(A)|=2ⁿ。注意∅∈P(A)且A∈P(A)，空集与自身都是幂集的元素。笛卡尔积A×B由所有有序对(a,b)组成，其中a∈A、b∈B。元素个数|A×B|=|A|·|B|，一般A×B≠B×A，有序性是关键。空集运算对比空集的笛卡尔积：A×∅=∅×B=∅，结果为空；但P(∅)={∅}非空。两者易混淆需特别注意区分。n元关系定义为A₁×A₂×...×Aₙ的子集。二元关系是最常用情形，将在后续章节中详细展开讨论其性质与运算。CHAPTER03二元关系与函数性质·闭包·等价·偏序·映射D离散数学RELATIONS判定方法关系的五种性质判定关系性质判定有三条路径。五种性质判定对照表性质集合定义矩阵特征图特征自反∀a∈A,(a,a)∈R主对角线全1每个节点有自环反自反∀a∈A,(a,a)∉R主对角线全0无自环对称(a,b)∈R⇒(b,a)∈R关于主对角线对称双向边或无边反对称(a,b)∧(b,a)∈R⇒a=b对称位不同时为1无双向边传递(a,b)∧(b,c)∈R⇒(a,c)∈RM²≤M长度2路径必有直达边三种判定方法互为补充，考试时根据题目给出的表示形式选择最高效的路径。DDISCRETEMATHRELATIONSCLOSURECONSTRUCTION关系闭包的构造方法三种闭包中自反与对称闭包可直接写出，传递闭包需Warshall算法。01自反与对称闭包直接构造自反闭包r(R)=R∪IA，只需在主对角线上补齐缺失的(a,a)有序对对称闭包s(R)=R∪R⁻¹，将R中每个(a,b)的逆序对(b,a)加入02传递闭包Warshall算法初始化矩阵M为R的关系矩阵，对k从1到n依次处理：若M[i][k]=1则将第k行布尔加到第i行算法结束后M即为传递闭包矩阵，时间复杂度O(n³)，适合手算n≤5的小规模关系03闭包运算的顺序与性质rs(R)=sr(R)自反与对称闭包可交换，但tr(R)≠rt(R)传递闭包与其他闭包不可交换求pst(R)时应按先自反、再对称、最后传递的顺序，确保最终结果同时具备三种性质D离散数学复习RELATIONSCHAPTERREVIEW等价关系与集合划分等价关系与集合划分是一体两面。01等价关系三要素自反+对称+传递缺一不可。如整数集上的模n同余是典型等价关系——任意整数与自身同余（自反），a≡b则b≡a（对称），a≡b且b≡c则a≡c（传递）。02等价类等价类[a]是与a等价的所有元素之集。不同等价类互不相交，全体等价类之并为原集合，构成对原集合的一个完整划分。03划分→等价关系定义x~y当且仅当x,y属于划分的同一块，该关系必为等价关系。划分与等价关系之间存在一一对应的双射关系。04商集A/R商集A/R={[a]|a∈A}，其基数等于划分的块数。模n同余的商集ℤ/nℤ恰有n个元素。DISCRETEMATHORDERRELATIONS偏序关系与哈斯图绘制哈斯图通过省略冗余边使偏序结构可视化。偏序关系定义：偏序关系≤满足自反、反对称、传递三条性质，全序是任意两元素均可比的特殊偏序极大元与最大元：极大元不一定唯一且未必是最大元，最大元若存在则唯一且必为极大元哈斯图绘制规则：省略自环与传递边，小元素在下，仅画覆盖关系的连线确界概念：上确界sup是所有上界中的最小元，下确界inf是所有下界中的最大元，可能不存在典型偏序集哈斯图示例H高校课程复习FunctionsCONTENT函数类型判别与复合反函数单射满射双射的判别是函数部分的核心考点。Injective·Surjective单射满射双射判别方法单射：设f(a)=f(b)推出a=b；有限集上|A|>|B|则必非单射满射：对任意b∈B找到a∈A使f(a)=b；有限集上|A|<|B|则必非满射Composition复合函数性质传递规律g∘f单⇒f单（但g未必单），g∘f满⇒g满（但f未必满）f,g均双射则g∘f双射且(g∘f)⁻¹=f⁻¹∘g⁻¹，逆序性质是复合运算的重要特征Inverse反函数存在条件与求解f⁻¹存在当且仅当f是双射，此时f⁻¹:B→A满足f⁻¹(b)=a⇔f(a)=b求解步骤：先证双射→令y=f(x)解出x=g(y)→验证g确为f的逆函数CHAPTER04代数系统群·环·域·同态·同构HDISCRETEMATHAbstractAlgebra群的定义与判定方法GROUPTHEORY群的四条公理必须逐一验证，缺一不可。STEP01四条公理逐一验证封闭性任取a,b∈G验证a*b∈G，不封闭则直接否定群结构结合律验证(a*b)*c=a*(b*c)，小集合可枚举，大集合需代数推导STEP02单位元与逆元单位元e满足a*e=e*a=a对所有a成立，若存在则唯一逆元a⁻¹满足a*a⁻¹=a⁻¹*a=e，每个元素的逆元唯一STEP03有限群与阿贝尔群有限群判别运算表每行每列为G的置换（拉丁方），结合单位元存在即可判定阿贝尔群额外要求a*b=b*a，整数加法群、模n加法群均为阿贝尔群H离散数学AlgebraSUBGROUPTHEORY子群判定与正规子群子群一步判定法a*b⁻¹∈H是最常用的验证工具。子群一步判定H⊆G非空且∀a,b∈H有a*b⁻¹∈H，则H≤G。一步判定将封闭性、逆元和单位元验证统一为单一条件，是最简洁的子群验证方法。有限子集判定有限子集H⊆G只需验证封闭性即可判定子群。有限封闭蕴含逆元与单位元的存在，因此无需逐一检验群的全部公理。正规子群N◁G：∀g∈G有gNg⁻¹=N，等价于gN=Ng对所有g成立。正规子群是构造商群G/N的基础，保证了陪集运算的良定义性。拉格朗日定理|H|整除|G|。推论：素数阶群无非平凡子群，元素阶整除群阶。该定理是有限群结构分析的基石性结果。HAbstractAlgebraHOMOMORPHISMREVIEW·群论群同态与同构判定同态核是正规子群、像是子群是同态的基本性质。01同态定义与核像性质f:G→H同态要求f(a*b)=f(a)∘f(b)，核Ker(f)◁G，像Im(f)≤Hf(e_G)=e_H，f(a⁻¹)=f(a)⁻¹，这些性质由同态定义直接推出02同构判定与不变量排除同构必双射且保运算，阶数、元素阶分布、阿贝尔性都是同构不变量克莱因四元群V₄与Z₄阶数同为4但V₄有3个2阶元而Z₄仅1个，故不同构03同态基本定理的应用G/Ker(f)≅Im(f)将同态分解为自然同态G→G/Ker与嵌入Im(f)↪H的复合应用示例：Z→Z/nZ的自然投影核为nZ，得Z/nZ≅Z_nH离散数学复习ALGEBRADEFINITIONS环与域的基本定义环到域是逐层加条件的递进结构。01环<R,+,·><R,+>为阿贝尔群，<R,·>为半群，乘法对加法满足左右分配律。02零因子与整环a≠0,b≠0但ab=0时称零因子；整环是无零因子的交换含幺环。03域交换含幺环且每个非零元有乘法逆元。Q、R、C均为域。04有限域GF(pⁿ)阶为素数幂，同阶有限域同构；Zp（p为素数）是最简有限域。HDISCRETEMATHSECTIONDIVIDERCHAPTER05图论连通性欧拉哈密顿树着色26GGraphTheoryFUNDAMENTALSCONCEPTS图的基本概念与握手定理握手定理是图论最基本的计数工具。图的定义无向图边为无序对{u,v}，有向图边为有序对<u,v>，混合图同时含两种边握手定理Σdeg(v)=2|E|推论：奇度顶点个数为偶数特殊图类完全图Kn有n(n−1)/2条边；k-正则图所有顶点度数为k，则nk=2|E|图同构必要条件：顶点数、边数、度数序列相同；充分条件需构造保邻接双射GraphTheoryGRAPHTHEORY欧拉图与哈密顿图判定欧拉图有简洁的充要条件，哈密顿图仅有充分或必要条件。欧拉图欧拉回路充要条件：连通且所有顶点度数为偶数欧拉通路条件：连通且恰有两个奇度顶点Sufficient&Necessary哈密顿图Ore定理（充分）：δ(u)+δ(v)≥n对所有不相邻u,v成立则为哈密顿图Dirac定理（Ore特例）：δ(G)≥n/2则为哈密顿图，使用更简便但适用范围更窄必要条件：P(G−S)≤|S|对所有S⊆V成立，违反则非哈密顿图SufficientorNecessaryOnlyH离散数学复习GRAPHTHEORYSECTION29·TREES树的性质与最小生成树树的多个等价定义提供了灵活的判定角度。01树的等价定义与基本性质连通无回路、连通且|E|=|V|−1、无回路且|E|=|V|−1、任意两点唯一通路四者等价n阶树有n−1条边，至少两片树叶（度1顶点），加任一边产生唯一回路02生成树的存在性与构造连通图必有生成树，可通过破圈法或避圈法构造生成树不唯一，不同构造顺序可能得到不同生成树，但边数恒为n−103最小生成树算法对比Kruskal：边按权排序，依次选不形成回路的边，用并查集判圈，适合稀疏图Prim：从起点出发，每次选连接已选与未选顶点的最小权边，适合稠密图GRAPHTHEORY30平面图判定与图着色欧拉公式及其推论e≤3v-6是平面图判定的第一道筛子。01欧拉公式连通平面图：v−e+r=2推论：e≤3v−6（v≥3）二部平面图：e≤2v−402库拉托夫斯基定理图是平面图⇔不含K₅或K₃,₃的细分作为子图K₅：5阶完全图·K₃,₃：完全二部图03色数χ(G)完全图：χ(Kn)=n圈图：χ(Cn)=2（n偶）或3（n奇）二部图：χ=204Brooks定理与四色定理Brooks定理：连通图若非完全图、非奇圈，则χ≤Δ四色定理：平面图χ≤4CHAPTER06组合数学初步计数·容斥·递推·经典模型31COMBINATORICS排列组合与递推关系排列组合公式是计数的基石，错位排列的递推式与通项公式均需掌握。01排列组合基本公式与恒等式P(n,r)=n!/(n−r)!，C(n,r)=n!/r!(n−r)!，Pascal恒等式C(n