离散数学第二部分集合论

第六章集合代数

6.1 集合的基本概念

定义梳理

集合、元素、成员：集合是不能精确定义的基本概念。直观地说，把一些事物汇集到一起组成一个整体就称作集合，而这些事物就是这个集合的元素或成员。
元素与集合之间的关系，属于、不属于：元素与集合之间的关系是隶属关系，即属于或不属于，属于记作∈，不属于记作∉
两个集合之间的关系，子集，包含：设A，B为集合，如果B中的每个元素都是A中的元素，则称B是A的子集合，简称为子集。这时也称B被A包含，或A包含B，记B⊆A。如果B不被A包含，则记作B⊈A。

包含的符号化表示为：B⊆A⇔∀x（x∈B→x∈A）
相等：设A，B为集合，如果A⊆B且B⊆A，则称A与B相等，记作A=B。如果A与B不相等，则记作A≠B。
- 相等的符号化表示为 A=B⇔A⊆B∧B⊆A
真子集：设A，B为集合，如果B⊆A且B≠A，则称B是A的真子集，记作B⊂A。如果B不是A的真子集，记作B⊄A
- 真子集的符号化表示为：B⊂A⇔B⊆A∧B≠A
空集：不含任何元素的集合称作空集，记作∅
- 空集可以符号化表示为：∅={x|x≠x}
n元集和m元子集：含有n个元素的集合简称为n元集，它的含有m个元素（m≤n）的自己称作它的m元子集。
单元集：只有一个元素的集合称为单元集。
幂集：设A为集合，把A的全体子集构成的集合称为A的幂集，记作P(A)
- 幂集的符号化表示为：P(A)={x|x⊆A}
全集：在一个具体问题中，如果所涉及的集合都是某个集合的子集，则称这个集合为全集，记作E
- 全集是有相对性的，不同的问题有不同的全集，即使是同一个问题也可以取不同的全集。

定理公式

空集的性质：空集是一切集合的子集。

6.2 集合的运算

定义梳理

并集：设A,B为集合，则A与B的并集A∪B的定义为：A∪B={x|x∈A∨x∈B}
- 可以推广到n个集合：A1∪A2∪A3…∪An={x|x∈A1∨x∈A2∨x∈A3…∨x∈An}
交集：设A,B为集合，则A与B的交集A∩B的定义为：A∩B={x|x∈A∧x∈B}
- 可以推广到n个集合：A1∩A2∩A3…∩An={x|x∈A1∧x∈A2∧x∈A3…∧x∈An}
相对补集：设A,B为集合，B对A的相对补集A-B的定义为：A-B={x|x∈A∧x∉B}
不交：如果两个集合的交集为∅，则称这两个集合是不交的。
对称差集：设A,B为集合，A与B的对称差集A⊕B定义为：A⊕B=(A-B)∪(B-A),有另一种定义为：A⊕B=(A∪B)-(A∩B)
绝对补集：在给定全集E后，A⊆E，A的绝对补集~A定义为： ~A=E-A={x|x∈E∧x∉A}
广义并：设A为集合，A的元素的元素构成的集合称作A的广义并，记作∪A，符号化表示为：∪A={x|∃z(z∈A∧x∈z)}
广义交：设A为非空集合，A的所有元素的公共元素称作A的广义交，记作∩B，符号化表示为：∩A={x|∀z(z∈A→x∈z)}
- 评注：注意广义并和广义交之前的区别，联系之前在第一部分的知识，为何对广义交我们表达为∩A={x|∀z(z∈A→x∈z)}，而不是∩A={x|∀z(z∈A∧x∈z)}？因为此二者有着不同的意义：∀z(z∈A→x∈z)是指对任意A的元素z都包含了x，而∀z(z∈A∧x∈z)是指对任意元素z，z肯定既属于A又包含x，先不说x本来就可以出现在∉A的元素的元素里面，这样的表述本来就是有问题的，因为一般来说在一定的背景中，只有全集才包含了∀z以及∅才为∀z的子集。所以，就会在一般的表述上出现这样的规律：∃后用∧，∀后用→
- 此外，广义交特别强调了集合A非空，而广义并中允许A=∅，这是因为对于广义并∪∅=∅，但是∩∅不是一个集合，在集合论中是没有意义的。
集合运算的优先顺序：称广义并、广义交、幂集、绝对补运算为一类运算，并、交、相对补、对称差运算为二类运算。
1. 一类运算优先于二类运算。
2. 一类运算之间由右向左顺序进行。
3. 二类运算之间由括号决定先后顺序。

6.3 有穷集的计数

定义梳理

文氏图（韦恩图）：集合之间的关系和初级运算可以用文氏图给予形象的表达。
1. 使用文氏图可以很方便地解决有穷集的计数问题。
2. 方法步骤：一般地说，每条性质决定一个集合。有多少条性质，就有多少个集合。如果没有特殊的说明，任何两个集合之间都画成相交的，然后将已知集合的元素数填入表示该集合的区域内。通常从n个集合的交集填起，根据计算的结果将数字逐步填入所有的空白区域。如果交集的数字是未知的，可以设为x。然后根据题目中的条件，列出一次方程或方程组，就可以求得所需要的结果。
欧拉函数：欧拉函数ϕ是数论中的一个重要函数，设n是正整数，ϕ(n)表示{0,1,…,n-1}中与n互素的数的个数

定理公式

包含排斥原理：设S为有穷集，P1,P2,…Pn是n个性质。S中的任何元素x或者具有性质Pi或者不具有性质Pi，两种情况必居其一。（当然，一个元素可以有多个性质，也可以没有以上性质）。令Ai表示S中具有性质Pi的元素的构成的子集，

则S中不具有性质P1，P2,…Pn的元素数为：

$$
|\overline{A_1}∩\overline{A_2}∩…∩\overline{A_n}|\=|S|-\displaystyle\sum^{n}{i=1}|A_i|+\displaystyle\sum{1≤i＜j≤n}|A_i∩A_j|-\\displaystyle\sum_{1≤i＜j＜k≤n}|A_i∩A_j∩A_k|+…+(-1)^n|A_1∩A_2∩…∩A_n|
$$
- ```
推论：S中至少具有一条性质的元素数为：
```
  $$
  |A_1∪A_2∪…∪A_n|=\
  \displaystyle\sum^n_{i=1}|A_i|-\displaystyle\sum_{1≤i＜j≤n}|A_i∩A_j|+\
  \displaystyle\sum_{1≤i＜j＜k≤n}|A_i∩A_j∩A_k|-…+(-1)^n|A_1∩A_2∩…∩A_n|
  $$

