画布 1
离散
  2一阶逻辑
    概念
      个体词
        5，x,小王，小李
      谓词
        ....是无理数
        ..与...同岁
          符号化为H（a,b)
        ...与...有关系
          符号化为G（a,b)
        0元谓词
          不带个体变项的谓词
            f(a)或G(a,b)
          个体常项
            a,b,c...
          个体变项
            子主题 1
        特性谓词
          M(X)
            在没有确定的个人域时，都是M(X)∧F（x)
      量词
        ∀
          ∀A（x）→B
            如果,对任意x,A（x）为真；那么B为真；
              如果该班的所有同学,都成绩优秀时；那么该班一定会被评为优秀班级.
          ∀x（A（x）→B）
            对任意x：如果A（x）为真,那么B为真；
              对于本班中的任何一个同学，如果他成绩优秀，那么该班就会被评为优秀班级。
                存在
            ∀x（¬A（x）∨B）=∀x（¬A（x））∨B=¬∃x（A（x））∨B=∃x A（x）→B
          全称量词对析取没有分配律
            有张三、李四2人,张三会百唱歌但不会跳舞,李四不会唱歌但会跳舞。度
“所有人或者会唱歌或者会跳舞”是对的，“所有人会问唱歌或者所有人会跳舞”是错的。
所以：全称量词对析取没有分配律。
              是错的
        ∃
          有坑
      公式
        子主题 1
      命题符号化
        在一阶逻辑符号化时，存在量词后用合取式，而全称量词后用蕴含式
          ∃用∧，∀用→
          在需要使用特性谓词限定个体域中的个体时，全称量词对应的特性谓词后面应该使用蕴含连接词。
同理，在需要使用特性谓词限定个体域中的个体时，存在量词对应的特性谓词后面应该使用合取连接词。
    杂记
      f的解释
      规则
        置换规则
        换名规则
      出现
        约束出现
        自由出现
        指导变元
      闭式
        没有自由出现的个体变项
        闭式在任何解释下都变成命题
    等值式
      量词辖域收缩与扩张等值式
        容易理解的
        子主题 2
          ∀x（A（x）→B）=∃x A（x）→B
          ∃x （A（x）→B）=∀xA（x）→B
        A（x）→B
      量词否定等值式
        ¬∃x A（x）→∀x¬A（x）
        ¬∀xA（x）→∃x ¬A（x）
      量词分配等值式
      消去量词等值式
    一阶逻辑等值演算
      一阶逻辑前束范式
        前束范式不唯一
        有→一定要收缩扩招
          ∀xF（x）→∃x G（x）=∃y∃x F（y）→G（x）
          但是∀x（A（x）→∃y G（y））=∀x∃y（A（x）→ G（y））已经扩到了
    逻辑有效式一定是可满足式
  1命题逻辑
    命题与联结词
      真假命题
        悖论不是命题
      以符号形式写出命题
      联结词
        ∧
        V
          排斥或
          相容或
        →蕴含
          q→p的情况
            只有...才
            除非... 否则非p
            假如没有...就没有
            只有，除非，假如 都是必要条件
          仅当
            p→q
        等价联结词
          P
            Q的情况
              当且...仅当
        与非联结词
            true
              当且仅当不同时为真
                ￢（p∧q)
        或非联结词
            true
              同时为假
                ￢（pVq)
      自然语言转化成逻辑语言
      公式：命题变项和联结词形成
        重言式
        可满足式
        矛盾式
    命题逻辑等值演算
      命题逻辑
        重言式
        等价等值式
          A→B)∧(B→A)或
          （r∧s)V( ￢r∧￢s)
          （rV￢s)∧( ￢rVs)
        有且只有一个人去
          （r∧￢s)∧( ￢r∧s)
      等值演算
        德摩根律
        分配
        结合
          （A∧￢B）∧B=A∧（￢B∧B）=0
        幂等
        蕴含等值
          A→B ⇔ ￢A∨B
        假言易位
          A→B=￢B→￢A
        吸收律
          Av(A∧B)=A
            A∧(AvB)=A
        等价否定等值式
    范式
      只能有┐∨∧
        不能有→，┐只能出现在（）内
          析取范式
            ∨
              但它由每个合取简单式构成
            主析取范式
              m1Vm2Vm5=Σ（1,2,5）
          合取范式
            主合取范式
              M1∧M2∧M5=Π（1,2,5）
            ∧
              由每个简单析取范式构成
        m12是极小项1100，大写的M是极大项,M13是0010，
          极小项是成真赋值
    推理
      推理定律
        分配律
          (AvB)∧(C∧D)
        假言三段论
          （A→B)∧（B→C)→（A→C)
        析取三段论
            已知条件1 或 条件2
