离散数学

Posted on |
Words count in article: 5.5k 字 | Reading time ≈ 21 分钟

Xmind下载

逻辑

命题

  • 或者为真或者为假而不是两者同时成立的一条陈述句

  • 量词

    • 全称量词$\forall x \quad P(x)$

    • 存在量词$\exists x \quad P(x)$

哎呀，图片不见了 > 需要掌握对嵌套量词的翻译，诸如$\forall x(C(x)\vee\exists y(C(y)\wedge F(x,y)))$：对于任意的x都有C(x),或者存在一个y，满足C(y),并且满足F(x,y)

  • 逻辑运算符

    • 条件语句$p\rightarrow q$：p为真而q为假时命题为假，否则为真
    • 合取$p\wedge q$（p并且q）两个命题都为真，命题为真
    • 析取$p\vee q$（p或q）只要两个命题至少一个为真，命题即为真
    • 异或$p\oplus q$:两个命题恰好一个为真，命题为真
    • 运算优先级哎呀，图片不见了（量词比所有的逻辑运算符都具有更高的优先级)

  • 命题运算

哎呀，图片不见了

  • 逻辑等价：所有可能情况下都有相同真值的两个复合命题是逻辑等价的

  • 德摩根律：哎呀，图片不见了

  • 可满足性：如果存在一个对其变元的真赋值使其为真，则为可满足的

  • 重言式

    • 命题变量所有可能值都为真的命题哎呀，图片不见了

  • 谬论

    • 命题变量所有可能值都为假的命题

证明方法

  • 逻辑表示：$(p_1\wedge p_2\dots \wedge p_n)\Rightarrow q$

    • q从逻辑上由p得到
    • 通过证明规则推理是一个重言式证明
    • 假言推理$(p\wedge(p\rightarrow q)\rightarrow q)$
    • 间接方法：逆否命题与其等价$(p\rightarrow q)\leftrightarrow((\neg p)\rightarrow (\neg q))$
    • 反证法$((p\rightarrow q)\wedge(\neg q))\rightarrow (\neg p)$
    • 数学归纳法哎呀，图片不见了
    • 强归纳法$(p_{n_0}\wedge p_{n_0+1}\dots \wedge p_k)\Rightarrow p_{K+1}$
    • 哎呀，图片不见了
    • 哎呀，图片不见了
    • 构造性证明：通过找到一个使得P(a)为真的元素a来给出$\exists xP(x)$的存在性证明
    • 唯一性证明：分为两部分，存在性（存在某个元素具有期望的性质）与唯一性（如果$x\not{=}y$,则y不具有该性质）

基本结构

集合

集合是对象的一个无序的聚集

当一个集合是有限的或者与正整数集具有一样的大小，则说这个集合是可数的

  • 空集$\emptyset$:不含有任何元素的集合

    除空集外，任何集合至少有$\emptyset$这一个元素，即为单元素集。所以任何非空集合都至少有两个子集，空集和集合S本身

  • 文氏图

集合的大小

若S有n个不同的元素，则称S为有限集，n为S的基数，记为|S|（$|\emptyset|=0$）

集合A和集合B相同的基数，当且仅当存在从A到B的一个一一对应，写成|A|=|B|（衡量两个集合大小的方法）

可数集

一个集合或者是有限集或者与自然数集具有相同的基数，这个集合就称为可数的.如果一个无限集S是可数的，我们使用$\aleph_0$来表示S的基数，写成$|S|=\aleph_0$

正奇数集、有理数集（将每个有理数表示为两个正整数之比）都是可数集合；实数集是不可数集

SCHRÖDER-BERNSTEIN定理

如果|A|和|B|是集合，且|A|≤|B|和|B|≤|A|，则|A|=|B|换言之，如果存在一对一函数f从A到B和g从B到A，则存在 A和B之间的一一对应画数。

集合运算

哎呀，图片不见了 哎呀，图片不见了 > 证明集合相等一种方法：证明每一个是另一个的子集