6.4 集合恒等式

定理公式

下面的恒等式给出了集合运算的主要算律，其中的A,B,C代表任意的集合。

幂等律：A∪A=A A∩A=A
结合律：
- ∪结合律：(A∪B)∪C=A∪(B∪C)
- ∩结合律: (A∩B)∩C=A∩(B∩C)
交换律:A∪B=B∪A A∩B=B∩A
分配律:
- ∪对∩的分配律:A∪(B∩C)=(A∪B)∩(A∪C)
- ∩对∪的分配律:A∩(B∪C)=(A∩B)∪(A∪C)
同一律:A∪∅=A A∩E=A
零律:A∪E=E A∩∅=∅
排中律:A∪~A=E
矛盾律:A∩~A=∅
吸收律:A∪(A∩B)=A A∩(A∪B)=A
德摩根律:
- 并集相对补:A-(B∪C)=(A-B)∩(A-C)
- 交集相对补:A-(B∩C)=(A-B)∪(A-C)
- 并集绝对补: ~(B∪C) = ~B ∩ ~C
- 交集绝对补:~(B∩C) = ~B ∪ ~C
- ~∅ = E
- ~E = ∅
双重否定律:~~A=A

不难看出,集合运算的规律和命题演算的某些规律是一致的(从本质上来讲它们都是布尔格的一种),所以命题演算的方法是证明集合运算等式的基本方法.

第七章

7.1 有序对与笛卡尔积

定义梳理

有序对(序偶):由两个元素x和y(允许x=y)按照一定的顺序排列成的一个二元组称为有序对或序偶,记作<x,y>,其中x是它的第一元素,y是它的第二元素.

有序对<x,y>具有以下的性质:
1. 当x≠y,<x,y>≠<y,x>
2. <x,y>=<u,v>的充分必要条件是x=u且y=v
这些性质是二元集{x,y}所不具备的.也就是有序对中的元素是有序的,而集合中的元素是无序的.
笛卡尔积：设A,B为集合,用A中元素为第一元素,B中的元素为第二元素构成有序对,所有这样的有序对组成的集合称作A和B的笛卡尔积,记作A×B.
- 笛卡尔积的符号化表示为: A×B={<x,y>|x∈A∧y∈B}.
- 由排列组合易得,|A|=m,|B|=n,|A×B|=mn.
- 笛卡尔积具有以下的性质:
  1. 对任意集合A,根据定义有A×∅=∅,∅×A=∅
  2. 一般地说,笛卡尔积运算不满足交换律,即
    
    A×B≠B×A(当A≠∅∧B≠∅∧A≠B)
  3. 笛卡尔积不满足结合律,即
    
    (A×B)×C≠A×(B×C) (当A≠∅∧B≠∅∧C≠∅,注意就算A=B=C该式还是成立的)
  4. 笛卡尔积运算对并和交运算满足分配律,即:
    - A×(B∪C)=(A×B)∪(A×C)
    - (B∪C)×A=(B×A)∪(C×A)
    - A×(B∩C)=(A×B)∩(A×C)
    - (B∩C)×A=(B×A)∩(C×A)
  5. A⊆C∧B⊆D⇒A×B⊆C×D
    
    注意:反过来推是不对的.可以这样讨论:
    1. 当A=B=∅,此时反过来推是对的.
    2. 当A≠∅且B≠∅,这时候反过来推也是对的.
    3. 当A=∅而B≠∅,若A⊆C成立,B⊆D不一定成立.同理当A≠∅而B＝空集,若B⊆D成立,A⊆C不一定成立(实际上此时A可以是任意的集合，因为A×B⊆C×D肯定成立)

7.2 二元关系

定义梳理

二元关系:如果一个集合满足一下条件之一:
1. 集合非空,且它的元素都是有序对;
2. 集合是空集.
则称该集合为一个二元关系,记作R.二元关系也可简称为关系.对于二元关系R,如果<x,y>∈R,则记作xRy;如果<x,y>∉R,则记作x$\bcancel{R}$y.
从A到B的二元关系、A上的二元关系：设A,B为集合,A×B的任何子集所定义的二元关系称作从A到B的二元关系.特别地当A＝B时称作A上的二元关系.
二元关系的数目:集合A上的二元关系的数目依赖于A的元素数.如果|A|=n,那么|A×A|=n^2^,A×A的子集(或者说A×A的幂集的元素)就有$2^{n^2}$个.每个子集代表一个A上的二元关系,所以A上有$2^{n^2}$个不同的二元关系.
空关系:对于任何集合A,∅是A×A的子集,称作A上的空关系.
全域关系EA:对任意集合A,定义其全域关系为EA={<x,y>|x∈A∧y∈A}=A×A.
恒等关系IA:对任意集合A,定义其恒等关系为 IA={<x,x>|x∈A}
小于等于关系:设A为实数集R的子集,那么A上的小于等于关系定义为:

LA={<x,y>|x,y∈A,x≤y}
整除关系:设A是非零整数集Z*的子集,那么A上的整除关系定义为:

DA={<x,y>|x,y∈A,x|y,即x是y的因子}
包含关系:设A是由一些集合构成的集合族,那么A上的包含关系定义为:

R⊆={<x,y>|x,y∈A,x⊆y}
类似地可以定义大于等于关系、小于关系、大于关系、真包含关系等。
表示关系的方法:集合表达法、关系矩阵和关系图。
1. 集合表达式
2. 关系矩阵:设A={x1,x2,…xn},R是A上的关系.令
  
  $$
  r_{ij}=
  \begin{cases}
  1,若x_iRx_j\qquad(i,j=1,2,…,n)\
  0,若x_i\bcancel{R}x_j
  \end{cases}
  $$
  
  则
  
  $$
  (r_{ij})=
  \left(
  \begin{matrix}
  r_{11}&r_{12}&\cdots&r_{1n}\
  r_{21}&r_{22}&\cdots&r_{2n}\
  \vdots&\vdots&&\vdots\
  r_{n1}&r_{n2}&\cdots&r_{nn}
  \end{matrix}
  \right)
  $$
  
  是R的关系矩阵，记作MR
