离散数学

我啥也不会。

直接跳到牌神的离散笔记
或者poria的离散笔记

离散数学结构 第9章 半群与群

9.1 关系及其性质

• binary relation 二元关系
  是集合，一个从到的二元关系就是的子集。

  所以，从到的二元关系的个数就是子集的个数。

  假设有个元素，那么定义在上的二元运算有个。（的子集个数）。

  理解为长为（元素总数）的字符串，每一位都可能是1或0，所有可能的字符串有个。

关系的性质

• reflexive :自反性
  对应任意的都有（即）

  • 元素集合上有个自反关系。

  
  由于所有自反对都在关系里，自反对的存在性固定为1，所有总数除以自反对的总数即可。

  • irreflexive：非自反
    没自反对。

• symmetirc：对称性
  则有。

注意自反算是对称。

• aymmetric：非对称
  没对称。

• antisymmetric：反对称性
  和同时成立，则。

这俩不是对立的:
1.同时存在：只有自反对。
2.同时不存在：关系里既有非自反的对称，又有不对称的。

• transitive：传递性
  ，那么有

• combining relation:关系的合成
  是到上的关系，是到的关系，有，若有，那么

注意：对于关系复合运算，是先算再算。这一点极其反直觉。
但是：对于函数复合运算,是先算再算。这一点符合直觉。
关于这个问题，神说得好：

• 关系的幂：

注意：从右到左运算，矩阵表示的时候别弄错了

• 定理：关系是传递的，当且仅当（二者可以互推）

9.2 n元关系及其应用

• 定义：如果有都是集合，那么定义在这些集合上的n元关系就是的子集。其中是这个关系的域，是这个关系的degree（阶）

• primary key：主键
  如果元组的一个域可以用来唯一地确定这个元组，那么就说这个域是这个元组的主键。

• composite key：复合键
  可以用来唯一确定一个元组的一组域的笛卡尔积。

• extension：关系的外延
  一个关系当前含有的元组。

• intension：数据库内涵
  数据库更持久的内容，包括其属性和名字。

• 运算

  • selection：选择运算
    运算符为。从所有的元组中找出所有符合条件的元组。

  • projection：投影运算
    懒得写了，放图
    

  简单说就是从n个域到m个域，只拿规定的m个域，其他的都不要了。

  • join：连接运算
    懒得写
    

  简单说就是把两个表拼一起，都有的域只取一遍。

9.3 关系的表示

• 关系矩阵

  • (布尔积)

  • 性质表示

    • 自反性：矩阵主对角线上所有元素都为1
    • 对称性：那么（或者同时为0）
    • 反对称性：,和不可以同时为1

注意：并不是，而是。
（即关系是从，更换了矩阵的行和列）

• directer graphs/digraphs：有向图
  • 定义：每个元素代表一个点，有序对为有向弧线
    • vertices/node：顶点/节点
    • edges/arcs：边/弧
    • initial vertex：起点
    • terminal vertex：终点
    • loop：环
      • 形如有序对，从顶点到其自身的一个弧表示
  • 性质表示：
    • 自反性：有向图的每个顶点都有环
    • 对称性：不同顶点之间的每条边都存在反方向
    • 传递性：如果同时有从顶点到顶点的弧，顶点到顶点的弧，那么就有顶点到顶点的弧。
    • 非对称：无双向边无自环
    • 反自反：只有自环没有双向边

9.4 关系的闭包

• closures of relations：关系的闭包

  • 定义：设是一个在集合上的关系，则关于性质的关系闭包是这样一种关系：它具有性质且包含关系，同时是中所有包含且具有性质的关系的子集。

  即闭包不仅是包含关系且具有性质的关系，同时也是这种关系中所含有序对最少的关系。

  • reflexive closure：自反闭包
    在中添加所有不在里形如的有序对即可

  • symmetric closure：对称闭包
    当，则添加

  • transitive closure：传递闭包
    这个是关键，展开讲讲。

如何得到传递闭包

一个概念

• connectivity relation：连通性关系
  常用符号表示，定义如下：
  
  自然，的关系矩阵如下：
  

• 关系的传递闭包就是连通性关系

  这个证明有点意思，这里写一下：
  1.是传递的且，显而易见。
  2.证明是所有包含关系且有传递性的关系的子集：
  先强调一个讲过的定理:如果是传递的，那么。
  现在假设属于传递关系，由于任意，所以作为所有并集的也是的子集。又因为，所以。证明完毕

