离散数学
适用场景
- 课程学习：计算机类、软件工程、信息安全、人工智能等专业本科《离散数学》的预习、复习与作业求解。
- 备课与教学：教师按教育部基本要求排课、设计教案与考核方案（四大板块：数理逻辑、集合论、代数结构、图论）。
- 证明训练：命题逻辑推理、关系性质、代数系统、图论性质的严格证明，以及数学归纳法等证明方法选择。
- 考研复习：计算机专业基础综合或自主命题专业课中离散数学相关考点的梳理与解题训练（具体考查范围以目标院校当年大纲为准）。
- 工程建模：把逻辑关系、网络拓扑、任务依赖（偏序）、权限集合、密码协议等抽象为离散结构并求解。
- 工具验算：用 Python（SymPy / NetworkX）验证手算的主范式、闭包、最小生成树、最短路、同余逆元。
核心知识框架
六个模块，对应国内主流教材四大板块并补充组合数学与初等数论：
- M1 数理逻辑：命题与五大联结词、真值表、永真/矛盾/可满足式、等值式（德·摩根等）、析取/合取范式与主析取/主合取范式、联结词完备集、自然推理系统 P（P/T/CP/归谬）、一阶逻辑符号化与量词否定等值式、前束范式。
- M2 集合论：集合运算与幂集 2ⁿ、笛卡尔积、容斥原理、二元关系性质（自反/对称/反对称/传递）、关系合成与闭包（Warshall 算法）、等价关系↔划分、偏序关系↔哈斯图、函数（单射/满射/双射）、基数与可数/不可数。
- M3 代数结构：二元运算性质、代数系统与同态同构、半群/独异点/群、群的基本性质与子群判定、循环群与置换群、环与域、格与布尔代数。
- M4 图论：图与矩阵表示、握手定理（Σd(v)=2|E|）、通路回路与连通、欧拉图（连通+全偶度）、哈密顿图（Dirac/Ore 充分条件）、树（m=n−1、Kruskal/Prim 最小生成树、Huffman）、平面图与欧拉公式（n−m+f=2）、二部图匹配（Hall 定理）、图着色（四色定理）。
- M5 组合数学：加法/乘法法则、排列组合、二项式定理与组合恒等式、递推方程（特征根法/生成函数）、Catalan 与 Stirling 数、鸽巢原理。
- M6 初等数论：整除与唯一分解、欧几里得算法、同余、费马小定理与欧拉定理、扩展欧几里得求模逆。
详细定义、公式、术语与标准对照见 references/uni-discrete-math-core.md。
标准作业流程（SOP）
十条流程，先按 SOP-0 判定题型（证明 / 计算 / 建模），再选对应步骤（完整版见 references/uni-discrete-math-sop.md）：
- SOP-0 题型判定：证明题看板块选 SOP-1/2/4/5/9；计算题选 SOP-3/6/7/8；建模题抽象为图/关系/代数系统。
- SOP-1 主范式：真值表法挑成真赋值得极小项析取；成假赋值得极大项合取；校验极小+极大=2ⁿ。
- SOP-2 自然推理证明：直接 / 附加前提(CP) / 归谬 / 消解四法，每步写清规则。
- SOP-3 关系与闭包：画关系图判性质；r/s 闭包补边；传递闭包用 Warshall 算法；等价↔划分，偏序↔哈斯图。
- SOP-4 群判定：封闭→结合→幺元→逆元四步；子群用 a∘b⁻¹∈H 判别法。
- SOP-5 欧拉/哈密顿图：欧拉查连通+全偶度；哈密顿优先 Dirac(δ≥n/2)/Ore，证非哈密顿用必要条件。
- SOP-6 树与最短路：Kruskal 避圈加边、Prim 扩点；Dijkstra 求最短路（权非负）。
- SOP-7 组合计数：分步用乘、分类用加、有"至少"用容斥、数列递推用特征根/生成函数。
- SOP-8 数论与模逆：欧几里得求 gcd，扩展欧几里得求 ax+by=gcd，互素时得模逆；费马/欧拉定理降幂。
- SOP-9/10 证明方法与工具：归纳法必验基例；Python(SymPy/NetworkX) 双验手算。
常见问题与排查
- Q：∀ 和 ∃ 顺序能换吗？ A：不能。∀x∃y P(x,y) 与 ∃y∀x P(x,y) 语义不同，符号化时逐层确认。
- Q：欧拉图和哈密顿图怎么区分？ A：欧拉图走遍每条边一次（无向要求全偶度）；哈密顿图走遍每个顶点一次（看度数充分条件）。
- Q：主析取和主合取搞反了？ A：主析取由极小项析取、对应成真赋值；主合取由极大项合取、对应成假赋值，二者互补。
- Q：全国统考数学考离散数学吗？ A：数一/数二/数三不考（只考高数、线代、概率统计）；它多见于计算机专业课，以目标院校当年大纲为准（需人工核实）。
- Q：判定群最容易漏哪步？ A：封闭性最常被忽略，其次是逆元；四步（封闭/结合/幺元/逆元）必须全查。
十六条高频错误对照表（量词顺序、否前件、主范式混淆、漏闭包边、忘传递性、漏封闭、子群判别式、欧拉/哈密顿混淆、树边数、欧拉公式漏外表面、容斥符号、鸽巢取整、归纳漏基例、"显然"无依据、同余逆元前提）见 references/uni-discrete-math-cases.md 第三节。
输出模板
解答一道离散数学题时，按此结构输出：
【题型】证明 / 计算 / 建模
【所用模块】M1–M6 之一
【步骤】
1. ……
2. ……（每步标注规则/定理）
【结果】……
【验算】用真值表 / 矩阵 / 工具 / 代回原式 复核
【注意】易错点提示
参考来源（MLA 格式）
- 屈婉玲、耿素云、张立昂。《离散数学（第2版）》。高等教育出版社，2015。ISBN 978-7-04-041908-5。
- 屈婉玲、曹永知、耿素云、张立昂。《离散数学及其应用（第3版）》。高等教育出版社，2026。ISBN 978-7-04-067723-2。
- 教育部高等学校计算机类专业教学指导委员会。《计算机类教学质量国家标准》。2018（附录核心课程体系）。
- 北方工业大学教务处。《离散数学Ⅰ 课程教学大纲》。jwc.ncut.edu.cn，2022-01。
- 西安电子科技大学。《离散数学 教学大纲》。ce.xidian.edu.cn。
- 国家高等教育智慧教育平台（武汉理工大学）。《离散结构》课程大纲。higher.smartedu.cn，2026。
- ACM/IEEE-CS。Computer Science Curricula 2023。Discrete Structures (DS) 知识领域说明。curricula.cs.luc.edu。
- Kenneth H. Rosen（袁崇义、屈婉玲等译）。《离散数学及其应用（原书第 7 版）》。机械工业出版社，2020。ISBN 978-7-11-164217-6。