3. 关系图：设A={x1,x2,…xn},R是A上的关系,R的关系图记作GR. GR有n个顶点x1,x2,…xn.如果<xi,xj>∈R,就在GR中就有一条从xi到xj的有向边.

7.3 关系的运算

定义梳理

关系的基本运算

定义域（define domain)：设R是二元关系，R中所有有序对的第一元素构成的集合称作R的定义域，记作domR,形式化表示为domR={x|∃y(<x,y>∈R)}.
值域(value range):设R是二元关系,R中所有有序对的第二元素构成的集合称作R的值域,记作ranR.形式化表示为:ranR={y|∃x(<x,y>∈R)}
域(field):设R是二元关系,R的定义域和值域的并集称作R的域,记作fldR.形式化表示为:fldR=domR∪ranR.
逆关系:设R是二元关系,R的逆关系,简称R的逆,记作R^-1^,其中R^-1^={<x,y>|<y,x>∈R}
右复合:设F,G是二元关系,G对F的右复合记作F∘G,其中F∘G={<x,y>|∃t(<x,t>∈F∧<t,y>∈G)}.
- 注意:本书采用的是右复合,在其他的地方可能会采用左复合,注意区分.对F∘G,在右复合中G是符合到F上的第二步作用,而在左复合中相反,F是复合到G上的第二步作用.以具体的函数关系举例,对f(x)和g(x),若∘为右复合,则f∘g=g(f(x));若∘为左复合,则f∘g=f(g(x)).
左复合:
限制、像：设R为二元关系,A是集合,
1. R在A上的限制记作R↾A,其中R↾A={<x,y>|xRy∧x ∈A}
2. A在R下的像记作R[A],其中R[A]=ran(R↾A)
3. 可以看出,R在A上的限制R↾A是R的子关系,即R↾A⊆R,而A在R下的像R[A]是ranR(R的值域)的子集，即R[A]⊆ranR.
运算顺序:本节所定义的关系运算中逆运算优先于其他运算,而所有的关系运算都优先于集合运算(因为关系也是集合,同样适用第六章中的集合运算),对于没有规定优先权的运算以括号决定运算顺序.
幂运算:设R为A上的关系,n为自然数,则R的n次幂R^n^定义为
1. R^0^={<x,x>|x∈A}=IA
2. R^n+1^=R^n^∘R
  
  由上面的定义可知，对于A上的任何关系R1和R2，都有R1^0^=R2^0^=IA.(不考虑空关系)
  
  也就是A上任何关系的0次幂都是A上的恒等关系，彼此相等.
  
  此外，对A的任何关系R都有R^1^都有R^1^=R，因为R^1^=R^0^∘R=IA∘R=R.
3. 幂R^n^的计算方法:考虑n≥2的情况.
  - 如果R是用集合表达式给出的,则可以直接通过n-1次右复合运算可以得出(n-1次是因为我们知道R^1^=R,从R^2^开始复合)
  - 如果R是用关系矩阵M给出的,则R^n^对应的关系矩阵是M^n^,即n个M矩阵之积.但与普通矩阵乘法不同的是,其中的相加用的是逻辑加,即1+1=1 1+0=1 0+1=1 0+0=0.
  - 如果R是用关系图给出的,则可以直接由图G给出R^n^的关系图G’. G’的顶点集与G相同.考察G的每个顶点,如果G中从xi出发经过n步长的路径到达顶点xj,则在G’中添加从xi到xj的边.把所有这样的边找到并添加到边集后,就可以得到图G’.

定理公式

关系基本运算的性质

定义域、值域、逆运算：设F是任意的关系，则有
1. (F^-1^)^-1^=F
2. domF^-1^=ranF ranF^-1^=domF
复合运算的性质:设F,G,H是任意的关系,则有
1. (F∘G)∘H=F∘(G∘H)
2. (F∘G)^-1^=G^-1^∘F^-1^
恒等关系与复合：设R为A上的关系，则R∘IA=IA∘R=R
复合对并的分配律：设F,G,H为任意关系,则
1. F∘(G∪H)=F∘G∪F∘H
2. (G∪H)∘F=G∘F∪H∘F
复合与交运算：设F,G,H为任意关系，则
1. F∘(G∩H)⊆F∘G∩F∘H
2. (G∩H)∘F⊆G∘F∩H∘F
- 评注：我们注意到复合对交运算是没有分配律的，这是为什么呢？课本上对A给出的证明是这样的：
- 任取<x,y>,有
  - ```
  <x,y>∈F∘(G∩H)
```
- ⇔∃t(<x,t>∈F∧<t,y>∈G∩H)
- ⇔∃t(<x,t>∈F∧<t,y>∈G∧<t,y>∈H)
- ⇔∃t((<x,t>∈F∧<t,y>∈G)∧(<x,t>∈F∧<t,y>∈H))
- ⇒∃t(<x,t>∈F∧<t,y>∈G)∧∃t(<x,t>∈F∧<t,y>∈H)
- ⇔<x,y>∈F∘G∧<x,y>∈F∘H
- ⇔<x,y>∈ F∘G∩F∘H
- 即可得出F∘(G∩H)⊆F∘G∩F∘H.
- 评注:这是一个形式化符号化的证明,如果要比较经验地去理解,不妨分析一下并举出实例.我们注意到由=变⊆的关键是在⇒那一步.推出的前面的式子要求找出同一个t,使得(<x,t>∈F∧<t,y>∈G)和(<x,t>∈F∧<t,y>∈H)同时成立,而推出后面的式子则不要求t是相同的,实际上完全可以写成 ∃t(<x,t>∈F∧<t,y>∈G)∧∃r(<x,r>∈F∧<r,y>∈H).我们举个简单的例子，设F={<1,2>,<1,3>},G={<2,5>},H={<3,5>}.此时G∩H=∅,从而F∘(G∩H)=∅.但是F∘G={<1,5>},F∘H={<1,5>},从而F∘G∩F∘H={<1,5>}.对于式B也是如此,只要设G={<1,2>},H={<1,3>},F={<2,5>,<3,5>}.
复合运算对并和交运算的性质可以推广到有限个的情况.即:
1. R∘(R1∪R2∪R3∪…∪Rn)=R∘R1∪R∘R2∪R∘R3∪…∪R∘Rn
2. (R1∪R2∪…∪Rn)∘R=R1∘R∪R2∘R∪…∪Rn∘R
3. R∘(R1∩R2∩…∩Rn)⊆R∘R1∩R∘R2∩…∩R∘Rn
4. (R1∩R2∩…∩Rn)∘R⊆R1∘R∩R2∘R∩…∩Rn∘R
限制、像:设F为关系,A,B为集合,则:
1. F↾(A∪B)=F↾A∪F↾B
2. F[A∪B]=F[A]∪F[B]
3. F↾(A∩B)=F↾A∩F↾B
4. F[A∩B]⊆F[A]∩F[B]
  - 评注：注意式D不是等号，而是⊆.举例:设F={<1,3>,<2,3>},A={1},B={2},那么A∩B=∅,F[A∩B]=∅,而F[A]={3},F[B]={3},F[A]∩F[B]={3}.此时F[A∩B]⊂F[A]∩F[B].也就是说,A和B共同元素在F下的像固然是相同的,但是A和B的不同元素在F下的像也可能是相同的.
