写了一份摘要,内容很少

Menu

Chap01 集合
Chap02 计数原理
Chap03 命题逻辑
Chap04 谓词逻辑
Chap05 证明技术
Chap06 二元关系
Chap07 特殊关系
Chap08 函数
Chap09 图


集合


  • 基数:集合中的元素个数
  • 幂集:某集合A所有不同子集构成的集合,符号化表示为P(A)或2^{A}
  •  \bigcup_{i = 1} ^ {n}A_i = A_1 \cup A_2 \cup\dots \cup A_n
  •  \bigcap_{i = 1} ^ {n}A_i = A_1 \cap A_2 \cap\dots \cap A_n

计数原理


总体上是高中的排列组合的扩展,就课本的内容而言是不及高考的,但是有可能考定义

  • 容斥原理
    我们计算某类物体的数目时,要排斥那些不应包含在这个计数中的数目,但同时要包容那些被错误地排斥了的数目,以此补偿。这种原理称为容斥原理(The Principle of Inclusion-exclusion)
    e.g.

    • |A \cup B| = |A| + |B| - |A \cap B|
    • |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|
  • 鸽笼原理
    若有n+1只鸽子住进n个鸽笼,则有一个鸽笼至少住进2只鸽子。
    鸽笼原理仅提供了存在性证明


命题逻辑

  • 具有确切真值的陈述句称为命题
  • 命题联结词优先级:否定 > 合取 > 析取 > 蕴含 > 等价
  • 对应的逻辑联结词:\neg > \land > \lor >   { }\rightarrow { }  >  { }\leftrightarrow{ }
  • 命题:基本等价关系(E)-P61
  • 极小项&极大项
    举个例子

    • 一个命题变元P
      极小项:P, \neg P
      极大项:P, \neg P
    • 两个命题变元P, Q
      极小项:P \land Q, \neg P \land Q, P \land \neg Q, \neg P \land \neg Q
      极大项:P \lor Q, \neg P \lor Q, P \lor \neg Q, \neg P \lor \neg Q
    • 以此类推
  • 使极小项为1的那组真值指派为对应极小项的编码
  • 使极大项为0的那组真值指派为对应极大项的编码
  • 等价公式转换法:任意命题公式向主合取范式/主析取范式的转化
    • 重复使用德摩根律和双重否定律
    • 使用分配律得到合取范式/析取范式
    • 消去短语/子句中重复的命题变元,去掉永真公式和永假公式
    • 向缺少某命题变元的短语/子句添加该变元,比如析取范式中某一短语缺少P就可以添加(\neg P \lor P)
    • 使用分配律展开,合并相同短语/子句,得到极小项/极大项
    • 用幂等律和分配律调整,得到标准的主合取范式/主析取范式
    • 例题:P77, P97
  • 真值表技术
    • 主析取范式:选出公式为真的所有行,找到每个解释对应的极小项,析取
    • 主合取范式:选出公式为假的所有行,找到每个解释对应的极大项,合取
  • 主合取范式、主析取范式的转换
    • 原理不赘述,教材P80
    • 具体操作为把极小项/极大项下标取补集,然后变换符号
    • 例题:P97
  • 推理:基本蕴含关系(I)-P85
  • 基本推理规则
    • P:前提引用
    • T:逻辑结果引用
    • CP:附加前提

谓词逻辑

  • 谓词翻译:根据命题的实际意义加入量词,全称量词加入时其刻画的特性谓词往往做蕴含前件存在量词加入时其刻画的特性谓词往往做合取项
  • 公式:量词等价关系(E)-P116
  • 前束范式&Skolem标准型
  • 公式:量词蕴含关系(I)-P121
  • 推理规则
    • US:全称特指规则
    • ES:存在特指规则
    • UG:全称推广规则
    • EG:存在推广规则
    • 用例:P122-123
  • Extra:泊松分酒问题
    因为条件给定后状态数量是有限的,所以感觉可以BFS
  • 习题:P134

证明技术

  • 直接证明&间接证明&blablabla...
  • 归纳法&强形式归纳法

二元关系

  • 笛卡尔积:AxB
    • 不满足交换律
    • 不满足结合律
    • 推广到n个集合
  • 前域、后域与定义域、值域的关系--P166
  • 布尔矩阵运算
    • 布尔积(满足结合律)
  • 关系的运算(类比集合的运算)--P173
    • 复合运算的条件和规则
  • 关系的逆运算(交换前域和后域,注意复合关系的逆运算)--P178
  • 关系的幂运算--P181
  • 关系的性质--P193
    • 自反性
    • 每个节点都有自环
        - 主对角线全为1
    • 反自反性
        - 每个节点都无自环
        - 主对角线全为0
    • 对称性
        - 任意两节点间没有单边
        - 对称矩阵
    • 反对称性
        - 任意两节点间最多有一条边
        - r_{ij}\land r_{ji}=0
    • 传递性
    • 定理--P194
        - 逆运算和交运算有很好的保守性
  • 闭包:增加最少元素具备所需性质

特殊关系

  • 等价关系:自反、对称、传递
    • 等价类&商集
  • 拟序&偏序+良序&全序
    • 有限全序集一定是良序集

函数

  • 单射、满射、双射
    • P243定理

  • 奇奇怪怪的定义
    • 零图:仅含孤立节点
    • 平凡图:仅含一个孤立节点
    • (n, m)图:n个节点m条边
    • n阶图:有n个节点
    • 混合图:无向边&有向边
    • 完全图:任意两个节点都有连接边
    • 生成子图:节点与原图相同,边集属于原图
    • 导出子图:节点集属于原图,以节点集中两个节点在原图中的边为边集
    • 补图:节点与原图相同,边集为补集
    • 连通分支:可达关系R的等价类导出的子图