信息安全原理与数学基础

上课是不可能好好上的，扯淡是一定要扯的。众所周知，与本氵课关系最小的内容是数学。

待补充内容：1.ND系统

离散数学

1 第一讲

1.1 第一次数学危机

起源于无理数的发现

信仰数字的毕达哥拉斯神奇地发现 $sqrt{2}$ 既不是整数也不是分数，这令人们意识到：存在不能用单位长度直接描述的线段？这一理论同毕达哥拉斯学派的理论相悖而被视为机密。直至希帕苏斯泄露了这一秘密并被扔进大海（悲）

1.1.1 第一次数学危机的解决

直至1872年狄德金提出了无理数的现代解释彻底解决了这一问题而这给了我们这些启示：

直觉和经验不一定靠得住，推理和证明才是最可靠的
几何学的某些真理同算术无关，集合量不能完全由整数及其比表示。数的尊崇地位受到挑战，古希腊数学观点得到极大冲击。几何学开始占据重要地位。

1.2 第二次数学危机

1.2.1 芝诺 Zeno of Elea 四个悖论

反对空间时间无限可分的两个悖论

运动不存在：运动是不可能的。由于运动的物体在到达目的地前必须到达其半路上的点，若假设空间无限可分则其有限距离包括无穷多点，于是运动的物体会在有限时间内经过无穷多点
阿基里斯追不上乌龟：我每次跑到乌龟位置时乌龟一定往前走了一段，所以我永远追不上乌龟。

反对空间时间有限可分的两个悖论

飞失不动：一支飞行的箭在每一个时刻都是静止的，因此其不可能运动起来。
游行队伍

1.2.2 第二次数学危机发生的背景

人们关注无穷，极限，极值等问题的关注导致了微积分的发明，从而引发了这样的问题：

无穷小是不是0？

但不同的解释都会引发矛盾

假设 无穷小等于0 ，则运算无法进行
假设 无穷小是一个极小常量，则与许多定理相悖
假设 无穷小是一个趋于0的变量，则其无法确定的值为工业带来麻烦

1.2.3 第二次数学危机的问题

1.2.4 无穷级数求和

格兰迪级数： $sumlimits_{n=1}^{infty}(-1)^n = ? $

1.2.4 第二次数学危机的启示

数学分析建立在实数理论的严格基础上
经验并不总是靠谱的

1.3 第三次数学危机

沉重地打击了集合论和逻辑基础

理发师只帮那些自己不理发的人理发
说谎者悖论：我现在说的这句话是谎话

1.3.1 第三次数学危机的解决

罗素提出类型论
策梅罗 Zermelo 提出公理化集合论来对朴素集合论进行了限制
希尔伯特 Hilbert 的形式化思想占统治地位

1.3.2 形式化理论的局限

希尔伯特提出四个问题，希望能够把整个数学理论系统形式化，并证明无矛盾。 1930年，哥德尔 Godel 发表了不完备性定理，证明了一个系统要么是不完备的，要么是存在矛盾的。

这是一个具有哲学意义的普适定理

2 第二讲

睡昏头了，不知道在讲什么，但是感觉好像在扯淡

3 第三讲

3.1 命题公式

3.1.1 命题公式的定义

简称公式，用大写字母表示，采用以下归纳定义

命题常元和命题变元为命题公式，称为原子公式
若 A 和 B 为命题公式，则 $lnot A, Alor B, Aland B, Arightarrow B, A leftrightarrow B $ 均为命题公式
只用有限步引用上述两条所组成的符号串是命题公式

有以下简化定义：

最外层括号可以省略
约定优先级以去除部分括号

为了简化描述，规定以下优先级： $$(lnot) > (lor , land) > (leftarrow) > (leftrightarrow)$$

除非有括号，否则按照从左到右，优先级从高到低进行运算。

3.2 真值函数

将连接词看成逻辑运算符，则命题公式可以被视作一个真值函数

3.2.1 赋值

将给予真值函数的一组值称为一个赋值（assignment）。对于一个确定的赋值，真值函数应当有一个唯一确定的真值。

将使真值函数值为真的赋值称为 其成真赋值
将使真值函数值为假的赋值称为 其成假赋值

3.2.2 真值表

当 $A(p_1,p_2…p_n)$ 中有k个联结词时，真值表应当有 $2^n$ 行，$k+n$ 列。

3.3 自然语言的形式化

对于自然语言描述的命题，经过抽象化，可以转化为命题公式

确认原子命题
确定联结词
把自然语言抽象化后联结

无论天是否下雨，我都不去上学。原子命题：p:天下雨 q:我去学校形式化命题：$q$, $(plorlnot p)rightarrow q$

注意事项：

善于确定原子命题
善于确定自然语言联结词
对于多个对象进行否定时要确定否定词位置和表意
不能省略不能省略的括号，必要时保留括号提高可读性
形式化结果不是唯一的，但在逻辑上是等价的

3.4 命题公式的分类

命题公式的分类：

重言式（永真式）tautology ：对于任何赋值，结果恒为真
矛盾式（永假式）contradiction：对于任何赋值，结果恒为假
可满足式：存在一组赋值，使结果为真

对于任何命题公式 A，有以下结论：

重言式（排中律） $A lor lnot A$
矛盾式（矛盾律）$B land lnot B$

3.5 逻辑等价式

若 $A leftrightarrow B$ 为重言式，则记 $A equiv B$。则有以下逻辑等价式，以下内容非常重要：

双重否定律： $lnotlnot A equiv A$
幂等律： $A lor A，A land A equiv a$
交换律： $Alor Bequiv Blor Aquad Aland Bequiv Bland A$
结合律： $(Aland B) land C equiv Aland (Bland C)quad (Alor B) lor Cequiv Alor(B lor C)$
分配律： $A lor(B land C)equiv(A lor B) land (A lor C)$$A land(B lor C)equiv(A land B) lor (A land C)$
德摩根定律： $lnot(Aland B)equivlnot A lor lnot Bquad lnot(Alor B)equivlnot A land lnot B$
吸收律 $Aland(Alor B)equiv Aquad Alor(Aland B)equiv A$
蕴含等值式：$A rightarrow B equiv lnot A lor B$
有 $Aleftrightarrow B equiv Ararr B land Brarr A$
零律： $A lor T equiv Tquad Aland F equiv F$
同一律: $Aland Tequiv Aland F equiv A$
排中律/矛盾律： $Alor lnot A equiv T quad Alandlnot A equiv F$
有 $lnot Tequiv F quad lnot F equiv T$
有 $Aland Brarr Cequiv Ararr(Brarr C)$
假言易位： $Ararr Bequivlnot B rarr lnot A$
归谬论： $(Ararr B)land(Ararrlnot B)equivlnot A$
有 $Alrarr B equiv(Aland B)lor(lnot Alandlnot B)$

3.6 逻辑蕴含式

若命题公式 $A$ 和 $B$ 满足 $Ararr B$ 为重言式，则称 $A$ 逻辑蕴含 $B$ ，记为 $Amodels B$。我们此前所讨论的等价式 $Aequiv B$ 等价于 $Amodels B land B models A$。

逻辑蕴含式含义即对于使 A 所有的其成真赋值都是 B 的其成真赋值

3.6.1 重要逻辑蕴含式

对于逻辑蕴含式，有以下重要结论：

