离散数学-知识梳理

离散数学-知识梳理，便于理解课本，有助于期末考试复习和背诵。可收藏，亦可使用后补充知识点，完善属于自己的知识框架。

离散数学-知识梳理

• 树部分
  • 树的基本理论
    • 定义：树是没有简单回路的连通无向图（一定是简单图）
      • 定理：一个无向图是树 当且仅当 它的每对顶点之间存在唯一简单通路
    • 森林：不含简单回路但不连通的图
    • 根：指定树的某个顶点为特殊顶点，称为根
      • 有根树：指定每条边的方向为离开根的方向生成的有向图，称为有根树
      • 父母/孩子/兄弟
      • 树叶：没有孩子的顶点
      • 内点：有孩子的顶点
    • 二叉树
    • 有序根树
      • 有序二叉树可以分为左子树和右子树
      • 有序树可以被递归定义
    • 平衡m叉树
      • 层数/高度：从根到任意顶点的最长通路的长度
      • 定义：高度为h的m叉树的所有树叶都在最下两层，则这棵树是平衡的
  • 树的性质
    • 带有n个顶点的树含有n-1条边【证明：数学归纳法】
    • 带有i个内点的满m叉树含有n=mi+1个顶点【满m叉树得顶点数、内点数、叶子数具有知一求二的性质】
      • 【以下定理证明基于：n=mi+1；n=i+l】
      • 已知顶点数n：i=(n-1)/m 个内点；l=[(m-1)n+1]/m 个树叶
      • 已知内点数i：n=mi+1 个顶点；l=(m-1)i+1 个树叶
      • 已知树叶数l：n=(ml-1)/(m-1) 个顶点；i=(l-1)/(m-1)个内点
    • 在高度为h的m叉树中至多有m^h个树叶【证明：数学归纳法-小于满m叉树】
  • 树的应用
    • 二叉搜索树：二分查找法
    • 前缀码
      • ？定义：用变长的位数来给字母编码，需要保证一个字母的比特串永远不出现在另一个字母比特串的开头部分，这样的编码被称为前缀码。
      • 作用：较短的比特串用来编码出现频繁的字母，而较长的用来编码不经常出现的字母，达到节省存储空间的目的。
      • 构造方法：用二叉树表示前缀码
        • 左0右1：通向左子树的边标记为0，通向右子树的边标记为1
        • 单向延申：树叶全部位于左子，右子除了最后的叶子全部用于延申树
        • 从根解码：读出根到终点的的结点的路径即为所求前缀码
    • 哈夫曼编码
      • 定义：该算法用一个字符串中符号的出现频率（用这个符号出现的次数除以这个字符串的长度）作为输入，产生一个这个 字符串的一个前缀码作为输出。
      • 作用：产出占用位数最少的前缀码编码树，是数据压缩中的基础算法。该算法是贪心算法。
      • 构造方法
        • 1. 给定符号及其频率，把所有符号作为顶点和频率作的顶点的权构成一个森林
        • 2. 把具有最小总权值的树合成一个新树，引入一个新根，根结点的权值为两个子树的权值和，其中权值大的树作为左子树，权值小的树作为右子树
        • 3. 重复上述步骤，直至森林缩小为单个树
  • 树的遍历：注意遍历方式和X缀表示法的关系
    • 前序遍历
    • 中序遍历
    • 后序遍历
  • 生成树
    • 定义：G是简单图，G的生成树是包含G的每个顶点的G的子图
      • 定理：简单图是连通的 当且仅当 它有生成树
    • ？构造生成树【数据结构图论中已经写过代码】
      • 深度优先搜索/回溯
      • 宽度/广度优先搜索
    • 最小生成树
      • 定义：连通加权图里的最小生成树是具有边的权之和最小的生成树
      • 构造方法
        • 普林（Prim）算法
          • 1. 选择图中权最小的边添加到树中
          • 2. 添加与已在树中顶点关联的且不会形成简单回路的权最小的边
          • 3. 已经添加了n-1条边时就停止
        • 克鲁斯卡尔算法
          • 1. 选择图中权最小的边添加到树中
          • 2. 添加不会形成简单回路的权最小的边（没有要求和树中顶点相连）
          • 3. 已经添加了n-1条边时就停止