幂运算的周期性:设A为n元集,R是A上的关系,则存在自然数s和t,使得R^s^=R^t^.

这个定理说明有穷集上只有有穷多个不同的二元关系.当t足够大时,R^t^必然与某个R^s^(s＜t)相等.
幂运算的次方:
1. R^m^∘R^n^=R^m+n^
2. (R^m^)^n^=R^mn^
幂运算的周期性应用:设R是A上的关系,若存在自然数s,t(s＜t)使得R^s^=R^t^,则
对任何k∈N,有R^s+k^=R^t+k^;
对任何k,i∈N,有R^s+kp+i^=R^s+i^,其中p=t-s(周期长度).
令S={R^0^,R^1^,…,R^n^},则对任意的q∈N有R^q^∈S.
可以看出,有穷集A上的关系R的幂序列R^0^,R^1^,R^2^,…是一个呈现周期性变化的序列。就如正弦函数，我们可以利用周期性把R的高次幂转化为R的低次幂.

7.4 关系的性质

定义梳理

自反与反自反: 设R为A上的关系,
1. 若∀x(x∈A→<x,x>∈R),则称R在A上是自反的
2. 若∀x(x∈A→<x,x>∉R),则称R在A上是反自反的
3. 自反关系举例:全域关系EA,恒等关系IA,小于等于关系LA,整除关系DA等都是在A上的自反关系
4. 反自反关系举例：小于关系、大于关系、真包含关系等
对称与反对称：设R为A上的关系，
1. 若∀x∀y（x,y∈A∧<x,y>∈R → <y,x>∈R),则称R为A上的对称关系
2. 若∀x∀y (x,y∈A∧<x,y>∈R∧<y,x>∈R → y=x),则称R为A上的反对称关系
3. 对称关系举例:A上的全域关系EA,恒等关系IA,和空关系∅都是A上的对称关系
4. 反对称关系举例:恒等关系IA和空关系∅也是A上的反对称关系,注意EA一般不是反对称关系,除非A为∅或单元集.
5. 评注: 可见对称与反对称的关系并不是完全对立的,一个关系可以同时是对称关系和反对称关系.而自反与反自反的关系是对立的,一个关系是自反的,就不可能是反自反的,当然它也有可能既不是自反的,也不是反自反的.
传递: 设R为A上的关系,若∀x∀y∀z(x,y,z∈A∧<x,y>∈R∧<y,z>∈R → <x,z>∈R,则称R为A上的传递关系
1. 传递关系举例:A上的全域关系EA,恒等关系IA,空关系∅,小于等于关系LA,包含关系,小于关系,真包含关系都为A上的传递关系.

定理公式

自反、对称、传递的判断（充分必要）：
1. R在A上自反当且仅当IA⊆R.
2. R在A上反自反当且仅当R∩IA=∅
3. R在A上对称当且仅当R=R^-1^
4. R在A上反对称当且仅当R∩R^-1^⊆IA
5. R在A上传递当且仅当R∘R⊆R
6. 利用此五条定理可以比较方便地从关系的集合表达式来判断或证明关系的性质.

关系的性质与关系矩阵和关系图:

关系的性质不仅体现在它的集合表达式上,也明显地反映在它的关系矩阵和关系图上.

	自反性	反自反性	对称性	反对称性	传递性
集合表达式	IA⊆R	R∩IA=∅	R=R^-1^	R∩R^-1^⊆IA	R∘R⊆R
关系矩阵	主对角线上的元素全是1	主对角线上的元素全是0	矩阵是对称矩阵	若rij=1,且i≠j,rji=0	对M^2^中1所在的位置,M中相应的位置都是1
关系图	每个顶点都有环	每个顶点都没有环	如果两个顶点之间有边,则一定是一对方向相反的边(无单边)	如果两个顶点之间有边,则一定是一条有向边(无双向边)	如果从顶点xi到xj有边,xj到xk有边,那么从xi到xk也有边

关系的性质和运算的关系:设R1和R2是A上的关系,它们具有某些共同的性质.在经过并,交,相对补,求逆,右复合等运算之后所得到的新关系是否还能保持原来关系的性质?如下表,其中✔表示能保持,✘表示不一定能保持:

	自反性	反自反性	对称性	反对称性	传递性
R1^-1^	✔	✔	✔	✔	✔
R1∩R2	✔	✔	✔	✔	✔
R1∪R2	✔	✔	✔	✘	✘
R1-R2	✘	✔	✔	✔	✘
R1∘R2	✔	✘	✘	✘	✘

7.5 关系的闭包

定义梳理

自反闭包、对称闭包、传递闭包的概念：设R是A上的关系，我们可以通过在R中添加一些有序对（尽可能少的有序对）来构造出具有某些R原来不具备性质的新关系R’,这个新关系R’就是闭包.
1. 若构造出来的R’具备自反性,就称为自反闭包
2. 若构造出来的R’具备对称性,就称为对称闭包
3. 若构造出来的R’具备传递性,就称为传递闭包
自反闭包、对称闭包、传递闭包的定义:设R是非空集合A上的关系,R的自反(对称,传递)闭包是A上的关系R’ ,使得R’满足的条件:
1. R’是自反的(对称或传递的);
2. R⊆R’ ;
3. 对A上任何包含R的自反(对称或传递)关系R’’都有R’⊆R’’(即R’是最小的那个)
4. 一般将R的自反闭包记作r(R),对称闭包记作s(R),传递闭包记作t(R).
  
  注：自反reflexive/reflexivity 对称symmetric/symmetry 传递transitive/transitivity

定理公式

构造闭包的方法

设R为A上的关系,则有
1. r(R)=R∪R^0^=R∪IA
2. s(R)=R∪R^-1^
3. t(R)=R∪R^2^∪R^3^∪…
  - 推论:设R为有穷集A上的关系,则存在正整数r使得t(R)=R∪R^2^∪R^3^∪…∪R^r^
4. 通过关系矩阵求闭包:设关系R,r(R),s(R),t(R)对应的关系矩阵分别为M,Mr,Ms,Mt,则
  - 自反闭包:Mr=M+E
  - 对称闭包:Ms=M+M‘
  - 传递闭包:Mt=M+M^2^+M^3^+…
  - 其中E是和M同阶的单位矩阵,M‘是M的转置矩阵,M^n^是指M的n次幂.注意上面等式中的矩阵相加都使用逻辑加.
5. 通过关系图求闭包:设关系R,r(R),s(R),t(R)对应的关系图分别记为G,Gr,Gs,Gt,则Gr,Gs,Gt的顶点集与G的顶点集相同.除了G的边以外,按照以下方法添加新的边:
  1. 自反闭包:考察G每个顶点,如果没有环就加上一个环，最终得到的是Gr
  2. 对称闭包:考察G的每一条边,如果有一条xi到xj的单向边,i≠j,则在G中加一条xj到xi的反方向的边.最终得到Gs
  3. 传递闭包:考察G的每个顶点xi,找出从xi出发的所有2步,3步,4步…,n步长的路径(n为G中的顶点数).设路径的终点为xj1,xj2,xj3,…xjk.(这里用k而不用n是因为并不是每个步长的路径都有,所以在这里应有k≤n).如果没有从xi到xjl(l=1,2,3,4,…,k)的边,那么就加上这条边.这样在检查完所有的顶点后就得到最终得到Gt.
沃舍尔Warshall算法:利用Warshall算法可以有效用计算机求出传递闭包的关系矩阵.
1. 设A={x1,x2,x3,…,xn},考虑M0,M1,M2,…,Mn这n+1个矩阵的序列，将矩阵Mk的i行j列的元素记作Mk[i,j].对于k=0,1,2,3,…n,Mk[i,j]=1当且仅当在R的关系图中存在一条从xi到xj的路径,并且这条路径除端点外只经过{x1,x2,…,xk}中的结点.不难看出,M0就是R的关系矩阵,因为M0中所对应的路径除端点外不经过任何结点,M0[i,j]=1表示xi和xj是直接相连的.而Mn就是对应R的传递闭包,因为传递闭包中xi到xj只要有路径(可以经过任意结点)就相连,Mn[i,j]=1对应的就是xi到xj之间有路径.
2. 这个M0,M1,…,Mn的矩阵序列中,M0是初始的状态,Mn是最终的解,也就是我们把传递闭包的求解分为了一个个更小问题组成的序列,M~~k+1~~的求解需要建立在Mk的基础之上.只要弄清楚M~~k+1~~和Mk的关系就可以进行递推求解.
3. 假设Mk已经计算完毕,如何计算M~~k+1~~?计算M~~k+1~~就是要确定每一组M~~k+1~~[i,j]是否为1.因为M~~k+1~~[i,j]=1对应的是从xi到xj之间有路径而且除端点外只经过{x1,x2,…xk,x~~k+1~~}中的结点.我们不妨把这些路径分为两类:
  1. 第一类是只经过{x1,x2,…,xk}中结点的路径,这些路径对应的Mk[i,j]=1,所以对于这种路径我们只要另M~~k+1~~[i,j]=Mk[i,j]=1就好.
  2. 第二类是经过x~~k+1~~,而且除了x~~k+1~~外只经过{x1,x2,…,xk}中结点的路径.因为回路可以从路径中删除,所以只考虑经过一次x~~k+1~~的路径.对于这样的路径,可以分为两段,从xi到x~~k+1~~,再从x~~k+1~~到xj,如果它是存在的则有对应的Mk[i,k+1]=1和Mk[k+1,j]=1.也就是说,当Mk[i,k+1]=1和Mk[k+1,j]=1时,M~~k+1~~[i,j]=1.
  综合这两类路径的情况,我们就可以得到Mk+1[i,j]=Mk[i,j]+Mk[i,k+1]·Mk[k+1,j].其中的+和·是逻辑加和逻辑乘.根据这个式子,我们很容易就可以写出对应的代码.
闭包的主要性质
通过闭包判断关系的性质：设R是非空集合A上的关系，则
1. R是自反的当且仅当r(R)=R
2. R是对称的当且仅当s(R)=R
3. R是传递的当且仅当t(R)=R
子集的闭包性质：设R1和R2是非空集合A上的关系，且R1⊆R2，则有
1. r(R1)⊆r(R2)
2. s(R1)⊆s(R2)
3. t(R1)⊆t(R2)
闭包对关系性质的继承：设R是非空集合A上的关系，
1. 若R是自反的,则s(R)与t(R)也是自反的.
2. 若R是对称的,则r(R)与t(R)也是对称的.
3. 若R是传递的,则r(R)也是传递的.
4. 注意到如果关系R是自反的或对称的,那么经过闭包运算以后得到的关系仍旧是自反的或对称的.但是对于传递关系则不然,它的自反闭包仍然保持传递性,但是它的对称闭包有可能失去传递性.所以,如果我们要得到一个关系R的自反对称传递闭包,那么传递闭包应该放在对称闭包之后.即:若令tsr(R)表示R的自反对称传递闭包,则tsr(R)=t(s(r(R)))或t(r(s(R)))或r(t(s(R))).

7.6 等价关系与划分

定义梳理

等价关系:设R为非空集合A上的关系.如果R是自反的、对称的、传递的,则称R为A上的等价关系.设R是一个等价关系,若<x,y>∈R,则称x等价于y,记作x~y.
等价类:设R为非空集合A上的等价关系,∀x∈A,令[x]R={y|y∈A∧xRy},称[x]R为x关于R的等价类,简称为x的等价类,简记为[x]或$\overline{x}$.可以看出,x的等价类就是A中所有与x等价的元素构成的集合.

定理公式

等价类的性质:设R为非空集合A上的等价关系,则
1. ∀x∈A,[x]是A的非空子集;
2. ∀x,y∈A,如果xRy,则[x]=[y];
3. ∀x,y∈A,如果x$\bcancel{R}$y,则[x]∩[y]=∅(即[x]与[y]不交)
4. ∪{[x]|x∈A}=A
商集:设R为非空集合A上的等价关系,以R的所有等价类作为元素的集合称为A关于R的商集,记作A/R,即

A/R={[x]R|x∈A}
划分:设A为非空集合,若A的子集族π(π⊆P(A),是A的子集构成的集合),满足下面的条件:
1. ∅∉π, 即π中没有空集
2. ∀x∀y(x,y∈π∧x≠y→x∩y=∅), 即π中的子集之间是不交的
3. ∪π=A, 即π的广义并等于A,也就是π中所有子集的并集等于A
则称π是A的一个划分,称π中的元素为A的划分块.
商集与划分:把商集A/R与划分作比较,容易得到商集就是A的一个划分,并且关于不同等价关系的商集对应的不同的划分.反之,给定A的一个划分π,定义对应的A上的关系R:R={<x,y>|x,y∈A∧x与y在π的同一划分块中},则容易得知实际上该关系R就是A上的等价关系,且该等价关系所确定的商集就是π.由此可见,A上的等价关系与A的划分是一一对应的.

7.7 偏序关系

定义梳理

偏序关系:设R为非空集合A上的关系.如果A是自反的、反对称的和传递的,则称R为A上的偏序关系,记作≼.设≼为偏序关系,若<x,y>∈≼,则记作x≼y,读作x”小于等于”y.
- 注意这里的”小于等于”不是指数的大小,而是指在偏序关系中的顺序性.x”小于等于”y的含义是:依照这个序,x排在y的前边或者x就是y.
可比:设≼为非空集合A上的偏序关系,定义
1. ∀x,y∈A,x≺y⇔x≼y∧x≠y
2. ∀x,y∈A,x与y可比⇔x≼y∨y≼x
  
  其中x≺y读作x”小于”y.这里所说的小于是指在偏序中x排在y的前边.
  
  从上面的定义可知,在具有偏序关系≼的集合A中任取两个元素x和y,可能有下列三种情况:
  - x≺y(或y≺x)
  - x=y
  - x与y不是可比的.
全序关系(线序关系):设R为非空集合A上的偏序关系,如果∀x,y∈A,x与y都是可比的,则称R为A上的全序关系(或线序关系).
偏序集:集合A和A上的偏序关系≼一起称作偏序集,记作<A,≼>.
覆盖:设<A，≼>为偏序集,∀x,y∈A,如果x≺y且不存在z∈A使得x≺z≺y,则称y覆盖x.
哈斯图:利用偏序关系的自反性、反对称性、传递性可以简化一个偏序关系的关系图,得到偏序集的哈斯图.
- 在画偏序集<A,≼>的哈斯图时,首先适当排列顶点的顺序,使得:∀x,y∈A,若x≺y,则将x画在y的下方.对于A中的两个不同元素x和y,如果y覆盖x,那就用一条线段连接x和y.
偏序集中的一些特殊元素:设<A,≼>为偏序集,B⊆A,y∈B.
- 最小元:若∀x(x∈B→y≼x)成立,则称y为B的最小元.
- 最大元:若∀x(x∈B→x≼y)成立,则称y为B的最大元.
- 极小元:若∀x(x∈B∧x≼y→x=y)成立,则称y为B的极小元.
- 极大元:若∀x(x∈B∧y≼x→x=y)成立,则称y为B的极大元.
- 注意:从上面的定义可以看出,最小元与极小元是不一样的.
  - 最小元是B中最小的元素,它与集合中任何的元素都是可比的;
  - 而极小元不一定与B中的元素都可比,只要没有比它更小的元素,它就是极小元.
  - 对于有穷集B,极小元一定存在,但最小元不一定存在.最小元如果存在,一定是唯一的,但极小元可能有多个.
  - 如果B中只有一个极小元,则它一定是最小元.
  - 同理，极大元与最大元的区别也如此这般。
偏序集的界：设<A,≼>为偏序集,B⊆A,y∈A.(注意与7.的不同,7中是y∈B)
- 若∀x(x∈B→x≼y)成立,则称y为B的上界.
- 若∀x(x∈B→y≼x)成立,则称y为B的下界.
- 令C={y|y为B的上界},则称C的最小元为B的最小上界或上确界.
- 令D={y|y为B的下界},则称D的最大元为B的最大下界或下确界.
- 注意:从上面的定义可以看出,
  - B的最小元一定是B的下界,同时也是B的最大下界.
  - 同样的,B的最大元一定是的B的上界,同时也是B的最小上界.
  - 但上面的两条反过来不一定正确.B的下界不一定是B的最小元,因为它可能不是B中的元素.同样,B的上界不一定是B的最大元.
  - B的最大下界也不一定是B的最小元,因为它可能不是B中的元素.B的最小上界也不一定是B的最大元,因为它可能不是B中的元素.
  - 还可以得知,如果B的上界y∈B,则y一定是B的最大元，而且它是B的最小下界.如果B的下界y∈B,则y一定是B的最小元，而且它是B的最大下界.
  - B的上界、下界、最小上界、最大下界都可能不存在。如果存在，最小上界和最大下界是唯一的.
调度问题：调度问题是偏序关系的典型的实例。一般性的调度问题可以描述为：

给定有穷的任务集T和m台相同的机器，T上存在偏序关系≼，如果t1≺t2，那么任务t1完成后t2才能开始工作。∀t∈T，l(t)表示完成任务t所需要的时间,d(t)表示任务t的截止时间.l(t),d(t)∈Z^+^.设开始时间为0,σ:T→{0,1,…}表示对任务集T的一个调度方案,其中σ(t)表示任务t的开始时间.D=max{σ(t)+l(t)|t∈T}表示完成所有任务的最终时间.假设每项任务都可以安排在任何一台机器上进行加工,如果σ满足下述3个条件,则称σ为可行调度.
1. ∀t∈T,σ(t)+l(t)≤d(t).即开始时间+完成需要的时间≤截止时间.
2. ∀i,0≤i≤D,|{t∈T|σ(t)≤i≤σ(t)+l(t)}|≤m.即在时刻t同时进行任务的机器不能超过m台.
3. ∀t,t’∈T,t≺t’⇒σ(t)+l(t)≤σ(t’).即任务安排必须满足任务集的偏序约束.求使得D最小的可行调度.
拓扑排序:将原来的偏序集<A,R>扩张成一个对应的全序集<A,R’>(当然,有可能本来就是一个全序集).忽略关系R’的自反性部分得到拓扑排序的序关系T.因此有R-IA⊆T.在扩张成全序关系时,原来偏序集中不可比的元素之间的次序可以任意确定.

第八章函数

8.1 函数的定义与性质

定义梳理

函数:设F为二元关系,若∀x∈domF都存在唯一的y∈ranF使xFy成立,则称F为函数.对于函数F,如果有xFy,则记作y=F(x),并称y为F在x的值.
函数的相等:设F,G为函数,则F=G⇔F⊆G∧G⊆F

由上面定义可知,若两个函数F和G相等,则一定满足以下的两个条件:
1. domF=domG.
2. ∀x∈domF=domG,都有F(x)=G(x).
从A到B的函数:设A,B为集合,如果f为函数,且domf=A,ranf⊆B,则f称作从A到B的函数,记作f:A→B.
B上A:所有从A到B的函数的集合记作B^A^,读作”B上A”.符号化表示为:B^A^={f|f:A→B}.
- 由排列组合可知,若|A|=m,|B|=n,且m,n＞0,则|B^A^|=n^m^.因为对于A中的每个元素,将映射到B中n个元素的其中一个,也就是有n种选择.而A一共有m个,且它们映射到B的选择是不相互影响的,所以据乘法原则,总选择数就是m个n相乘,即n^m^.
- 当A或B中至少有一个为空集时,可以分成下面三种情况:
  - A=∅且B=∅,则B^A^=∅^∅^={∅}.
  - A=∅且B≠∅,则B^A^=B^∅^={∅}.
  - A≠∅且B=∅,则B^A^=∅^A^=∅.
  - 注意:∅≠{∅}.其中的区别是由于函数的定义导致的,所以当A≠∅而B=∅,此时对于A中的元素在B中都找不到唯一的映射,因为B中本来就没有元素,所以此时从A到B不存在函数.但如果A=∅而B≠∅,此时A中没有元素,也就不用在B中找唯一映射,与函数的定义是不相违背的,因此从A到B有一个空函数∅.
像:设函数f:A→B,A1⊆A,B1⊆B.
1. 令f(A1)={f(x)|x∈A1},称f(A1)为A1在f下的像.特别地,当A1=A时,称f(A)为函数的像.
2. 令f^-1^(B1)={x|x∈A∧f(x)∈B1},称f^-1^(B1)为B1在f下的完全原像.
3. 注意:要区别函数的值和像的区别.函数值f(x)∈B而函数的像f(A1)⊆B,
  
  实际上f(A1)就是在A1上所有函数值的集合.
函数的性质:设f:A→B,
1. 满射:若ranf=B,则称f:A→B是满射的
2. 单射:若∀y∈ranf都存在唯一的x∈A使得f(x)=y,则称f:A→B是单射的.
3. 若f:A→B既是满射又是单射的,则称f:A→B是双射的(或一一映像).
4. 注意:(下面可以为证明一个函数的性质提供方法)
  - 如果:f:A→B是满射的,对任意的y∈B,都存在x∈A(不一定唯一),使得f(x)=y.
  - 如果f:A→B是单射的,对于x1,x2∈A,x1≠x2,一定有f(x1)≠f(x2).换句话说,如果对于任意x1,x2∈A,有f(x1)=f(x2),则一定有x1=x2.
常函数：设f:A→B,如果存在c∈B使得对所有的x∈A都有f(x)=c,则称f:A→B是常函数.
恒等函数:称A上的恒等关系I^A^为A上的恒等函数.对所有的x∈A都有I^A^(x)=x.
函数的单调性：设<A,≼>,<B,≼>为偏序集,f:A→B,如果对任意的x1,x2∈A,x1≺x2,就有f(x1)≼f(x2),则称f为单调递增的.如果对任意的x1,x2∈A,x1≺x2,就有f(x1)≺f(x2),则称f为严格单调递增的.类似地,可以定义出单调递减和严格单调递减的函数.
特征函数:设A为集合,对任意的A’⊆A,A’的特征函数χA’:A→{0,1}定义为

$$
\chi_{A’}=
\begin{cases}
1,\quad a∈A’\
0,\quad a∈A-A’
\end{cases}
$$

即在A’里面的就映射为1,在A-A’里面的就映射为0.
自然映射:设R是A上的等价关系,令

$$
g:A→A/R\
g(a)=[a],∀a∈A
$$

称g是从A到商集A/R的自然映射.

注意到a∈A而[a]⊆A.

8.2 函数的复合与反函数

定义梳理

函数的复合:函数是一种特殊的二元关系,函数的复合就是关系的右复合.一切和关系右复合的定理都适用于函数的复合.

定理公式

函数复合的性质:设F,G是函数,则F∘G也是函数,且满足:
1. dom(F∘G)={x|x∈domF∧F(x)∈domG}
2. ∀x∈dom(F∘G)有F∘G(x)=G(F(x)).
3. 推论1:设F,G,H为函数,则(F∘G)∘H和F∘(G∘H)都是函数,且(F∘G)∘H=F∘(G∘H).
4. 推论2:设f:A→B,g:B→C,则f∘g:A→C,且∀x∈A都有f∘g(x)=g(f(x)).
复合函数与函数性质:设f:A→B,g:B→C.
1. 如果f:A→B,g:B→C都是满射的,则f∘g:A→C也是满射的.
2. 如果f:A→B,g:B→C都是单射的,则f∘g:A→C也是单射的.
3. 如果f:A→B,g:B→C都是双射的,则f∘g:A→C也是双射的.
4. 注意：该定理说明函数的复合运算能够保持函数的单射、满射和双射的性质.但是该定理的逆命题不一定成立,即如果f∘g:A→C是单射(或满射或双射)的,不一定有f:A→B和g:B→C都是单射(或满射或双射)的.
恒等函数与函数复合:设f:A→B,则有f=f∘IB=IA∘f.

该定理说明了恒等函数在函数复合中的特殊性质,特别地,对于f∈A^A^有f∘IA=IA∘f=f.
函数的逆运算:任给函数F,它的逆F^-1^不一定是函数,只是一个二元关系,因为F^-1^有可能会破坏函数的单值性.
反函数:设f:A→B是双射的,则f^-1^:B→A也是双射的.对于双射函数f:A→B,称f^-1^:B→A是它的反函数.
恒等关系与双射函数的复合:设f:A→B是双射的,则f^-1^∘f=I^B^,f∘f^-1^=I^A^.

8.3 双射函数与集合的基数

定义梳理

等势:设A,B是集合,如果存在从A到B的双射函数,那么称A和B是等势的.记作A≈B,如果A不与B等势,则记作A$\cancel{≈}$B.
1. 一些等势集合的例子:
  - Z≈N
  - N×N≈N
  - N≈Q
  - (0,1)≈R,其中(0,1)={x|x∈R∧0<x<1}.
  - [0,1]≈(0,1)
  - 对任何a,b∈R,a＜b,[0,1]≈[a,b].
优势:设A,B是集合,如果存在从A到B的单射函数,则称B优势于A,记作A≼·B.如果B不是优势于A,则记作A$\bcancel{≼·}$B.
真优势:设A,B是集合,如果A≼·B且A$\cancel{≈}$B,则称B真优势于A,记作A≺·B.如果B不是真优势于A,则记作A≺·B.
把自然数定义为集合:用空集和后继n^+^(紧跟在n后面的自然数)可以把所有的自然数定义为集合,即:

0=∅

n^+^=n∪{n},∀n∈N.

示例：1=0∪{0}=∅∪{∅}={∅},2=1∪{1}={∅}∪={∅,{∅}},3=2∪{2}={∅,{∅},{∅,{∅}}}…

可以在此基础上得出自然数的4个性质:
1. 对任何自然数n有n≈n
2. 对任何自然数n,m,若m⊂n,则m$\cancel{≈}$n.
3. 对任何自然数n,m,若m∈n,则m⊂n.
4. 对任何自然数n和m,以下三个式子:
  
  m∈n,m≈n,n∈m
  
  必成立其一且仅成立其一.这个性质称为自然数的三歧性.
然后就可以定义自然数的相等与大小,即对任何自然数n和m,有
1. m=n⇔m≈n
2. m<n⇔m∈n
有穷,无穷集:一个集合是有穷的当且仅当它与某个自然数(按照4.中的集合定义)等势;如果一个集合不是有穷的,则称作无穷集.

可以看出,任何有穷集只与唯一的自然数等势.因为两不同自然数之间是不等势的.
基数:对于有穷集合A，称与A等势的那个唯一的自然数为A的基数，记作cardA（或|A|),即cardA=n⇔A≈n
1. 自然数集合N的基数记作ℵ0(读作阿列夫零),即cardN=ℵ0
2. 实数集R的基数记作ℵ(读作阿列夫),即 cardR=ℵ
基数的相等与大小:设A,B为集合,则
1. cardA=cardB⇔A≈B
2. cardA≤cardB⇔A≼·B
3. cardA＜cardB⇔cardA≤cardB∧cardA≠cardB
4. 一些集合的基数比较：
  1. cardZ=cardQ=cardN×N=ℵ0.
  2. cardP(N)=card2^N^=card[a,b]=card(c,d)=ℵ.
  3. ℵ0＜ℵ