有 $Amodels Alor B$
有 $A land Bmodels A$
有 $Aland (Ararr B)models B$
有 $(Ararr B)land lnot Bmodels lnot A$
有 $lnot A land(Alor B)models B$
有 $(Ararr B)land(Brarr C)models Ararr C$
有 $(Ararr B)land(Crarr D)models(Aland C)rarr(Bland D)$
有 $Alrarr Bland Blrarr C models Alrarr C$

3.7 逻辑结果

逻辑结果被推广为 $Gamma models B$，其中 $Gamma$ 是由一系列命题公式组成的集合，这一结果代表了 $Gamma $ 中每一个命题公式的成真赋值都是 $B$ 的成真赋值。注意一下特殊情况：

若 $Gamma$只包含一个命题公式 $A$ ，则$A models B$
若$Gamma$ 为空集，则计作 $models B$，即 $B$ 为重言式

3.8 逻辑等价式，蕴含式重要性质

对于命题公式的自反、对称、传递，有以下重要性质：

公式 $Aequiv B$ 当且仅当 $models (A lrarr B)$
公式 $(Amodels B)models (A rarr B)$
若 $Aequiv B$ 则 $Bequiv A$
若 $Aequiv Bquad B equiv C$ 则 $Aequiv C$
若 $Amodels B$ 则 $lnot B models lnot A$
若 $Amodels Bquad Bmodels C$ 则 $Amodels C$
若 $Amodels Bquad Aequiv A’quad Bequiv B$ 则 $A’ models B’$

3.9 代入和替换原理

3.9.1 重言式的代入原理

代入原理（Rule of Substitution）：即对于重言式 $A$，将其中的某一变元 $p$，将其全部替换为命题$B$，将其记为 $A(B/p)$。则 $A(B/p)$ 也是重言式，因为重言式的真值与其变元的取值无关。但在代入式必须将某一变元全部代入，否则该原理不成立。

思考：如果B中包含p或A中某变元，该原理是否成立? 答案：成立。

3.9.2 替换原理

替换原理（Rule of Replacement）：即对于任意一个命题公式 $A$，将其中的任意一子式 $C$ 替换为 $D$，且满足 $Cequiv D$ 从而得到新命题公式 $B$，则有 $Aequiv B$。

3.9.3 替换原理和代入原理的一些区别

替换原理能应用于任意命题公式，而代入原理只能应用于重言式
替换原理能够替换公式任意子式，而代入原理在替换式必须保证该变元被全部替换

3.10 如何证明等价式、蕴含式

3.10.1 真值表法

逻辑等价式：真值表中 $Alrarr B$ 全为真 逻辑蕴含式：真值表中 $Ararr B$ 全为真

3.10.2 讨论赋值

用于证明逻辑蕴含： 证明 $A$ 的成真赋值都是 $B$ 的成真赋值或 $B$ 的成假赋值都是 $A$ 的成假赋值 （假言易位）

3.10.3 推演法

基于 3.6，3.8中的已有等价，蕴含公式和替代原理，代入原理对逻辑表达式进行推演变化。

$$i.g.1: (Alor B) rarr C equiv(Ararr C) land (Brarr C)$$

$$(Alor B)rarr Cequiv lnot(Alor B)lor Cqquad(1.蕴含等值式)$$

$$lnot(Alor B)lor Cequiv (lnot Aland lnot B)lor Cqquad (2.德摩根定律)$$

$$(lnot Aland lnot B)lor C equiv (lnot Alor C) land(lnot Blor C)qquad(3.分配律)$$

$$(lnot Alor C) land(lnot Blor C)equiv(Ararr B)land (Brarr C)qquad(3.蕴含等值式)qquad Q.E.D.newline$$

$newline$

$$i.g.2: (Aland B) models lnot A rarr (Crarr B)$$

$$A models Alor(lnot Clor B)$$

$$Alor(lnot Clor B)equiv lnot Ararr(lnot Clor B)equiv lnot Ararr(Crarr B)qquad(1.蕴含等值式)$$

$$(Aland B)models lnot Ararr(Crarr B)qquad Q.E.D.$$

4. 范式

每一个命题公式都会有很多与其逻辑等价的公式，而范式是在多个逻辑等价的命题公式中，相对标准或规范的一种形式。

4.1 范式基本定义

对于范式，我们规定了以下几个概念：

文字（literals）：命题常元、变元和他们的否定，其中前者称为正文字，后者称为负文字
析取子句（disjunctive clauses）文字或若干文字的析取
合取子句（conjunctive clauses）文字或者若干文字的合取
互补文字对（complemental pairs of literals）正文字和其对应的负文字
析取范式（disjunctive normal form）：$A’$ 称为 $A$ 的析取范式，若 $A’equiv A$ 且 $A’$ 为合取子句或若干合取子句的析取，则称 $A’$ 为 $A$ 的析取范式。例如 $prarr q$ 的析取范式为 $lnot plor q$，又比如 $((p rarr q) land lnot p)lor lnot q$ 的析取范式为 $lnot plor(qland lnot p)lor lnot q$
合取范式（conjunctive normal form）析取子句或若干析取子句的合取，其他概念同析取范式。值得注意的是，对于析取范式和合取范式，其中不会包含蕴含。而对于析取/合取范式，其对应的最后一级连接词应为析取/合取。

$$i.g.1.quadlnot p rarr lnot(prarr q)$$

4.2 范式的应用

4.2.1 重言式/矛盾式识别

合取范式中每个析取子句都包含了至少一个互补文字对

（p or not p or q）and (p or q or not q) 矛盾式识别析取范式每个合取子句都包含了至少一个互补文字对

4.3 求取范式的一般步骤

消去联结词
去掉单项蕴含和双向蕴含
使用德摩根律将否定联结词内深入，只能作用于文字
使用分配律

4.4 范式的唯一性问题

一个公式的析取范式或合取范式都不是唯一的。
一个公式的析取范式可能同时又是合取范式，如一个文字

5 主范式

用于解决析取范式和合取范式不唯一的问题

5.1 主范式定义

主析（合）取范式：若公式 $A’$ 为 $A$ 的主析（合）取范式，满足以下条件：

$A’$ 为 $A$ 的析（合）取范式
所有文字 $p_1,p_2…p_n$ 恰好出现一次

5.2 主范式唯一存在证明

主范式是存在且唯一的，为了证明这一观点，给出一些约定：

合取子句文字按照包含变元下标从小到大排列
对于包含所有变元 $p_1,p_2…p_n$ 并排列好文字顺序的合取子句，我们称为极小项（min term），计作 $m_i$
其中 $iinmathbb{Z}$，且其对应n位二进制数表示描述了对应下标的变元在合取子句中的否定状态
如果该位为0，表示负文字

5.2.1 极小项赋值定理

极小项只有唯一的成真赋值
且该极小项赋值恰好为极小项下标二进制数中变元下标对应二进制位的值

以 $m_5=p_1land lnot p_2land p_3$ 为例，其唯一的成真赋值恰好为 ${5}_2={101}_2$

5.2.2 极小项成真赋值与主范式成真赋值的关系

主析取范式的极小项的成真赋值也是主析取范式的成真赋值
主析取范式的任意成真赋值一定是某个极小项的成真赋值
主析取范式不包含的某个极小项的成真赋值即是主析取范式的成假赋值

因此这种对应关系已经极其明显了，一个主析取范式事实上就是其所有成真赋值对应极小项的析取。

5.2.3 存在性证明

证明任意不完整的子句都可以被拓展成一个包含所有文字的子句
而对于在一个子句中多次出现的变元可以通过等幂律，矛盾律等去掉
经过以上步骤我们可以使所有子句都包含所有文字，在整理边缘顺序后所有合取子句均为极小项，再按下标排列即可

