自考02324离散数学核心内容

自考02324离散数学核心内容一、总体结构（考试就考这5大块）命题逻辑（选择、填空、等值演算、主范式、推理）谓词逻辑（量词、等值式、推理）集合与关系（集合运算、等价关系、偏序、函数）代数系统（运算性质、半群/独异点/群、环域基础）图论（通路、回路、欧拉图、哈密顿图、树、最小生成树、握手定理）二、第1部分：命题逻辑（必考、送分）1.基本联结词¬非、∧合取（且）、∨析取（或）、→蕴涵、↔等价重要等值（背熟）：A→B⟺¬A∨BA↔B⟺(A→B)∧(B→A)德摩根律：¬(A∧B)⟺¬A∨¬B；¬(A∨B)⟺¬A∧¬B蕴涵等值、假言易位：A→B⟺¬B→¬A2.公式分类重言式（永真）矛盾式（永假）可满足式3.主范式（必考计算）极小项mᵢ：简单合取，成真赋值唯一极大项Mᵢ：简单析取，成假赋值唯一关系：¬mi​⟺Mi​求主析取范式步骤：消去→、↔否定内移（德摩根）展开为析取范式补变元（A⟺A∧(B∨¬B)）合并、排序→得到

mi1​∨mi2​∨⋯4.推理理论（证明必考）推理规则：假言推理：A→B,A⇒B拒取式：A→B,¬B⇒¬A假言三段论：A→B,B→C⇒A→C析取三段论：A∨B,¬B⇒A三、第2部分：谓词逻辑（选择+简答）1.量词∀全称量词∃存在量词2.重要等值式（背）¬∀xA(x)⟺∃x¬A(x)¬∃xA(x)⟺∀x¬A(x)量词辖域收缩/扩张（变元不出现即可进出）消去量词：对有限个体域展开3.谓词推理UI（全称特指）：∀xA(x)⇒A(c)EG（存在推广）：A(c)⇒∃xA(x)EI、UG注意约束条件（常考选择题陷阱）四、第3部分：集合与关系（分值最大）1.集合运算并∪、交∩、差−、补～、对称差⊕吸收律、结合律、交换律、分配律、德摩根律2.关系（A×A的子集）表示：集合、关系矩阵、有向图3.关系的性质（必考选择）自反、反自反对称、反对称传递快速判断：自反：主对角线全1对称：矩阵对称（rij​=rji​）传递：若

rij​=1∧rjk​=1⇒rik​=14.闭包（必考）r(R)：自反闭包（加主对角线1）s(R)：对称闭包（补对称位置）t(R)：传递闭包（R+，可用Warshall算法）5.等价关系（核心）满足：自反+对称+传递每个等价关系对应一个划分等价类：[a]={x∣xRa}商集：所有等价类的集合6.偏序关系（≤）满足：自反+反对称+传递哈斯图（去掉自环、箭头、传递边）概念：最大元、最小元、极大元、极小元、上界、下界、最小上界、最大下界7.函数满射（值域=陪域）单射（不同元像不同）双射（既单又满）复合函数、逆函数（仅双射可逆）五、第4部分：代数系统（背概念+判断）1.运算性质封闭、结合、交换、幂等、分配、吸收2.单位元、零元、逆元单位元e：唯一零元θ：唯一逆元：若可结合则逆元唯一3.代数系统层次（必考）广群：非空+封闭运算半群：封闭+

结合独异点：半群+

单位元群：独异点+

每个元素有逆元4.群的性质消去律阶：元素阶、群的阶子群判定：非空、封闭、有逆元（或

ab−1∈H）六、第5部分：图论（计算+证明+选择都考）1.基本概念无向图、有向图、顶点、边、环、重边、简单图、完全图、正则图、二部图2.握手定理（必考）无向图：∑v​d(v)=2m有向图：∑d+(v)=∑d−(v)=m推论：奇度顶点必有偶数个3.通路、回路、连通性连通图（任意两点可达）强连通/单向连通/弱连通（有向图）4.欧拉图（一笔画）无向欧拉图：连通+所有顶点度数为偶数有向欧拉图：弱连通+每个顶点入度=出度5.哈密顿图（考点多）无充分必要条件，只记充分/必要：必要：删顶点子集S，连通分支数≤|S|充分（Dirac）：n≥3，每个顶点度≥n/2⇒哈密顿图6.树（必考大题）无向树T（连通、无回路）等价定义：连通无回路n=m+1任意两点唯一通路连通，但删任意一边不连通无回路，但加任意一边有唯一回路生成树连通图必有生成树最小生成树MST：Kruskal（避圈，按权从小到大加边）Prim（选点，贪心扩展）7.有向树、根树根、叶、内点、层数、高二叉树：左孩子、右孩子完全二叉树、满二叉树七、最常考计算题（套路固定，必练）命题公式

真值表、判断类型求

主析取/主合取范式（必考）命题逻辑

构造证明（前提→结论）求关系的

自反/对称/传递闭包画

哈斯图，求最大元、极小元、上界用

握手定理

求顶点数/边数求

最小生成树（Kruskal/Prim）判断

欧拉图、求欧拉回路代数系统判断：半群、独异点、群八、最常考证明题（模板直接套）证明

等价关系：证自反、对称、传递证明

偏序关系：自反、反对称、传递证明

子群：封闭+逆元或

ab−1∈H证明

图是树：证连通+

n=m+1

或无回路+连通命题/谓词

推理证明：按规则一步步写九、考前10分钟极简速记（必背）A→B⟺¬A∨B主范式：极小项成真，极大项成假等价关系：自反+对称+传递⇨划分偏序：自反+反对称+传递