5. 从这里可以看出,集合的基数就是集合的势.基数越大,势越大.
有穷基数,无穷基数:将已知的基数按从小到大的顺序排列就得到:0,1,2,3,…,ℵ0,ℵ,…(注意连续统目前尚未得到证明)
1. 其中0,1,2,…,n,…恰好是全体自然数,是有穷集合的基数,也称作有穷基数.
2. 而ℵ0,ℵ,…是无穷集合的基数,也称作无穷基数,ℵ0是最小的无穷基数,而ℵ后还有更大的无穷基数如cardP(R).
可数集(可列集):设A为集合,若cardA≤ℵ0,则称A为可数集或可列集.

关于可数集有以下命题:
- 可数集的任何子集都是可数的
- 两个可数集的并是可数的
- 两个可数集的笛卡尔积是可数的
- 可数个可数集的并仍是可数的
- 无穷集A的幂集P(A)不是可数集

定理公式

等势的性质:设A,B,C是任意的集合,
- A≈A(自反性)
- 若A≈B,则B≈A(对称性)
- 若A≈B,且B≈C,则A≈C(传递性)
- 根据这三个性质可以得到:
  1. N≈Z≈Q≈N×N
  2. R≈[0,1]≈(0,1) 这个结果可以强化为任何实数区间(包括开区间,闭区间,以及半开半闭的区间)都与实数集合R等势.
