离散数学(集合论)

集合论离散数学1集合论十九世纪下半叶，康托尔创立了著名的集合论，在集合论刚产生时，曾遭到许多人的猛烈攻击。但不久这一开创性成果就为广大数学家所接受了，并且获得广泛而高度的赞誉。数学家们发现，从自然数与康托尔集合论出发可建立起整个数学大厦。因而集合论成为现代数学的基石。2当时德国数学家康托尔试图回答一些涉及无穷量的数学难题，例如“整数究竟有多少？”“一个圆周上有多少点？”0—1之间的数比1寸长线段上的点还多吗？”等等。而“整数”、“圆周上的点”、“0—1之间的数”等都是集合，因此对这些问题的研究就产生了集合论。31903年，一个震惊数学界的消息传出：集合论是有漏洞的！这就是英国数学家罗素提出的著名的罗素悖论。可以说，这一悖论就象在平静的数学水面上投下了一块巨石，而它所引起的巨大反响导致了第三次数学危机。4罗素悖论把所有集合分为2类，第一类中的集合以其自身为元素，第二类中的集合不以自身为元素，假令第一类集合所组成的集合为P，第二类所组成的集合为Q，于是有：P={A∣A∈A}Q={A∣A∉A}问，Q∈P还是Q∈Q？若Q∈P，那么根据第一类集合的定义，必有Q∈Q，但是Q中任何集合都有A∉A的性质，因为Q∈Q，所以Q￠Q，引出矛盾。若Q∈Q，根据第一类集合的定义，必有Q∈P，而显然P∩Q=∅，所以Q∉Q，还是矛盾。5理发师悖论

在某个城市中有一位理发师，他的广告词是这样写的：“本人的理发技艺十分高超，誉满全城。我将为本城所有不给自己刮脸的人刮脸，我也只给这些人刮脸。我对各位表示热诚欢迎！”来找他刮脸的人络绎不绝，自然都是那些不给自己刮脸的人。可是，有一天，这位理发师从镜子里看见自己的胡子长了，他本能地抓起了剃刀，你们看他能不能给他自己刮脸呢？如果他不给自己刮脸，他就属于“不给自己刮脸的人”，他就要给自己刮脸，而如果他给自己刮脸呢？他又属于“给自己刮脸的人”，他就不该给自己刮脸。6它对数学家说：“解决我，不然我将吞掉你的体系！”7罗素悖论使得数学基础问题第一次以最迫切的需要的姿态摆到数学家面前，导致了数学家对数学基础的研究。而这方面的进一步发展又极其深刻地影响了整个数学。如围绕着数学基础之争，形成了现代数学史上著名的三大数学流派。从1900年到30年这三十年间，许多数学家就数学的哲学基础这一问题展开了讨论，并形成了不同的数学基础学派，主要有逻辑主义、形式主义和直觉主义三大学派8集合论部分第3章集合的基本概念和运算第4章二元关系和函数9第3章集合的基本概念和运算3.1集合的基本概念3.2集合的基本运算3.3集合中元素的计数103.1集合的基本概念

集合的定义与表示集合与元素集合之间的关系幂集11集合的基本概念1.集合：若干个（有限或无限）固定事物的全体元素表示方法：列举法A={a,b,c,d}

描述法B={x|x∈Z,3<x≤6}…12集合与元素的关系Ａ＝｛a，｛b，c｝，d

｝aA｛b,c｝

AbA131.子集合：2.真子集：3.集合相等：集合之间的关系A

B

x(x

A

x

B)包含A

B

A

B

A

B真包含14n元集，m元子集含有n个元素的集合简称n元集,它的含有m个(m≤n)元素的子集称为它的m元子集.例题3.2:A={a,b,c},求A的全部子集.0元子集,即空集,只有1个

.1元子集,即单元集,个{a},{b},{c}2元子集个

{a,b},{a,c}{b,c}3元子集1个{a,b,c}n元集的集合个数为:

15幂集定义P(A)={B|B

A}

设A={a,b,c},则P(A)={,{a},{b},{c},{a,b},{a,c},{b,c}{a,b,c}}计数:如果|A|=n，则|P(A)|=2n