那么利用条件2的否定可以得到条件1成立
比如：我今天去游泳 或者 去爬山
如果我说,我今天不去爬山
那么肯定知道我今天要去游泳
        假言推理
          （A→B)∧A→B
            如果我刷牙，那我肯定用了牙刷，如果我刷了牙。所以用了牙刷
        拒取式
          （A→B)∧￢B→A
            如果我刷牙，那我肯定用了牙刷，如果我没用牙刷。所以我肯定没刷牙
        构造性二难
          如果我刷了牙，那我用了牙刷，如果我是男人，那我有胡子。如果我刷了牙或者是男人，那么，我用了牙刷或者有胡子
            （A→B)∧（C→D）∧（AvC)→(BvD)
            假言推理的升级版
        破坏性二难
          如果我刷了牙，那我用了牙刷，如果我是男人，那我有胡子。如果我没有用了牙刷或者有胡子。，那么，我没有刷牙或者是男人
            （A→B)∧（C→D）∧￢(BvD)→￢（AvC)
        合取引入
          结论中可以引入前提条件，毕竟前提条件都为真,如（PvQ)是前提
            如r合取引入
              r∧（PvQ)
        化简律
          r∧s
            r
        附加律
        想不起来就用真值表
      推理形式是否正确
        有效推理和能推出正确结论的推理并不度相同。有效推理仅指形式正确，并不保证结版论一定正确。在演绎推理中，要保证结论正确，必须同时满足两个条件：1、有效的推理形权式，2、前提内容真实。而有效的推理形式并不涉及前提内容的真实性
          辑学中有效的推理是指推理的形式符合规则，即前提与结论的联系方式合乎推理的规则
          推理无效就要去证明 前提真结论假这种情况存在
        推理正确，当且仅当为重言式
          等值演算法
          真值表法
          主析取范式法
          观察法
          CP规则附加前提证明法Conclusion Premise
            结论里的蕴含式移到前提，结论只留一个
          归谬法
            结论的否定
              引入条件，结论为0
          归结法
            结论的否定
            前提全改为简单析取式
            引入条件，结论为0
              统一写归结，引入，不写析取三段论之类的
          前提条件可以用好几次
            如P多次引入，前提都是真的，当然可以多次引入
          ES(存在指定规则 Exstential Specify)
UG(全称推广规则 Universal Generalize)
          A→B前提条件A为真时，B为真。推理正确。推理条件都不正确，结论为真，怎么可能叫推理正确。常识
        推理形式
    子主题 6
      x+2=7不是命题，是真值不确定的陈述句
      长江和黄河是中国最长的两条河是简单命题
        主语：长江和黄河 谓语:是中国最长的两条河：
        如果改为长江和黄河都是是中国最长的两条河是复合命题
        与“连结的是主语
          李梅和李雪是姐妹：
            符号化为：p
  集合基础知识
    集合
      空集是一切集合的子集
      幂集
        P(A)=｛Φ,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}｝
    德摩根律
    对称差
    A=Ø无元素，B={Ø}有一个元素Ø
      属于关系指的是元素和集合之间的关系
    ⊂
      包含关系指的是集合之间的关系,例如集合A={1,2,3}集合B={1,2},那么A就包含B
    C
      复数集
    0是偶数
    |A|=集合A上的元素数目
      文氏图
    子主题 11
    T规则
    偏序的逆也是偏序
  7代数系统
    定义
      零元
        乘法的0元是0
      1是乘法群幺元，0是加法群幺元，幺元乘以任何x都等于x
    二元运算
      加法，乘法
    代数系统
      半群
        子半群，他的子集
          一个群是另一个群的子群，要证明任意两个元素a.b属于子群，且两元素乘积和a逆属于子群
            子主题 1
      独异点（单元半群）
        含有幺元的半群
      群
        对任意x都含有逆元的独异点
          x^-1是逆元，x。x^-1=e 如加法群中，3的逆元是-2
      各种群
        平凡群
          只有单位元的群如<{0},+>
        循环群
          U(9)U(9) units组成的一个群。{1,2,4,5,7,8},{}里面的数全部与9互质。