康托定理:
1. N$\cancel{≈}$R
2. 对任意集合A都有A$\cancel{≈}$P(A)
优势的性质:设A,B,C是任意的集合,则
1. A≼·A.
2. 若A≼·B且B≼·A,则A≈B.
3. 若A≼·B且B≼·C,则A≼·C.
4. 注意:这三条定理为证明集合之间的优势提供了方法,也为证明集合之间的等势提供了一个有力的工具.因为在某些情况下直接构造从A到B的双射函数是相当困难的.相比之下,构造两个单射函数f:A→B和g:B→A则可能要容易得多.

#学习 #理论 #离散数学

离散数学第二部分集合论

http://thinkerhui.site/2024/01/03/课程学习/离散数学第二部分集合论/

作者

thinkerhui

发布于

2024年1月3日

许可协议

机器学习期末复习上一篇

2023区块链原理与技术期末考试下一篇

离散数学第二部分集合论

离散数学第二部分集合论

第六章 集合代数

6.1 集合的基本概念

定义梳理

定理公式

6.2 集合的运算

定义梳理

6.3 有穷集的计数

定义梳理

定理公式

6.4 集合恒等式

定理公式

第七章

7.1 有序对与笛卡尔积

定义梳理

7.2 二元关系

定义梳理

7.3 关系的运算

定义梳理

定理公式

7.4 关系的性质

定义梳理

定理公式

7.5 关系的闭包

定义梳理

定理公式

构造闭包的方法

闭包的主要性质

7.6 等价关系与划分

定义梳理

定理公式

7.7 偏序关系

定义梳理

第八章 函数

8.1 函数的定义与性质

定义梳理

8.2 函数的复合与反函数

定义梳理

定理公式

8.3 双射函数与集合的基数

定义梳理

定理公式

第六章集合代数

第八章函数