16空集和全集全集：如果所涉及的集合都是某个集合的子集,则称这个集合为全集,记作E.空集：不含任何元素的集合,记为17第3章集合的基本概念和运算3.1集合的基本概念3.2集合的基本运算3.3集合中元素的计数183.2集合的基本运算集合基本运算的定义

文氏图（JohnVenn）集合运算的算律恒等式的证明19集合基本运算的定义并

A

B={x|x

A

x

B

}交

A

B={x|x

A

x

B}相对补

A

B={x|x

A

x

B}对称差

A

B=(A

B)

(B

A)=(A

B)(A

B)

绝对补

A=E

A

20文氏图表示21例题A={1,2,3},B={1,4},C={3}AB={1,2,3,4}=BAAB={1}=BAA-B={2,3}B-A={4}C-A=

AB={2,3}{4}={2,3,4}对称差的等价定义为AB=(AB)-(AB)当两个集合的交集是空集时,称他们是不交的.22关于运算的说明运算顺序：和幂集优先，其他由括号确定并和交运算可以推广到有穷个集合上，即

A1

A2

…An={x|x

A1

x

A2

…

x

An}

A1

A2

…An={x|x

A1

x

A2

…

x

An}23

交换A

B=B

AA

B=B

AA

B=B

A结合(A

B)C=A

(B

C)(A

B)C=A

(B

C)(A

B)C=A

(B

C)幂等A

A=AA

A=A集合运算的算律吸收律的前提：

、可交换24

与

与

分配A

(B

C)=(A

B)(A

C)A

(B

C)=(A

B)(A

C)A

(B

C)=(A

B)(A

C)吸收A

(A

B)=AA

(A

B)=A25集合运算的算律（续）

D.M律A

(B

C)=(A

B)(A

C)A

(B

C)=(A

B)(A

C)

(B

C)=B

C

(B

C)=B

C双重否定

A=A26

E补元律A

A=A

A=E零律A

=

A

E=E同一律A

=AA

E=A否定

=E

E=27第3章集合的基本概念和运算3.1集合的基本概念3.2集合的基本运算3.3集合中元素的计数28集合的基数与有穷集合包含排斥原理有穷集的计数3.3集合中元素的计数29集合A的基数：集合A中的元素数，记作cardA注：||=0;有穷集

A：cardA=|A|=n，n为自然数.有穷集的实例：

A={a,b,c},cardA=|A|=3；

B={x|x2+1=0,x

R},cardB=|B|=0无穷集的实例：

N,Z,Q,R,C等集合的基数与有穷集合30

解：

2的倍数是：2，4，6，8，10，12，14，16，18，20。共10个；例1

求不超过20的正整数中2或3的倍数的个数。因为6，12，18在两类中重复计数，应减去。3的倍数是：3，6，9，12，15，18。共6个；故答案是：10+6-3=13容斥原理31

对于求两个有限集合A和B的并的元素数目，我们有即具有性质A或B的元素的个数等于具有性质A的元素个数和具有性质B的元素个数减去同时具有性质A和B的元素个数。(1)定理1容斥原理32ABA∩BU3.1

容斥原理33AB

CA∩BA∩B∩CB∩CA∩CU3.1

容斥原理34定理23.1

容斥原理35同理可推出：利用数学归纳法可得一般的定理：3.1

容斥原理36(4)定理3设A1,A2,…,An是有限集合，则3.1

容斥原理37(5)容斥原理指的就是（4）和（5）式。用来计算有限集合的并或交的元素个数。3.1

容斥原理38包含排斥原理定理设S为有穷集，P1,P2,…,Pm

是m种性质，Ai是S

中具有性质Pi

的元素构成的子集，i=1,2,…,m.则S

中不具有性质P1,P2,…,Pm的元素数为39S中至少具有一条性质的元素数为推论40解：S={x

|xZ,1x

1000},

如下定义S

的3个子集A,B,C：

A={x

|x

S,5|x

}，

B={x

|x

S,6|x

}，

C={x

|x

S,8|x

}例1求1到1000之间（包含1和1000在内）既不能被5和6整除，也不能被8整除的数有多少个？应用41对上述子集计数：