• 图论部分
  • 理论知识
    • 图的基础理论
      • 图的分类
        • 按顶点集大小
          • 有限图
          • 无限图
        • 按边的重数
          • 简单图：没有两条不同的边连接一对相同的顶点（默认是无向图）
          • 多重图
          • 伪图：包含环（连接同一顶点的边）或多重边的图
        • 按边的方向
          • 有向图
          • 无向图
          • 混合图
        • 特殊的图
          • 完全图 Kn：每对不同顶点之间都有一条边的简单图
          • 圈图 Cn：围成一个圈的简单图
          • 轮图 Wn：圈图中间加一个点并与圈上各点相连
          • n立方体图 Qn
      • 基础术语
        • 邻接/相邻：顶点与顶点的关系
        • 关联/连接：顶点与边的关系
        • 邻居 N(v)：具有相邻关系的所有顶点的集合
        • 度 deg(v)：与该顶点相关联的边的数目
          • 对有向图分为出度deg+(v)和入度deg-(v)两种
          • 顶点上的环对顶点的度作出双倍贡献（2）
          • 孤立点：度为0的点
          • 悬挂点：度为1的点
      • 握手定理：顶点的度之和为边数的两倍
        • 无向图中有偶数个度为奇数的顶点
        • 有向图中入度=出度=边数
    • 图的表示
      • 邻接表：表头为所有顶点，表体为与该顶点相邻的所有顶点（从该点出发的边的终点）
      • 邻接矩阵：表示有无边相连的01矩阵（横看发射，竖看接收）
        • 无向图的邻接矩阵是对称的
        • 伪图也可以用邻接矩阵来表示：不再是01矩阵，每项代表两个顶点之间边的条数
        • 邻接表适合稀疏图（边较少），邻接矩阵适合稠密图
      • 关联矩阵：纵轴为顶点，横轴为边的01矩阵，当二者有关联时取1
    • 图的同构
      • 定义：G1与G2的点集存在双射关系f，且f满足a,b在G1中相邻 当且仅当 f(a)与f(b)在G2中也相邻（对应点相邻），则称G1与G2同构
      • 图形不变量：在图的同构中保持不变的属性，判断不同构的关键
        • 顶点数/边数
        • 对应顶点的度
        • 长度为k的简单回路的存在性
      • 判断同构：构造一个双射关系f（找对应点）
    • 图的连通性
      • 通路：一系列边的序列
        • 回路（圈）：在相同顶点开始和结束且长度大于0的通路【区分环的定义】
        • 简单通路/回路：不重复地包含相同的边的通路或回路
        • 路长：通路中经过的边的数量（顶点数-1）
        • 计算通路数：vi到vj的长度为r的不同通路数目等于图的邻接矩阵A的r次幂的第(i,j)项的值
      • 连通性
        • 无向图
        • 有向图
          • 强连通：任意一对顶点a,b都有a到b和b到a的边
          • 弱连通：有向图的基本无向图（去掉箭头的有向图）是连通的
        • 连通分支
          • 割点：删除该顶点和它所关联的边就破坏了图的连通性（产生更多连通分支）
            • 不含割点的连通图称为不可分割图（如完全图Kn）
            • 点割集/分割集：删除这个集合中的所有点后图的连通性被破坏
            • 点连通度：非完全图的点连通度为点割集的最小顶点数，记作k(G)。k(G)越大就认为G的连通性越好。
            • 若k(G)>=k则称G是k连通的
          • 割边：删除该边就破坏了图的连通性
            • 边连通度：与点连通度的定义类似，也具有相似的概念，记作λ(G)
            • 不等式：k(G)<=λ(G)<=min{deg(v)}
    • 二分图/偶图
      • 定义：将简单图G的顶点分成两个不相交的非空集合V1，V2使得图中的所有边都从V1的一个顶点连接V2的一个顶点。（V1，V2）称为顶点集的一个二部划分
      • 判定充要条件：图的着色数为2
      • 完全二分图：两个划分中每个顶点都对各自有边，记作Km,n
      • 应用：匹配问题
        • 匹配（M）：二分图中边的子集，要求在子集中没有两条边关联相同的顶点（即每个顶点至多只有一条边相连）。若顶点在匹配中有边相连，则称被匹配。
        • 最大匹配：含有最多边数的一个匹配称为最大匹配
        • 完全匹配：若V1中每个顶点都是匹配中边的端点（或|M|=|V1|），则称匹配M时从V1到V2的完全匹配
        • 霍尔婚姻定理：完全匹配的充要条件
          • 定理：二分图G中有一个V1到V2的完全匹配 当且仅当 对V1的所有子集A有|N(A)|>=|A|（其中N(A)表示A所有相邻点的集合）
    • 欧拉图
      • 欧拉回路：包含每一条边的简单回路
        • 充要条件：含有至少2个顶点的连通多重图具有欧拉回路 当且仅当 它的每个顶点的度都为偶数
      • 欧拉通路：包含每一条边的简单通路
        • 充要条件：连接多重图具有欧拉通路但无欧拉回路 当且仅当 它恰有2个度为奇数的顶点
    • 哈密顿图
      • 哈密顿回路：经过G中每个顶点恰好一次的简单回路
        • 没有已知的充要条件判断哈密顿回路
        • 充分条件
          • 带有度为1的顶点的图没有哈密顿回路
          • 狄拉克定理：G是n个顶点的简单图，且n>=3，若G中每个顶点的度都至少为n/2，则G有哈密顿回路
          • 欧尔定理：G是n个顶点的简单图，n>=3，若G中每一对不相邻的顶点u、v来说，都有deg(u)+deg(v)>=n，则G有哈密顿回路
          • 狄拉克定理是欧尔定理的推论
          • 满足上述两定理可以判定有哈密顿图，但不满足不一定没有哈密顿回路
      • 哈密顿通路：经过G中每个顶点恰好一次的简单通路
    • 最短通路问题
      • 加权图：每条边赋上一个数的图
      • 狄克斯特拉算法 【构造最短通路】
        • 1. 用0标注起点，∞标注其他点，并把起点纳入点集S
        • 2. 检索与点集内所有点相邻的所有点，找出从起点到这些点的路径并算出路径长度（可以借助对点集内点的标记值来快速计算）
        • 3. 得到路径最短的一个点，用这个最短路径值标记这个点并将这个点纳入点集S
        • 4. 重复上述步骤，直到把所求终点也纳入点集
        • 当这个过程持续到所有顶点都加入在点集中就可以求出a到所有顶点的最短通路的长度
      • TSP（旅行商）问题：弗洛伊德算法【求最短通路长度；不能构造】
    • 平面图问题
      • 定义：若可以在平面中画出一个图而边没有任何交叉，则这个图是平面图。这种画法被称为这个图的平面表示。
      • 欧拉公式：G是带e条边和v个顶点的连通平面简单图，设r是G的平面图表示中被分割出的面数，则满足r=e-v+2 【？证明】
        • 欧拉公式证明一个图的所有平面表示都把平面分成相同数目的面，其中包括一个无界的面
        • 推论1：若G是连通平面简单图且v>=3，则e<=3v-6（证明K5不是平面图）
          • Kn 当 n>=5 时都不是平面图
        • 推论2：若G是连通平面简单图，则G中有度数不超过5的顶点
        • 推论3：若G为连通平面简单图且v>=3，且没有长度为3的回路，则e<=2v-4（证明K3,3不是平面图）
      • 库拉图斯基定理：若一个图包含同胚于K3,3或K5的子图，则这个图一定不是平面图
        • 前提：K3,3和K5不是平面图（用欧拉公式推论证明）
        • 初等细分：删除一条边<u,v>且添加一个新顶点w和两条新边<u,w>,<w,v>【翻译：在一条边上加一个顶点】，这是一个构造新图的操作
        • 同胚：若两个图可以从相同的图经过一系列初等细分得到，则称这两个图同胚
    • 图着色问题
      • 图的着色数：着色一个图所需要的最少颜色数，记作x(G)
      • 四色定理：平面图的着色数不超过4
      • 完全图Kn的着色数：x(Kn)=n
      • 二分图的着色数：x(Km,n)=2
  • 题型
    • 基本概念考察
    • 欧拉图和哈密顿图的判断和构造
    • 二分图和匹配的判断和应用
    • 平面图
      • 判断平面图
      • 着色问题
    • 最短通路问题
      • 构造最短通路：狄克算法
      • 求最短通路长度：弗洛伊德算法
    • 图的邻接矩阵
      • 计算邻接矩阵
      • 利用邻接矩阵分析图特征
    • 图的同构判断
