离散数学

用于想学习的朋友来复习或者提前自学，也可以用于期末的复习，虽然不够全面但算是入门的知识。

离散数学

• a. 集合
  • 元素与集合关系
    • 元素∈/∉集合
    • 集合⊆/⊊/=集合
  • 幂集
    • 集合A中有n个元素，则幂集为2^n
  • 集合的基本运算
    • 并运算A∪B
    • 交运算 A∩B
    • 差运算 A-B ∈A∉B
      • A-B=A∩B补
    • 对称差 A⊕B=（A∪B）-（A∩B）
  • 集合的代数公式
    • 可利用文氏图进行推导
    • 等幂律
      • A∪A=A；A∩A=A
    • 交换律
      • A∩B=B∩A；A∪B=B∪A；A⊕B=B⊕A
    • 结合律
      • A∪(B∪C)=(A∪B)∪C；A∩(B∩C)=(A∩B)∩C；A⊕(B⊕C)=(A⊕B)⊕C
    • 分配律
      • A∩(B∪C)=(A∩B)∪(A∩C)；A∪(B∩C)=(A∪B)∩(A∪C)
    • 吸收律
      • A∪(A∩B)=A；A∩(A∪B)=A
    • 同一律
      • A∪∅=A；A∩U=A
    • 零一律
      • A∪U=U；A∩∅=∅
    • 补余律
      • A∪A'=U；A∩A'=∅ ‘表示补
    • 摩根律
      • (A∪B)'=A'∩B'；(A∩B)'=A'∪B' '表示补
    • 对合律
      • A''=A '表示补
  • 包含排斥原理
    • 包含排斥原理1
      • 丨A∪B丨=丨A丨+丨B丨- 丨A∩B丨 丨A∪B∪C丨 =丨 A丨+丨B丨+丨C丨 -丨 A∩B丨 -丨 B∩C丨 - 丨C∩A丨 +丨 A∩B∩C丨
    • 包含排斥原理2
      • 丨A'∩B'丨=丨U丨-丨A∪B丨
• b. 二元关系
  • 笛卡尔乘积 丨A丨=n，丨B丨=m，则丨A×B丨=n×m
  • 关系
    • A到B的关系 A×B的所有子集都是从A到B的关系
      • 当丨A丨=n，丨B丨=m，A到B共可定义2^(n×m)种不同的二元关系
    • A上的关系 A×A的子集都是A上的关系
    • A上的特殊关系 空关系 全域关系 恒等关系（自反）
  • 前域与值域
    • 前域叫domR 值域叫ranR R上的前域即所有有序对中的第一元 R上的值域即所有有序对中的第二元
  • 平凡子集
    • 空集
    • 集合本身
  • 表示方法
    • 表格表示
    • 关系矩阵
    • 关系图
  • 关系的性质
    • 空关系不具有自反关系 但是具有反自反 对称 反对称 可传递性
    • 自反关系 对于A中每一个元素a 都有（a,a）∈R
    • 反自反关系 对于A中每一个元素a 都有（a,a）∉R
    • 对称的关系 每当（a,b）∈R时，一定有（b,a）∈R
    • 反对称的关系 当a≠b时 如果（a,b）∈R时，一定有（b,a）∉R
    • 可传递的关系 每当（a,b）∈R且（b,c）∈R时，一定有（a,c）∈R
  • 五种关系
    • 等价关系 R是自反的 对称的 传递的二元关系
    • 相容关系 R是自反的 对称的二元关系
    • 偏序关系 R是自反的 反对称的 传递的二元关系
      • 极大元 极小元
      • 最大元 最小元
      • 上界 下界
      • 上确界 下确界
    • 复合关系 类似两个集合的传递
    • 逆关系 将集合里的第一元与第二元转换
  • 关系的闭包运算
    • 自反闭包r(R) 只需把R中缺少的自反有序对补上即可
    • 对称闭包s(R) 只需把R中缺少的对称有序对补上即可
    • 传递闭包t(R) 只需把R中缺少的传递有序对补上即可
• c. 函数
  • 函数的定义 丨A丨=n 丨B丨=m 则A到B可以定义m^n个不同的函数
  • 特殊函数
    • 单射函数 丨A丨=n 丨B丨=m （m≥n） A到B的单射函数有A（n，m） n在上
    • 双射函数 丨A丨=n A到A的双射函数有n!
    • 满射函数