|S|=1000,|A|=

1000/5

=200,|B|=1000/6=133，

|C|=1000/8

=125,

|A

B|=1000/30

=33,|B

C|=1000/40

=25,|B

C|=1000/24

=41,|A

B

C|=1000/120

=8,代入公式

N=1000

(200+133+125)+(33+25+41)

8=600例1（续）42文氏图法

求1到1000之间（包含1和1000在内）既不能被5和6整除，也不能被8整除的数有多少个？43例2

24名科技人员，每人至少会1门外语.英语：13；日语：5；德语：10；法语：9英日：2;英德：4；英法：4；法德：4会日语的不会法语、德语求：只会1种语言人数，会3种语言人数x+2(4-x)+y1+2=13x+2(4-x)+y2=10x+2(4-x)+y3=9x+3(4-x)+y1+y2+y3=19x=1,y1=4,y2=3,y3=2

44二元关系和函数离散数学45第4章二元关系与函数4.1集合的笛卡儿积与二元关系4.2关系的运算4.3关系的性质4.4关系的闭包4.5等价关系和偏序关系4.6函数的定义和性质4.7函数的复合和反函数464.1集合的笛卡儿积和二元关系

有序对笛卡儿积及其性质二元关系的定义二元关系的表示47有序对定义

由两个客体x和y，按照一定的顺序组成的二元组称为有序对，记作<x,y>实例：点的直角坐标(3,

4)有序对性质有序性<x,y>

<y,x>（当x

y时）

<x,y>与<u,v>相等的充分必要条件是

<x,y>=<u,v>

x=u

y=v例1<2,x+5>=<3y

4,y>，求x,y.解3y

4=2,x+5=y

y=2,x=3

48有序n元组定义一个有序n(n3)元组<x1,x2,…,xn>是一个有序对，其中第一个元素是一个有序n-1元组，即

<x1,x2,…,xn>=<<x1,x2,…,xn-1>,xn>

当n=1时,<x>形式上可以看成有序1元组.实例

n维向量是有序

n元组.49笛卡儿积定义设A,B为集合，A与B的笛卡儿积记作A

B，即A

B={<x,y>|x

A

y

B

}例2A={1,2,3},B={a,b,c}

A

B={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,<3,a>,<3,b>,<3,c>}

B

A={<a,1>,<b,1>,<c,1>,<a,2>,<b,2>,<c,2>,<a,3>,<b,3>,<c,3>}50笛卡儿积的性质不适合交换律

A

B

B

A(A

B,A

,B

)不适合结合律

(A

B)

C

A

(B

C)(A

,B

)对于并或交运算满足分配律

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)若A或B中有一个为空集，则A

B就是空集.

A

=

B=

若|A|=m,|B|=n,则|A

B|=mn

51性质的证明证明A

(B

C)=(A

B)

(A

C)证任取<x,y><x,y>∈A×(B∪C)

x∈A∧y∈B∪C

x∈A∧(y∈B∨y∈C)

(x∈A∧y∈B)∨(x∈A∧y∈C)

<x,y>∈A×B∨<x,y>∈A×C

<x,y>∈(A×B)∪(A×C)所以有A×(B∪C)=(A×B)∪(A×C).52例题解(1)任取<x,y><x,y>

A

C

x

A

y

C

x

B

y

D

<x,y>

B

D

例3(1)证明A=B

C=D

A

C=B

D

(2)A

C=B

D是否推出A=B

C=D?为什么？(2)不一定.反例如下：

A={1}，B={2},C=D=

,则A

C=B

D但是A

B.53二元关系的定义定义如果一个集合满足以下条件之一：（1）集合非空,且它的元素都是有序对（2）集合是空集则称该集合为一个二元关系,简称为关系，记作R.如<x,y>∈R,可记作xRy；如果<x,y>

R,则记作xy实例：R={<1,2>,<a,b>},S={<1,2>,a,b}.R是二元关系,当a,b不是有序对时，S不是二元关系根据上面的记法，可以写1R2,aRb,ac等.