• 关系部分
  • 关系的概念
    • 笛卡尔积：A x B定义为A与B的笛卡尔积，其为有序对（a,b）构成的集合，a属于A且b属于B
    • 二元关系：有序对组成的集合，是A与B笛卡尔积的子集，用记号aRb表示有序对(a,b)满足关系R
    • 函数与关系：函数是一种特殊的关系
    • 集合的关系：集合与自身的关系是自身和自身的笛卡尔积的子集
    • 逆关系：有序对反序的关系
      • 两次求逆等于自身
      • 转置和求逆可以互换顺序
      • 不满足德摩根律
  • 关系的性质
    • 自反性：对于所有元素均有aRa
    • 对称性：若aRb存在，则bRa一定存在
    • 反对称性：只有在两个元素相等时才能满足aRb存在时bRa也存在【对称与反对称的概念不是对立的，可以同时具有或同时不具有】
    • 传递性：若aRb，bRc，则有aRc
  • 关系的组合
    • 交并补差
    • 关系的合成（复合关系）
      • 定义：已知aRb、bSc，R与S的合成使有序对（a，c）组成的集合，要求a∈A，c∈C且存在b∈B使aRb，bSc
      • 与函数合成的区别：没有要求前一个的值域必须是后一个定义域的子集，只需要存在特定元素满足条件即可（定义域不要求占满）
      • 构造方法：画图，只看起点和终点
      • 关系的幂运算：递归地定义R的n次幂为R的n次组合到自身
        • 关系R满足传递性 当且仅当 R^n是R的子集（n=1,2,3...）
  • 关系的表示
    • 关系矩阵：ai与bj有关系时关系矩阵的（i，j）项为1，否则为0
      • 表示定义在一个集合上的关系的矩阵式一个方阵
      • 方阵的主对角线上所有元素都等于1，则R是自反的
      • 方阵关于主对角线对称，则R是对称的
      • 方阵关于主对角线对称的位置不同时出现1，则R是反对称的
      • 关系合成的矩阵
        • 布尔积：用矩阵乘法法则做且运算
        • 合成关系的矩阵等于原关系的布尔积，也适用于关系幂的计算
    • 关系图：每个元素看成点，每个有序对看成一条带有箭头的弧，自身到自身的弧用环来表示
      • 每个顶点都有环，则R是自反的
      • 每一条边都存在同顶点的方向相反的边，则R是对称的
      • 图中不存在两条方向相反的边，则R是反对称的
      • 图中不存在不能构成三角形的三条连续边，则R是传递的
  • 关系的闭包
    • 定义：集合上包含R的，具有性质P的最小关系S（所有A上的具有性质P的关系都包含S）
    • 分类
      • 自反闭包 r（R）
        • 求法：R ∪ 对角关系
      • 对称闭包 s（R）
        • 求法：R ∪ R的逆关系
      • 传递闭包 t（R）
        • 路径：一系列边的序列；在同一点开始和结束的长度大于等于1的路径称为回路或圈
        • 定理：R为集合A上的关系，从a到b存在一条长为n的路径 当且仅当（a,b）∈R^n【翻译：R的n次幂相当于关系图中所有长为n的路径连接的起点和终点的有序对的集合】
        • 连通性关系：关系图中所有路径的总和（R*是所有R^n的并集）
          • 关系Ｒ的传递闭包等于连通性关系R*
        • 关系R定义在有n个元素的集合上，则若（a,b）∈R，则a,b间的路径最长为n（若a≠b，则最长路径为n-1）【意义：限制检测路径长度的范围，使之可以计算】
        • 求传递闭包的算法
          • 关系矩阵乘法：R*的关系矩阵=所有R^n的关系矩阵的并
          • 沃舍尔算法
            • 内部顶点：路径中除了起点和终点外的所有顶点
            • 计算方法：采用递推的方法利用上一个矩阵求下一个矩阵，第一个矩阵W0为R的关系矩阵，最后一个矩阵Wn为R的连通性关系（传递闭包）
              • 下缀n为当前结果中路径的最大内点数
              • 继承型：存在一条vi到vj的且内部顶点在k-1个顶点中的路径（Wk-1矩阵中对应值已经为1）
              • 中转型：新增的顶点vk使存在vi到vk和vk到vj的且这两条路径的内部顶点在前k-1个顶点中（Wk-1矩阵中这个新增元素有对应射入和射出）
              • 算法：wij(k)=wij(k-1)∪(wik(k-1)∩wkj(k-1))
  • 等价关系/类
    • 等价关系：同时具有自反性、对称性、传递性的关系
      • 满足等价关系的元素往往具有某些共同的性质
      • 最广泛使用的等价关系是模m同余关系
    • 等价类：R是定义在A上的等价关系，与A中一个元素有关系的所有元素的集合叫做a的等价类，记作[a]R或[a]
      • 代表元：一个等价类的任何元素都可以作为这个类的代表元
    • 集合的划分：不相交的非空子集且所有子集的并集为自身的集合（本质：集合的集合）
      • 设R是定义在集合A上的一个等价关系，R的所有等价类的并集就是集合A
      • a∈A有a属于且仅属于一个等价类 等价于 不同等价类没有交集
      • 等价类构成划分：可用集合的每个划分来构成等价关系，两个元素满足等价 当且仅当 它们在划分的同一子集中
      • 划分和等价关系/等价类有一一对应关系
  • 偏序关系：同时具有自反、反对称、传递性的关系
    • 偏序集：集合S与定义在其上的偏序关系R一起称为偏序集（S,R）
    • 全序：当S中每对元素都是可比的，则S称为全序集或线序集/链，R为全序或线序
      • 良序：全序且S的每个非空子集都有一个最小元素，则称S为良序集（有下限非无限）
      • 良序归纳原理：从整个集合的最小元素开始递推证明命题（类似数学归纳法）
    • 哈塞图：移除偏序关系中默认存在的边的最简图
      • 画法
        • 移除自反关系产生的环
        • 移除传递边（跨点边）
        • 确定一个方向，让所有边都满足这个方向，然后移除箭头
      • 覆盖关系：若x<y且不存在z满足x<z<y，则y覆盖x，所有满足覆盖的(x,y)有序对称为(S,<=)的覆盖关系
        • 哈塞图中指向上面的边与覆盖关系中的有序对相对应【哈塞图就是覆盖关系的表示】
        • 覆盖关系可以还原偏序集：偏序集为覆盖关系的传递闭包的自反闭包
    • 极大元/极小元
      • 极大/小元：不小/大于这个偏序集的任何其他元素
        • 极大元和极小元都可以有多个，它们对应图上的最高/最低层级，而同层可以有多个结点
      • 最大/小元：大/小于每个其他元素的元素
        • 最大元和最小元若存在则一定是唯一的
      • 上/下界：找到一个元素大/小于或等于偏序集的子集A中的所有元素，这个元素称为A的一个上/下界
        • 上下界可以不是唯一的
        • 必须指定一个子集才能确定上下界
      • 最小上界/最大下界：若存在则唯一
        • 判断：主要看有没有同级
      • 格：每对元素都有最小上界和最大下界的偏序集
      • ？拓补排序