5.2.4. 唯一性证明

反证法

假设有两个不同的主析取范式，易得他们等价
则两个主析取范式中至少有一个不同的极小项，由5.2.2可知这不可能
因此这两个主析取范式是相同的

$mathbb{Q}.mathbb{E}.mathbb{D}$

5.2.5 主合取范式

合取可以看成成假赋值唯一的析取，其他同上。

5.3 公式的等值分类

存在性证明给出了主析取范式的构造步骤
具有相同主析取范式的公式都是等值的，同属一个等值类
公式的数量无限多，但对于 n 个文字的主析取范式数量是有限的，极小项数量为 $N=2^n$ ，而主析取范式数量为 $2^N$
主析取范式数量与等值类数量相同

6 联结词集完备性

6.1 真值函数

每一个等值类都对应唯一的真值函数
定义域【0，1】，值域【0，1】
真值函数与等值类内每个命题公式一一对应

6.2 功能完备集

如果任意一个真值函数都可以用仅包含某个联结词集中的联结词的命题公式表示，则称这个联结词集为功能完备集。

由各种范式证明可以发现 $lbracelnot,land,lor,rarr.lrarrrbrace$ 是一个功能完备集
若一个功能完备集中存在联结词去掉后仍为功能完备集，称该联结词为冗余联结词
若一个功能完备集不存在冗余联结词，称其为极小完备集
存在只有一个运算符的功能完备集：Pierce记号 $pdarr q=lnot(plor q)$

7 形式系统

重言式反映了人类逻辑思维的基本规律。

排中律
矛盾律
假言推理 a and(a ra b) models b
归谬推理 (amodels b) and not b models not a
穷举推理（alor b）land(ara c) and (b ra c) models c

而形式系统是这样一个系统：

形式系统是一个符号体系
系统中的概念由符号表示，推理即符号变换的过程
将若干重要重言式作为基础，称为公理
系统内符号变换的一句是若干确保由重言式导出重言式的规则，chenweituiliguize
系统保证输入永真前提下输出永真

7.1 证明

公式序列 $A_1,A_2…A_n$ 称为 $A_n$ 的一个证明，如果 $A_i$

是公理
或者由其他 $A_j(j<i)$ 由推理规则推得的

当这样的证明存在时，称 $A_m$ 为系统的定理 theorem

7.2 演绎

设 $Gamma$ 为一个公式集合，公式序列 $A_1,A_2…A_n$ 称为 $A_n$以 $Gamma$ 为前提的演绎，如果 $A_i$

是$Gamma$ 为中的公式
是公理
或者由其他 $A_j(j<i)$ 由推理规则推得的

证明是演绎在 $Gamma=varnothing$时的特例

7.3 形式系统的例子

7.3.1 命题演算系统 Proposition Calculus

组成：

命题变元：$p,q,r,s,p_1,q_1,r_1,s_1$
命题常元: T,F
联结词: 功能完备集 $lbrace lnot , rightarrowrbrace$
括号（）

命题公式:

命题变元与常元为公式
$lnot p,prightarrow q$为公式
只有有限次由上述规则产生的符号串才是命题公式

公理 (aximo)

公理总是重言式，在输入是重言式的前提下，公理保证输出也为重言式。以下为 PC运算系统的公理：

A1：$Arightarrow(Brarr A)$
A2: $(Ararr(Brarr C))rarr((Ararr B)rarr (Ararr C))$
A3: $(lnot A rarr lnot B)rarr(Brarr A)$（类似逆否命题）

推理规则

在运算系统内，公式推理基于以下推理规则进行推理：

分离规则：$models(A,Ararr B)rarr models B$，即在A永真前提下若A单向蕴含B永真则B永真，也可以记作 $frac{A,Ararr B}{B}$

7.3.2 PC的性质

合理性(Soundness)

PC运算系统的合理性体现在定理和演绎上：

对于PC，在输入永真前提下，保证推出的定理都是永真式，即$vdash_{PC}Ararr models A$
如果 $A$ 是 $Gamma$ 的演绎结果，那么 $A$ 是 $Gamma$ 的逻辑结果，即$Gammavdash_{PC} A rarr models A$

合理性说明了PC的定理和演绎结果都是合乎逻辑的。

这一性质也说明了PC的重言式特点，首先A1-3都是重言式，其次，分离规则保真，因此由 $Gamma$ 和公理规则导出的定理都是重言式。

一致性(Consistency)

这一性质说明了运算系统的可靠性：

$modelslnot((vdash_{PC}A )land(vdash_{PC} lnot A))$

即不存在一个陈述 $A$，其能同时导出 $A$ 与 $lnot A$ 的永真性，这也说明了 PC 系统的推理不存在自相矛盾，不会导出不一致的结果。

完备性(Completeness)

$models Ararr vdash_{PC}A$
$Gamma rarr A, Gammavdash_{PC}A$

这一性质说明了一个合乎逻辑的命题一定可以在运算系统中通过一定的推导得到。

7.3.3 PC 运算例子

$$i.g.1 vdash_{PC}Ararr A$$

A2全部由A替换
A1全部由Ara A替换掉
使用分离规则可知 1中右侧永真
用A替换掉A1中的B
对3，4进行分离

$$Gamma lbrace A, Brarr (Ararr C)rbrace vdash_{PC} Brarr C$$

a
bra(ara c)
ara (rra a)
b ra a
a2 ab互换
对2，5进行分离规则
对4，6进行分离规则

7.3.4 元定理

演绎定理

对任意公式集合 $Gamma vdash_{PC} Ararr B$ 当且仅当 $Gammalor{A}vdash_{PC}B$
若 $Gamma=varnothing$，$vdash_{PC}Ararr B$ 当且仅当 $lbrace Arbracevdash_{PC} B$ 或 $Avdash_{PC} B$

归谬定理

$Gamma lorlbracelnot Arbracevdash_{PC} B, Gamma lorlbracelnot Arbrace vdash_{PC} lnot B$,那么 $Gamma vdash_{PC} lnot A$

归谬定理表明了若一组假设能推出相互矛盾的结果代表这组假设并不一致，其中存在矛盾，而在前提中存在矛盾时一组假设能够推出任何一个结论。

穷举定理

$Gamma lor Avdash_{PC} B, Gamma lor lnot A vdash_{PC} B rarrGamma vdash_{PC} B$

ig：|-pc not not A ra A

公理A1 notnotA 代入A notA代入B
演绎定理 {not not a,not a} pc not not a
公理a1 notA代入A not notA代入B 4.演绎定理

7.3.5 PC系统定理判定问题

仅用PC系统中公理和分离规则难以保证在有限步骤判断一个命题公式是否定理
同构：真值函数运算系统
只要判断对应逻辑表达式是否是重言式即可
若用真值表，一定可以在有限步内完成

7.3.6 MIU运算系统

组成

符号系统：MIU组成的串
初始串MI 公理MI
规则一：若xI为定理，xIU也是定理
规则二若Mx 是定理，Mxxx也是定理
规则三：xIIIy为定理，xUy也是定理
若xUUy为定理，xy为定理

定理树

由当前步定理按照规则不断向下构成的定理树

7.4 形式系统的意义

形式系统定义就是符号串集合的构造性定义
符号体系规定了符号串可能包含的字符
公理规定了几个集合中的符号串（或者这种符号串的模式）
推理规则给出了从集合中已有字符串推出其他字符串的方式