• 怎么计算

  • 用定义算：连续计算的布尔幂，直到第次幂为止（即布尔幂开始重复为止）。当计算每次幂时，就求出这个幂与所有较小幂的并。当进行到第次幂时（开始重复时），就得到了的矩阵。
    例图：
    

    这种硬算的方法考试会考，所以还是要会

  • warshall’s algorithm：沃舍尔算法

  理解方法1：
  构造时，若第行的第列的元素是1，那么就在保留第行原有所有1的前提下，将第行所有的1按照对应列的方式复制到第行。
  理解方法2：
  列出第行中的1元素的列，
  列出第列中的1元素的行，
  标记为1.
  例图如下，是初始关系矩阵：
  

  这个属于是考试重点，必须得会的那种。
  其实这里的理解方法是抄的，这个图也是偷的，嘿嘿

9.5 等价关系

• equivalence relations：等价关系
  等价关系具有自反性，对称性和传递性。

• 写法表示对于某个特定的等价关系而言，和是等价的元素。

• equivalence classes:等价类

  • 定义：若是一个定义在集合上的关系，那么所有和中元素满足关系的元素的集合被称为的等价类。用表示，若语境下只有一个关系，可以简写称。定义可写作：
    
    如果，叫做这个等价类的representative（代表元）。就是说一个等价类里的任何元素都可以作为该等价类的代表元。

• 定理：设是定义在集合上的等价关系，下面的关于集合中的两个元素的命题是等价的：

  • 套关系的三个性质都可以证出来，不赘述了。

• partition：划分

  • 定义：集合的不相交的非空子集构成的集合，且这些集合的并集就是。

  • 定理：如果是定义在上的一个等价关系，那么的等价类构成的一个划分。反过来给定一个的一个划分，那么同样也有某个等价关系以此为等价类。

  给个例子（从划分到等价类）：
  

9.6 偏序

• partial orderings：偏序
  定义在集合上的关系，如果是自反，反对称且传递的，就称为偏序，集合和其上的关系一起被称为偏序集，记作，集合中的元素被称为偏序集的元素。

等价关系理解成等于，所以左右对称，偏序理解成大于小于，所以不能对称

• 偏序的几个符号：

  • 表示
  • 表示且
    反过来是一个道理，不赘述了。

• 可比性
  如果中元素满足或者，那么可比，否则不可比。
  （即不存在或者）

• totally ordered/linearly ordered 全序/线序
  对于偏序集，中的每一对元素都可比，那么这种偏序集就称为全序集/线序集/chian（链）。称为全序/线序。

• well-ordered：良序
  对于偏序集，如果是全序，且的每个非空子集都有一个最小元素，那么就称这个偏序集是良序集（well-ordered set)。

• the principle of well-ordered induction：良序归纳定义
  不好解释，书上翻译也不好，直接放英文版。
  

• lexicographic order：字典顺序
  
  要求或者.

Hasse Diagrams

把这个单列出来是因为我刚发现我把这玩意儿忘干净了。
赶紧瞅瞅。

• covering relation：覆盖关系
  对于偏序集,若且不存在。则称被覆盖。覆盖的有序对称为的覆盖关系。

• 构建哈塞图
  在用有向图表示关系的基础上，去掉所有自环，传递，对称，只留下覆盖关系，箭头向上。
  如：
  

  • maximal and minimal elements：极大元和极小元
    极大元不小于这个偏序集中的所有元素，极小元不大于这个偏序集中的所有元素。
    • greatest element：最大元。大于偏序集中所有其他元素。唯一存在。
    • least element：最小元，小于偏序集中的所有其他元素。唯一存在。
    • upper bound：上界。若是偏序集的子集，若对于所有都有，则称是子集的一个上界。
    • lower bound：下界。若是偏序集的子集，若对于所有都有，则称是子集的一个下界。
    • **LUB(least upper bound)**：最小上界
      **GLB(greatest lower bound)**：最大下界
      顾名思义。不赘述了。

• lattice：格
  若在一个偏序集中，对于任意两个元素，都可以找到它们的最小上界和最大下界，则称这个偏序集为一个格。
  给个例子：
  
  其中是格，不是格（中{}就有两个最小上界）