• d. 图论
  • 图的基本类型
    • 具有n个顶点的有限图称为n阶图 具有n个顶点，m条边的图常记作（n,m）
    • 有向边
      • 有向边的箭头方向自始点指向终点
    • 无向边
      • 无向边的每个端点都可以作为始点或终点
    • 有向图 图中各边都是有向边
    • 无向图 图中各边都是无向边
      • 无向图的矩阵是对称矩阵
    • 混合图 图中既有有向边又有无向边
    • 逆图 将有向图D中的每一条边方向颠倒得到逆图D'
    • 有限图 图中有有限个顶点 （无限个称无限图 不做讨论）
    • 多重图 含有平行边的图
      • 平行边指两个顶点之间有多条边（对于有向图则是有多条同方向的边）
    • 简单图 不含平行边和自回路的图
      • 平行边指两个顶点之间有多条边（对于有向图则是有多条同方向的边） 自回路指一条边的两个端点重合 称为自回路或者自环
    • 定向图 把无向图G的每条边添加箭头成为有向边，得到有向图D 则D是G的定向图
    • 底图 把有向图D的每条边箭头去掉成为无向边，得到无向图G 则G是D的底图
  • 图的顶点度数
    • 无向图中顶点的度数 deg(v)
      • 孤立点 度数为0
      • 悬挂点 度数为1
        • 与悬挂点关联的边称为悬挂点
    • 握手定理 n为顶点m为边数 则所有点的度数之和＝2m
    • 有向图中顶点的度数 入度＝出度=m条边
      • 入度 deg-(v)
      • 出度 deg+(v)
  • 完全图
    • 无向完全图
      • 在n阶无向图中，如果任意两个不同顶点之间都有一条边关联，则称此无向图为无向完全图，记作Kn 易得n阶无向图中是(n-1)-正则图 推论 n阶无向完全图kn有n×(n-1)/2条边
    • 有向完全图
      • 在n阶有向图中，如果任意两点都有两条方向相反的有向边关联，且每一个顶点都有自回路，则称此有向图为有向完全图 推论 n阶有向完全图有n²条边
    • 竞赛图
      • D为n阶有向图，如果D的底图为无向完全图kn，则D为竞赛图
  • 子图
    • 删边 删去图中某一条边保留该边的端点
    • 删点 删去某一点以及这个点关联的所有边
    • 主子图 删点得到的图为主子图
    • 生成子图 删边得到的图为生成子图
  • 补图
    • 5个顶点的自补图仅有两种
  • 连通性与最短通路
    • 简单通(回)路
      • 如果一条通(回)路中的各边都是不相同的，则称这样的通(回)路为简单通(回)路。 回路指通路中的始点与终点相同
    • 基本通(回)路
      • 如果一条通(回)路中的各个顶点都是不相同的，则称这样的通(回)路为基本通(回)路
    • 无向图的连通性
    • 有向图的连通性
      • 如果有向图中存在一条通过图中各个顶点的回路，则此有向图是强连通的 如果有向图中存在一条通过图中各个顶点的通路，则此有向图是单向连通的
      • 强连通
      • 单向连通
      • 弱连通
    • 最短通路
      • 狄克斯特洛算法
        • 穷举法
        • 递推法
        • 列表法
  • 树
    • 无向树
      • 设T是无向简单图且T不存在任何回路，则称T为无向树，或简称树
      • 树叶 度数为1
      • 内结点/分枝点 度数＞1
      • 四点性质
        • 1.若树有n个顶点，m条边，则m=n-1 2.树中任意两点有且仅有一条通路相连 3.在树中任意删去一条边，则变成不连通路 4.在树中任意两个不邻接的顶点中添加一条边，则构成的图中包含唯一回路。
      • 最小生成树
        • 设G是无向连通图，若G的一个生成子图T是一棵树，则称T是图G的生成树
      • 克鲁斯卡尔算法
    • 有向树
      • 底图为无向树的有向图称为有向树
      • 有根树
        • 在有向树T中，如果有且仅有一个入度为0的点，其他点的入度均为1，则称有向树T为有根树。
        • 根 入度为0的点 一般为树上最高的点
        • 树叶/叶片 出度为0的点
        • 分枝点/内结点 出度不为0的点
      • 层次/水平
        • 在有根树中，从树根到顶点x的通路长度，即自根到点x的通路中所含边的条数
      • 高度
        • 在有根树T中，最长通路的长度
      • 家族
        • 设ab是有根树T中的一条有向边，如果a是始边，b是终边，则称a是b的父亲，b是a的儿子 如果T中有一条以a为始点，x为终点的有向通路，则称a是x的祖先，x是a的后裔
      • k元树与完全k元树
        • 设T是有根树，如果T中各个分枝点的儿子树最多为k，则称有根树T为k元树 如果每一个分枝点的儿子树都是k，则称此有根树为完全k元树 推论 当T是完全k元树时，如果其分枝点数为i，树叶数为t 则有公式 i=(t-1)/(k-1) i+t为树中顶点的总数
    • 周游算法
      • 前序周游算法
      • 中序周游算法
      • 后续周游算法
    • 前缀码与最优树
