一、数理逻辑Mathematical Logic1.1 命题逻辑Propositional Logic命题能判断真假的陈述句。逻辑联结词联结词符号含义否定¬p非p合取p∧qp且q析取p∨qp或q蕴含p→q若p则q等价p↔qp当且仅当q重要公式德·摩根律¬(p∧q) ≡ ¬p∨¬q¬(p∨q) ≡ ¬p∧¬q蕴含等值式p→q ≡ ¬p∨q假言易位p→q ≡ ¬q→¬p范式析取范式DNF多个合取项的析取如 (p∧q)∨(¬p∧r)合取范式CNF多个析取项的合取如 (p∨q)∧(¬p∨r)主析取范式每个合取项包含所有命题变元1.2 谓词逻辑Predicate Logic基本概念个体词讨论对象常量、变量谓词描述个体性质或关系如 P(x)x是质数量词全称量词 ∀x对所有的x存在量词 ∃x存在某个x重要等价式¬∀x P(x) ≡ ∃x ¬P(x)¬∃x P(x) ≡ ∀x ¬P(x)∀x∀y P(x,y) ≡ ∀y∀x P(x,y)∃x∃y P(x,y) ≡ ∃y∃x P(x,y)∀x P(x) ∧ ∀x Q(x) ≡ ∀x (P(x)∧Q(x))∃x P(x) ∨ ∃x Q(x) ≡ ∃x (P(x)∨Q(x))二、集合论Set Theory2.1 基本概念集合具有某种特定性质的对象元素的总体。常见集合N自然数集Z整数集Q有理数集R实数集∅空集2.2 集合运算运算符号定义并集A∪B{x | x∈A 或 x∈B}交集A∩B{x | x∈A 且 x∈B}差集A−B{x | x∈A 且 x∉B}补集∁A{x | x∉A}相对全集U对称差A△B(A−B)∪(B−A)重要公式分配律A∩(B∪C) (A∩B)∪(A∩C)吸收律A∪(A∩B) A德·摩根律集合形式∁(A∩B)∁A∪∁B2.3 特殊集合幂集 P(A)A的所有子集构成的集合|P(A)| 2^|A|笛卡尔积A×B {(a,b) | a∈A, b∈B}三、关系Relation3.1 关系及其性质二元关系R ⊆ A×B即A到B的子集。关系的性质在A上的关系R性质定义符号自反∀a∈A, (a,a)∈R反自反∀a∈A, (a,a)∉R对称若(a,b)∈R则(b,a)∈R反对称若(a,b)∈R且(b,a)∈R则ab传递若(a,b)∈R且(b,c)∈R则(a,c)∈R等价关系同时满足自反、对称、传递的关系。偏序关系同时满足自反、反对称、传递的关系。全序关系满足偏序 任意两元素可比。3.2 哈斯图Hasse Diagram偏序关系的简化图示省略自反环和由传递性导出的边。3.3 关系的闭包闭包类型最小超集自反闭包R ∪ {(a,a) | a∈A}对称闭包R ∪ R⁻¹传递闭包R⁺R的传递扩张四、函数Function4.1 基本概念函数映射f: A→BA中每个元素在B中有唯一像。类型定义单射一对一若f(a₁)f(a₂)则a₁a₂满射映上∀b∈B, ∃a∈A使f(a)b双射既是单射又是满射4.2 复合函数与反函数复合函数(f∘g)(x) f(g(x))反函数若f是双射则存在f⁻¹: B→A满足f⁻¹(f(a))a五、图论Graph Theory5.1 基本概念图 G (V, E)顶点集V和边集E。类型说明无向图边无方向有向图边有方向简单图无重边、无自环多重图允许重边完全图 Kₙ任意两点均有边二部图顶点可分成两组边只跨组顶点的度无向图关联边的数目有向图入度指向该顶点的边 出度从该顶点出发的边握手定理∑deg(v) 2|E|5.2 路径与连通性路径顶点序列 v₀→v₁→...→vₖ相邻顶点间有边回路起点和终点相同的路径连通图任意两点间有路径强连通有向图任意两点间互相可达弱连通有向图忽略方向后连通5.3 特殊图欧拉图存在经过每条边恰好一次的回路。判定连通且所有顶点度数为偶数哈密顿图存在经过每个顶点恰好一次的回路。判定无简单充要条件需必要条件如割点、度数条件树连通且无回路的图。性质|E| |V| − 1生成树包含所有顶点的树最小生成树Kruskal算法、Prim算法5.4 图的矩阵表示邻接矩阵A[i][j] 1有边或0无边关联矩阵行顶点列边5.5 平面图能画在平面上使边不相交的图。欧拉公式v − e f 2连通平面图f为面数库拉托夫斯基定理K₅和K₃,₃是判断非平面图的关键六、树Tree6.1 有根树根唯一的顶层节点叶子度为1的非根节点内节点非叶节点深度根到节点的路径长度高度最大深度6.2 二叉树每个节点最多有两个子节点。满二叉树每节点有0或2个子节点完全二叉树除最后一层外全满最后一层左对齐遍历方式前序、中序、后序、层次6.3 最优二叉树霍夫曼树带权路径长度最小的二叉树用于数据压缩Huffman编码。七、组合数学Combinatorics7.1 计数原理乘法原理P m × n分步进行加法原理P m n分类进行容斥原理|A∪B| |A| |B| − |A∩B||A∪B∪C| |A||B||C| − |A∩B|−|A∩C|−|B∩C| |A∩B∩C|7.2 排列与组合场景公式排列从n取r有序P(n,r) n!/(n−r)!组合从n取r无序C(n,r) n!/[r!(n−r)!]圆排列首尾相连(n−1)!重复排列n^r多重集排列n!/(n₁!n₂!...nₖ!)组合恒等式C(n,r) C(n−1,r−1) C(n−1,r)7.3 生成排列和组合字典序法按字典顺序生成所有排列。组合的生成使用回溯法或递归。八、递推与生成函数8.1 递推关系递推关系用前项表示后项的等式。常见递推斐波那契Fₙ Fₙ₋₁ Fₙ₋₂一阶线性aₙ c aₙ₋₁ d线性齐次aₙ c₁aₙ₋₁ c₂aₙ₋₂ ... cₖaₙ₋ₖ8.2 求解递推特征方程法线性齐次写出特征方程 r^k − c₁r^{k−1} − ... − cₖ 0解出特征根得到通解形式生成函数法G(x) ∑aₙxⁿ普通生成函数利用生成函数求解递推九、代数结构Algebraic Structures9.1 基本概念结构定义半群非空集合S 满足结合律的二元运算幺半群半群 有单位元群幺半群 每个元素有逆元阿贝尔群满足交换律的群环有加法和乘法两种运算满足一定公理域满足更多公理的环如Q、R、C9.2 同态与同构同态保持运算的映射 f(a·b) f(a)*f(b)同构双射的同态十、经典算法与定理主题内容图的连通性DFS、BFS、Dijkstra最短路径、Floyd-Warshall最小生成树Kruskal并查集、Prim拓扑排序DAG的顶点线性排序匹配问题二分图最大匹配匈牙利算法网络流Ford-Fulkerson算法、最大流最小割定理