• topological sorting：拓扑排序

  • 定义：从一个偏序构造一个相容的全序。
  • compatible:相容的
    只要就有，那么称偏序和全序是相容的。

    这里的和分别泛指某种偏序关系和某种全序关系。

  • 拓扑排序的步骤：
    简单来说就是一直选极小元素拿出来，直到只剩下一个元素，然后把这些元素按照拿出来的顺序用连接起来。
    如果有多个极小元素怎么办？
    那就随便挑一个拿出来。
    给个例子：
    

离散数学结构 第九章

9.1 再论二元运算

• A binary operation on a set . 集合A上的二元运算。
  定义为一个处处有定义的函数
  可以用来表示。
  • 性质：所形成的每个有序对都对应一个中的元素，且仅对应一个元素。由于都属于，所以可以说是closed（封闭）的
    但中的每个元素可以被多个有序对对应，且不是每个元素都会被对应。（即不满足单射满射）
  • 关于上的binary opration有多少种，合适的理解是构造的表格，表格中的每个格子都有种填法。所以共有中运算。

注意：和binary relation（二元关系）进行区别， 一个例子就是定义在上的binary relation有个，而定义在上的binary operation有个。（为中的元素个数）

• 二元运算的性质
  • commutative . 可交换的。
    • 满足交换性，则其表关于主对角线对称。
  • assoative . 可结合的。
  • idempotent . 幂等的。

9.2 半群

• semigroup . 半群。 非空集合和定义在上的可结合的二元运算。

有时可以用或者表示半群。

若不可结合则成为groupoid（广义群）。即其仅是封闭的但不可结合。

• free semigroup generated by . （由产生的）的自由半群。
  设为非空集合，是中所有元素的所有有限序列的集合。则自由半群是定义在 上，运算为的半群。

  理解成是数组，然后是所有中元素组成的有限字符串的集合。运算就是连接字符串的函数（比如strcat）

• monoid 幺半群。具有identity（单位元）的半群。

  • identity 单位元 满足。

    即幺半群封闭，可结合且具有单位元。

• subsemigroup 子半群。 令为一个半群，为的一个子集，若在运算*下是封闭的，则称 是的子半群。

  证明子半群，一般是证明其封闭性，而在其上的可结合一般是默认的。
  但不排除有些神经病题目里，都不是的子集的情况。

• submonoid 子幺半群。沿袭上面的定义，如果是一个幺半群，且单位元为，那么如果,则称是的子幺半群。

  即和的单位元是同一个。
  是其自身的一个子幺半群

• powers of . 幂
  假设是一个半群，，对于任意，我们依据递归的方式，定义幂如下

  ，且当是幺半群时，有。

  根据这个定义，我们可以认为：

  如果都是非负整数，那么

  同时也可以得到以下两个定理。

  • 如果是一个半群，，，那么 是 的一个子半群。
  • 如果是一个幺半群，， 或 ，那么 是 的一个子幺半群。

  注意：这两个定义就为我们指明了怎么去找一个半群的子半群或者子幺半群。

  找子半群：
  1.将半群的任意一个元素添加进集合中，然后添加该元素的幂次
  2.重复步骤1，添加新加入元素的幂次，直至没有新的元素被添加进来，则得到了一个子半群。
  找子幺半群：
  1.将单位元添加进集合
  2.将半群的任意一个元素添加进集合中，然后添加该元素的幂次
  3.重复步骤2，添加新加入元素的幂次，直至没有新的元素被添加进来，则得到了一个子幺半群。

  同构与同态

• isomorphism .同构。
  有半群，，如果函数是个双射函数，同时,那么我们说，是isomorphic，是isomorphism，符号表示为。

显而易见也是同构（isomorphism），不赘述了。

证明函数是同构：

• 先证明这个函数是单射的，即当时,则。
• 再证明这个函数是满射的，即映射域中每个都有对应的。
• 证明。

证明一个函数是同构按照上述步骤即可。但若要证明两个半群是同构的，则要求在半群之间构造一个同构。
显然，这个看点子，没想到那就是真的想不到了。

关于简判两个半群是否同构：

同构指的是两个半群的结构是一致的，那么可以选择将两个半群的运算表画出来。
如果用对应元素替代后，得到的表完全一致，则认为这两个半群同构。

根据上面这一大堆，显然，其中是的单位元，是的单位元。
所以与幺半群同构的只能是幺半群。

• homomorphism 同态。
  当的函数满足，则是同态。

是逊版的同构，若和同态的，那么中多个元素可以对应同一个中元素，中的某个元素也可以不与任何中元素对应。