相应的4的units，U(4)U(4) 是{1，3} ，4 以内只有1，3与4互质。
2是9的生成元(generator),因为
211 mod 9 = 2
222 mod 9 = 4
233 mod 9 = 8
244 mod 9 = 7
255 mod 9 = 5
266 mod 9 = 1
          定义为若—个群G的每—个元都是G的某—个固定元a的乘方，则称G为循环群，记作G=(a)，a称为G的—个生成元
          3
        交换群
          阿贝尔群（Abelian Group），又称交换群或加群.设<G,☆>是群，如果运算☆知满足交换律，
a ☆ b = b ☆ a
则称<G,☆>是交换群
例.<Z,+> , <Q,+> , <R,+> , <Zn,+n> (”+”都是普通的加法道；“+n”是模的加法)都是交换群
            阿贝尔群（Abelian Group），又称交换群或加群，是这样一类群：
它除了满足一般的群公理，即运算的结合律、G 有单位元、所有 G 的元素都有逆元之外，还满足交换律公理。
        置换群
          n元对称群的子群
        四元群
      环与域
        环
            要有逆元
            对乘法的要求只有适合结合律一条
        整环
          交换，含幺，无零因子的环
        域
      格和布尔代数
          1和2都有两个上界，因此这两个点没有最小上界(最小上界有且只能有一个)
          <s,。>满足交换律，结合律，分配律则也是格
        分配格
          x∨(y∧z)=(x∨y)∧(x∨z)
          x∧(y∨z)=(x∧y)∨(x∧z)
          ∧最大下界，∨最小上界
        有补格
            a和a'是互补，L中所有元素都有补元
      同态
        单射映射
          单同态
        满射映射
          满同态
        双射映射
          同构
        到自身
          自同态
  6树
    无向树定义
      d(v)=1的都称为树叶，所以非平凡树至少有两个树叶
      连通不含回路的无向图称为无向树
      只有一个根
        平凡树
      树是连通的，删掉任何一条边都会变得不连通
      边=顶点-1 m=n-1
      度数=联结顶点的边数
      deg=2m
    生成树
      定义
        无向连通图中存在生成树
        在生成树中的称为树枝
        不在树中的称为弦
        所有弦的集合称为余树
          它并不一定是树
        边》顶点-1
      最小生成树
        克鲁斯卡尔kruskal算法
          把边按从小到大排序依次加入树中
    根树
      定义
        入度为0称为树根
        层数，树高，儿子，父亲，有序树
        其它
          每个分支点最多r个儿子-r元树
            r元树是有序的-r元有序树
          每个分支点恰有r个儿子-r元正则树
            r元正则树是有序的-r元有序正则树
            r元正则树的树叶的层数等于树高h-r元完全正则树
              r元完全正则树是有序的-r元有序完全正则树
      分支点
        内点
          入度为1，出度大于等于1
        树根
    哈夫曼算法
      权值最小的先合成树，最后总的权值最小（小的放左边）
    最佳前缀码
      0和1
        若只有一个儿子（子结点），命为0
    遍历
      首先遍历根结点，然后遍历左子树，再遍历右子树-前序
      首先遍历左子树，再遍历根结点，再遍历右子树-中序
      首先遍历左子树，然后遍历右子树，最后访问根结点-后序
    子主题 7
  5图
    基本概念
      无向图和有向图
        简单无向图 △《n-1
      各种图
        含平行边的图称为多重图
        不含平行边和环的图称为简单图
          有向图可以！！！<c,d>和<d,c>不是平行边
        最大度数=最小度数是k-正则图
        是特殊的n-1正则图-完全图
        在无向圈里放置一个顶点使它与每个顶点均相邻, 这是n阶-轮图
          所有顶点加起来等于n，n阶轮图
        2^n个顶点，一个正方形套一个正方形，为N方体图
        顶点标了名字叫标定图
        图中任意两点都是连通，称为连通图
        圈图
          一个圈
        对偶图
      度数为1的为悬挂顶点，与它关联的边是悬挂边
      最大度△
        △+最大出度
        △-最大入度
      最小度ξ
        ξ+最小出度
        ξ-最小入度
      一个顶点的度数=deg(v2)
        子主题 1
      无向简单图△《n-1
      图不可能只有一个奇度顶点，度数为偶数
          每一个连通分支都是一个单独的图,而图的奇度顶点是偶数个,所以图G中的两个奇度顶点必在同一连通分支内,所以这两个奇度顶点必然连通.
    子图和补图
      子图
        从原图中删去一些百点或删去一些线或既删去一些点又删去一些线，剩下的部分（当然必须仍然度是图）。允许两种极端情况：什么都不删；删去所有点和所有线
      真子图
        专同“子图”，但不允许什么都不删
      生成子图
        同“子图”，但只允许删去线，不允许删去点
      补图
        以所有能使G成为完全图Kn的添加边组成的集合
          一个图有着跟G相同的点，这些点之间有边相连当且仅当在G里面他们没有边相连，如Kn的补图为n阶零图
          自补图
            当一个图和它的补图同构时，为自补图。
    同构
      每个点出入度不变，图的整个拓扑结构不变(连通性)，顶点个数不变
    图的连通性
      通路的条数
      所有的边各异-简单回路
      所有的边和点各异-初级回路（圈）
        长度为奇数称为奇圈
      初级回路的边可以重复-复杂回路（高级）
      无向图的连通性和连通度
        点割集
          少了这些点，图失去连通性。而且它的子集不会
          若只有一个，称为割点
        边割集
          少了这些边，图失去连通性。而且它的子集不会
          若只有一个，称为割边
            桥
        连通度
          点连通度
            K（G）=最少的顶点个数使图失去连通性
          边连通度
            λ（G）=最少的边个数使图失去连通性
          平凡图为0，完全图为n-1
        连通分支称为p(G)
      最小度》边连通度》点连通度，ξ》λ》K
      有向图的连通性和连通度
        短程线
          Vi到Vj最短通路
          距离d=长度
        单向连通图
          任意两个顶点至少有一个可达另一个顶点
        强连通图
          任意两个顶点相互可达
      每个度数至少为2，则包含一条回路
      弱连通
        无向图的
    图的矩阵
      无向图的关联矩阵
        边与顶点的联系
          0
          1
          环2
      有向图
        有向图的关联矩阵
          边e与顶点v的联系
            1顶点是边的起始点
            0没有关系
            -1顶点是边的终点
        有向图的邻接矩阵
          顶点到顶点的通路条数联系
          V1到v3的长度为2的通路有多少条
        有向图的可达矩阵又称连通矩阵
          顶点i是否能到达J
            0
            1
          主对角元素全为1
          图是强连通的当且仅当矩阵全为1
            将矩阵的1~n-1次方对应点相加求和，存入另一n*n矩阵中，将此矩阵非0元素全部置为1，将对角线元素置为1，便得到此图的可达矩阵。
          边数
            边数=n(n-1)
        每一列正好一个1一个-1,1的总数等于-1的总数
    特殊的图
      二部图(不考）
        定义
          顶点分成两个不相交的子集，G中任何一条边一条属于V1一条属于V2
            当且仅当无奇数度长度的回路
            一个点回到原点只能是偶数边数
          n阶零图是二部图
          完全二部图
            V1每个节点都与V2每个节点相邻
          证明
            每条回路经过的边数都是偶数
        匹配
          E中边不相邻
            极大匹配
              多一条边就是相邻了
            最大匹配
              极大匹配边数最多的
          匹配的边数与最小顶点子集数关系
            匹配的边数等于最小顶点子集数关系，完备匹配
            特殊的完备匹配。与两个子集数都相等，完美匹配
        证明二部图的完备匹配
          相异性条件
            V1任意k个顶点和V2的k个顶点相邻
              边数等于V1定点数，当然是这样
          t条件
            V1至少关联t条边
            V2至多关联t条边
          则这个二部图存在完备匹配
      欧拉图
        欧拉回路（一笔画），也称为欧拉图
          不重复遍历所有的边回到原点（顶点可以经过多次，必须经过图中所有的边）
            简单回路不需要经过图中所有的边，所以简单回路不一定是欧拉回路
        定义无向图
          G是连通图且无奇度顶点
            所有顶点的度数为偶数
        定义有向图
          当且仅当D是连通的且所有顶点的入度等于出度
        欧拉通路
          经过边一次且仅一次
      哈密顿图
        经过每个顶点一次且仅一次，哈密顿通路
        经过每个顶点一次且仅一次的回路，哈密顿回路（初级回路），也称为哈密顿图
          一定要经过每个顶点，边可以不管
            哈密顿回路属于初级回路，但初级回路不一定是哈密顿回路，因为不包括每一个点
        定义
          哈密顿回路一定没有割点
      平面图
        null
        定义
          除顶点外没有边交叉出现
          画出没有边交叉的图称为平面嵌入或平面表示
            否则称为非平面图
          平面图的边把区域画成若干区域
            面积无限-外部面
            有限-内部面
              包围这个面的回路称为-边界
            边界的长度称为=次数 deg(R)
        极大平面图
          任意不相邻的两个顶点之间加一个边，所得图就是非平面图，则为极大平面图
          他的每个面的长度（次数）=3
          是连通的
          2m=3r (r是面数）
            总的次数=2m
          定理6.17
          K5和k3,3都不是平面子图
          证明是平面图
            平面图的欧拉公式n-m+r=2
              n-m+r=k+1
                k=连通分支
              子主题 2
            必要条件
              m《3n-6
            充要条件
              不同胚于K33或K5
          子主题 8
        同胚
          反复插入和消去2度顶点后同构
        库拉图斯基定理
          子主题 1
          子主题 2
        极大平面图每面的次数皆为3
    任何图都是4-可着色的
      偶阶圈图顶点着色2个
      奇阶圈图顶点着色3
      偶阶轮图顶点着色4个
      奇阶轮图顶点着色3个
      二部图顶点着色两个
  4函数
    性质
        函数!!!A到B的函数的集合，就是X到Y的集合
      函数
        x只对应一个y，y=f(x)=x的平方-1。
        <1,5><1,6>就不是函数，只是二元关系
    定义
      单射
        不存在两枪打在一个点上,可以有的靶子没有点。这依然是单射。7个猎人，10个靶子
        唯一的x，f(x)=y
        对于∀x都有对应的y，y可以有多，ranf不一定等于集合B
      满射
        多个子弹打在一个点上，要全被打到
        y中的元素都有对应
        ranf=B
      双射
        一一对应，如y=x
        既是满射又是单射
      自然映射一定是满射，但不一定是双射
        从A到商集A/R的自然映射肯定是满射，可能是单射（当任意一个等价类中只有一个元素时）
        子主题 2
    复合
      两个函数是单射的，则复合函数也是单射。
      两个函数是满射的，则复合函数也是满射
      两个函数是双射的，则复合函数也是双射
      复合函数的定义域和值域怎么理解
    反函数
      f^-1
      f可逆则f是双射，f是双射则f可逆
      f*f^-1(x)=x
    函数的像和完全原像？
      像就是y，原像就是x，f就是函数
        设X,Y是两个非空来集合，如果存在一个法则f，使得对X中每个元素自x，按法则f，在Y中有唯一确定的元素y与之对应，则称f为从X到Y的映射。其中y称为元素x（在映射知f下）的像道，元素x称为元素y（在映射f下）的一个原像。
  3关系
    有序对和笛卡尔积
      <x,y>
      A×B = {(x,y)|x∈A∧y∈B}
        4.笛卡尔积运算对并和交运算满足分配律，即
Ax(B∪C)=(AxB)∪(AxC)
(B∪C)xA=(BxA)∪(CxA)
Ax(B∩C)=(AxB)∩(AxC)
(B∩C)xA=(BxA)∩(CxA)
        (AxB)xC≠Ax(BxC)笛卡尔积运算不满足结合律，除非三者都为空
          左边的元素是 (（1,2）,3) ,右边的元素是 (1,（2,3）)
        N阶笛卡尔积如空间直角坐标系
      P(A)是幂集
    二元关系R
      包含R∈
      整除Da
        <x,y> x|y
      等于
      恒等IA
        （a,a)
      子主题 4
      全域关系 Ea ={(x,y)|x∈A∧y∈A}
      二元关系是序偶的集合
    关系的矩阵
    关系的基本运算
      fldR域
      dom定义域
      逆关系R^-1
        R是对称的，则R逆也对称，R补也对称
      R的幂R^2等等，就是线性代数的求法
      鸽巢定理
        n+1个鸽子放进n个笼子里
      R^0=IA
    关系的性质
      自反
        <x,x>
      反自反
        <x,x>一个都不属于R
      既不是自反也不算反自反
      对称
        <x,y>在则<y,x>也在
      反对称
        <x,y>则<y,x>是<x,x>
          <y,x>不存在则也是反对称
      非对称
        既不是对称也不是反对称
      传递
        <x,y>和<y,z>在，则<x,z>也在
          <y,z>不在，则也是传递的
            {<1,3>}和{<1,2><3,2>}也是传递的，它们没有<y,z>
            R1=｛<1，1>，<2，2>｝是传递的
      像集
      对称，传递不一定能推出自反
        集合为{1, 2, 3}，R={(1, 2), (2, 1), (1, 1), (2, 2)}。显然R是对称的，传递的，但是，不是自反的。因为(3, 3)不在R中
      R可能即是对称也是反对称。比如{<a,a,><b,b>}，但是但是 {<a,a,><b,b>，<c,a><a,c>} a不等于c，所以不是反对称的，而是对称的
        反对称不是对称的子集
    关系的闭包
      向R中加入少量有序对，使它有（自反，传递，对称）性质
        自反 r(R)
          R^0是自环
        symmetry 对称s(R)
        t(R)
          传递闭包
            沃舍尔算法
              纸上思想
                k=1,第一行所有有1的地方画竖线，第一列所有有1的地方画横线，交叉的地方0改为1。直到k=n
                两个数逻辑加时，如两个数都是0则结果是0,否则为1
              代码思想
                链接
                k=1时，第一行的元素逻辑加到第一列所有有1的那一行
                k=2时，第二行的元素逻辑加到第二列所有有1的那一行。一直如此，直到K=n
      tsr(R)
        次序
          先算自反再算对称，再算传递
    等价关系
      R是自反的对称的传递的，则称R为A上的等价关系--
      等价类
        根据传递性来划分等价！！！
          比如从1出发，传递所能接触的所有元素化为一类！！！
      商集
        A/R
          就是等价类的划分
            {{1,4,7}{2,5}{3,6}}
        A/I
          关于恒等关系划分
            {{1},{2},{3},{4},{5},{6},{7}}
      划分
        就是一个蛋糕切划分，切块没有公共部分，切块合在一起是原来蛋糕，切块不能是空集
          115划分还没
    偏序关系偏序集与哈斯图
      偏序
        偏序关系都是带自反，反对称和传递的
          所以恒等关系属于偏序，集合包括IA
      拟序
        反自反，传递
      全序
        集合内任何一对元素在在这个关系下都是相互可比较的
          全序关系指的是集合A,任意x和y,元素之间有偏序关系,x≤y,或者y≤x
      最小上界
        就是类似于最小公倍数
      最大下界
        最大公约数
      上界
        所有的公倍数
      下界
        所有的公约数
      哈斯图的箭头
        箭头→末端指向的是y <x,y>
      设A={a,b}，,则A上共有 3 个不同的偏序关系
    {1,2}上可以定义16种关系
    子主题 10
  所以总的次数=2*总边数
  自由主题