7.4.1 定理判定问题

形式系统中的定理就是在集合中的符号串
定理的证明过程就是符号串的构造过程
这个过程需要在有限步内完成

7.5 命题逻辑的解析

命题逻辑的最小研究单元是原则命题，并没有进一步的内部结构，定义命题是对确定对象做出判断的陈述句，那么对于不确定的对象和不同的情况怎么办？

命题逻辑中推理，关注真值的推演
假言推理，归谬推理，穷举推理
建立在重言式，代入和替换原则上
命题逻辑中，命题之间相互独立

8 命题之间的内在逻辑

在经典的三段论推理中，命题逻辑有些力不从心，一个正确推理在命题逻辑中并非是永真式。而事实上三段论中的命题包含着某种内在关联，这也是我们研究谓词逻辑所关心的。

8.1 谓词逻辑命题的结构分析

命题：对确定的对象做出判断的陈述句
被作判断的对象：个体
作出的判断：谓词
个体数量：量词
谓词逻辑将量词作用于个体，引入个体变元，讨论不确定的对象，也称为一阶逻辑

8.1.1 个体

谓词逻辑中一切被讨论的对象被称作个体。

确认的个体常用 a,b,c 表示，称为个体常元(constants)
不确定个体常用 x,y,z,u,v,w，称做个体变元(variables)
个体域指个体变元的取值，取值可以是有穷或无穷集合
全总个体域指一切事物组成的个体域

8.1.2 谓词

谓词是表示个体性质或关系的语言成分，通常是谓语
谓词中可以放置个体的空位称为个体空位。

8.1.3 谓词命名式

将谓词中的个体空位用变元字母代替，称作谓词命名式
常用 $P, Q, R$ 代表谓词，谓词命名式形式类似与函数表示类似 $P(x_1cdots x_n)$
命名式中的变元字符没有独立含义，仅是占位符(placeholder)。类似于函数传递中的形式参数

8.1.4 谓词填式

将谓词命名式中的个体空位用个体变元或常元代替，则称为谓词填式。注意，谓词填式与命名式形式相同意义不同，若谓词填式中的所有个体都是常元，则谓词填式演变为一个有确定真值的命题。

8.1.5 量词

不同于口语中所指的数量词，谓词逻辑中的量词特指以下两类：

全称量词 (Universal Quantifier) $forall$ 类似口语全部、所有
存在量词 (Existential Quantifier) $exists$ 类似口语存在、有些

注意，量词作用于谓词时需要引入一个指导变元：

约束变元 (Bound Variables)，就是这个被引入的指导变元，同时放入谓词填式和量词中。约束变元可以改名而不改变语句含义，同时不能被随意取值。
不同于约束变元，而那些可以被取值代入的个体变元称为自由变元(Free Variables)

量词辖域

量词所作用的谓词或者复合谓词表达式，称为其辖域(Domain of Quantifier) 对于一元谓词 $forall x P(x), exists x P(x)$都是命题，而量词也有其对应逻辑关系：

对于有穷个体域的全称量词命题等价于所有命题合取
对于有穷个体域的存在量词命题等价于所有命题析取

8.1.6 谓词公式

谓词公式是满足以下规则所产生的一切符号串的总和：

谓词填式/命题常元是公式，称为原子公式
若$A, B$是公式，$x$ 为自由变元，那么$Aland B, Alor B, lnot A, A, Ararr B, Alrarr B, exists x, A, forall x, A$ 均为公式
只有有限次使用上述规则形成的符号串是公式

联结词优先级和括号省略约定和命题逻辑与命题逻辑相同

注意：若 $forall/exists x, A$ 的公式 $A$ 中不包含变元 $x$，则该谓词命题等价于 $A$。

谓词公式成为命题

如果给定个体域，且谓词公式中所有谓词都有明确含义，所有自由变量取定个体，则谓词公式成为一个命题。

可以用数学公式代替谓词形式，数学公式本身则代表了某种谓词逻辑关系。

8.1.7 语句形式化

设个体域为人类，有命题：有人勇敢，但不是所有人勇敢：

$$exists People, Brave(People)landlnot(forall People, Brave(People))$$

8.1.8 谓词公式真值条件

讨论谓词公式的真值，需要满足以下条件：

给定个体域
所有谓词都有明确意义
所有自由变元取定个体

永真式

对于永真式的讨论始终是逻辑的重要部分，对于谓词公式，有不同层次的永真，给定个体域 $D$，公式 $A$ 中所有谓词符号的解释 $I$：

若自由变元 $x_1, x_2cdots x_n$ 在取值 $u_1, u_2cdots u_n$ 处公式为真，则称 $A$ 在 $u_1, u_2cdots u_n$ 处为真
若在谓词解释 $I$下，$A$ 自由变元在任何取值下公式为真，则称 $A$ 在解释 $I$ 下为真
在个体域 $D$ 下，$A$在每个解释 $I$ 下为真，称 $A$ 在 $D$ 上永真
$A$ 在任何个体域下为真，称 $A$ 永真

对谓词公式A的解释I定义如下: 指定一个论域D，有时为了强调这个论域，称I在D上的解释。对A中出现的每一个n元函词，指定一个D上的n元个体函数常量。对A中出现的每一个n元谓词，指定一个D上的n元谓词常量。对A中出现的每一个个体变元，指定D中的一个个体常量。对A中出现的每一个命题变元，指派一个真值T或F。即所谓的对谓词公式的解释类似于对谓词命题的取值列举。

可满足式和永假式

至少有一种方法使 $A$ 为真，$A$ 为可满足式
与第四种永真相同前提下，$A$ 永远为假为永假式

8.1.9 谓词公式的逻辑等价和逻辑蕴含

有 $Aequiv B$ 当且仅当对一切情况 $A$ 和 $B$ 有相同的真值
有 $Amodels B$ 当且仅当 $A$ 的所有成真赋值均为 $B$ 的成真赋值

8.2 谓词逻辑运算

8.2.1 重要永真式

同命题逻辑相同，谓词逻辑同样有许多重要的永真式：

所有命题逻辑的重言式均为谓词逻辑重言式
当 $A$ 不包含 $x$ 时, $(forall x, A)equiv A | (exists x, A)equiv A$
有 $forall x, A(x) models A(x) | A(x)models exists x, A(x) | forall x, A(x)models exists x, A(X)$
有 $lnotexists/forall x, lnot A(x) equiv forall/exists x, A(x)$ 这条说明了逆否命题同原命题的等价性
有 $lnotexists/forall x, A(x)equiv forall/exists x, lnot A(x)$

$B$ 不包含 $x$ 时:

有 $(forall/exists x, A(x)) lor B equiv forall/exists x, (A(x)lor B)$
有 $(forall/exists x, A(x)) land B equiv forall/exists x, (A(x)land B)$

$B$ 包含 $x$ 时：

有 $forall x, (A(x)land B(x)) equiv (forall x, A(x)) land (forall x, B(x))$
有 $(forall x, A(x)) lor (forall x, B(x)) models forall x,(A(x)lor B(x))$
有 $exists x, (A(x)land B(X)) models (exists x, A(x))land (exists x , B(x))$
有 $exists x, (A(x)lor B(X)) equiv (exists x, A(x))lor (exists x , B(x))$

8.3 量词的组合与顺序

值得注意，谓词公式中的量词不能随意改变顺序，以下是一些规则：