函数

令A和B是非空集合，从A到B的函数f是对元素的一种指派，对A的每个元素恰好指派B的一个元素，写成：$f:A\rightarrow B$。A为f的定义域，B为f的陪域

如果两个函数的定义域、陪域、映射关系都相同，这两个函数是相等的

  • 单射函数：函数是一对一的，对于定义域上的a，b有$f(a)=f(b)\rightarrow a=b$
  • 满射函数（映上）：对每个$b\in B$有元素$a\in A$使得$f(a)=b$
  • 双射函数：函数即时一对一的，又是映上的
  • 反函数$f^{-1}$：有$f(a)=b$时$f^{-1}(b)=a$(如果函数不是一一对应的，就无法定义反函数)
  • 合成函数：有$(f\circ g)(a)=f(g(a))$(交换律不成立)
  • 部分函数：A的一个子集为f的定义域，对于A中但不在f定义域的元素没有定义

序列

一种用来表示有序列表的离散结构

递推关系

  • 递归关系
  • 初始条件

求和

代数结构

由对象集合及运算的数学结构，称为代数系统

  • 特殊元（都是唯一的）

    • 幺元$ex=xe=x$
    • 零元$\theta x=x\theta=\theta$
    • 逆元$x*x^{-1}=e$

同态

  • 象的积等于积的象$f(a*b)=f(a)\oplus f(b)$

同构

  • 当f是A到B的一个同态

    • f为满射函数为满同态
    • f为单射函数为单同态
    • f为双射函数为同构

同余关系

  • 代数结构上的相等关系
  • 哎呀，图片不见了

商集

  • 集合A关于运算~的所有等价类作为元素组成的集合

自然同态

  • 建立同余关系便可确定一个自然同态
  • 假设R是S上一个同余关系，S/R是对应的商半群，由f(a)=[a]定义一个从S到S/R的同态的满射的函数,被称为自然同态

同态基本定理

  • 设f是S到T的一个同态，R是S上关系，对于S中的ab，a R b,当且仅当f(a)=f(b)

    • R是一个同余关系
    • T和商半群S/R是同构的

  • $$
    (\bar{f}\circ f_R)(a)=\bar{f}(f_R(a))=\bar{f}([a])=f(a)
    $$

  • 哎呀，图片不见了

计数

乘积法则

假设一个过程可以被分解为两个任务，如果任务一有n1种方式，任务二有n2种方式，那么完成这个过程有n1×n2种方式

一个有限集S的不同子集数是$2^{|S|}$

求和法则

如果完成任务一有n1种方式，完成任务二有n2种方式，并且这些任务不能同时执行，那么完成两个任务有n1+n2种方式

减法法则（容斥原理）

如果一个任务可以通过n1种方式用方法一完成、或者通过n2种方式用方法二完成，那么执行这个任务的方法数是n1+n2减去两类方法中执行这个任务相同的方法$|A_1 \bigcup A_2|$

除法法则

如果一个任务能由一个可以用n种方式完成的过程实现，而对于每种完成任务的方式w，在n种方式中正好有d种与之对应，那么完成这个任务的方法数为n/d

鸽巢原理

  • 如果n个鸽子被分配到m个鸽巢中且m＜n，那么至少有一个鸽巢含有两个或更多的鸽子
  • 推广鸽巢原理：如果N个物体放入k个盒子，那么至少有一个盒子包含了至少$\lceil N/k\rceil$

排列

具有n个不同元素的集合的r排列数为：$P(n,r)=n(n-1)(n-2)\dots(n-r+1)=\frac{n!}{(n-r)!}$

组合

具有n个不同元素的集合的r组合是从该集合中无序选取r个元素，r组合数记为C(n,r)$C(n,r)=\frac{n!}{r!(n-r)!}$

关系

可以使用两个相关元素构成的有序对来表达两个集合元素之间的关系，A到B的二元关系是A出B的子集