• homomorphic image . 同态像。满足满射的同态。

如果的是一个同态像，那么有（同样的，是的单位元，是的单位元。）
之所以要求同态像，是因为只有满射时，才可以保证 对于中任意元素都成立。若中有某一元素不属于这个映射，自然该元素可以和不满足上式，那么也就不是中单位元了。

• 沿袭定义，是同态像，若是的子半群，那么是的子半群。

• 沿袭定义，是同态像，若是交换半群，那么是交换半群。

以上两条均要求是同态像（即满射）,均是为了保证映射包含了中所有元素，才能对中所有元素成立，从而对成立。

9.3 半群的积和商

本节介绍了两种由已有半群得到新半群的方法。

方法一：做积
若和是两个半群，那么是一个半群。其中理解为

自然，若是幺半群，是幺半群，也是幺半群，单位元是

方法二：做商

在考虑方法二之前，先说点必要知识。

• congruence relation 同余关系。
  半群上的一个等价关系（自反，对称，传递）如果满足 和 推出

证明同余关系的步骤：

• 先证明它是一个等价关系；
• 再证明可以由和推出。

现在我们把第九章的知识引进来，再堆上几个定义。
这玩意儿怎么这么多定义，捏妈妈的

• 第九章提到的等价关系可以定义集合的一个划分，而这里的等价关系可以定义半群的一个划分。
  我们用或者表示包含的等价类，表示所有等价类的集合。

• quotient semigroup/factor semigroup . 商半群/因子半群
  现在我们在上定义一个运算,则其是的一个函数。而理解为 。那么我们称半群就是quotient semigroup/factor semigroup。

推论：半群是幺半群，那么其商半群也是幺半群，且其单位元为。

• natural homomophism . 自然同态。

半群半群的一个函数，那么显然是一个同态像，这时也可以称为称为自然同态。

• fundamental homomorphism theorem . 同态基本定理
  设是一个半群到半群的一个同态像。又令存在等价关系，其对于中的和满足当且仅当。
  那么我们可以得到：
  • 是一个同余关系。
  • 半群和商半群是同构的。

很长一串，让人没有阅读兴趣。可以这么理解：首先是同余关系显而易见，然后可以认为同余关系把原本中存在的多对一的多个元素，合并成了一个元素，从非单射变成了单射，因此就从原本的同态像变成了同构。
即
重点在于商代数和同余关系是可以互相转化。知道这个就差不多了。

图解：

其中和是同态像，是同构。

9.4 群

• Group . 群。
  是其中每个元素都有inverse的幺半群。

  的逆元（inverse）满足

即群满足以下几点：
1.满足结合律。
2.有单位元。
3.封闭。
4.每个元素都有且仅有一个逆元，对应的逆元在G中。

• Abelian group . 阿贝尔群
  满足交换律的群。

• cancellation property . 消去性质
  先设是一个群，然后都是中的元素。

  • = 得到
    (left cancellation property 左消去性质)
  • = 得到
    (right cancellation property 右消去性质)

• 不知道是个啥但反正是个定理

• 唯一解

  • 方程在中有唯一解
  • 方程在中有唯一解

关于证明（仅第一个式子的证明，第二个式子同理即可）：
证明有解：必定为其一个解。
证明唯一：若有两个,都是解，则，左消去律完了之后，两个解就相等了。

• multiplication table . 乘法表

需要提的一点是，在群的乘法表中，每行每列，所有元素都会出现且每个元素仅会出现一次。这一点和唯一解的性质是吻合的。

• finite group . 有限群
  字面意思，有限群的order（阶）是其中元素的个数，表示。

• 讨论一下阶分别是1，2，3，4的有限群。

  • 一阶群没什么好说的，就一个单位元

  • 二阶群
    
    只有一种形式，也没什么好说的。

  • 三阶群
    
    同样只有一种形式，即右图这种

  以上的三个群都是阿贝尔群

  • 四阶群

  

  这里一共给了四种不同的四阶群，且都是阿贝尔群。
  但需要注意的是表给的三个群实际上是同构的。

  证明：将中的在运算栏里的行和列位置对换，中的在运算栏里的行和列对换，就可以得到和一致的图了。（最多再改下字母）
  显然不和其余三个同构，因为其任意元素和自身运算都得到单位元，其余三个显然没有这个性质。

  由给出的群称为克莱因四元群，记为,并且其是最小的非循环群，剩余三个称为。

  • 循环群：

    三角对称群