54从A到B的关系与A上的关系定义设A,B为集合,A×B的任何子集所定义的二元关系叫做从A到B的二元关系,当A=B时则叫做A上的二元关系.例4A={0,1},B={1,2,3},R1={<0,2>},R2=A×B,R3=

,R4={<0,1>}.那么R1,R2,R3,R4是从A到B的二元关系,R3和R4同时也是A上的二元关系.计数|A|=n,|A×A|=n2,A×A的子集有个.所以A上有个不同的二元关系.55A上重要关系的实例设A为任意集合，

是A上的关系，称为空关系EA,IA分别称为全域关系与恒等关系，定义如下：

EA={<x,y>|x∈A∧y∈A}=A×A

IA={<x,x>|x∈A}如,A={1,2},则

EA={<1,1>,<1,2>,<2,1>,<2,2>}

IA={<1,1>,<2,2>}

56A上重要关系的实例（续）小于等于关系LA,整除关系DA,包含关系R

定义：

LA={<x,y>|x,y∈A∧x≤y},A

R，R为实数集合

DB={<x,y>|x,y∈B∧x整除y},B

Z*,Z*为非0整数集

R

={<x,y>|x,y∈A∧x

y},A是集合族.57实例例如A={1,2,3},B={a,b},则

LA={<1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3>}DA={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}

A=P(B)={

,{a},{b},{a,b}},则A上的包含关系是R

={<

,

>,<

,{a}>,<

,{b}>,<

,{a,b}>,<{a},{a}>,<{a},{a,b}>,<{b},{b}>,<{b},{a,b}>,<{a,b},{a,b}>}

58关系的表示表示方式：关系的集合表达式、关系矩阵、关系图关系矩阵：若A={a1,a2,…,am}，B={b1,b2,…,bn}，R是从A到B的关系，R的关系矩阵是布尔矩阵MR=[rij]m

n,其中

rij

=1

<ai,bj>

R.关系图：若A={x1,x2,…,xm}，R是从A上的关系，R的关系图是GR=<A,R>,其中A为结点集，R为边集.如果<xi,xj>属于关系R，在图中就有一条从xi

到xj

的有向边.注意：关系图适于表示A上的关系

59实例A={1,2,3,4},R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},R的关系矩阵MR和关系图GR如下：60第4章二元关系与函数4.1集合的笛卡儿积与二元关系4.2关系的运算4.3关系的性质4.4关系的闭包4.5等价关系和偏序关系4.6函数的定义和性质4.7函数的复合和反函数61基本运算定义定义域、值域、域逆、合成、限制、像基本运算的性质幂运算定义求法性质4.2关系的运算62关系的基本运算定义定义域、值域

和域

domR={x|

y(<x,y>

R)}

ranR={y|

x(<x,y>

R)}

fldR=domR

ranR

例1R={<1,2>,<1,3>,<2,4>,<4,3>},则

domR={1,2,4}

ranR={2,3,4}

fldR={1,2,3,4}63关系的基本运算定义（续）逆与合成

R

1={<y,x>|<x,y>

R}

R∘S={<x,y>|

z(<x,z>

S

<z,y>

R)}例2R={<1,2>,<2,3>,<1,4>,<2,2>}

S={<1,1>,<1,3>,<2,3>,<3,2>,<3,3>}

R

1={<2,1>,<3,2>,<4,1>,<2,2>}

R∘S

={<1,2>,<1,4>,<3,2>,<3,3>}S∘R={<1,3>,<2,2>,<2,3>}64限制与像定义

F在A上的限制

F↾A={<x,y>|xFy

x

A}A在F下的像

F[A]=ran(F↾A)实例R={<1,2>,<2,3>,<1,4>,<2,2>}

R↾{1}={<1,2>,<1,4>}

R[{1}]={2,4}R[{1,2}]={2,3,4}注意：F↾A

F,F[A]ranF

65关系基本运算的性质定理1设F是任意的关系,则(1)(F

1)

1=F(2)domF

1=ranF,ranF

1=domF66定理2设F,G,H是任意的关系,则

(1)(F∘G)∘H=F∘(G∘H)(2)(F∘G)

1=G

1∘F

1关系基本运算的性质（续）

