画布 1
离散数学
  基础知识
    集合
      性质
    序列
      将对象以一定次序列举出来
  逻辑
    命题
      或者为真或者为假而不是两者同时成立的一条陈述句
      量词
        全称量词
        存在量词
      命题变量
      逻辑联结词
        条件命题
        合取
        析取
        当且仅当
      命题运算
      重言式
        命题变量所有可能值都为真的命题
      谬论
        命题变量所有可能值都为假的命题
    证明方法
      逻辑表示：
        q从逻辑上由p得到
        通过证明规则推理是一个重言式证明
        假言推理
        间接方法：逆否命题与其等价
        反证法
        数学归纳法
        强归纳法
  计数
    排列
      乘法原理（依次完成）
    组合
    鸽巢原理
      如果n个鸽子被分配到m个鸽巢中且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 x1，x1 R x2，，，的一条有限序列
          表示R中存在从x到y长度为n的一条道路
          表示R的连通关系
      性质
        自反和非自反
          自反：
            Dom(R)=Ran(R)=A
          非自反：
        对称和非对称
          对称：
            不是对称的：
          非对称：
            不是非对称的：
          反对称：
            不是反对称的：
      传递关系
        推广：
      等价关系
        如果一个关系是自反的、对称的、传递的
        如果F是集合A的一个划分，那么F可以构造A上的一个等价关系
        等价类
          与a有关系的所有元素为a的等价类
      闭包
        包含关系R且满足某种性质的关系S
        闭包S为所有包含R且具有性质P的关系的子集
        自反闭包
        对称闭包
        传递闭包
          沃舍尔算法：将第k行加到第k列有1的行上
      合成
  代数结构
    由对象集合及运算的数学结构，称为代数系统
      二元运算
        结合、分配、吸收、幂等、交换、封闭
      特殊元
        幺元
        零元
        逆元
        都是唯一的
    同态
      象的积等于积的象
    同构
      当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是同构的
  序
    偏序集
      偏序R：自反、反对称、传递（如≥、≤）
      a,b可比：
        偏序集中每一对元素不必都是可比的
      全序集
        如果一个偏序集中每一对元素都是可比的
      偏序的有向图中没有长度比1大的环
      哈塞图
      拓扑排序
        构造一个全序的过程
      极值元
        极大元：A中不存在比它大的元
        极小元：A中不存在比它小的元
        最小上界：B为A的一个子集，LUB（B）是a的最小的上界
        最大下界
    格
      集合中任意两个元素所组成的子集都有最小上界和最大下界的一个偏序集
      同构的格
    布尔代数
      布尔多项式
  群与半群
    半群
      非空集合S以及一个定义在S上的可结合的二元运算*
        如果*是一个交换运算，则称半群为交换半群
      幺半群
        具有单位元的半群
      子半群
        T为S的一个非空子集，ab属于T，a*b也属于T
      群的同构
      半群的积
        同余关系
      同态象
        f为一个满射的S到T的同态，T是S的同态象
    群G
      具有单位元e的幺半群
      阿贝尔群
        满足交换律的群
      性质
        G中每个元素a在G中仅有一个逆元
        消去性质
        ax=b,ya=b在G中有唯一解（a,b为G中元素）
        阶不相等的两个群不可能是同构的
      乘法表
        任意行列中不能存在重复的元素，必须在空格中填e
      三角形对称群
        不是阿贝尔群
        n个元素的所有置换的集合在合成运算下是阶为n！的群，称为n个字母的对称群（Sn）
        元素是集合的置换的集合
        运算为“依次序定义”
    子群H
      条件
        包含G的幺元
        a，b属于H，ab也属于H
        元素a的逆元也属于H
      正规子群
        定义
          对于G的所有元素a，有左陪集等于右陪集
        设R是G上的一个同余关系，H=[e]（包含单位元的等价类）,H为G的一个正规子群
          [a]=aH=Ha
      核ker(f)
        G上的同余关系的等价类总是G的某个正规子群的陪集
        若f是G到G‘的满同态，f的核为
          ker(f)是G的一个正规子群
          商群G/ker(f)与G’是同构的
          ker(f)=[e]
    编码
      概念
        报文
          一个有限字母表中字符的有限序列
          运算
          阶数：2^m
          单位元：(0,0,……,0)
          每个元素都是自己 的逆元
        编码函数
          代码字e(b)
          编码函数e是单射的
        Hamming距离
          x，y不相同的位置数
          编码函数最短距离
            所有不同对代码字间距离的最小值
            设e为一个群码，e的最短距离是非零代码字的最小权
          一个编码函数能够检测k个或更少错误当且仅当它的最短距离至少是k+1
        群码
          如果
            Bn的每个子群都是一个阿贝尔群
      奇偶校验码H
        模2布尔积
          如果奇数个相应对包含两个1，Cij为1；如果偶数个相应对包含两个1，Cij为0
          分配性质
        同态
          是Bn的一个正规子群
        编码函数
          设
          推论：
      译码与纠错
        译码函数
          满射函数
          b为报文
          代码字x，接受字xt
            xt的左陪集
              xt到代码字xi的距离恰好为varepsilon的权
              \varepsilon是有最小权的陪集成员是xi是最接近xt的代码字
              一个有最小权的元素称作陪集首部
                不一定是唯一的
        最大似然方法
          根据编码函数e确定译码函数d
          步骤
            确定Bn中N=e(Bm)的所有左陪集
            对于每个陪集，求陪集首部（最小权的字）
            确定接受字xt属于N的陪集
              Bn中存在
              N的陪集形成Bn的一个划分
            由3得到的陪集首部
              计算
                若
                  xt的译码为b
          陪集表（译码表）
            译码过程
              当一个字xt被接收，确定包含它的行，求该行陪集首部并且把它与xt相加，即可得到最接近xt的代码字
            构造
              第一行为N，其余行为不属于N的其他元素与N异或
            简化形式
              x*H为x的校验子
                计算每个陪集首部的校验子
                计算接受字的校验子
                求接受字所在陪集
                  计算
                    若
                      xt的译码为b