首先给个图

接下来我们考虑转置运算
首先，我们定义分别为将图形逆时针旋转

然后是关于进行反射的运算。

解释一下每个图里转置运算的含义
以为例：
第一列：，即将为1的点移动到目前为2的点的位置
第二列：，即将为2的点移动到目前为3的点的位置
第三列：，即将为3的点移动到目前为1的点的位置
所以表现出来的效果是逆时针旋转

我们将所有这些运算都算进一个集合，然后引进一个运算*（依次序运算）：

注意：这个运算是依次序运算，和复合运算的运算顺序不同。
我们称这个群为，单位元是。

然后我们就可以发现一个非常奇怪的地方，如果按照是逆时针旋转，是逆时针旋转的方法进行计算，得到的结果和乘法表并不一致。
以和为例，如果依照旋转，那么应该分别得到下图中第一行和第二行的内容：

可以看到，这两种运算得到了相同的答案，但这和乘法表的内容是明显相悖的。
所以这里要指出一个可能犯的理解上的误区，这里的转置运算并不是旋转，而是点与点的交换。换句话说，在第二行的地方，我们依旧执行，，,而不是旋转三角。
这里本来应该有一张正确的过程图，但我懒得画了，理解一下我的意思就行

犯这种错误理解的主要原因，是中文翻译写的确实剑走偏锋。
要是没犯这个错误的话，那恭喜你浪费了阅读这些东西的几十秒。

顺便，这个群是教材提到的第一个不是阿贝尔群的例子

• subgroup 子群
  设是一个子集，使得：
  • 里有的单位元
  • 是封闭的
  • 中有其所有元素对应的逆元
    是的一个子群。

找子群：
1.将单位元添加进集合。
2.任意加入一个非单位元的元素，同时加入该元素的幂次和其逆元。
3.重复步骤2，把新加入的元素的幂次和逆元加入进集合，直至没有新的元素可以被添加进来，那么我们就得到了一个子群。
类似于找子幺半群，但注意要将逆元也添加进来。

• trivial subgroups . 平凡子群
  群的平凡子群就是其本身，和其集合为的子群。
  //不知道这个定义有啥用。

• 群的同构与同态

  • 不同阶的群一定不同构。
  • 同态：
    设和是两个群。是一个同态，那我们可以得到以下的关系。
    • ()
    • 如果,则

      就是说的逆对应的逆。

    • 如果是的一个子群，则是的一个子群。

  证明群的同态和同构，和半群的差不多

  9.5 群的积和商

• 群的积
  设和是群，那么的二元运算理解为。

  这个定义里没加运算符，脑子里过的时候自己记得加上

• 。指的是是所有模的余数的集合在加法运算下的群。比如说的集合就是

  • 我们定义如图：
    
  • 定理：当且仅当互素时，有

    推广: 如果是群，那么有也是一个群

• 群上的同余关系（和半群的一致）
  设是群上的一个同余关系，那么半群是一个群，其中在上的且满足。

推论：

• 如果是上的一个同余关系，那么定义为的是半群到半群的一个同态。
• 如果是一个同态像，那么当等价关系在上被定义为：当且仅当的时候，我们可以得到：
  • 是一个同余关系
  • 由定义的函数是的一个同构。

说白了这个推论就是把同态和同态基本定理套到了群里头。