二元运算

  • 结合、分配、吸收、幂等、交换、封闭

n元关系

投影

将n元组映射到m元组，即删除了n元组的n-m个分量

连接

$J_p(R,S)$是m+n-p元关系，即将m元组的后p个分量与n元组的前p个分量相同的第一个关系中所有m元组和第二个关系的所有n元组组合起来产生的一个新的关系

笛卡尔积

  • 有序对（a,b）：对象ab以指定次序出现的一个列举

  • 笛卡尔积A×B：A与B中元素a,b的所有有序对(a,b)组成的集合

  • A的划分：A的非空子集的一个集合

    • A的每个元素属于划分中的某个集合
    • 如果A1和A2是划分中的不同元素，A1∩A2为空集

关系R

  • 笛卡尔积的子集

  • 关系矩阵M 哎呀，图片不见了

  • 关系有向图

    • 道路

      • R中从a到b长度为n的道路指：从a开始到b结束且具有$a R x_1，x_1 R x_2，\dots$的一条有限序列
      • $R^n$表示R中存在从x到y长度为n的一条道路
      • $R^{\infty}$表示R的连通关系
      哎呀，图片不见了

      性质

    • 自反和非自反

      • 自反：$对于\forall a\in A,有(a,a)\in R$

        • Dom(R)=Ran(R)=A

      • 非自反：$对于\forall a\in A,有(a,a)\notin R$

    • 对称和非对称

      • 对称：$只要(a,b)\in R，就有(b,a)\in R$

        • 不是对称的：$\exists (a,b)\in R,但(b,a)\notin R$

      • 非对称：$如果(a,b)\in R，那么(b,a)\notin R$

        • 不是非对称的：$\exists (a,b)\in R且(b,a)\in R$

      • 反对称：$如果(a,b)\in R且(b,a)\in R，则a=b$

        • 不是反对称的：$\exists a\neq b,(a,b)\in R,(b,a)\in R$

    • 传递关系$(a,b)\in R,(b,c)\in R\rightarrow(a,c)\in R$

      • 推广：$R是传递的当且仅当对于所有n\ge 1，R^n\subseteq R$

    等价关系

    • 如果一个关系是自反的、对称的、传递的

    • 在等价关系中，如果两个元素有关联，就可以说它们是等价的

    • 等价类

      • 与a有关系的所有元素为a的等价类，记作$[a]_R$
      • 如果$b\in [a]_R$,b叫做这个等价类的代表元

    • 如果R是等价关系，下面三条语句是等价的：

    $$
    (1)aRb;\quad (2)[a]_R\cap[b]_R\neq\empty;\quad(3)[a]_R=[b]_R
    $$

    划分

    等价类构成A的划分，它们将A分成不相交的子集。集合S的划分是S的不相交的非空子集构成的集合
    $$
    \bigcup_{a\in A}[a]_R=A\
    [a]_R\neq[b]_R时，[a]_R\cap[b]_R=\empty
    $$

    如果F是集合A的一个划分，那么F可以构造A上的一个等价关系

    闭包

    • 包含关系R且满足某种性质的关系S

    • 闭包S为所有包含R且具有性质P的关系的子集

    • 自反闭包$R\cup \Delta \quad(\Delta={(a,a)|a\in A})$

    • 对称闭包$R\cup R^{-1}$

    • 传递闭包$R^{\infty}$

      • 沃舍尔算法：将第k行加到第k列有1的行上
      哎呀，图片不见了

  • 合成$\cup^n_{i=1}(a_{ij}\cap b_{ij})$

序