• 逻辑和证明部分
  • 命题逻辑题型
    • 命题符号化问题
      • 用命题变量来表示原子命题
      • 用命题联结词来表示连词
    • 命题公式的类型判断
      • 利用真值表判断
      • 利用已知的公式进行推理判断
      • 利用主析取和合取范式判断
        • 定理：A为含有n个命题变元的命题公式，若A的主析取范式含有2^n个极小项，则A为重言式，若极小项在0到2^n之间，则为可满足式，若含有0个极小项，则A为矛盾式；若A的主合取范式含有2^n个极大项，则A为矛盾式，若极小项在0到2^n之间，则为可满足式，若含有0个极小项，则A为重言式
        • 翻译：一个命题公式化成主范式后，若所有项都分布在主析取范式中（主合取范式为1）则为重言式；若所有项都分布在主合取范式中（主析取范式为0）则为矛盾式；若均有分布，则为可满足式。【思想来源：真值表法求主范式】
        • 一个质析取式是重言式的充要条件是其同时含有某个命题变元及其否定式；一个质合取式是矛盾式的充要条件是其同时含有某个命题变元及其否定式
        • 一个析取范式是矛盾式当且仅当它的每项都是矛盾式；一个合取范式是重言式当且仅当它的每项都是重言式
    • 求（主）析取或合取范式
      • 等值演算法
        • 1. 利用条件恒等式消除条件（蕴含和双条件）联结词，化简得到一个范式
        • 2. 在缺项的质项中不改变真值地添加所缺项，化简得到一个主范式
        • 3. 找出包含所有命题变元排列中剩余项，凑出另一个主范式（思想上类似于真值表法）
      • 真值表法
        • 1. 画出命题公式真值表
        • 2. 根据真值表结果求出主范式
          • 主析取范式：真值为1的所有项，每一项按对应01构成极小项
          • 主合取范式：真值为0的所有项，每一项按对应01构成极大项
    • 形式证明与命题推理
      • 形式证明：命题逻辑的论证是一个命题公式的序列，其中每个公式或者是前提，或者是由它之前的公式作为前提推得的结论，序列的最后一个是待证的结论，这样的论证也称为形式证明。
      • 核心方法
        • 把非条件语句全部转为条件语句
        • 利用条件的逆否命题和双条件的拆分
        • 利用重言式/矛盾式来不改变真值地添项
        • 蕴含证明规则：A1,A2, …, An⇒ A → B 等价于A1,A2, …, An,A⇒ B【意义：使用结论的前提时应标为附加前提】（适用：结论为条件语句）
        • 反证法：若要证A1,A2, …, An⇒ B，将ØB加入前提，通过证明：A1,A2, …, An, ØB⇒ C, ØC完成证明。（适用：结论仅单命题）
    • ？根据已知命题构造满足一定真值组合条件的命题表达式
    • 真值表的应用
  • 谓词逻辑题型
    • 涉及谓词的命题符号化问题
      • 特性谓词
      • 存在量词/全称量词
    • 判断谓词公式的真值/谓词公式关系式对错判断
      • 对于一个谓词逻辑公式，给每个谓词符号指定一个具体谓词，每个自由变量取定其个体域中的个体，称为这个谓词逻辑公式的一个解释。一个谓词逻辑公式，如果它在每个解释的真值均为真，则称其为永真式。
      • A≡ B当且仅当A↔B为永真式；；A⇒B当且仅当A→B为永真式。
    • 谓词逻辑推理证明的检错和纠错
      • 推理规则（将量词去掉，将谓词逻辑的推理化作命题逻辑的推理）
        • 全称示例US：∀xA(x) ⇒A(x)
        • 全称生成UG：A(x)⇒ ∀xA(x)
        • 存在示例ES：∃xA(x) ⇒A(c) （c为特定解释）
        • 存在生成EG：A(c)⇒ ∃xA(x)
  • 基础知识
    • 逻辑运算符/联结词
      • 合取（Conjunction）：交集，且运算
      • 析取（Disjunction）：并集，或运算
      • 异或
      • 否定/非
      • 条件
      • 双条件
    • 命题公式分类
      • 重言式/永真式
        • 命题公式的逻辑等价
        • 命题公式的蕴含关系
      • 矛盾式
      • 可满足式/可能式
    • 范式（Normal Form）【判断：看最外层的运算符】
      • 原子命题：不能继续拆分的命题（包括否命题）
      • 质XX式
        • 质合取式：若干原子命题的合取
        • 质析取式：若干原子命题的析取
      • XX范式
        • 析取范式：质合取式的析取
        • 合取范式：质析取式的合取
        • 主范式
          • 最小项：包含所有项的合取式
          • 最大项：包含所有项的析取式
          • 主析取范式：每项质合取式都是最小项
          • 主合取范式：每项质析取式都是最大项
    • 命题运算律
      • 交换律
      • 结合律
      • 分配律
        • p∨ (q∧r) ≡ (p ∨q) ∧(p ∨r)
        • p∧(q ∨r) ≡ (p ∧q) ∨(p ∧r)
      • p→ q≡ ¬p∨ q
      • p↔ q≡ (p ∧ q)∨ (¬p∧ ¬q)
    • 推理规则
      • 假言推理：p → q, p ⇒ q
      • 取拒式：p → q, Øq ⇒ Øp
      • 假言三段论：p → q, q→ r ⇒ p → r
      • 析取三段论：p ∨ q, Øp ⇒ q
      • 附加律：p ⇒ p ∨ q
      • 化简律：p ∧ q ⇒ p
      • 合取律：p, q⇒ p ∧ q
      • 消解律：p ∨ q, Øp ∨ r ⇒ q ∨ r
    • 谓词和量词
      • 与函数对比：y=f(x)
        • 谓词：定义运算关系f
        • 量词：定义x取值范围（论域）
        • 二者共同决定真值y
        • 由上述元素构成命题函数
      • 量词种类
        • 全称量词
        • 特称量词/存在量词
        • 唯一性量词
      • 命题函数表示方式
        • 大写字母表示谓词
        • 小写字母表示个体（命题函数中个体出现的次序很重要）
      • 论域与特性谓词
        • 引入特性谓词来代替论域声明
        • 特性谓词和普通谓词应用不同的字母体系来表示
        • 特性谓词表示方式
          • ∀xP(x) ⇝ ∀x(A(x)→ P(x))
          • ∃xP(x) ⇝ ∃x(A(x)∧ P(x))
