Discrete Mathematics

数理逻辑

命题

• 非真即假：T/F，1/0
• 排中律：反证法
• 逻辑联结词+原子命题（p,q,r,s） -- 复合命题
• 逻辑联结词：非~，和^（合取），或v（析取），
• 蕴含：如果。。那么。。p->q(只有在p为1而q为0的时候这个命题是假命题，和逆否命题等价)，充分/必要条件，双向蕴涵p<->q
• 命题公式：A,B,C
• 优先级：非，和/或，蕴涵，双向蕴涵
• 真值表：n个命题变元，k个联结词，2^n行，k+n列
• 成真赋值，成假赋值。命题公式可分为重言式（永真），矛盾式（永假），可满足式
• 逻辑等价：A |=| B
• ~A v B等价于A->B；A<->B等价于(_AvB)^(AvB)或者(A^B)v(~A~B)
• 若A->B是永真式，写成：A|=B，证明这个命题：A的所有成真赋值都是B的成真赋值，或者B的所有成假赋值都是A的成假赋值
• 代入原理：永真式，代替同一命题变元的所有出现
• 替换原理：任意命题，任意代替一个等价的命题公式
• 范式：逻辑等价的，且只含否，和，或。析取范式（合取子句的析取），合取范式（析取子句的合取）
• 主析取范式：每个合取子句里p1，p2...刚好出现一次；主合取范式：...
• _{,v,^：功能完备集；极小的功能完备集：{},v}/{_,^}/{,->}...
• 皮尔斯记号：pq |=| ~(p v q)：极小的功能完备集
• 命题演算形式系统PC：公理（定理），推理规则。同构系统：真值表，可用真值表判断PC中的定理
• 分离规则：A，A->B，可以得到B
• 三大元定理：归谬定理（反证法），穷举定理（若一个前提本身和反面都能推出结论，那么结论与前提无关），演绎定理（前提可以移作前件）

谓词逻辑（一阶逻辑）

• 将量词作用于个体，引入个体变元(x,y,z)。（个体常元）
• 谓词（P,Q,R）中可以放置个体的空位数称为元数：单元，二元谓词
• 谓词命名式：P(x)；谓词填式：填入实际的个体
• 量词：所有，存在
• 谓词公式：给定个体域，所有谓词都有明确意义，所有变元取定个体
• 一阶谓词演算形式系统FC：个体项，合式公式，7条公理
• 分离规则
• 自然推理系统ND

集合