偏序集

  • 偏序R：自反、反对称（需要对元素进行排序）、传递（如≥、≤）

  • a,b可比：偏序集中每一对元素不必都是可比的

  • 全序集：如果一个偏序集中每一对元素都是可比的

  • 良序集：如果R是全序的，并且S的每个非空子集都有一个最小元素

    • 良序归纳原理：设S是一个良序集。如果对所有$y\in S$ $P(y)$为真，且对所有$x\in S$有$xRy$，那么$P(x)$对所有的$x\in S$为真

  • 偏序的有向图中没有长度比1大的环

  • 哈塞图

    • 移除自反的环以及移除所有由于传递性必须出现的边
    • 若$xRy$且不存在$z\in S$使得$xRzRy$，则称元素y覆盖元素x，y覆盖x的有序对(x,y)的集合称为偏序集上的覆盖关系

  • 拓扑排序

    • 相容：只要$aRb$就有$a\preccurlyeq b$则称全序$\preccurlyeq $和偏序$R$是相容的
    • 构造一个全序的过程
    • 哎呀，图片不见了

  • 极值元

    • 极大元：A中不存在比它大的元
    • 极小元：A中不存在比它小的元
    • 最大元：存在一个元素大于每个其他元素
    • 最小元：存在一个元素小于每个其他元素
    • 一个偏序集可以有多个极大元和多个极小元，而最小元和最大元是唯一的
    • 上界：一个大于等于子集A中所有元素的元素
    • 下界：一个小于等于子集A中所有元素的元素
    • 最小上界：
    • 最大下界

格

  • 集合中任意两个元素所组成的子集都有最小上界和最大下界的一个偏序集
  • 同构的格哎呀，图片不见了

布尔代数

哎呀，图片不见了

图

图的同构

两个图具有完全相同的形式，从某种意义上就是两个图的顶点间存在着一一对应，这个边应保持边的对应关系。即如果存在一对一的和映上的从V1到V2的函数f，且f具有这样的性质：对V1中所有的a，b在G1中相邻当且仅当f(a)和f(b)在G2中相邻，则称G1、G2是同构的

  • 图形不变量：同构的简单图必须具有相同的顶点数、边数，并且对应顶点的度也必须相同

性质

  • 握手定理：设m条边的无向图中$2m = \sum_{v\in V}deg(v)$，图中顶点度的总和是边数的两倍
  • 无向图有偶数个度为奇数的顶点
  • $\sum_{v\in V}deg^{-}(v)=\sum_{v\in V}deg^{+}(v)=|E|$

连通性

  • 通路：边的序列
  • 连通分支：图的一个最大连通子图
  • 割点：删除图中一个点和它关联的边后，产生比原图更多的连通分支的子图

欧拉通路

  • 欧拉回路是包含G的每条边的简单回路

  • 欧拉通路是包含G的每条边的简单通路

  • 若连通图有欧拉回路，则每个顶点必有偶数度

  • 含有至少两个顶点的连通多重图具有欧拉回路当且仅当它的每个顶点的度都为偶数

  • 哎呀，图片不见了

  • 连通多重图具有欧拉通路但无欧拉回路当且仅当它恰有两个度为奇数的点

哈密顿通路

  • 哈密顿通路：经过G中每一个顶点恰好一次的简单通路
  • 哈密顿回路：经过G中每一个顶点恰好一次的简单回路
  • 狄拉克定理：如果G是有n个顶点的简单图，其中n≥3，并且G中每个顶点的度都至少为n/2，则G有哈密顿回路
  • 欧尔定理：如果G是有n个顶点的简单图，其中n≥3，并且对于G中每一对不相邻的顶点u和v，都有deg(u)+deg(v)≥n，则G有哈密顿回路

最短通路

哎呀，图片不见了 哎呀，图片不见了

平面图

在平面中画出且边没有任何交叉的图

欧拉公式

$$
r=e-v+2（r为平面图中面数、e为边数、v为顶点数）
$$

  • 若v≥3，有$e\le3v-6$
  • G有不超过5的顶点
  • 若v≥3并且没有长度为3的回路，则$e\le2v-4$

初等细分

若一个图是平面图，则通过删除一条边并添加一个新顶点和两条边获得的任何图也是平面图，该操作称为初等细分

同胚

若相同的图通过一系列初等细分获得G1、G2，则称它们是同胚的