• coset . 陪集。
  陪集分为left coset（左陪集）和right coset（右陪集）。
  定义如下：
  设是的一个子群，那么由决定的中的左陪集是集合,同理，右陪集就是集合。

  • normal subgroup 正规子群
    如果对于中所有都有，那么我们说是的一个正规子群。

  注意: 正规子群并不要求对于中的任意元素都有，而是只要对于任意的，中都有一个元素满足即可。（可为本身）

  • 当为中一个元素时
    如果，那么，当然，同时也有。
    

    关于这一点的证明：
    以为例，我们只需要证明和同时成立即可。
    证明：这个非常明显，因为作为群是封闭的，所以对于任意的，，有，因此。
    证明：由上面的证明可知，对于任意的，，都有，那么同时也就有（因为是群，所以存在且唯一）。通过这一点，我们不难发现，当确定时，和也就一一对应了（类似于单射）,又因为和的数量是相等的，那么自然每一个都有且只有一个对应（类似于满射和双射被同时证明了）。

  因此寻找陪集的时候，当时，不用计算或者，因为结果总是。

  • 如果是个阿贝尔群，则其所有子群都是正规子群。

  这一点显而易见。

  • 设是上的一个同余关系，，即是在定义下的包含单位元的等价类，我们容易得知是的一个正规子群。且。
    //其实我觉得这个定理放在这没啥意义而且显得突兀。但因为教材上显得太突兀了，所以我把这句话写在这里给你看看。

  而从上面的这个定理，我们不难联想到商群实际上就是由的所有左陪集（或右陪集）所组成的，且群中的运算定义为：
  
  并且定义为的是到的一个同态像。所以我们也把写成。

  就是也是商群的意思。

  • 设是的一个正规子群，是上的下述关系：当且仅当。
    那么我们可以推断：

    1. 是上的同余关系。
    2. 是关于的等价类，其中是的单位元。

    证明同余关系：
    1.关于是等价关系的证明省略，自证。
    2.设,，那么我们需要证明，即。
    因为是正规子群，所以在中存在元素满足。
    现在取,再在左右两式左边都与相乘。得到。
    那么左边为需要证明的部分，右边因为群的封闭性而属于。同余关系得证。

    证明是：
    ，如果,那么且,即和是等价类。对于中所有元素都满足这一点。所以是。

• kernel . 核。
  设是从群上同态像，则有核且写作，定义为：
  

  就是把所有映射为的元素提出来做了个集合。

  则有

  • 是的一个正规子群。
  • 商群和同构。

  易证就是在对应同余关系下的。所以这两点显然成立。

  离散数学结构 第十一章 群和编码

  鸡掰。这一块没咋看懂。

  11.1 二元信息码和检错码

省略掉又臭又长的引入，11.1开头实际上给了一大堆定义：

• 设定集合,群设定成在模2加法运算下的集合，即群设定为。
  模2运算如下图：
  

• 是一个运算为的群，其中定义为：
  
  注意有个元素，所以其阶为。

可以理解为中的元素是长为的01字符串的所有可能情况，由于每一位都可能为0或1，所以共有个元素。

注意：中的单位元是,每一个元素都是其自身的逆。

• encoding function 编码函数
  一般表示成单射函数
  • code word 代码字
    ,则称为的代码字。（是一条01字符串）

代码字的传输过程如图：

• weight 权
  ，中1的个数被称为的权，记作。

• parity check code 奇偶校验码
  构建一个编码函数：
  若（是01字符串，到是0或1），定义，其中：
  
  那么称这个编码函数是奇偶校验码。

  奇偶校验码的权是偶数，如果传输中有奇数个错误就可以被检测，偶数个检测不了。

• Hamming distance 海明距离
  表示为（不一定是这个符号，我只是找不到拿这个凑合一下），指的是的权。即和中的个数。

• minimum distance 最短距离
  编码函数的最短距离指的是不同对代码字之间距离的最小值，即
  

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

理解为如果出现的错误个数小于最短距离，那么得到的错误的字符串不可能属于，所以可以发现错误。假如错误的位数超过了最小距离，那么就有可能使，就可能检测不出错误。所以最短距离至少是才能使可检测错误个数小于等于。

• group code 群码
  如果编码函数满足是的一个子群，那我们称这个编码函数是一个群码。

这就要求：
1.有中的单位元，即。
2.每个元素都有对应的逆元。（如果满足了第一条，那么每个元素都会是其自身逆元）
3.是封闭的。

以及因为是阿贝尔群，所以其所有子群都是正规子群。

• 设是一个群码，那么的最短距离是非零代码字的最小权。

因为对于任意，。即中任意两个元素的海明距离都会是另一个元素的权。

• 关于模2的布尔积的定义：
  

就是布尔积那一套，但区别在于与完后按照1的数目模2。

• 
  和满足分配律。

• 设是非负整数且,是一个布尔矩阵，那么函数定义为：
  
  是从到的一个同态像。

  • 是的一个正规子群。
    接下来的讲的是如何定义让其可以用于验错。

• parity check matrix 奇偶校验矩阵
  定义如下：
  
  这个矩阵共有行，列。
  用定义一个编码函数，,其中到满足：
  
  那么可以得到如下定理：

  • 设，那么当且仅当对某个。

    即当时，传输过程中没有发生差错。

该定理的证明如图：

• 由上面的一大堆，稍微绕一下就可以知道：
  
  因为同态像的核也可以认为是一个正规子群，所以显然也是一个群码。