• 元素，隶属关系
• 空集，有限集（元素个数：基数），无限集
• 外延公理：两个集合相等当且仅当它们具有相同的元素
• 概括公理：元素的确定性
• 正规公理：集合有限可分
• 子集，集合与集合：隶属/包含，子集个数：2^n；真子集
• A=B当且仅当互为子集
• 集合运算：并，交，差，补
• 取补之后，交变并，并变交
• 幂集：所有子集作为元素构成的集合
• 集合族：所有元素都是集合；其元素下标的集合叫做标志集
• 广义并：集合族中所有集合的并集
• 归纳定义：基础条款，归纳条款，终极条款
• 归纳原理：证明基础定义、归纳条款都满足性质P
• 数学归纳法：....
• 二元有序组/二元组：记作<a,b>：{a,{a,b}}两二元组相等当且仅当两元素相等
• <a,b,c>=<<a,b>,c>
• 笛卡尔积：AxB = {<u,v>|u,v属于A,B}
• 分配律：Ax(B(AxC).其中$代表并/交/差
• 元组：用来表示关系。空关系：空集；全关系：笛卡儿积；相等关系：<x,x>
• 关系图：前域指向陪域的箭头（定义域指向值域）
• 关系矩阵：aij为0或1
• 逆关系R~:BxA：关系矩阵转置
• R和S的合成关系：R。S：对应关系矩阵乘法
• 二元关系：自反/反自反；对称/反对称；传递/反传递

特殊关系及函数

• 等价关系：自反、对称、传递
• 划分：不空、不交、不漏
• A上的所有等价类的集合构成A的一个划分
• 划分和等价关系一一对应
• 划分细于：等价关系属于
• 积划分是所有细于两种划分的最粗划分。对应等价关系交运算
• 和划分。不对应并运算
• 序关系：自反、反对称、传递的二元关系。哈斯图
• 最小/极小元、最大/极大元：差别在于是否包含不可比较的元素
• 上/下界；上确界：所有上界集合的最小元
• 链：子集B中的任意元素都是可以比较的。反链。链的长度
• 半序关系：反自反、反对称、传递
• 函数：单值性；函数的合成g(f(x))
• 单射函数（单调函数？）；满射函数：值域等于陪域；双射函数：既是单射又是满射
• 逆函数：只有双射函数才有逆函数；左逆函数（单射函数）；右逆函数（满射函数）

图论

• 图G=<V,E>：结点集合V+边集E（可能存在相同元素）；有向边用结点的二元有序组表示
• 有限图：V，E都是有限集合；重数大于1的边称为重边；图成为重图
• 简单图：无环、无重边的图；完全图：任意结点之间都有连接；赋权图
• 端点的度：关联端点的边的数目；有向图中分为出度和入度
• 度的总和是边的数目的两倍；一度的顶点称为悬挂点
• K-正则图：所有顶点的度相等的图；Kn是n-1正则图
• 子图
• 补图：并之后为完全图，交之后为空
• 同构图
• 拟路径中的边不相同，称作路径；路径中的顶点不相同，称为通路；头尾两点相同的路径为闭路径；头尾相同的通路称为回路
• 有拟路径必有路径，必有通路；有闭路径必有回路
• 无向图连通性：任意两个顶点都是可达的；有向图强连通性：相互可达；单向连通的有向图；弱连通：看作无向图时是连通的
• 连通子图
• 欧拉图、欧拉路径：所有顶点（可重复），所有边（不重复）；充要条件：无向图：所有顶点的度都是偶数且G连通；有向图：G弱连通且每个顶点的出度和入度都相等
• 欧拉路径充要条件：无向图：...
• 哈密顿图：经过所有顶点（不可重复）的回路；充分非必要条件

特殊图

• 邻接矩阵：有边时对应为1，否则为0；
• 关联矩阵：顶点和边的关系
• 二分图Knm:G至少有两个顶点且回路长度是偶数
• 匹配：任意两条边都没有公共顶点；最大匹配；完全匹配；x!=y的二分图一定没有完全匹配
• 平面图：各边仅在顶点处相交
• 树：连通无回路的无向图；树叶：悬挂点；分支点：非树叶；空树；森林：每个连通分支都是树
• 树：顶点数比边数多1；是二分图，平面图；树根
• 父节点，子节点，兄弟节点，子树
• n元树：至多有n个子节点
• 二元有序树可以表示任何n元有序树
• 二元树的遍历：先根次序（根，左子树，右子树）；中根次序；后根次序
• 树的应用：表达式树：树叶为运算数，分支节点为运算符
• 排序树：左子节点的值都小于根，右子节点都大于

抽象代数

• 二元运算：*；普遍性；单值性；封闭性
• 代数结构：非空集合S，运算，公理；<S,*>
• 幺元：xe=ex=x；x*er=x：右幺元
• 零元：xo=ox=o
• 逆元：x*y=e，y称作x的逆元
• 多于1个元素的载体集上零元没有逆元
• 左可约：ax=ay->x=y;;;右可约：xa=ya-->x=y
• 在满足结合律的代数结构中，有逆元的元素可约
• 同构代数结构s-->s'；h(xy)=h(x)‘h(y)
• 同态映射
• 同余关系
• 半群：满足结合律的代数结构；
• 独异点：含有幺元的半群
• 群：每个元素都有逆元的独异点
• 阿贝尔群（交换群）：满足交换律
• 环：有两个二元运算

形式语言

• 自动机：检验输入的句子是不是语言
• 正则表达式
• 语法G，起始符，终结符，非终结符
• 语言L(G)
• 导出树：起始符作为树根
• 0型语法：图灵机识别，1型语法：线性有界自动机；2型语法：下推自动机
• 正则语法：有限状态自动机
• 语法分析
• BNF范式：定义为（::=），或（|），非终结符（<>）；可表示2、3型语法
• 扩展BNF：可选项[]；重复项{}
• 语法图：方框表示非终结符，圆表示终结符，箭头线表示连接
• 正则集合<->正则语法
• 主导图翻译成正则表达式：串联、并联|、回路*

有限状态机FA

• 判断字符串是否属于L(G)
• 对于所有的输入，输出的状态有限
• 五元组M(A,S,Y,s0,F)
• 状态图：双环表示接受状态
• 对应正则语言
• 泵引理：能被接受的且长度超过状态数的串中间部分重复之后仍然会被接受
• 商机器

图灵机

• 无限长纸带，读写头（左移，右移，不动L,R,N）。停机状态（SH,SY接受,SN）时纸带的内容就是输出
• 识别：0型语言
• 图灵机变种：计算能力相同，都可以归结到单纸带单向的图灵机
• 识别与判定，识别存在永不停机的情况，只有L和L的补语言都是可识别的情况下，L才是图灵可判定的
• 哥德尔编码：将形式语言L编码为自然数的集合
• 通用图灵机存在，输入为a,k;a是图灵机的哥德尔数，k是图灵机输入的哥德尔数
• 图灵机停机问题：不存在一个算法，能够判断某个图灵机在给定输入下是否会停机。启示：算法不是万能的
• 哥德尔不完备定理