67A上关系的幂运算设R为A上的关系,n为自然数,则R的n次幂定义为：

(1)R0={<x,x>|x∈A

}=IA

(2)Rn+1=Rn∘R

68幂的求法对于集合表示的关系R，计算Rn

就是n个R右复合.矩阵表示就是n个矩阵相乘,其中相加采用逻辑加.例3设A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>},求R的各次幂,分别用矩阵和关系图表示.解R与R2的关系矩阵分别为69同理，R0=IA,R3和R4的矩阵分别是：因此M4=M2,即R4=R2.因此可以得到

R2=R4=R6=…,R3=R5=R7=…

幂的求法（续）70R0,R1,R2,R3,…的关系图如下图所示幂的求法（续）71定理4设R是A上的关系,m,n∈N,则

(1)Rm∘Rn=Rm+n

(2)(Rm)n=Rmn

幂运算的性质（续）72内容提纲集合的笛卡尔积与二元关系关系的运算关系的性质关系的闭包等价关系和偏序关系函数的定义和性质函数的复合和反函数734.3关系的性质自反性反自反性对称性反对称性传递性74定义自反性反自反性对称性反对称性传递性定义xA,有<x,x>RxA,有<x,x>R若<x,y>R则<y,x>R若<x,y>R,且xy,则<y,x>R若<x,y>R且<y,z>R则<x,z>R关系矩阵特点主对角线的元素全为1主对角线的元素全为0矩阵为对称矩阵如果rij=1,且xy则rji=0关系图特点图中每个节点都有环图中每个节点都没有环如果两个顶点之间有边,一定是一对方向相反的边.如果两个顶点之间有边,一定是一条有向边.如果xi到xj有边，xj到xk有边，则xi到xk一定有边．75关系性质判别

自反反自反对称反对称传递表达式IA

RR∩IA=

R=R

1

R∩R

1

IA

R

R

R76实例例1A={1,2,3},R1,R2,R3是A上的关系,其中

R1＝{<1,1>,<2,2>}R2＝{<1,1>,<2,2>,<3,3>,<1,2>}R3＝{<1,3>}R1既不是自反也不是反自反的R2自反,R3反自反,77实例例2设A＝{1,2,3},R1,R2,R3和R4都是A上的关系,

其中

R1＝{<1,1>,<2,2>}，R2＝{<1,1>,<1,2>,<2,1>}

R3＝{<1,2>,<1,3>}，R4＝{<1,2>,<2,1>,<1,3>}R1

对称、反对称.R2

对称，不反对称.R3

反对称，不对称.R4

不对称、也不反对称.78实例例3设A＝{1,2,3},R1,R2,R3是A上的关系,其中

R1＝{<1,1>,<2,2>}

R2＝{<1,2>,<2,3>}

R3＝{<1,3>}

R1和R3是A上的传递关系

R2不是A上的传递关系79实例例4判断下图中关系的性质,并说明理由.(2)反自反，不是自反的；反对称，不是对称的；是传递的.(1)不自反也不反自反；对称,不反对称；不传递.(3)自反，不反自反；反对称，不是对称；不传递.804.4关系的闭包闭包定义闭包的构造方法集合表示矩阵表示图表示81闭包定义定义

设R是非空集合A上的关系,R的自反（对称

或传递）闭包是A上的关系R

,使得R

满足以下条件：（1）R

是自反的（对称的或传递的）（2）R

R

（3）对A上任何包含R的自反（对称或传递）关系R

有R

R

.

一般将R的自反闭包记作r(R),对称闭包记作s(R),传递闭包记作t(R).82闭包的构造方法定理1设R为A上的关系,则有

(1)r(R)=R∪R0(2)s(R)=R∪R

1(3)t(R)=R∪R2∪R3∪…

说明：对于有穷集合A(|A|=n)上的关系,(3)中的并最多不超过Rn.

若R是自反的，则r(R)=R;若R是对称的，则

s(R)=R;若R是传递的，则t(R)=R.83设关系R,r(R),s(R),t(R)的关系矩阵分别为M,Mr,Ms和Mt,则

Mr

=M+EMs=M+M’

