信息安全原理与数学基础(三)

基本信息

授课教师：zbs

Lecture 07 集合论

世界上所有的马都是同一个颜色

忽略了数学归纳法的 base，即从 k = 1 到 k = 2 是伪的

 

集合的概念

集合就是集合

按照集合中事物数目是否有限，分为有限和无限集合

• 全部的集合论的历史，都是围绕无限开始的
  • 潜无限：无限的过程 自然数列 1, 2, 3, …, n, …
  • 实无限：完成的整体 自然数的整体 {1, 2, 3, …, n, …}

集合论需要纯理性的论证，不能用直观和常识简单掌握

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

组成集合的对象称为成员或元素

• 元素可以是任何具体或抽象的事物
• 元素也可以是集合

 

元素和集合的隶属关系

$a\in A$

$a\notin A$

 

规定集合的方式

• 列举法
• 描述法：利用谓词公式
• 归纳法

 

基本概念

$\empty=\lbrace\rbrace$

• 有限集合：空集和有限元素的集合
• 无限集合

基数

 

三大基本公理

1. 外延公理
   • $A=B\lrarr\forall x(x\in A\lrarr x\in B)$
2. 概括公理
   • $S=\lbrace x|x\in U\land P(x)\rbrace$
3. 正规公理
   • $\nexists A_1, A_2, A_3, …,s.t.\ …\in A_3\in A_2\in A_1$
   • 集合不能是自己的元素：$A=\lbrace A\rbrace$ 是非法的

 

子集合

$\forall x(x\in A\to x\in B)\to A\sube B$

$\lbrace1\rbrace\sube\lbrace1,\lbrace1\rbrace\rbrace$

$\lbrace1\rbrace\in\lbrace1,\lbrace1\rbrace\rbrace$

定理

1. $A=B\iff A\sube B,B\sube A$

2. $(A\sube B)\land(B\sube C)\to A\sube C$

3. $\forall A,A\sube U$

4. $\forall A,\empty\sube A$

5. 空集是唯一的

6. $A为有限集合，|A|=n,则A的子集个数为2^n=\displaystyle\sum_{i=0}^n C_n^i$

 

Lecture 08

真子集

$A\sube B,A\ne B\to A\sub B$

 

集合的基本运算

1. Union $A\cup B\iff x\in A\land x\in B$
2. Intersection $A\cap B\iff x\in A\lor x\in B$
3. Difference $A-B\iff x\in A\land x\notin B$
4. Complement $\overline{A}=U-A\iff x\notin A$

 

交和并的运算性质

• $A\cup A=A,A\cap A=A$
• 交换律
• 结合律
• $A\cup\empty=A,A\cup U=U,A\cap\empty=\empty,A\cap U=A$
• 分配律
• $A\cap(A\cup B)=A,A\cup(A\cap B)=A$

 

差和补的运算性质

• $A-A=\empty,A-\empty=A,A-U=\empty$
• $A-(B\cup C)=(A-B)\cap(A-C)$
• $A-(B\cap C)=(A-B)\cup(A-C)$
• $\overline{A}\cup A=U,\overline{A}\cap A=\empty$
• 德摩根律
• $A-B=A\cap\overline{B}$

 

集合运算和子集的关系

• $A\sube A\cup B$
• $A\cap B\sube A$
• $A-B\sube A$
• $(A\sube B)\equiv(A-B=\empty)\equiv(A\cup B=B)\equiv(A\cap B=A)$
• $A\sube B\to\overline{B}\sube\overline{A}$

 

幂集 power set

$\rho(A)=\lbrace x|x\sube A\rbrace$

• $\empty\in\rho(A),A\in\rho(A)$
• $|\rho(A)|=2^{|A|}$

幂集的性质

• $A\sube B\lrarr\rho(A)\sube\rho(B)$

 

集合族 collection

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

集合族的标志集

• $集合族C=\lbrace S_d|d\in D\rbrace,则D记作C的标志集$

 

集合族的运算

广义并：所有集合的并集 $\cup C=\lbrace x|\exist S(S\in C\land x\in S)\rbrace$
广义交：所有集合的交集 $\cap C=\lbrace x|\forall S(S\in C\to x\in S)\rbrace$

• $\cup C=\bigcup_{d\in D}S_d$
• $\cap C=\bigcap_{d\in D}S_d$

 

集合族运算的性质

$A\cap(\cup C)=\cup(A\cap S:S\in C)$
$A\cup(\cap C)=\cap(A\cup S:S\in C)$
$A-(\cap C)=\cup(A-S:S\in C)$
$A-(\cup C)=\cap(A-S:S\in C)$
$-(\cup C)=\cap(\overline{S}:S\in C)$

 