• 集合部分
  • 集合关系判断和证明
    • 包含
    • 相等
  • 集合运算
    • 幂集
    • 交并补
    • 差集
  • 集合的划分：详见关系中等价类部分
  • 集合的基数
    • 概念
      • 基数：描述集合大小的量，在有限集中等于集合元素的个数，记作|A|
      • 无限集的大小比较
        • 无限集A与B有相同的基数（大小相同） 当且仅当 存在从A到B的双射（一一对应）
        • 若存在A到B的内射（一对一），则有|A|<=|B|；且当A与B有不同的基数时|A|<|B|
    • 可数集的判断
      • 阿里夫零：定义自然数集的基数为阿里夫零
      • 和自然数集具有相同的基数的无限集是可数的，基数为阿里夫零
      • 证明方法：和自然数集构造一个双射函数
    • ？不可数集的证明
• 函数部分
  • 函数的概念
    • 定义：F:A→B 相当于对A的每个元素恰好唯一指派B的一个元素，又称映射或变换【一个自变量不能对应多个因变量，反之可以】
      • 定义域：A
      • 陪域：B【注意不是值域，因为B中可能没有满射】
    • 像：定义域中元素经变换后在值域中对应的元素
      • 值域：A中元素的所有像的集合
    • 原像：变换前在定义域中的元素
  • 函数的性质
    • 单射/一对一/入射/内射（one-to-one/injection） ：对任意f(a)=f(b)有a=b，即单调性（一个因变量不能对应多个自变量，即不存在多箭头）
      • 递增/递减：定义域和陪域都是实数集子集
      • 严格递增/递减
      • 证明方法
        • 1. 令f(a)=f(b)推出a=b，证明不成立则反之
        • 2. 严格单增/单减的函数一定是单射函数
    • 满射/映上（onto/surjection）：一个函数是满射 当且仅当 对每个b有a使得f(a)=b，即B被射满（陪域和值域相等）
      • 证明方法：设任意元素b属于B，通过b=f(a)导出a，并证明a属于A，证明不成立则在B中找到一个无法在A中找到原像的元素
    • 双射/一一对应（one-tone correspondence/bijection）：既是单射又是满射，即A中元素和B中元素一一对应
  • 复杂函数
    • 反函数
      • 前提条件：f:A→B为双射函数，故一一对应关系被称为可逆的(invertible)
    • 函数合成/复合函数
      • 符号顺序：从左到右为定义域的传递，即最外层在最左侧
      • 前提条件：传递过程中前一个函数的值域一定包含于后一个函数的定义域（子集关系）
    • 恒等函数
  • 函数的应用