Mt=M+M2+M3+…E是和M同阶的单位矩阵,M’是M的转置矩阵.注意在上述等式中矩阵的元素相加时使用逻辑加.闭包的构造方法（续）84闭包的构造方法（续）设关系R,r(R),s(R),t(R)的关系图分别记为G,Gr,Gs,Gt

,则Gr,Gs,Gt

的顶点集与G的顶点集相等.除了G的边以外,以下述方法添加新边：

考察G的每个顶点,如果没有环就加上一个环，最终得到Gr

.考察G的每条边,如果有一条xi到xj

的单向边,i≠j,则在G中加一条xj

到xi的反方向边，最终得到Gs.考察G的每个顶点xi,找从xi出发的每一条路径，如果从xi到路径中任何结点xj

没有边，就加上这条边.当检查完所有的顶点后就得到图Gt

.85实例例1设A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>},R和r(R),s(R),t(R)的关系图如下图所示.

Rr(R)s(R)t(R)864.5等价关系与偏序关系等价关系的定义与实例等价类及其性质商集与集合的划分等价关系与划分的一一对应偏序关系偏序集与哈斯图偏序集中的特定元素87一、等价关系的定义与实例定义

设R为非空集合上的关系.如果R是自反的、对称的和传递的,则称R为A上的等价关系.设R是一个等价关系,若<x,y>∈R,称x等价于y,记做x～y.

实例

设A={1,2,…,8},如下定义A上的关系R：

R={<x,y>|x,y∈A∧x≡y(mod3)}其中x≡y(mod3)叫做x与y模3相等,即x除以3的余数与y除以3的余数相等.88等价关系的验证验证模3相等关系R为A上的等价关系,因为

x∈A,有x≡x(mod3)

x,y∈A,若x≡y(mod3),则有y≡x(mod3)

x,y,z∈A,若x≡y(mod3),y≡z(mod3),

则有x≡z(mod3)自反性、对称性、传递性得到验证89A上模3等价关系的关系图设A={1,2,…,8},

R={<x,y>|x,y∈A∧x≡y(mod3)}

90二、等价类及性质定义设R为非空集合A上的等价关系,

x∈A，令

[x]R

={y|y∈A∧xRy

}称[x]R

为x关于R的等价类,简称为x的等价类,简记为[x].实例A={1,2,…,8}上模3等价关系的等价类：

[1]=[4]=[7]={1,4,7}[2]=[5]=[8]={2,5,8}[3]=[6]={3,6}91等价类的性质

定理1

设R是非空集合A上的等价关系,则

(1)

x∈A,[x]是A的非空子集.

(2)

x,y∈A,如果xRy,则[x]=[y].

(3)

x,y∈A,如果xy,则[x]与[y]不交.

(4)∪{[x]|x∈A}=A，即所有等价类的并集就是A.

92实例A={1,2,…,8}上模3等价关系的等价类：

[1]=[4]=[7]={1,4,7}，

[2]=[5]=[8]={2,5,8}，

[3]=[6]={3,6}

以上3类两两不交，

{1,4,7}{2,5,8}{3,6}={1,2,…,8}93三、商集定义

设R为非空集合A上的等价关系,以R的所有等价类作为元素的集合称为A关于R的商集,记做A/R,

A/R={[x]R

|x∈A

}实例

A={1,2,…,8},A关于模3等价关系R的商集为

A/R={{1,4,7},{2,5,8},{3,6}}

A关于恒等关系和全域关系的商集为：

A/IA

={{1},{2},…,{8}}

A/EA

={{1,2,…,8}}94集合的划分定义

设A为非空集合,若A的子集族π(π

P(A))

满足下面条件：

(1)

π(2)

x

y

(x,y∈π∧x≠y→x∩y=

)(3)∪π=A

则称π是A的一个划分,称π中的元素为A的划分块.95例题例1设A＝{a,b,c,d},

给定π1,π2,π3,π4,π5,π6如下：

π1={{a,b,c},{d}}，π2={{a,b},{c},{d}}

π3={{a},{a,b,c,d}},π4={{a,b},{c}}

π5={

,{a,b},{c,d}},π6={{a,{a}},{b,c,d}}

则π1和π2