归纳定义

归纳定义 Inductive definition

1. 基础条款：规定哪些元素是属于待定义集合
2. 归纳条款：规定如何从已确定的集合元素进一步确定其他元素
3. 终极条款：规定待定义的集合只含有上述元素

1+2：完备性条款
3：纯粹性条款

归纳法定义Vanadium的生日：

• 基础条款：Vanadium出生的那天是Vanadium的生日
• 归纳条款：如果某天是Vanadium的生日，那么这一天的整一年以后也是Vanadium的生日
• 终极条款：除了上面两条包括的日子，其他任何一天都不是Vanadium的生日

 

归纳原理

$对于谓词P确定的归纳集合A，归纳条款函数为g$

• $证明\forall x_0\in A,P(x_0)=T$
• $证明\forall x_0,P(g(x_0))=T$

 

定义自然数

• P1：至少有一个对象是自然数，记作 $0$
• P2：如果 $n$ 是自然数，那么 $n$ 必定恰巧有一个直接后继 $n^\prime$
• P3：$0$ 不是任何自然数的后稷
• P4：如果 $m，n$ 的直接后继相同，则 $m=n$

加法

• $x+0=x$
• $x+y^\prime=(x+y)^\prime$

乘法

• $x\otimes0=0$
• $x\otimes y^\prime=(x\otimes y)+x$

 

利用集合定义自然数

• $\empty\in N$
• $x\in N\to x^\prime\cup\lbrace x\rbrace\in N$
• 略

$0\in1\in2\in…,0\sube1\sube2…$

Lecture 09

有序组

二元有序组

称集合族 {a, {a, b}} 为二元有序组 / 二元组 / 序偶 <a, b>，其中a，b分别称为第一分量和第二分量

• $<a,b>=<c,d>\iff a=b,c=d$

 

N元有序组

递归定义

$<a_1, a_2, … a_n> = <<a_1, a_2, …, a_{n-1}>, a_n>,n\ge2$

 

笛卡尔积

对任意集合 $A_1,A_2$，称$A_1\times A_2$为笛卡尔积

• $A_1\times A_2=\lbrace<u,v>|u\in A_1,v\in A_2\rbrace$
• 不支持结合律，不支持交换律
• $\empty\times A=A\times\empty=\empty$
• $R^2=R\times R$: 笛卡尔平面
• $R^3=R\times R\times R$: 笛卡尔空间

 

笛卡尔积对集合运算的分配律

$\forall A,B,C,\forall \#\in\lbrace\cap,\cup,-\rbrace$