• 组合计数
  • 鸽笼原理
    • 定义
      • 如果k+1或更多的物体放入k个盒子，那么至少有一个盒子包含了2个或更多的物体，鸽巢原理又被称为狄利克雷抽屉原理
    • 推论
      • 一个从有k+1或更多个元素的集合到k个元素的集合的函数f一定不是一对一函数（单射/内射: 单调性即一个自变量只对应一个因变量）
      • 广义鸽巢原理：如果N个物体放入k个盒子，那么至少有一个盒子包含了至少N/k（向上取整）个物体
        • 应用：搞清球-盒子模型中谁是球（需要推出重复），谁是盒子
          • 把若干物体分到k个盒子中使某个盒子至少有r个物体，至少需要 k(r-1)+1 个物体
            • 1. 先把k个盒子每个都装上r-1个物体
            • 2. 给任意一个盒子放入一个物体
      • 每个由n^2+1个不同实数构成的序列都包含一个长为n+1的严格递增子序列或严格递减子序列
    • Ramsey（拉姆齐）数：R(m,n)
      • 引例：朋友敌人问题
        • 若6个人两两之间不是敌人就是朋友，证明至少有3个人彼此是朋友或敌人
          • 先用鸽巢原理说明确定一个人的情况下至少有3个人是朋友或敌人
          • 然后对3个人的那个分类分情况讨论
      • 定义：要保证图包含子图Km或其补图包含子图Kn，顶点数至少为R(m,n)
      • 已知：R(3,3)=6, R(2,n)=n, R(4,4)=18
        • 目前只知道9个拉姆齐数的精确值
    • 例题：第七版
      • P340 例9：服务器连接
      • P341 例10：比赛分配
      • P341 例11：整除
  • 排列组合
    • 无重复的排列组合
      • 排列：m个物体有序地放入n个空位中，记作 A(m,n)
        • 公式：A(m,n)=P(m,n)=m!/(m-n)!
      • 组合：m个物体无序地放入n个空位中，记作 C(m,n)
        • 公式：C(m,n) = A(m,n)/n! = m!/n!(m-n)!
        • 另一个记号：x可以不是整数
      • 记号记忆：
        • 横式大数在前
        • 括号竖式大数在上（物体数）
        • 字母竖式大数在下
    • 有重复的排列组合
      • 本质：依然是n个选择，r个空位，但不要求 n>=r（可以重复）
      • 有重复的排列
        • 物体都不同：n^r（依然从空位的角度思考）
        • 具有不可区别的物体（分组）的排列：把n个不同的球分为k类的全排列数，每类有ni个球
          • 组合证明：依次无序取ni个球
      • 有重复的组合：从选项的角度思考（空位填到选项箱子里）
        • 理解：把空位和选项箱子内边界摆在一起都算待填的空，再填这些空
        • 公式：C(n+r-1, n-1) = C(n+r-1, r) 【把空位填到箱子里】【方法1】
        • 其他理解形式
          • 方程形式：x1+x2+x3+...+xn = r 的非负整数解的个数
            • 理解：把1当作球，有x1、x2...xn这n种的"1"球选择，有r个空位可以放入这些球
            • 拓展：给xi添加下界和上界 如 a<=xi<=b
              • 处理下界侧：换元 yi = xi - a 即可还原默认条件 yi >= 0
              • 处理上界侧：去掉 xi >= b 的情况
              • 多个变量下界可以一起处理，但上界一次只能处理一个
          • 反向理解：r个相同的球放入n个不同的盒子
    • 应用
      • 依然是球-盒子模型（或者说n选项-r空位模型），搞清谁是球谁是盒子，能不能重复选取即可
    • 二项式定理
      • 二项式公式
      • 多项式公式
    • 组合证明法：构造情景组合，用不同过程得到的同一目的结果应该相同
      • Pascal 恒等式
        • 证明：直接展开
        • 意义：组合证明法（寻找问题的情景组合）
          • 左式：从n+1个小球中取出k个小球
          • 右式：分为取第一个和不取两种情况
            • 取第一个小球的情况：从剩下的n个小球中取出k-1个小球
            • 不取第一个小球的情况：从剩下n个小球中取k个小球
      • 朱世杰恒等式
        • 代数证明：直接展开
        • 组合证明情景：不太明白
      • VANDERMONDE 恒等式
        • 代数证明：略
        • 组合证明：
    • 第二类Strling数 S(n,j)：把球放入盒子问题
      • 定义：n个不同的球放入j个相同的盒子，要求每个盒子均放球，放法数记为S(n,j)
      • 不同的球放入不同的盒子：等价为具有相同元素的有重复排列（分类全排列）
      • 相同的球放入不同的盒子：等价于有重复的组合（空位填分类）
      • 不同的球放入相同的盒子：n个不同的球放入j个不同的盒子，要求每个盒子均放球，这相当于基数为n的集合到基数为j的集合的满射（且单射），可用容斥原理计算满射的个数
      • 相同的球放入相同的盒子：n个相同的球(1)放入k个相同的盒子相当于，将数n分成最多k个正整数之和，不计次序，这个问题称为数的分拆
  • 递推关系
    • 递推关系：一个序列的递归定义指定了一个或多个初始项和一个由前项确定后项的规则，这个规则就是递推关系
    • 递推关系的解：一个满足递推关系公式的通项公式
    • 应用举例
      • 汉诺塔
      • 斐波那契数列
      • 二进制编码
      • 偶校验编码
    • CATALAN（卡特兰）数 Cn
      • 向算式x1*....*xn中添加括号改变运算顺序，加括号的方式称为Catalan数，记作Cn
      • 公式
        • 初始条件：C0 = 1, C1 = 1
      • 证明
        • 1. 注意到所有的加括号都会有一个乘号留在所有括号之外用作将两部分乘起来
        • 2. 选定一个乘号作为锚点，分成左右两个子任务
        • 3. 将所有子任务加起来
  • 递推式
    • 相关概念
      • 递推式一般形式：xn =f(n, xn−1,xn−2, …)
        • 阶数k：递推式中x项数
        • 线性递推式：xn = c1 xn−1 + c2 xn−2 + …,+ck xn−k +F(n)
          • ck , F(n)为 n 的函数
          • 常系数线性递推式：ck 均为常数
          • 齐次线性递推式：F(n)=0
      • 递推式的解：xn=g(n)代入递推式可得到n的恒等式
        • 通解：含有待定参数的一般形式
        • 特解：参数确定的一个解
      • 初始值：序列最开始k个项的值（与递推式中阶数对应）
    • 递推方程求解（尤其是2阶方程）
      • 求解齐次常系数线性递推式
        • 1. 令 xn = λ^n 代入递推式得到特征方程
        • 2. 解出特征方程的根λ，xn = λ^n是递推式的解
          • 特征多项式一定有k个复根，可能有重根
            • 有k个不同的复根则得到递推式的k个解，彼此线性无关，可以直接构成解空间的基
            • 通解公式
              • n为xn中的n（第n项）
              • bk为前k项通项推出的初始条件：代入k=0,1,2...的通项公式，由给出的条件算出a0，再解后面的系数
            • 若特征方程有重根，则需要添加次数
              • 二阶二重根
              • k阶m重根
      • 求解非齐次常系数线性递推式
        • 形式：不是所有F(n)都可解
          • 其中F(n)为Pn(t)*s^n时可解
          • Pn(t)为n的t次多项式
          • s^n为固定项，默认为1^n
        • 解的形式：通解+一个特解
          • 任意两个特解的差为通解
          • 通解：相伴的齐次线性递推方程的解
          • 特解：根据F(n)设出形式然后代入方程求解
            • 形式：n^m*Qn(t)*s^n
              • s与通解的特征根匹配
              • m为根的阶数（可为0）
              • Qn(t)为n的t次多项式（最高次与F(n)相同），注意不要漏掉常数项
            • 求解：代入方程
  • 动态规划
    • 定义：将问题递归地分解为更简单的重叠子问题，通过解决子问题来解决原问题
    • 经典例题：P429 讲座问题
  • 生成函数
    • 定义：把序列的项表示成一个形式幂级数的系数，称为G(X)
      • 求生成函数是函数级数展开的逆运算，相当于求无限项的和函数
      • 若序列为有限项，则生成函数为多项式
      • 一些重要的生成函数
    • 广义二项式系数
    • 用生成函数解决计数问题
      • 有重复的组合（方程形式）【方法2】
        • 每项都拆成1+x+x^2+x^3+....的形式
        • 对于ei的上下限对应级数中x的次数上下限
        • 所有项的级数相乘结果中C对应的次数的项的系数就是方程的解（满足条件的组合数）
  • 容斥原理
    • 定义：求并集把各集合加起来后需要减去重叠的部分（基数）
      • 用N表示基数，交集符号省略，容斥原理可写成
        • Ai是有限集A的子集，Ai'表示该子集在A的补集
        • Ai的划分标准是其中元素都满足某一性质
    • 应用
      • 确定具有约束条件的方程的整数解个数（方法3）
      • 筛法求素数
        • 前提：已知对于正整数n≠ 1，若n不是素数，其最小素因子≤√n
        • 先列举1— [√N]的素数，然后在1~N中排除这些数的倍数
        • 容斥原理表示
          • Ai表示 i的倍数构成的集合（能被i整除的数），i为1~√n的所有素数
          • 1~N中所有素数的集合表示为：倍数集合+基础素数集合-{1}
            • 以1~100为例：A2’A3’A5’A7’ ∪{2, 3, 5, 7} –{1}
            • N(A2’A3’A5’A7’)= 100 – ([100/2]+[100/3]+[100/5]+[100/7]) +([100/6]+…+[100/35]) – ([100/30]+ [100/42]+[100/70]) = 22
      • 求两个集合间满射的个数
        • 已知：有集合B,C, |B| = m, |C| = n. C = {1, 2, …, n}
        • 定义集合A为B到C的映射：令 A= C^B
        • 定义A的子集Ai为B到C中减去{i}的映射：Ai = (C–{i})^B
        • 容斥原理表示：N(A1’ A2’ … An’)=N(A)-C(n,1)(n – 1)m +C(n, 2)(n – 2)m +···
          • N(A) = n^m