是A的划分,其他都不是A的划分.96四、等价关系与划分的一一对应商集A/R就是A的一个划分

不同的商集对应于不同的划分

任给A的一个划分π,如下定义A上的关系R：

R={<x,y>|x,y∈A∧x

与y在π的同一划分块中}则R为A上的等价关系,且该等价关系确定的商集就是π.例2给出A＝{1,2,3}上所有的等价关系97等价关系与划分之间的对应π1,π2和π3分别对应等价关系R1,R2和R3.

R1={<2,3>,<3,2>}∪IA，R2={<1,3>,<3,1>}∪IA

R3={<1,2>,<2,1>}∪IAπ4对应于全域关系

EA，π5对应于恒等关系

IA98五、偏序关系定义非空集合A上的自反、反对称和传递的关系，称为A上的偏序关系，记作≼.设≼为偏序关系,如果<x,y>∈≼,则记作x≼y,读作x“小于或等于”y.

实例集合A上的恒等关系IA是A上的偏序关系.

小于或等于关系,整除关系和包含关系也是相应集合上的偏序关系.99相关概念x与y可比：设R为非空集合A上的偏序关系,

x,y

A,x与y可比

x≼y

∨y≼x.

全序关系：

R为非空集合A上的偏序,

x,y

A,x与y都是可比的，则称R为全序（或线序）实例：数集上的小于或等于关系是全序关系整除关系不是正整数集合上的全序关系100覆盖：设R为非空集合A上的偏序关系,x,y∈A,如果x≺y且不存在z

A

使得x≺z≺y,则称y覆盖x.实例：{1,2,4,6}集合上的整除关系,2覆盖1,4和6覆盖2.4不覆盖1.

相关概念（续）101六、偏序集与哈斯图定义

集合A和A上的偏序关系≼一起叫做偏序集,记作

<A,≼>.实例：整数集和小于等于关系构成偏序集<Z,≤>，幂集P(A)和包含关系构成偏序集<P(A),R

>.哈斯图：利用偏序的自反、反对称、传递性简化的关系图特点：每个结点没有环，两个连通的结点之间的序关系通过结点位置的高低表示，位置低的元素的顺序在前，具有覆盖关系的两个结点之间连边102哈斯图实例例4<{1,2,3,4,5,6,7,8,9},R整除><P({a,b,c}),R

>103A={a,b,c,d,e,f,g,h}

R={<b,d>,<b,e>,<b,f>,<c,d>,<c,e>,<c,f>,<d,f>,<e,f>,<g,h>}∪IA

哈斯图实例（续）例5已知偏序集<A,R>的哈斯图如右图所示,试求出集合A和关系R的表达式.

104七、偏序集的特定元素定义设<A,≼>为偏序集,B

A,y∈B.(1)若

x(x∈B→y≼x)成立,则称y为B的最小元.(2)若

x(x∈B→x≼y)成立,则称y为B的最大元.(3)若

x(x∈B∧x

≺y)成立,则称y为B的极小元.(4)若

x(x∈B∧y

≺x)成立,则称y为B的极大元.

105求最大，最小，极大，极小元106定义

设<A,≼>为偏序集,B

A,y

A.(1)若

x(x∈B→x≼y)成立,则称y为B的上界.

(2)若

x(x∈B→y≼x)成立,则称y为B的下界.

(3)令C＝{y|y为B的上界},则称C的最小元为B的最小上界或上确界.

(4)令D＝{y|y为B的下界},则称D的最大元为B的最大下界或下确界.偏序集的特定元素(续)107求上界，下界，上确界，下确界108第4章二元关系与函数4.1集合的笛卡儿积与二元关系4.2关系的运算4.3关系的性质4.4关系的闭包4.5等价关系和偏序关系4.6函数的定义和性质4.7函数的复合和反函数1094.6函数的定义与性质函数的定义函数定义从A到B的函数函数的像函数的性质函数的单射、满射、双射性构造双射函数110一、函数定义定义

设F为二元关系,若

x∈domF

都存在唯一的y∈ranF

使xFy

成立,则称F为函数.对于函数F,如果有xFy,则记作y=F(x),并称y为F在x的值.例1F1={<x1,y1>,<x2,y2>,<x3,y2>}