11.2 译码和纠错

• decoding function associated with e . 与e有关的译码函数
  ，然后有满足无噪声时，,其中是上的恒等函数。（）

• correct k or fewer errors . 矫正个或者更少的错误
  在的传输有个错误及以下，译码函数可以把转换成原本对应的。就说数据对矫正个或者更少的错误。

• maximum likelihood decoding function . 最大似然方法(最大似然译码函数)

简单解释如下：
有，从的所有代码字中挑出代码字使得，有，则让。

• 定理：当是一个的编码函数，是与有关的最大似然译码函数，那么可以纠正个或者更少错误当且仅当的最短距离至少为

如果的最短距离小于，那么有可能出现同时与多个的距离相等的情况。

• coset leader 陪集首部

设是中的代码字的集合,中有个元素。现传输得到的，其左陪集是
其中,那么的权就是和的海明距离。若权最小则最接近，称是陪集首部。

• 构建最大似然译码函数

译码表(decoding table)的构建
1.先把按顺序列到第一行
2.取不在第一行中，且权为1的最小的中的元素，计算和中每个元素的异或值得到左陪集，写到第二行。
3.重复步骤二，但要求不在以上所有行中，得到第三行
4.如果权为1的写尽，则写权为2的，且依旧要求不在上述行中。直到表中包含了中所有元素
比如下图就是一个译码表：

• syndrome . 校验子
  对于一个编码函数，如果我们有奇偶校验矩阵：

，就是的校验子。

• 定理：,属于中的相同左陪集当且仅当

所以可以通过校验子来缩小译码表：

实际上只是缩小了译码表，但要算的东西多了一堆。

简单来说就是算一下的校验子，看看和哪个陪集首部一样，比如说和一样，那就通过得到中对应的代码字，这时若有，那么。

但题目一般就是只给一个奇偶校验矩阵，要你写陪集首部和校验子。这个时候就不得不先算出，然后列出译码表得到陪集首部，之后一个个算出校验子。
巨麻烦。

十一章后面不讲。没了。

离散数学第八章 高级计数基础

8.2 求解线性递推关系

感觉不用理解，记解法就完事了，这个应该出不了证明题。

求解常系数k阶线性齐次递推关系

• 一个常系数的阶线性齐次递推关系是形如：
  
  的递推关系，其中是实数，且。

• 特征方程和特征根
  对于阶线性齐次递推关系，有使得。
  所以原递推表达式可以写成
  
  这个方程称作特征方程，被称为特征根。

如果特征方程有不相等的根：

• 定理1
  对于递推关系，如果其特征方程有两个不相等的根，那么可以得到，其中是常数。

• 的求解
  有初始条件，则
  
  
  由以上两个式子可以解出。

如果特征方程有相同的根：

• 定理2
  对于递推关系，如果其特征方程只有一个根，那么可以得到，其中是常数。

• 对于的求解：
  有初始条件，则
  
  
  由以上两个式子可以解出。

一般情况：

• 定理3：无相同根
  设都是实数，那么假设特征方程
  
  有个不相等的根，那么序列是递推关系
  
  的解，当且仅当
  
  如果,其中都是常数。

• 定理4：有相同根
  设都是实数，那么假设特征方程
  
  有个不相等的根，重数分别为那么序列是递推关系
  
  的解，当且仅当
  
  如果,其中都是常数。

求解常系数线性非齐次递推关系

不在考纲里，不写。

8.4 Generating Functions

生成函数就是形如

这样的函数。

• 定理1
  
  这个定理说明的是生成函数的相加和相乘要怎么算
• 定理2
  
  
  这俩说明了广义二项式的形式，以及可以与广义二项式之间相互转换。
  这个相互转换有点重要，是后面用生成函数求n元素集合k组合数的基础。
• 常用的生成函数
  
  
  
  
  这几个生成函数用的概率比较大而且不能被其他生成函数推导出来。
  其中第一个和第三个可以推出大部分的生成函数。

生成函数解决计数问题

这种问题一般列出生成函数的形式就可以。
一般步骤就是列出每个变量对应的约束条件下的可能性，然后所有这些变量的可能性相乘，最后得到的对应的所需要的结果的系数，就是所有这些变量的组合可能总数。

• eg1：,
  给出的生成函数表达式为，全部相乘之后指数为17的系数就是所有组合可能。
• eg2：1美元，2美元，5美元买东西，不考虑纸币次序。