• $A\times(B\#C)=(A\times B)\#(A\times C)$
• $(B\#C)\times A=(B\times A)\#(C\times A)$

 

笛卡尔积的基数关系

对有限集合 $A_i$

$|A_1\times A_2\times…\times A_n|=|A_1|\cdot|A_2|\cdot…\cdot|A_n|$

 

关系

关系是两组对象之间的联系和对应，采用二元组或多元组的集合来表示关系

$R为A_i的n元关系，R\sube A_1\times A_2\times…\times A_n$

• $若A=A_i,则R是A上的n元关系$
• $若n=2，则R上A上的二元关系$

 

二元关系

• 空关系 $\empty\sube A\times B$
• 全关系 $A\times B$
• 相等关系 $E_A=<x,x>|x\in A$
• $xRy:<x,y>\in R;\lnot xRy:<x,y>\notin R$
• $\mathrm{Dom}(R)=\{x|x\in A\land\exist y(<x,y>\in R)\}$
• $\mathrm{Ran}(R)=\{y|y\in B\land\exist x(<x,y>\in R)\}$
• A: 前域，B: 陪域

关系的表示法

• 集合表示法
• 关系图法
  • 前域 $=$ 陪域
  • 前域 $\ne$ 陪域
• 关系矩阵法
  • $m_{ij}=1\iff a_iRb_j$
  • $m_{ij}=0\iff \lnot a_iRb_j$

 

关系运算

关系相等

• $若R,S有相同的前域和陪域，则R=S\iff\forall x\forall y(xRy\lrarr xSy)$

作为集合的运算

• $R\cup S=\{<x,y>|xRy\lor xS\}$
• $R\cap S=\{<x,y>|xRy\land xSy\}$
• $R - S = \{<x,y>|xRy\land\lnot xSy\}$
• $\overline{R}=\{<x,y>|\lnot(xRy)\}$
• $R^{-1}=\{<y,x>|xRy\sube B\times A\}$

作为矩阵的运算

• $M_{R^{-1}}={M_R}^{-1}$

 

关系运算的性质

• ${(R^{-1})}^{-1}=R$
• ${\overline{R}}^{-1}=\overline{R^{-1}}$
• $(R\#S)^{-1}=R^{-1}\#S^{-1}$
• $R\sube S\iff R^{-1}\sube S^{-1}$

 

关系合成运算

$R\sube A\times B,S\sube B\times C,A\circ B\sube A\times C$

• $E\circ R=R\circ E=R$
• $\empty\circ R=R\circ\empty =\empty$
• $R\circ R^{-1}=E_A$
• $R^{-1}\circ R=E_B$

兄弟和父子关系合成是叔侄关系哦

这里用矩阵运算特别简单
将数乘换成合取，数加换成析取

 

合成运算的性质

• $R\circ(S\cup T)=(R\circ S)\cup(R\circ T)$
• $(S\cup T)\circ R=(S\circ R)\cup(T\circ S)$
• $R\circ(S\cap T)\sube(R\circ S)\cap(R\circ T)$
• $(S\cap T)\circ R\sube(S\circ R)\cap(T\circ S)$
• $(R\circ S)^{-1}=S^{-1}\circ R^{-1}$
• 满足结合律

 

关系的幂运算

$R^n=R\circ…\circ R$

• $R^0=E_A$
• $R^{m+n}=R^m\circ R^{n}$
• $(R^{m})^n=R^{mn}$

 

幂关系有限定理

$$|A|=n,R\sube A^2,\exist i,j\in \Bbb{N},s.t.0\le i<j\le 2^{n^2},R^i=R^j$$

 

A上的特殊二元关系

自反关系

$\forall x(x\in A\to xRx)$

反自反关系

$\forall x(x\in A\to\lnot xRx)$

对称关系 symmetric

$\forall x\forall y(x,y\in A\land xRy\to yRx)$

反对称关系 antisymmetric

$\forall x\forall y(x,y\in A\land (xRy\land yRx\to x=y))$

传递关系 transitive

$\forall x\forall y\forall z(x,y,z\in A\land(xRy\land yRz\to xRz))$

• $\empty$ 是反自反的，不是自反的
• $A=\empty$ 那么A上的空关系就是自反的，也是反自反的
• $E_A$ 是对称的，也是反对称的

• 所有非空集合上的空关系是反自反、对称、反对称、传递的；
• 全关系是自反、对称、传递的；
• 相等关系是自反、对称、反对称、传递的
• 整数集合上的整除关系是自反、反对称、传递的
• 三角形的相似和全等关系都是自反、对称、传递的

 

定理

• $R自反\iff E_A\sube R$
• $R反自反\iff E_A\cap R = \empty$
• $R对称\iff R\sube R^{-1}$
• $R反对称\iff R\cap R^{-1}\in E_A$
• $R传递\iff R^2\sube R$

 

运算封闭性

运算	自反	反自反	对称	反对称	传递
交 $\cap$	T	T	T	T	T
并 $\cup$	T	T	T	F	F
差 $-$	F	T	T	T	F
补 $\sim$	F	F	T	F	F
逆 $\kern{}^{-1}$	T	T	T	T	T
合成 $\circ$	T	F	F	F	F

 

等价关系

A 上的自反、对称、传递的二元关系

• 三角形的相似、全等关系
• 舍友关系
• 取模 $x\equiv y\mod k\iff k|(x-y)$

等价类

在 FDS，我们叫他并查集

设 R 是 A 的等价关系，$\forall a\in A,a的等价类[a]_\mathrm{R}=\{x|x\in A\land x\mathrm{R}a\}$

• a 称作代表元素
• 每个代表元素确定一个等价类

• 模 2 相等：$[1], [0]$
• $E_A$ 有 $|A|$ 个等价类，都是单元素集合
• $A\times A$ 只有一个等价类 $A$

等价类的性质

• $[a]_\mathrm{R}\ne\empty$
• $a,b,c,…\in[a]_\mathrm{R}$

等价类定理

• $\forall a,b\in A,a\mathrm{R}b\iff[a]_\mathrm{R}=[b]_\mathrm{R}$
• $\forall a,b\in A,([a]=[b])\oplus([a]\cap[b]=\empty)$

Lecture 11 划分

划分是结婚集合 A 的子集族 $\pi$:

• $\forall B(B\in\pi\to B\ne\empty)$
• $\bigcup\pi=A$
• $\forall B\forall C(B\in\pi\land C\in\pi\land B\ne C\to B\cap C=\empty)$
• specially: $\empty$ 的划分为 $\empty$

等价与划分

等价类的集合构成一个划分

划分对应一个等价关系

等价和划分是一一对应的

划分之间的关系

$|\pi|越大，划分越细$

细于：$\pi_1\le\pi_2\iff$ $\pi_1$ 的每个单元都包含于 $\pi_2$ 的某个单元

• 真细于：$\pi_1<\pi_2\iff\pi_1\ne\pi_2$

细于和子集

$R_1\sube R_2\lrarr\pi_1\le\pi_2$

划分的运算

积划分

$\pi_1\cdot\pi_2$ 是细于两者的最粗划分

对应交运算

和划分

$\pi_1+\pi_2$ 是粗于两者的最细划分

不对应并！！！

定义二元关系闭包 $t(R)$

• $t(R)$ 是 A 上具有传递性质且包含 R 的最小关系

对应并的结果的闭包

商集

称 A 的划分为 A 的 R 商集，$A/R$

序关系

定义：自反、反对称、传递的二元关系

存在序关系的集合称作有序集 $<A,\le>$

• 不大于关系：$<N,\le>$
• 包含关系：$<\rho(A),\sube>$
• 整除关系$<Z^+,|>$

Hasse 图

哈斯图是对序关系的关系图的一种简化画法

• 由于序关系自反，因此各节点都有自环，在哈斯图中省去
• 由于序关系反对称且传递，因此关系图中任何两个不同的结点直接不会有双向的边或通路，所以省去边的箭头，把向上的方向定位箭头方向
• 由于序关系传递，所以省去所有推定的边，即如果 $a\le b，b\le c 有 a\le c$，省去 $ac$ 边

排序

• $a\le b$: a 先于或等于 b
• $\lnot(a\le b)$: a, b 无法比较

最小元，最大元，极小元，极大元

存在不可比较的关系，因此

• 最 强调的是所有元素都能与自己比较
• 极 强调的是不存在比自己大/小的元素（忽视不可比较）

上（下）界

$B\sube A$

B 的上界: $a\in A\land \forall x(x\in B\to x\le a)$
B 的下界: $a\in A\land \forall x(x\in B\to a\le x)$
上确界：上界的最小元
下确界：下界的最大元

定理

• 最大元是上确界
• 上确界且属于B，这是最大元
• 如果有确界，则确界是唯一的

链和反链

链：子集 B 中任何两个元素都是可以比较的
反链：子集 B 中任何两个元素都是不可以比较的

定理

如果 A 中最长的链的长度为 n，则 A 存在一个划分：有 n 个单元，每个单元都是一个反链

半序关系

反自反、反对称、传递的二元关系

• 实数集合的大于关系
• 公司内部员工的下属关系

Lecture 12 函数

$f\sube X\times Y,\forall x\in X,\exists y\in Y,<x,y>\in f\Rightarrow f:X\to Y$

• 前域与定义域重合
• 单值性
  $y=f(x)$
  • y: 像点
  • x: 原点

• 恒等函数 $I_A$
• $y=2x$
• $f_{add}:N\times N\to N,y=x_1+x_2$

函数的规定方法

• 列表法
• 图表法
• 解析法
• 递归定义/归纳定义法

Len(“”)=0
Len(str)=Len(str[1:])+1

函数的相等和包含

$f:A\to B,g:C\to D$

$A=C,B=D,f(x)=g(x)\Rightarrow f=g$
$A\sube C,B=D,f(x)=g(x)\Rightarrow f\sube g$

函数的个数

X 到 Y 到全体函数：$Y^X$

定义域子集的映像

映像：X 的子集到 Y 到子集到映射

$f^\prime(A),A\sube X$

特性

满足交运算，属于并运算和差运算

函数的合成

$f:X\to Y,g:Y\to Z,f\circ g:X\to Z$

$f\circ g(x)\equiv g(f(x))$

反直觉，参照上下文判断

合成满足结合律，不满足交换律

$f\circ f\circ…\circ f=f^n$

$f\circ E_X=E_Y\circ f=f$

等幂函数：$f^n=f$

常见函数的分类

单射函数

$\forall x_1\ne x_2,f(x_1)\ne f(x_2)$

单射的合成也是单射

$g\circ f$是单射，$f$ 是单射

满射函数

$\forall y\exists x,y=f(x)$

满射的合成也是满射

$g\circ f$是满射，$g$ 是满射

双射函数

既是单射也是满射，一一对应

双射的合成也是双射

$g\circ f$是双射，$f$ 是单射，$g$ 是满射

由前两个定理易得

逆函数

$f^{-1}$不一定是函数

• f不是单射，则没有逆函数
• f不是满射，则$Dom(f^{-1})\ne Y$

只有双射有逆，逆也是双射

• $(f^{-1})^{-1}=f$
• $f^{-1}\circ f=E_X$
• $f\circ f^{-1}=E_Y$
• $(f\circ g)^{-1}=g^{-1}\circ f^{-1}$

左逆函数

右逆函数