有 $forall x forall y, A(x,y) equivforall yforall x , A(x,y)$
有 $forall xforall y, A(x,y) models exists y forall x, A(x,y)$
有 $exists yforall x, A(x,y)models forall xexists y, A(x,y)$
有 $forall xexists y , A(x,y) models exists yexist x, A(x,y)$
有 $exists xexists y , A(x,y) equiv exists yexists x , A(x,y)$

当 $C$ 中无变元时：

有 $forall/exists x, Crarr A(x)equiv Crarrforall/exists x, A(x)$
有 $forall x, (A(x)rarr B(x))models forall x, A(x)rarr forall x, B(x)$

8.4 一阶谓词演算形式系统

First order predicate Calculus，简称 FC

8.4.1 FC符号系统

个体变元 $x,y,z,u,v,w$
个体常元 $a,b,c,d,e$
个体间运算符号 $f^{(n)}(cdots), g^{(n)}(cdots)$，其中 $n$ 代表自由变元个数
谓词符号 $P^{(n)}, Q^{(n)}, S^{(n)}$
真值联结词 $lnot, rarr$

8.4.2 FC高级语言成分

括号 $(, )$
个体项(term) 简称项: 变元常元均为项
对任意正整数，若 $f^{(n)}$ 为n元函数符，$t_1, t_n$ 为项，则 $f^{(n)}$ 也是项
除有限次使用以上条款得到的符号串外没有别的东西是项

8.4.3 合式公式

合式公式(Well-formed Formula)，简称公式。满足以下规则：

对任意非负整数 $n$，$P^{(n)}$ 为 $n$ 元谓词符，$t_1-t_n$ 为项，则 $P^{(0)}(Constant), P^{(n)}(t_1,t_2cdots t_n)$为公式
若$A, B$为公式，$v$ 为个体变元，则$(lnot A), (Ararr B), ( forall v, A(v))$ 为公式

8.4.4 全称封闭式

若 $v_1-v_n$ 为公式中的自由变元，那么$forall v_1forall v_2cdotsforall v_n, A$或$forall v_1forall v_2cdotsforall v_n, A(v_1, v_2cdots v_n)$ 称为全称封闭式

若A中不含自由变元，全称封闭式可以是其本身

8.4.5 公理

对于 FC 运算系统，同样有公理：

A1-A3：同 PC 公理
A4: $forall x, A(x)rarr A(t/x)$ (t/x 指用 t 替换 x)
A5: $forall x, (A(x)rarr B(x))rarr(forall x, A(X)rarrforall x, B(x))$
A6: $Ararr forall x, A$ 其中 $A$ 是不包括自由变元 $x$ 的公式
A7: 1-6的全称封闭式都是 FC 的公理

8.4.6 推理规则和重要性质

同PC

8.4.7 重要规则

全称引入规则
存在消除规则

8.5 ND

9 集合论

集合论是以集合概念为基础，研究集合一般性质的学科。

集合是比数更初级的概念，是一些确定的，相异的个体的总和。

9.1 集合的分类

集合可以分为有限集合和无限集合，而集合论研究的主要范畴是无限集。而对于无限概念，有以下理解：

潜无限：进程的无限，指永远延续无法完成的进程
实无限：作为已经完成整体的无限，例如自然数集

9.2 朴素集合论

康托尔证明了单位长度数轴上的点同整个空间中点的等价关系，并引入了基数等一系列概念，建立了朴素集合论，但第三次数学危机的出现使朴素集合论的理论受到了冲击。

这说明关于无限集的一切性质都不是人能通过主观直接理解的，需要理性的论证和逻辑推演。

9.3 公理化集合论

9.3.1 集合定义

集合(set)是作为整体识别的，相互区别的，确定的一些对象的总体

整体识别：这些对象是集合的基本研究单位，不再分割
相互区别：这些对象是各异的
确定：这些对象属于或者不属于集合是确定的

9.3.2 集合基本概念

集合的组成对象：称为成员或元素。其可以是任何具体或抽象事物，也可以是集合，但不能是这个集合本身。
集合记号 $lbrace rbrace$
元素与集合间的隶属关系：$ain A, anotin A$
空集：没有任何元素的特点集合称为空集，记作 $varnothing=lbracerbrace=lbrace x|xneq xrbrace$
有限集：空集和只包含有限多个元素的集合的总称
无限集：不是有限集的集合（直接的定义相当困难）

9.3.3 规定集合的方式

列举法

将所有元素列举，如 $A=lbrace 1,2,3,4rbrace$

描述法

用谓词公式描述集合中元素的特征，如 $A=lbrace x|x<1rbrace$

归纳法

归纳定义(Inductive Definition)

基础条款：规定某些元素为待定义集合成员，集合其他元素可以从其他元素出发逐步确定
归纳条款：规定由一确定的集合元素去进一步确定其他元素的原则
终极条款：只有以上条款产生的才是集合成员
前两者被称为完备性条款
后者被称为纯洁性条款

9.4 集合论三大基本原理

9.4.1 外延公理

9.4.2 概括公理

9.4.3 正规公理

9.5 子集合

9.5.1 子集合概念

真子集：若 $Asube Bland Aneq B$，则形成真子集，记作 $Asub B$

9.5.2 子集合性质

有时候隶属和包含关系同时成立，如 $lbrace 1rbracein/subelbrace 1, lbrace 1rbracerbrace$
定理一：对于任意集合 $A$ 和 $B$，$A=Blrarr (Asube B)land(Bsube A)$
定理二：设任意集合 $A,B,C$，若$(Asube B)land (Bsube C)rarr Asube C$ （注意：包含有传递性，但隶属不一定。）
定理三：对任意集合 $A$，$models Asube rm U$
定理四：对任意集合 $A$，$models varnothing sube A$
定理五：空集是唯一的
定理六：对有限集合 $card(A)=n$，$A$ 的子集的个数为 $2^n$

9.6 集合基本运算

集合运算指以集合为运算单位，结果还是集合的运算

并运算(Union): $cup: Acup B=lbrace x|xin Alor xin Brbrace$
交运算(Intersection): $cap: Acap B=lbrace x|xin Aland xin Brbrace$
差运算(Difference): $-: A- B=lbrace x|xin Aland xnotin Brbrace$
补运算(Complement): $overline: overline A=U-A=lbrace x|xnotin Arbrace$

9.6.1 集合运算基本性质

等幂律：$Acup A=A, Acap A=A$
交换律：$Acup/cap B=Bcup/cap A$
结合律：$Acup/cap(Bcup/cap C)=(Acup/cap B)cup/cap C$
分配律：
与特殊集合运算：
有：$Acup(Acap B)=A$

差和补运算性质：

特殊集合：A-A A-space A-u
A-(b or c)=(a-b)and(a-c)
A-(b and c)=(a-b)or(a-c)
not not A=a,not u=space, not space=u
a and not a=space a or not a=u
demogen
a-b =a and not b

集合运算与子集关系

asube alor b
acap b sube A
a-bsube A
asube Bequiv a-b=varnothing equiv acup b=bequiv acap b=a
asube B, not Bsube not A

运算性质证明

aland b=u alor b = varnothing proof b= not a proof1: 按照集合等价定义证明证明二：运算性质证明 A= aland u=aland(blor not b)=aland blor aland not b=varnothing lor aland not b=(bland not b)lor aland not b=not bland (alor b)=uland not b=not b qed

幂集power set:a的所有子集构成的集合对于任意集合A，rho A=x/xin A 易知 Ain rho A,varnothing in rho A card(rho A)=2^card(A)

