1. 数理逻辑（基础工具）

核心是命题逻辑与谓词逻辑（一阶逻辑）。

 核心公式：德·摩根律（¬(P∧Q)=¬P∨¬Q）、蕴含等值式（P→Q = ¬P∨Q）。

考点：求前束范式、主析取/合取范式，以及推理证明（假言推理、反证法）。

易错：量词辖域扩张时注意变元是否自由，换名规则要牢记。

 

2. 集合论与关系（抽象核心）

包含集合运算、关系性质与函数。

关系性质：自反（有环）、反自反（无环）、对称（双向）、反对称（单向）、传递（连锁）。

 两大重难点：等价关系（对应集合划分）与偏序关系（哈斯图找极大/小元、上/下确界）。

考点：关系的复合运算、闭包求法（自反闭包r(R)=R∪IA）。

 

3. 代数系统（结构视角）

研究运算的封闭性、结合律、幺元（单位元）和逆元。

 群论阶梯：半群 → 含幺半群 → 群 → 阿贝尔群（交换群）。

 核心定理：群中消去律成立；子群判定需“非空+封闭+逆元”。

 考点：判断给定集合和运算是否构成群，以及循环群的生成元。

 

4. 图论（重头戏，分值高）

研究顶点与边的连通关系。

必记公式：握手定理（所有顶点度数之和 = 2×边数），推论是奇度顶点必有偶数个。

 经典区分：欧拉图（一笔画，无奇度顶点）vs 哈密顿图（经过所有顶点一次，必要不充分条件）。

树：n个顶点连通无环，必有 n-1 条边；最小生成树用 Kruskal（加边） 或 Prim（加点） 算法。

考点：判断是否为二部图（无奇环）、平面图（欧拉公式 v - e + r = 2）。

 

5. 组合数学（计数技术）

两大原理：加法原理（分类）与乘法原理（分步）。

核心工具：容斥原理（求交集补集）、鸽巢原理（抽屉原理，最不利原则）。

递推：常考错排问题（Dn=(n-1)(Dn-1+Dn-2)）和斐波那契数列。

 

6. 初等数论（算法根源）

 核心：整除、同余（模运算）、最大公约数（辗转相除法）。

考点：求逆元（扩展欧几里得算法）、中国剩余定理（一次同余方程组）。