哎呀，图片不见了

库拉图斯基定理

一个图是非平面图当且仅当它包含一个同胚与$K_{3,3}或K_5$的子图

图着色

  • 简单图的着色是对该图的每个顶点都指定一个颜色，使得两个相邻的顶点颜色相同

  • 四色定理：平面图的着色不超过4

群与半群

半群

  • 非空集合S以及一个定义在S上的可结合的二元运算*

    • 如果*是一个交换运算，则称半群为交换半群

  • 幺半群

    • 具有单位元的半群

  • 子半群

    • T为S的一个非空子集，ab属于T，a*b也属于T

  • 半群的积

    • $(s_1,t_1)‘’(s_2,t_2)=(s_1s_2,t_1*’t_2)$
    • 同余关系$a \ R \ a’,b \ R \ b’\rightarrow (a*b)\ R\ (a’*b’)$

  • 同态象

    • f为一个满射的S到T的同态，T是S的同态象

半群的同构

  • 设$(S,)和(T,‘)$是两个半群，如果函数$f:S\rightarrow T$是从S到T的一个一一对应（单射、满射），并且对S中的所有a和b有$f(ab)=f(a)‘f(b)$，则称$f:S\rightarrow T$是从$(S,)到(T,‘)$的一个同构

  • 哎呀，图片不见了

  • 如果f是从交换半群$(S,)到半群(T,‘)$的一个同构，分别有单位元e，e’，那么$f(e)=e’$

  • 如果f是从交换半群$(S,)到半群(T,‘)$的一个满同态，分别有单位元e，e’，那么$f(e)=e’$

  • 如果f是从交换半群$(S,)到半群(T,‘)$的一个同态，S’是S的一个子半群，那么f下S’的象是T的子半群

  • 如果f是从交换半群$(S,)到半群(T,‘)$的一个满同态，那么$(T,*’)$也是交换半群

群G

  • 具有单位元e的幺半群$a \ R \ a’,b \ R \ b’\rightarrow (a*b)\ R\ (a’*b’)$

  • 阿贝尔群

    • 满足交换律的群

  • 性质

    • G中每个元素a在G中仅有一个逆元$aa^{-1}=a^{-1}a=e$
    • 消去性质

    $$
    \begin{cases}
    ab=ac\Rightarrow b=c \
    ba=ca\Rightarrow b=c
    \end{cases}
    $$

    • $(a^{-1})^{-1}=a,\quad (ab)^{-1}=b^{-1}a^{-1}$
    • ax=b,ya=b在G中有唯一解（a,b为G中元素）
    • 阶不相等的两个群不可能是同构的

  • 乘法表

    • 任意行列中不能存在重复的元素，必须在空格中填e

  • 三角形对称群

    • 哎呀，图片不见了
    • 不是阿贝尔群
    • n个元素的所有置换的集合在合成运算下是阶为n！的群，称为n个字母的对称群（$S_n$）
    • 元素是集合的置换的集合
    • 运算为“依次序定义”

子群H

  • 条件

    • 包含G的幺元
    • a，b属于H，ab也属于H
    • 元素a的逆元也属于H

  • 正规子群

    • 定义:对于G的所有元素a，有左陪集等于右陪集

    • 设R是G上的一个同余关系，$H=[e]$（包含单位元的等价类）,H为G的一个正规子群

      • $[a]=aH=Ha$

    • 若G是任意一个群，G上的同余关系的等价类总是G的某个正规子群的陪集，反之，G的任意一个正规子群的陪集恰好是关于G上某个同余关系的等价类

  • 核ker(f)

    • G上的同余关系的等价类总是G的某个正规子群的陪集
    • 若f是G到$G’$的满同态，f的核为$ker(f)={a\in G|f(a)=e’}$
      • $ker(f)$是G的一个正规子群
      • 商群$G/ker(f)$与$G’$是同构的
      • $ker(f)=[e]$