幂集的性质： asube b 当且仅当 rho asube rho b

集合族 collections 每一个元素都是集合的集合

集合族的标志集若集合族C能被表示成下标的形式 C={Sd|din D} 则这些下标组成的集合称为集合族的标志集标志集可以是自然数，某些连续的符号例子C={{0},{0,1}…}没有标志集若定义N_n={0,1…n-1},则C的标志集为 Z+ 若集合{Sa,Sb,Sc},则其标志集为{a,b,c} A的幂集也是一个集合族

集合族的运算广义并：集合族中所有集合的并集广义交：同上

集合a和集合族s aland(lor c)=lor{Aland S:sin C} alor(land c)=land(alor S) A-(land C)=lor{a-s:sin c} not(lor C)=land{not S:sin C}

使用集合定义自然数

皮亚诺peano使用五大公理刻画了自然数至少有一个对象为自然数记作0 p2 若n为自然数，则n必恰有一个直接后继，记作n‘ p3 0不是任何自然数的直接后继 p4 如果两个数后继相等，则他们相等 p5 满足上述条件的数是自然数

利用集合运算定义自然数找一个简单集合作为0:varnothig 找一种集合运算定义直接后继：cupcaplnot 并且这种运算不能得到0对应的集合，因为0不是任何数的直接后继通过集合关系反应自然数的顺序性质：subsube

基础条款 varnothing in N 归纳条款若xin N,x’=xcup{x}

事实上 1={0},2={0,1},3={0,1,2}… 则0/in1/in2… o/sube1/sube2…

归纳定义自然数的运算 巨复杂 加法的定义： x+0=x x+y’=(x+y)’ 乘法的定义 xtimes 0=0 xtimes y’=(x*y)+x

归纳原理假设集合A是由归纳定义的集合要证明集合中所有元素具有性质p，即 forallx(xin Ararr P(x)) 证明方法归纳基础：针对归纳定义的基础条款，证明基础条款的所有元素使其为真归纳规则：针对归纳条款得到的一切元素也要满足性质p

数学归纳法正确性证明反证法假设完成以下推理归纳基础 P(0) 为真归纳推理 forallk(P(k)rarr P(k+1)) 但是并非对所有自然数都有性质P 将这些不满足性质P的自然数构成一个非空自然数子集，则该自然数子集必有一个最小的自然数，记作m 显然m>0，记作n+1，这样n一定有性质p，则p（n）为真，而P（m）为假，这显然为假

有序组元素的无序性是集合的特征之一，元素的有序组合如何从集合定义

二元有序组，或称二元组，2-tuple，或者序偶 ordered pairs 设ab为任意对象，称集合族{{a},{a,b}} 为二元有序组 <a,b>

定理 <a,b>=<c,d>，当且仅当a=c,b=d 证明充分性显然必要性 {{a},{a,b}}={{c},{c,d}} 故cup{{a},{a,b}}={{c},{c,d}} cap{{a},{a,b}}={{c},{c,d}} 证毕

N元有序组<a1,a2,a3> n=2时标准定义 n>2时<a1,a2…an>=<<a1,a2,…an-1>,an> ai称为第i分量

笛卡尔积对任意集合，A1tinmesA2指两集合的笛卡尔积 A1times A2={<u,v>|uin A,v in B} A1times A2times …An={A1timesA2…An-1}times An

例子 Atimesvarnothing=varnothingtimes A=varnothing R^2={<x,y>}R^2为笛卡尔平面