• e. 命题逻辑
  • 命题逻辑的基本概念
    • 命题
      • 命题：能判断其真假的陈述句 两个要求 1.判断其真值 2.陈述句 要注意 我正在说假话 是个悖论 不是命题！
      • 真命题 T 1
      • 假命题 F 0
      • 简单命题（原子命题）即不可拆分命题
      • 复合命题 即由联结词和简单命题组合
    • 命题联结词
      • 联结词的运算优先级：¬ ∧ ∨ → ↔ （优先级从左到右递减）
      • • 否定（¬）类似非
          • 
        • 合取（∧）类似并且
          • 
        • 析取（∨）类似或
          • ∨ 是兼容或 Eg：我喜欢唱歌或者喜欢跳舞 设P是我喜欢唱歌 Q是我喜欢跳舞 则命题符号化为P∨Q 不兼容或/排斥析取 Eg：我晚上九点看书或者打球 设P是我晚上九点看书 Q是我晚上九点打球 P跟Q晚上九点只会发生一个 则命题符号化为（¬P∧Q）∨（P∧¬Q） 
        • 蕴含（→）类似如果...则...
          • P→Q P是条件 Q是结论 P是Q的充分条件 
        • 双条件（↔）类似当且仅当
          • 
    • 判断公式类型
      • 列真值表进行判断公式类型 等值演算法进行判断公式类型 去掉→和↔ 换成¬ ∧ ∨
      • 永真式（恒为1）又叫重言式
      • 永假式（恒为0）又叫矛盾式
      • 可满足式：不是永假式的式子
  • 命题逻辑等值演算
    • 等值式⇔（⇔不是联结词）
      • 两个命题A与B在分量的不同指派下，其真值总是相同时，则称这两个命题公式A和B逻辑等价
    • 常见等值式
      • 双否定律 ¬¬P⇔P
      • 等幂律 P∧P=P / P∨P=P
      • 交换律 P∧Q⇔Q∧P / P∨Q⇔Q∨P
      • 结合律 (P∧Q)∧R⇔P∧(Q∧R) ∨同理
      • 分配律 P∧（Q∨R)⇔(P∧Q)∨(P∧R) ∨同理
      • 摩根律 ¬（P∧Q）⇔¬P∨¬ Q ∨同理
      • 吸收律 P∧(P∨Q)⇔P ∨∧同理
      • 01律
        • P∨0⇔P P∧1⇔P P∨1⇔1 P∧0⇔0 P∨¬P⇔1 P∧¬P⇔0
      • 蕴含等值式 P→Q⇔¬P∨Q
      • 等价等值式 P↔Q⇔(P→Q)∧(Q→P)
    • 范式
      • 合取式：有限个文字的合取 例如P∨Q / P∨¬Q / ¬P
      • 析取式：有限个文字的析取 例如¬P∧Q / P∧Q∧R / ¬P
      • 合取范式：有限个析取式的合取 即(...∧...)∨(...∧...)∨...
      • 析取范式：有限个合取式的析取 即(...∨...)∧(...∨...)∧...
      • 主析取范式 通过真值表法或者等值演算法求解
        •  第一步 先列出所要求的式子真值表 第二步 寻找所要求的式子中真值为1的项 第三步 对应第二步找到左边单元项 将它们合取 0即非x 1即原x 第四步 将每一项括号然后析取
      • 主合取范式 通过真值表法或者等值演算法求解
        •  第一步 先列出所要求的式子真值表 第二步 寻找所要求的式子中真值为0的项 第三步 对应第二步找到左边单元项 将它们析取 0即原x 1即非x 第四步 将每一项括号然后合取
      • 永真蕴含式 四个性质
        • 1. 如果A⇔B，则A⇒B和B⇒A 2. 如果A⇒B，则P∧A⇒P∧B 3. 如果A⇒B.P⇔Q，则P∧A⇒Q∧B 4. 如果A⇒B且B⇒C，则A⇒C
  • 命题逻辑推理理论
    • 直接证明法 P已知条件 T推出结论
    • 间接证明法 刚开始有个P[附加前提]
• f. 谓词逻辑
  • 个体词：可独立存在的客体
  • 谓词：用来说明个体的性质或个体间关系
    • A(X) 一元谓词 B(X,Y) 二元谓词 推广 有n元谓词
  • 量词
    • 全称量词∀ 命题后面跟着→
    • 存在量词∃ 命题后面跟着∧
  • 推理理论
    • 全称指定规则US (∀x)P(x)⇒P(c)
    • 存在指定规则ES (∃x)P(x)⇒P(c)