F2={<x1,y1>,<x1,y2>}

F1是函数,F2不是函数

111函数相等定义

设F,G为函数,则

F=G

F

G∧G

F

如果两个函数F和G相等,一定满足下面两个条件：

(1)domF

=domG

(2)

x∈domF

=domG

都有F(x)=G(x)

实例函数

F(x)=(x2

1)/(x+1),G(x)=x

1不相等,因为domF

domG.

112从A到B的函数定义

设A,B为集合,如果

f为函数

domf

=A

ranf

B,则称f为从A到B的函数,记作f：A→B.实例

f：N→N,f(x)=2x是从N到N的函数

g：N→N,g(x)=2也是从N到N的函数

113B上A定义

所有从A到B的函数的集合记作BA,读作“B上A”，符号化表示为

BA={f|f：A→B}计数：

|A|=m,|B|=n,且m,n>0,|BA|=nm.A=

,则BA=B

={

}.

A≠

且B=

,则

BA=

A=

.

114实例例2设A={1,2,3},B={a,b},求BA.

解BA={f0,f1,…,f7},其中

f0={<1,a>,<2,a>,<3,a>},f1={<1,a>,<2,a>,<3,b>}

f2={<1,a>,<2,b>,<3,a>}，f3={<1,a>,<2,b>,<3,b>}

f4={<1,b>,<2,a>,<3,a>}，f5={<1,b>,<2,a>,<3,b>}

f6={<1,b>,<2,b>,<3,a>},f7={<1,b>,<2,b>,<3,b>}

115函数的像定义设函数f：A→B,A1

A.

A1在f下的像：

f(A1)={f(x)|x∈A1}

函数的像

f(A)

注意：函数值f(x)∈B,而像f(A1)

B.例3

设f：N→N,

且

令A={0,1},B={2},那么有

f(A)=f({0,1})={f(0),f(1)}={0,2}116二、函数的性质定义设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是双射的f

满射意味着：

y

B,都存在x

A

使得

f(x)=y.f单射意味着：f(x1)=f(x2)

x1=x2

117实例例4判断下面函数是否为单射,满射,双射的,为什么?

(1)f：R→R,f(x)=

x2+2x

1

(2)f：Z+→R,f(x)=lnx,Z+为正整数集

(3)f：R→Z,f(x)=

x

(4)f：R→R,f(x)=2x+1

(5)f：R+→R+,f(x)=(x2+1)/x,其中R+为正实数集.

118解(1)f：R→R,f(x)=

x2+2x

1

在x=1取得极大值0.既不单射也不满射.(2)f：Z+→R,f(x)=lnx

单调上升,是单射.但不满射,ranf={ln1,ln2,…}.(3)f：R→Z,f(x)=

x

满射,但不单射,例如f(1.5)=f(1.2)=1.

(4)f：R→R,f(x)=2x+1

满射、单射、双射,因为它是单调的并且ranf=R.(5)f：R+→R+,f(x)=(x2+1)/x

有极小值f(1)=2.该函数既不单射也不满射.

实例（续）119常函数、恒等函数、单调函数

1.

设f：A→B,若存在c∈B

使得

x∈A

都有

f(x)=c,则称f：A→B是常函数.2.称A上的恒等关系IA为A上的恒等函数,对所有的x∈A

都有IA(x)=x.3.设f：R→R，如果对任意的

x1,x2∈R，x1<x2,就有f(x1)

f(x2),则称f为单调递增的；如果对任意的x1,x2∈A,x1<x2,就有f(x1)<f(x2),则称f为严格单调递增的.

类似可以定义单调递减和严格单调递减的函数.120第4章二元关系与函数4.1集合的笛卡儿积与二元关系4.2关系的运算4.3关系的性质4.4关系的闭包4.5等价关系和偏序关系4.6函数的定义和性质4.7函数的复合和反函数1214.7函数的复合与反函数函数的复合函数复合的定理函数复合的性质反函数反函数存在的条件反函数的性质122函数复合的定理定理

设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))

例如：

G:RR,G(x)=x+1,

F