• 数论
  • 除法算法/模余算法
    • 所有除法算法都假设只有整数存在
    • 整除： a | b 表示 b = ka （建议念成b是a的整数倍防止混淆）
    • 带余除法：a为整数，d为正整数，则存在唯一的整数q和r，满足0<=r<d，使得a = dq + r
      • 除表示法：q = a div d
      • 模表示法：r = a mod d
      • 上述表达式左边都是被除数，右边都是除数
    • 模指数运算
      • 定义：b^n mod m 结果是余数
      • 算出b^n再模m是不可行的，需要利用指数n的二进制展开式进行计算
      • 二进制展开算法
        • 1. 将次数n转换为二进制
        • 2. 有结果寄存器x和乘积寄存器power两个变量，x初始化为1，power初始化为b mod m
        • 3. 若二进制代码中第i位为0，则x不变，power=power^2；若第i位为1，则x = x*power mod m, power = power^2 mod m
      • 利用欧拉定理和费马小定理计算
        • 1. 对次数进行分解，化成若干个可叠加和复用的部分（简化运算用）
        • 2. 进行指数运算时，若结果大于m了则进行一次求余，化成同余式
        • 3. 化成同余式后进行下一步操作运用 ac ≡ bd (mod m) 的性质继续重复上述运算步骤，直至求完所有次数
        • 例题：正向推导
          • 根据题目条件确定欧拉定理条件：(p, m)=(p, 12) = 1
          • 求出φ(m)，构造欧拉定理：p^φ(m)≡ 1 (mod m)
          • 利用同余式性质从欧拉定理公式向题目靠拢
  • 最大公因数
    • 定义：a, b是整数，ab≠ 0, a, b的公共的因数称为它们的公因数，公因数中最大的那个称为它们的最大公因数，记作gcd(a, b), 或者(a,b). 若(a,b) = 1，则称a,b互素
    • 欧几里得算法/辗转相除法
      • 基础引理：若a=bq+r, 则(a,b)=(b,r)
      • 推论：ab != 0，则存在整数m,n使得ma+nb = (a,b)
      • 辗转相除法
        • 过程：a div b作带余除法，用除数作被除数，余数作除数（参考引理），直至余数为0，最后一个非零余数即为gcd
        • 表示为线性组合
          • 1. 根据保留的算式，通过展开余数 r = a - bq的方式代入
          • 2. 每一步都只展开余数，展开后与留下的被除数（展开项的除数）进行系数合并
          • 3. 继续展开余数直到顶层
  • 素数
    • 定义：p是正整数，p≠ 1，若p的正因数只有1和p本身，则称p为素数 （1既不是素数也不是合数）
    • 定理
      • 若p是素数且p|ab，则p|a或p|b
      • 存在无穷多个素数
      • 整数的唯一分解性：每个大于1的整数都可以写成素数之积且写法唯一
  • 同余式
    • 定义
      • a,b为整数而m为正整数，当m整除a-b时称a模m同余b（即 a-b = km），记作a≡ b (mod m)
      • 含义
        • 可以理解为一个等式和括号里的注释两部分构成，等式部分决定大部分性质
        • a和b除以m得到的余数相同，即 a mod m = b mod m
        • 若 0<=b<m ，则有 a≡ b (mod m) 等价于 a mod m = b
      • 注意
        • 模不是余数而是除数，模运算的结果才是余数
        • 此处的mod和作为运算符的mod不同，与后面的m作为整体作为记号存在
    • 性质
      • f(x)是整系数多项式，则f(a)≡ f(b) (mod m)
      • (a,m)=(b,m)
    • 同余类
      • 对同一个模同余的所有数称为一个同余类
    • 模逆
      • 利用辗转相除法求解同余方程的方法
      • 模逆存在定理：若(a,m) = 1（必须互素）, 则一定存在 b 使 ab ≡ 1 (mod m)，称b为a模m的逆
      • 求 a 模 m 的逆
        • 1. 根据题意翻译成 ab ≡ 1 (mod m) 的形式，并根据定义写出 ab - 1 = mk
        • 2. 通过辗转相除法计算 gcd(a,m) = 1，注意保留算式
        • 3. 通过算式反向代入表示最后的余数1，直到表示成 1 = ab - mk 的形式，其中b就是所求的模逆（式中蓝色要为题目的值）
        • 4. 其他模m同余为b的值也是a的逆（即B = b + mk）
    • 线性同余方程/一次同余式
      • 形式：ax≡ b (mod m)
      • 同余式有解判定
        • 解存在：ax≡ b (mod m) 有解的充要条件是(a,m) | b，且有解时恰好有 (a,m) 个解
        • 解唯一：若 (a,m) = 1【模逆存在】, 则同余式ax≡ b (mod m) 有唯一解
      • 同余式的解
        • 解的形式：x ≡ bc(mod m)
          • 其中b为原方程参数，c为a模m的逆
          • 解的形式表示了x属于这个同余类，即表示了一系列数
        • 求解方法
          • 求出模逆之后就可以在一次同余式两边同时乘以模逆来解同余方程/在模逆等式两边同时乘以参数b表示x
          • 数学语言：已知模逆c【即 ac≡ 1 (mod m)】，则acb≡ b (mod m)，所以x ≡ cb(mod m) 是同余式的解
    • 欧拉定理
      • 欧拉函数φ(n)
        • 定义：n是正整数，1~n 中与 n 互素的数的个数记作 φ(n)
        • 求φ(n)：利用容斥原理证明
        • 在RSA中的应用：若n可以分解为若干个互质的整数之积，则φ(n)也可以分解成这些质数的φ(n)之积
      • 欧拉定理
      • 费马小定理：欧拉定理的特殊情况
        • 定理内容
        • 应用：运算整数高次幂的模p余数
    • 高次同余式（方程）
      • 形式：x^a ≡ b(mod m)
      • 应用欧拉定理与费马小定理解方程
        • 应用条件：若b,m互素，则其解 x 必与 m 互素
          • 若还有a,φ(m)互素，则同余式 ay≡ 1 (mod φ(m))有解 y=c，即ac = 1 + kφ(m)
            • 将原方程再乘方c次得：x^ac ≡ b^c (modm) → x^(1+kφ(m))≡ b^c (mod m)
            • 由欧拉定理和(x,m)=1【条件】：x^φ(m) ≡ 1(mod m)
            • 将上式除以下式（已知互质可以相消）得：x≡ b^c (mod m)
        • 总结：x≡ b^c (mod m)
          • b,m都是原方程中的参数
          • c为同余式 ay≡ 1 (mod φ(m))的解【把高次同余式转化成一次同余式】
          • 关键为求出φ(m)
      • 解法步骤
        • 1. 对m进行质因数分解，并求出φ(m)
  • RSA 密码
    • 密钥生成：公钥和私钥生成后就可以丢弃p,q
      • 公钥(N,e)：公开的，用于加密明文的密钥
        • 1. 选取两个大素数p,q，算出N = pq 和 φ(N) = (p-1)(q-1) 【欧拉函数性质】
        • 2. 任意选取一个数e，保证e与φ(N)互素
        • 3. (N, e)称为公钥，并在网络上公开用于明文的加密
      • 私钥d：储存在本地的私有密钥，用于解密明文
        • 1. 解同余式ed≡ 1 (mod φ(n))算出d ，由于1<φ(n)原式等价于 ed mod φ(n) = 1 ，亦等价于ed = kφ(n) + 1
        • 2. 由 ed = kφ(n) + 1 表示出私钥d = (kφ(n) + 1)/e
        • 3. 求出e模φ(n)的逆 即为所求的私钥 d
      • 加密原理：大素数求模运算几乎是不可逆的（不能在有限时间内求出φ(N) ）
    • 加密算法
      • 已知明文编码m和公钥e，求解 x ≡ m^e (mod N) （要求m与x均落在1~N上，所以等价于 求 m^e mod N = x ），解出x即为所求密文
      • 过程中需要用到模指数运算
    • 解密算法
      • 已知密文C和私钥d，求解 m ≡ C^d (mod N)（同样要在1~N上）等价于 求 m^e mod N = x ，解出m即为明文
      • 过程为模指数运算