一般来说，不满足交换律、结合律 Atimes(B#C)=(Atimes B)#(atimes c) (b#c)times a=(btimes a)#(ctimes a) times是集合运算

证明第一条 <x,y>in Atimes(Blor C) equiv xin Aland yin (Blor C) equiv in A land(yin B lor yin C) equiv (xin A land yin B)lor(xin Aland yin C) equiv(<x,y>,xin a,yin b)lor(<x,y>,xin a,xin c)

定理对任意有线集合A1-An card（A1times A2…times An）=card(A1)times…card(An)

关系的基本概念指各个对象之间的联系和对应最常见的是两组对象之间的联系与对应

关系的定义 R称为A1-An-1到An的n元关系，若R为A1times…An的一个子集，当A1=A2=。。An时称R为A上的n元关系如果R是AtimesB的子集，称其为二元关系，若A=B，称其为A上的二元关系列举法，描述法，归纳法

二元关系空关系varnothing 全关系Atimes B指整个笛卡尔积的集合相等关系子集<x,x> xRy表示<x,y>in R,lnot xRy表示<x,y>notin R dom（R）={x|xin Aland exists y(<x,y>in R)} ran®={y|yin Bland exists x(<x,y>in R)} A称为前域，B称为陪域

关系的表示法集合表示法，前面有例子关系图法前域和陪域都是有线集合‘ 一般的关系图，有向箭头表示元素之间存在关系可以表示前域和陪域相同的关系图

关系矩阵法表示设关系Rsube Atimes B 懂得都懂（

作为集合的关系运算并交叉补补 overline R=Atimes B-R

对应关系矩阵运算 M_R M_S为关系矩阵并则矩阵对应分量做析取交则逐个合取

R^-1={<y,x>|xRy} R-1sube Btimes A 关系矩阵为原矩阵的转置

你运算和并交叉补等都满足分配律 R的逆的逆等于自己 R的逆的补等于R的补的逆 R运算S的逆等于R的逆运算S的逆 Rsube S 当且仅当逆包含

关系合成运算 composition Rcirc S表示xz二元组且xy，yz分别满足rs Rcirc Ssube Atimes C

例子 E_a a上的想等关系 E_b b上的想等关系 Rsube Atimes B E_a circ R=Rcirc E_a =R 上面那条全集换成空集 Rcirc R^-1=E_A R^-1circ R=E_b

关系矩阵的合成计算关系运算的矩阵等于运算关系矩阵的乘积

幂关系有限定理不停自身合成总会得到相同的关系证明： R的任意次幂仍是二元关系二元关系是有限的 Atimes A是有限的抽屉原理可知总有重复的

特殊性质的二元关系

空关系天然是反自反的，但不是自反的若A是空的，那么空关系就是自反的，同时也是反自反的自反是因为前键为假 A上的相等关系既是对称的，又是反对称的

A上的空关系是传递的在所有非空集合上，空关系都是反自反，对称，反对称，传递的全关系是自反，对称传递的想等关系是自反对称反对称传递的整数集合上的整除关系是自反，反对称，传递的三角形的相似全等关系都是自反，对称，传递的

关系特性的一些定理 R自反 lrarr E_A sube R R反自反，当且仅当与自反没有交集对称则与其逆矩阵等价

运算空间是封闭的

12 等价关系

等价关系R定义为：A上的自反、对称、传递的二元关系 [katex display=true]XRX\ \ xRy\rarr yRx\ \ xRy\land yRz\rarr xRz[/katex]

12.1 等价类

设 [katex]R[/katex] 为 [katex]A[/katex] 上的等价关系，对于每个 [katex]a\in A[/katex]，[katex]a[/katex] 的等价类记作 [katex][a]_R[/katex]，定义为：[katex][a]_R=\lbrace x\in A\land xRA\rbrace[/katex]，其中 [katex]a[/katex] 称为 [katex][a]_R[/katex]的代表元素。

等价类是[katex]A[/katex]的子集，每个代表元素代表一个等价类

有如下例子：

“模2相等”关系有两个等价类，[katex][0][/katex][katex][1][/katex]

12.1.1 等价类的性质

任何一个等价关系，等价类总不会是空集
同一个等价类可能有不同的代表元素

12.1.2 等价类定理

[katex]R[/katex]是[katex]A[/katex]上的等价关系，[katex]\forall a,b\in A[/katex]，[katex]aRb[/katex]当且仅当[katex][a]_R=[b]_R[/katex]
[katex]R[/katex]是[katex]A[/katex]上的等价关系，[katex]\forall a,b\in A[/katex]，则要么则任意的[katex][a]_R=[b]_R[/katex]，要么[katex][a]_R\cap[b]_R=\varnothing[/katex]

12.2 划分

空间的子集的集合族，且均不空，无交集，并集为该空间

[katex]A=\lbrace 1,2,3,4 \rbrace,\ \pi_1=\lbrace \lbrace 1 \rbrace ,\ \lbrace 2,3,4\rbrace \rbrace[/katex]

12.3 等价关系与划分

所有等价类的集合，构成 [katex]A[/katex]的一个划分，将其称作等价关系对应的划分。

反之，集合 [katex]A[/katex] 的一种划分 [katex]\pi[/katex]，也对应 [katex]A[/katex] 上的一个等价关系 [katex]R[/katex]，称其为划分对应的等价关系

12.3.1 等价关系与划分的一一对应

对应[katex]\pi[/katex] 的等价关系为 [katex]R[/katex]，当且仅当 [katex]R[/katex] 对应的划分为 [katex]\pi[/katex]

证明：略

12.4 划分之间的关系

我们用“粗细”概念比较划分，若 [katex]|\pi|[/katex] 越多，代表划分越细，反之则越粗。

12.4.1 细于关系

细于：[katex]\forall A\in \pi_1,\exists B\in \pi_2,A\sube B[/katex]，则我们称[katex]A[/katex]细于 [katex]B[/katex]，记作[katex]\pi_1\leq \pi_2[/katex]
真细于：若 [katex]\pi_1\leq \pi_2\land \pi_1\neq \pi_2[/katex]，我们称 [katex]\pi_1[/katex] 真细于 [katex]\pi_2[/katex]，记作[katex]\pi_1<\pi_2[/katex]

12.4.2 划分比较与子集的关系

[katex]\pi_1,\ \pi_2[/katex]分别是等价关系 [katex]R_1,\ R_2[/katex] 的划分，那么[katex]R_1\sube R_2\lrarr \pi_1\leq\pi_2[/katex]

定理说明：

越小（包含二元组越少）的等价关系对应越细的划分
最小的等价关系是相等关系 [katex]E_A[/katex]，对应最细的划分：每个单元仅包含一个元素
最大的的等价关系是全关系，对应最粗的划分：仅有一个单元

12.5 划分的运算

对应于等价关系的交、并运算，划分也有对应的运算

12.5.1 积划分

有划分[katex]\pi_1,\ \pi_2[/katex]，则其积划分 [katex]\pi_1\cdot\pi_2[/katex]满足以下条件：

[katex]\pi_1\cdot\pi_2\leq\pi_1\land\pi_1\cdot\pi_2\leq\pi_2[/katex]
[katex]\forall \pi\leq\pi_1\land\pi\leq\pi_2,\ \pi\leq\pi_1\cdot\pi_2[/katex]
即积划分是所有比原划分细的划分中最粗的

积划分对应的等价关系是等价关系的交运算。

12.5.2 和划分

有划分[katex]\pi_1,\ \pi_2[/katex]，则其和划分 [katex]\pi_1+\pi_2[/katex]满足以下条件：

[katex]\pi_1\leq\pi_1 +\pi_2\land\pi_2\leq\pi_1 +\pi_2[/katex]
[katex]\forall \pi\geq\pi_1\land\pi\geq\pi_2,\ \pi\geq\pi_1+\pi_2[/katex]
即和划分是所有比原划分粗的划分中最细的

和划分并不等价于等价关系的并运算，这是因为等价关系的传递性对于并运算不具有封闭性

12.5.3 商集

13 序关系

序关系 [katex]R[/katex] 定义为：集合 [katex]A[/katex] 上的自反、反对称、传递的的二元关系

存在序关系的集合称为有序集，表示为 [katex]<A,R>[/katex]，一般的有序集表示为 [katex]<A,\leq>[/katex]

13.1 哈斯图

哈斯图（Hasse Graph）是对序关系关系图的一种简化画法，满足以下要求：

由于序关系是自反的，因此每个节点都有环，省去这些环
由于序关系反对称且传递，因此关系图中任何两个节点都不会有双向边或通路，因此省去箭头，把向上的方向定义为箭头方向
由于序关系存在传递性，因此省略所有推定的边

哈斯图表明了在一组序关系中，并非所有的元素都会产生比较关系，例如 [katex]<\lbrace 2,3,4,8,12\rbrace , |>[/katex]中2和3不存在序关系。

13.2 有序集元素的排序

[katex]a\leq b[/katex] 称a先于或等于b；a小于或等于b

13.3 上/下界

上界：大于等于所有元素
下界：小于等于所有元素
上确界：上界集合最小元
下确界：下界集合最小元
最大/最小元一定是上/下确界

13.4 链和反链

链满足以下条件：

子集 [katex]B[/katex] 中的任意一个元素都要可以比较
[katex]\forall x\forall y\in B,\ x\leq y\land y\leq x[/katex]

反链满足：

子集中任意两个元素都不可比较
[katex]\forall x\forall y\in B,\ \lnot(x\leq y\land y\leq x)[/katex]

13.4.1 链和反链定理

对于集合 [katex]A[/katex]，存在最长链长度为 [katex]n[/katex]，则 [katex]A[/katex] 存在一个划分，能将其分为 [katex]n[/katex] 个反链。

14 半序关系

满足反自反，反对称，传递的二元关系

15 函数

有二元关系 [katex]f\sube X\times Y[/katex]，对于每个 [katex]x\in X[/katex]，有唯一的 [katex]y\in Y[/katex]与之对应，且[katex]<x,y>\in f[/katex]，则称其为函数，记作[katex]f:x\rarr y[/katex]

当[katex]X=X1\times X2\cdots\X_N[/katex]，则称其为多元函数
函数有单值性
函数表示为 [katex]y=f(x)[/katex]，称[katex]y[/katex]为[katex]x[/katex]的像点，[katex]x[/katex]为[katex]y[/katex]的源点

15.1 函数的规定方法

列表法：列举所有序偶
图表法：用坐标系上的点集表示函数
解析法：用算术表达式或其他命名式表示函数
递归定义定义函数

15.2 函数的相等和包含

若[katex]f:A\rarr B,\ g:C\rarr D,\ A=C,\ B=D\rarr f=g[/katex]

15.3 函数的个数

[katex]|X|=m,\ |Y|=n,|\lbrace f|f:X\rarr Y\rbrace|=n^m[/katex]

15.4 定义域子集的映像image

定义域子集对应函数值的集合

15.5 函数的合成

以类似传递的方式可以把两个函数合成，且合成后仍是函数

15.6 单射，满射和双射

15.6.1 单射函数

[katex]x\neq y\rarr f(x)\neq f(y)[/katex]

单数函数的合成仍然是单射函数

15.6.2 满射函数

[katex]\forall y,\ \exists x,\ f(x)=y[/katex]

满射函数的合成仍然是满射函数

15.6.3 双射函数

既是单射又是满射，也称为一一映射函数

双射函数的合成仍然是双射
满射函数和单射函数的合成是双射函数

15.7 逆函数

只有单射函数的逆才满足单值性
只有满射函数的逆才能使定义域全
因此只有双射函数有逆函数

对于非双射函数，也存在类似于逆函数的对应函数

左逆函数：若其与函数的合成为x单位矩阵，称其为左逆函数，这样的函数只可能是单射
右逆函数：若函数与其合成为y单位矩阵，则其为右逆函数，这样的函数只可能是满射

16 图

基本见FDS笔记

16.1 图的基本概念

简单图：无环和重边的无向图
完全图：任意两个结点间都有边关联的简单图
孤立结点：没有边相连的结点
零图：全是孤立结点的图

16.2 赋权图

[katex]G=<V,E,f,g>[/katex]

结点权函数：
边权函数
普通图只研究拓扑关系
赋权图附加了数量关系

16.3 度的性质

16.4 正则图

所有顶点度数相同的图称为正则图，顶点度数为 [katex]k[/katex] 称为 k-正则图。[katex]K_n[/katex] 是 n-1 正则图。

16.5 子图和生成子图

生成图指 [katex]G_1\sube G_2\land V_1=V_2[/katex]

16.6 补图

结点相同，边没有公共边，且并集构成完全图

16.7 图的同构

结点数和边数相同且能够通过将一张图的结点一一置换为另一张图结点名后变为另一张图的两张图形成同构。

16.8 拟路径

一个结点一个边的方式记录两个结点间的路径

16.8.1 路径

拟路径中的边无重合则称为路径

16.8.2 通路

顶点不重合的路径

16.8.3 起点终点一样的路径称为闭路径

16.9 路径与通路的性质

路径和通路定理有拟路径必有路径，必有长度不大于结点数减一的通路

16.10 连通性

起点终点相同或存在一条路径联通的无向图指无向图中任意两个顶点都是科大的强连通的有向图指任意两个顶点互相可达单向连通有向图指任意两个顶点至少一个可以到达另一个

16.11 欧拉图及欧拉路径

欧拉图：如果有一条经过所有顶点所有边的闭路径
欧拉路径：有一条通过所有顶点所有边的路径

16.11.1 欧拉图的充分必要条件

无向图：连通且所有顶点的度都是偶数
有向图，弱连通且每个顶点的出度与入度相同

16.11.2 欧拉路径的充分必要条件

无向图：连通且恰有两个顶点的度为奇数
有向图：恰有两个顶点入度不等于出度，且一个出度比入度大1，一个入度比出度大1

16.12 汉密尔顿图及汉密尔顿通路

哈密顿图：一条经过所有顶点的回路（不要求经过所有边）
汉密尔顿通路：不需要是回路

16.12.1 判定定理

一些充分非必要的定理：

每一对顶点度数之和不小于顶点总数-1则有一条汉密尔顿通路
每一对顶点度数之和不小于顶点总数，且顶点总数大于等于3

16.13 邻接矩阵

见FDS笔记

拟路径：邻接矩阵自乘l次后 [katex]a_{i,j}[/katex] 代表由 [katex]i[/katex] 到 [katex]j[/katex] 有 [katex]a_{i,j}[/katex] 条长度为 [katex]l[/katex] 的拟路径

16.14 关联矩阵（简单无向图）

表示顶点和边的关联关系
通过矩阵的秩来判定图的连通分支个数

16.15 路径矩阵

[katex]A^{\lbrace m \rbrace}=A\land A\cdots\land A[/katex]
[katex]B=A\lor A^2\cdots\lor A^{|v|}[/katex]上述析取合取代表矩阵加法和乘法
[katex]P=E^{|v|}\lor B[/katex]

16.16 二分图

满足以下条件的无向集：

考虑结点集合的一个划分 [katex]X，\ Y[/katex]
且所有边均由一个集合指向另一个集合，集合内部不存在边
若每个顶点之间都有边，则称其为 完全二分图，称为[katex]K_{|X|,|Y|}[/katex]

16.16.1 二分图的等价条件

至少有两个顶点，且所有回路的长度均为偶数

16.16.2 匹配

将 [katex]E[/katex] 的一个子集如果任意两条边都没有公共端点，则其被称作一个匹配
边数最多的匹配称为最大匹配
若 [katex]U/V[/katex] 的所有端点出现在这一匹配中，称作 U/V-完全匹配

16.16.3 最大匹配：匈牙利算法

任取一个匹配M（可以是空集或者只有一条边）
令S为非饱和点（尚未匹配的点）的集合
如果所有点已经匹配，则已经是最大匹配
从S中取出一个非饱和点作为起点，从此起点走交错路P（一步在M中一步不在M中）
若P为增广路（终点也是非饱和点），则令[katex]M=M\oplus P=(M-P)\cup(P-M)[/katex]
若P永远不是增广路，则去掉该点回到第三步重新匹配

16.17 平面图

一个图是否可以画成任意两条边都不相交的样子？

平面图：如果无向图G可以在一个平面上图示出来且只在顶点处相交，称其为平面图
[katex]K_5,K_{\lbrace 3,3\rbrace}[/katex] 都是平面图

16.17.1 平面图等价条件

G或者G的子图经过任何同胚操作后都不以[katex]K_5,K_{\lbrace 3,3\rbrace}[/katex]为子图
同胚操作：增加或删除二度结点

16.18 树

树是简单图
树是二分图
树是平面图
任意两个节点仅有一条通路，没有回路

16.18.1 生成树

是树的生成子图称为生成树。

16.18.2 根树

一个孤立结点是根树，[katex]v_0[/katex] 称为树根
讲根树与已有根树的根做边

17 代数

17.1 代数结构与抽象代数

代数结构：在一个对象集合上定义若干运算，并设定若干公理描述运算的性质
抽象代数：抛弃代数结构中对象集合与运算的具体意义，研究运算一般规律，研究针对运算的特殊对象并对代数结构进行分类研究

概率论

入典：这门课真的很简单！大家都认真学，不可能的！看看你左边右边，两个人一定有一个不认真学的！难度不会高于高中一些中档题的！

1 概率含义

1.1 概率性质

2 概率公式

2.1 全概率公式

2.2 贝叶斯公式

3 独立

3.1 独立的定义

A与B独立当且仅当: [katex display=true]P(AB)=P(A)P(B)[/katex]

3.2 独立与互斥的区别

独立与互斥并不是一种等价关系，A 与 B 同时满足 [katex]P(AB)=0[/katex] 和 [katex]P(AB)=P(A)P(B)[/katex] 当且仅当其中一者为零概率事件。

3.3 三者独立的条件

A, B, C互相独立当且仅当任意两者相互独立，即满足以下条件：

[katex]P(AB)=P(A)P(B)[/katex]
[katex]P(AC)=P(A)P(C)[/katex]
[katex]P(BC)=P(B)P(C)[/katex]
[katex]P(ABC)=P(A)P(B)P(C)[/katex]

4 随机变量

随机变量是定义在某个样本空间上的结果的取值集合，同时这个空间上的概率函数将随机变量的每一个取值与结果一一映射。随机变量满足以下规则：

使用大写字母命名随机变量，小写字母代表常量
可能的变量取值的集合被称为随机变量的范围（range）
我们使用 [katex]S_X[/katex] 来表示随机变量 [katex]X[/katex] 的取值范围
[katex]S(x)[/katex] 表示随机事件 [katex]S[/katex] 在结果 [katex]x[/katex] 下的对应随机变量的值，而不是这一事件发生的概率