编码

  • 概念

    • 哎呀，图片不见了

    • 报文$B^m$

      • 一个有限字母表中字符的有限序列
      • 运算$\oplus:(x_1,x_2,\dots,x_m)\oplus(y_1,y_2,\dots,y_m)=
        (x_1+y_1,x_2+y_2,\dots,x_m+y_m)$
      • 阶数：$2^m$
      • 单位元：$(0,0,……,0)$
      • 每个元素都是自己 的逆元

    • 编码函数$e:B^m\rightarrow B^n$

      • 代码字e(b)
      • 编码函数e是单射的

    • Hamming距离

      • x，y不相同的位置数

      • 编码函数最短距离

        • 所有不同对代码字间距离的最小值
        • 设e为一个群码，e的最短距离是非零代码字的最小权

      • 一个编码函数能够检测k个或更少错误当且仅当它的最短距离至少是k+1

    • 群码

      • 如果$e(B^m)={e(b)|e\in B^m}=Ran(e)为B^n的一个子群$

        • $B_n$的每个子群都是一个阿贝尔群

  • 奇偶校验码H

    • 哎呀，图片不见了

    • 模2布尔积

      • 如果奇数个相应对包含两个1，$C_{ij}$为1；如果偶数个相应对包含两个1，$C_{ij}$为0
      • 哎呀，图片不见了
      • 分配性质$(D\oplus E)F=(DF)\oplus(E*F)$

    • 同态$f_H(x)=x*H,\quad x\in B^n$

      • $N={x\in B^n|x*H=\bar{0}}$是$Bn$的一个正规子群

    • 编码函数$e_H:B^m\rightarrow B^n$

      • $x=e_H(b)=b_1b_2\dotsb_mx_1x_2\dots x_r$
      • 设$x=y_1y_2\dots y_mx_1\dots x_r \in B^n,那么x*H=\bar{0}当且仅当对某个b\in B^m,x=e_h(b)$
      • 推论：$e_H(B^m)={e_H(b)|b\in B^m}是B^n的一个子群$

  • 译码与纠错

    • 译码函数$d:B^n\rightarrow B^m$

      • 满射函数

      • 若b为报文,有$(d\circ e)(b)=d(e(b))=b$

      • 代码字x，接受字$x_t$

        • $x_t$的左陪集$x_t\oplus N={\varepsilon_1,\varepsilon_2,\dots,\varepsilon_{x^m}}\quad(\varepsilon_i=x_t\oplus x^{(i)})$

          • $x_t$到代码字的距离恰好为$\varepsilon_i$的权

          • $\varepsilon_i$是有最小权的陪集成员是$x^{(i)}$是最接近$x_t$的代码字

          • 一个有最小权的元素称作陪集首部

            • 不一定是唯一的

    • 最大似然方法

      • 根据编码函数e确定译码函数d

      • 步骤

        • 确定$B_n$中$N=e(B_m)$的所有左陪集

        • 对于每个陪集，求陪集首部（最小权的字）

        • 确定接受字$x_t$属于N的陪集

          • $B_n$中存在$2^n/2^m=2^r个N的不同陪集$
          • N的陪集形成$B_n$的一个划分

      • 由3得到的陪集首部

        • 计算$x=x_t\oplus \varepsilon$,若$x=e(b),那么d(x_t)=b$，则$x_t$的译码为b

    • 陪集表（译码表）

      • 译码过程

        • 当一个字$x_t$被接收，确定包含它的行，求该行陪集首部并且把它与$x_t$相加，即可得到最接近$x_t$的代码字

        • 构造

          • 第一行为N，其余行为不属于N的其他元素与N异或(N为代码字集合)

      • 简化形式

        • x*H为x的校验子

          • 计算每个陪集首部的校验子

            • 计算接受字的校验子

          • 求接受字所在陪集

            • 计算$x=x_t\oplus \varepsilon$,若$x=e(b),那么d(x_t)=b$，则$x_t$的译码为b
谢谢你请我吃糖果
0%