离散数学 (第七版) 课件 第二部分 集合论

1

集合论2集合论部分第3章集合的基本概念和运算第4章二元关系和函数3第3章集合的基本概念和运算3.1集合的基本概念3.2集合的基本运算3.3集合中元素的计数43.1集合的基本概念

集合的定义与表示集合与元素集合之间的关系空集全集幂集5集合定义与表示集合没有精确的数学定义理解：一些离散个体组成的全体组成集合的个体称为它的元素或成员集合的表示

列元素法

A={a,b,c,d}

谓词表示法

B={x|P(x)}

B由使得P(x)为真的

x

构成常用数集

N,Z,Q,R,C

分别表示自然数、整数、有理数、实数和复数集合，注意0是自然数.6集合与元素元素与集合的关系：隶属关系属于，不属于

实例

A={x|xRx2-1=0},A={-1,1}

1

A,2A注意：对于任何集合A和元素x(可以是集合)，

x

A和x

A两者成立其一，且仅成立其一.7隶属关系的层次结构例3.1A={a,{b,c},d,{{d}}}{b,c}

Ab

A{{d}}A{d}Ad

A

8集合之间的关系

包含（子集）

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

B

A

B

不真包含

A

B

思考：

和

的定义注意

和

是不同层次的问题9空集与全集空集

不含任何元素的集合实例{x|x2+1=0xR}就是空集定理空集是任何集合的子集

A

x(x

x

A)T

推论空集是惟一的.证

假设存在1和2，则1

2且1

2，因此1=2全集E

相对性在给定问题中，全集包含任何集合，即

A

(A

E)10幂集定义

P(A)={x|x

A}实例

P(

)={

}，

P({

})={

,{

}}

P({1,{2,3}})={,{1},{{2,3}},{1,{2,3}}}计数如果|A|=n，则|P(A)|=2n

113.2集合的基本运算集合基本运算的定义

文氏图（JohnVenn）例题集合运算的算律集合包含或恒等式的证明12集合基本运算的定义并

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

13文氏图表示14关于运算的说明运算顺序：和幂集优先，其他由括号确定并和交运算可以推广到有穷个集合上，即

A1

A2

…An={x|x

A1

x

A2

…

x

An}

A1

A2

…An={x|x

A1

x

A2

…

x

An}某些重要结果

A

B

A

A

B

A

B=

（后面证明）

A

B=

A

B=A15只有一、二年级的学生才爱好体育运动

F:一年级大学生的集合S：二年级大学生的集合

R：计算机系学生的集合M：数学系学生的集合

T：选修离散数学的学生的集合

L：爱好文学学生的集合P：爱好体育运动学生的集合T(MR)SRST(MF)T=MLPPFSS(MR)P除去数学和计算机系二年级学生外都不

选修离散数学例1

所有计算机系二年级学生都选修离散数学数学系一年级的学生都没有选修离散数学数学系学生或爱好文学或爱好体育运动16例2

分别对条件(1)到(5)，确定X集合与下述那些集合相等。

S1={1,2,…,8,9},S2={2,4,6,8},S3={1,3,5,7,9},

S4={3,4,5},S5={3,5}

若X

S3=,则X

若X

S4,X

S2=,则X

若X

S1，XS3,则X

若X

S3=,则X

若

X

S3，XS1,

则X=S2=S5=S1,S2,S4=S3,S5与S1,...,S5都不等17

交换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

与

与

分配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)=A集合运算的算律吸收律的前提：、可交换18集合运算的算律（续）

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=A

E补元律A

A=A

A=E零律A

=

A

E=E同一律A

=AA

E=A否定

=E

E=19集合包含或相等的证明方法证明

X

Y命题演算法包含传递法等价条件法反证法并交运算法证明X=Y命题演算法等式代入法反证法运算法以上的X,Y代表集合公式20任取x，

x

X…x

Y

命题演算法证X

Y

例3证明A

B

P(A)

P(B)

任取x

x

P(A)x

A

x

B

x

P(B)

任取x

x

A{x}A{x}P(A){x}P(B){x}B

x

B21包含传递法证X

Y找到集合T满足X

T且T

Y，从而有X

Y例4A

B

A

B证

A

B

AA

A

B

所以

A

B

A

B

22利用包含的等价条件证X

Y例5A

C

B

C

A

B

C

证A

C

A

C=C

B

C

B

C=C

(A

B)C=A(B

C)=A

C=C(A

B)C=C

A

B

C

命题得证23反证法证X

Y欲证X

Y,假设命题不成立，必存在x使得

x

X且x

Y.然后推出矛盾.例6证明A

C

B

C

A

B

C证假设A

B

C不成立，则

x(x

A

B

x

C)

因此

x

A或

x

B，且x

C

若x

A,则与A

C矛盾；

若x

B,则与B

C矛盾.

24利用已知包含式并交运算例7证明

A

C

B

C

A

C

B

C

A

B证

A

C

B

C，A

C

B

C

上式两边求并，得

(A

C)(A

C)(B

C)(B

C)

(A

C)(A

C)(B

C)(B

C)

A(C

C)

B(C

C)

A

E

B

E

A

B由已知包含式通过运算产生新的包含式

X

Y

X

Z

Y

Z,X

Z

Y

Z25

例8证明A(A

B)=A

（吸收律）证任取x,

x

A(A

B)x

A

x

A

B

x

A(x

A

x

B)x

A

命题演算法证明X=Y任取x

，

x

X…x

Y

x

Y…x

X

或者

x

X…x

Y26等式替换证明X=Y例9证明A

(A

B)=A

（吸收律）证(假设交换律、分配律、同一律、零律成立)

A

(A

B)=(A

E)

(A

B)同一律

=A

(E

B)分配律

=A

(B

E)交换律

=A

E

零律

=A

同一律不断进行代入化简，最终得到两边相等27反证法证明X=Y例10证明以下等价条件

A

B

A

B=B

A

B=A

A

B=

(1)(2)(3)(4)证明顺序：

(1)(2),(2)(3),(3)(4),(4)(1)假设X=Y不成立，则存在x使得x

X且x

Y，或者存在x使得x

Y且x

X，然后推出矛盾.28(1)(2)显然B

A

B，下面证明A

B

B.任取x，

x

A

B

x

A

x

B

x

B

x

B

x

B因此有A

B

B.综合上述（2）得证.(2)(3)

A=A

(A

B)

A=A

B

（将A

B用B代入)29(3)(4)假设A

B

,即

x

A

B，那么x

A且x

B.而

x

B

x

A

B.从而与A

B=A矛盾.(4)(1)假设A

B不成立，那么

x(x

A

x

B)

x

A

B

A

B

与条件（4）矛盾.30集合运算法证明X=Y例11证明A

C=B

C

A

C=B

C

A=B证由A

C=B

C

和

A

C=B

C

得到

(A

C)-(A

C)=(B

C)-(B

C)

从而有A

C=B

C

因此

A

C=B

C(A

C)C=(B

C)C

A(C

C)=B(C

C)A=B

A=B由已知等式通过运算产生新的等式

X=Y

X

Z=Y

Z,X

Z=Y

Z，X-Z=Y-Z31集合的基数与有穷集合包含排斥原理有穷集的计数3.3集合中元素的计数32集合A的基数：集合A中的元素数，记作cardA有穷集

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等集合的基数与有穷集合33包含排斥原理定理设S为有穷集，P1,P2,…,Pm

是m种性质，Ai是S

中具有性质Pi

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

中不具有性质P1,P2,…,Pm的元素数为34证明证设x不具有性质P1,P2,…,Pm,

x

Ai

,i=1,2,…,m

x

Ai

Aj

,1i<j

m

…

x

A1

A2…Am

,x对右边计数贡献为

10+00+…+(1)m·0=1证明要点：任何元素

x，如果不具有任何性质，则对等式右边计数贡献为１，否则为０35证明（续）设x具有n条性质，1n

m

x

对|S|贡献为1

x

对贡献为

x

对贡献为

….

x

对|A1

A2…Am|贡献为

x对右边计数贡献为36S中至少具有一条性质的元素数为证明将定理1代入即可推论37解：S={x|xZ,1x1000},

如下定义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整除的数有多少个？应用38对上述子集计数：

|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（续）39文氏图法

求1到1000之间（包含1和1000在内）既不能被5和6整除，也不能被8整除的数有多少个？40例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

41例3求欧拉函数的值

欧拉函数：

(n)

表示{0,1,…,n

1}中与n互素的数的个数.

(12)=4，与12互素的数有1,5,7,11.解：

n的素因子分解式Ai={x|0

x<n

1且

pi整除

x}42实例与60互素的正整

数有16个：1,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59.4344第4章二元关系与函数4.1集合的笛卡儿积与二元关系4.2关系的运算4.3关系的性质4.4关系的闭包4.5等价关系和偏序关系4.6函数的定义和性质4.7函数的复合和反函数454.1集合的笛卡儿积和二元关系

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

由两个客体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

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

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

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

n维向量是有序

n元组.48笛卡儿积定义设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>}

A={

},P(A)

A={<

,

>,<{

},

>}49笛卡儿积的性质不适合交换律

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

50性质的证明证明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).51例题解(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.52二元关系的定义定义如果一个集合满足以下条件之一：（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等.53从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上有个不同的二元关系.例如|A|=3,则A上有=512个不同的二元关系.54A上重要关系的实例设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>}

55A上重要关系的实例（续）小于等于关系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是集合族.类似的还可以定义大于等于关系,小于关系,大于关系,真包含关系等等.56实例例如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}>}

57关系的表示表示方式：关系的集合表达式、关系矩阵、关系图关系矩阵：若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,B为有穷集，关系矩阵适于表示从A到B的关系或者A上的关系，关系图适于表示A上的关系58实例A={1,2,3,4},R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},R的关系矩阵MR和关系图GR如下：59基本运算定义定义域、值域、域逆、合成、限制、像基本运算的性质幂运算定义求法性质4.2关系的运算60关系的基本运算定义定义域、值域

和域

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}61关系的基本运算定义（续）逆与合成

R

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

R}

R∘S=|<x,z>|

y(<x,y>

S

<y,z>

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>}62合成运算的图示方法

利用图示（不是关系图）方法求合成

R∘S={<1,2>,<1,4>,<3,2>,<3,3>}

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

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↾=

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

F,F[A]ranF

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

(1)(F

1)

1=F(2)domF

1=ranF,ranF

1=domF证(1)任取<x,y>,由逆的定义有

<x,y>∈(F

1)

1

<y,x>∈F

1

<x,y>∈F所以有(F

1)

1=F(2)任取x,x∈domF

1

y(<x,y>∈F

1)

y(<y,x>∈F)

x∈ranF

所以有domF

1=ranF.同理可证ranF

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

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

1=G

1∘F

1证(1)任取<x,y>,<x,y>

(F∘G)∘H

t(<x,t>∈H∧<t,y>∈F∘G)

t(<x,t>∈H∧

s(<t,s>∈G)∧<s,y>∈F)

t

s(<x,t>∈H∧<t,s>∈G∧<s,y>∈F)

s(

t

(<x,t>∈H∧<t,s>∈G)∧<s,y>∈F)

s(<x,s>∈G∘H∧<s,y>∈F)

<x,y>∈F∘(G∘H)

所以(F∘G)∘H=F∘(G∘H)关系基本运算的性质（续）

66(2)任取<x,y>,<x,y>∈(F∘G)

1

<y,x>∈F∘G

t(<y,t>∈G∧(t,x)∈F)

t(<x,t>∈F

1∧(t,y)∈G

1)

<x,y>∈G

1∘F

1

所以(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

注意：对于A上的任何关系R1和R2都有

R10=R20=IA

对于A上的任何关系R都有

R1=R68幂的求法对于集合表示的关系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,…的关系图如下图所示幂的求法（续）R0R1R2=R4=…R3=R5=…71幂运算的性质定理3设A为n元集,R是A上的关系,则存在自然数s和t,使得Rs=Rt.证R为A上的关系,由于|A|=n,A上的不同关系只有个.当列出R的各次幂

R0,R1,R2,…,,…,必存在自然数s和t使得Rs=Rt.72定理4设R是A上的关系,m,n∈N,则

(1)Rm∘Rn=Rm+n

(2)(Rm)n=Rmn

证用归纳法

(1)对于任意给定的m∈N,施归纳于n.

若n=0,则有

Rm∘R0=Rm∘IA=Rm=Rm+0假设Rm∘Rn=Rm+n,则有

Rm∘Rn+1=Rm∘(Rn∘R)=(Rm∘Rn)∘R=Rm+n+1,

所以对一切m,n∈N有Rm∘Rn=Rm+n.幂运算的性质（续）73(接上页证明)(2)对于任意给定的m∈N,施归纳于n.若n=0,则有

(Rm)0=IA=R0=Rm×0

假设(Rm)n=Rmn,则有

(Rm)n+1=(Rm)n∘Rm=(Rmn)∘Rm=Rmn+m=Rm(n+1)

所以对一切m,n∈N

有(Rm)n=Rmn.幂运算的性质（续）744.3关系的性质自反性反自反性对称性反对称性传递性75自反性与反自反性定义设R为A上的关系,

(1)若

x(x∈A→<x,x>

R),则称R在A上是自反的.

(2)若

x(x∈A→<x,x>

R),则称R在A上是反自反的.

实例：反关系：A上的全域关系EA,恒等关系IA

小于等于关系LA,整除关系DA反自反关系：实数集上的小于关系幂集上的真包含关系

76实例例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>}R2自反,R3反自反,R1既不是自反也不是反自反的77对称性与反对称性定义

设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→x=y),则称R为A上的反对称关系.

实例：对称关系：A上的全域关系EA,恒等关系IA和空关系

反对称关系：恒等关系IA，空关系是A上的反对称关系.

78实例例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

不对称、也不反对称.79传递性定义

设R为A上的关系,若

x

y

z(x,y,z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R),

则称R是A上的传递关系.

实例：

A上的全域关系EA,恒等关系IA和空关系

小于等于关系,小于关系，整除关系，包含关系，真包含关系

80实例例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上的传递关系81关系性质的充要条件设R为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

82关系性质判别

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

RR∩IA=

R=R

1

R∩R

1

IA

R

R

R关系矩阵主对角线元素全是1主对角线元素全是0矩阵是对称矩阵若rij＝1,且i≠j,则rji＝0对M2中1所在位置,M中相应位置都是1关系图每个顶点都有环每个顶点都没有环如果两个顶点之间有边,是一对方向相反的边(无单边)如果两点之间有边,是一条有向边(无双向边)如果顶点xi连通到xk

,则从xi到xk

有边

83实例例8判断下图中关系的性质,并说明理由.(b)反自反，不是自反的；反对称，不是对称的；是传递的.(a)不自反也不反自反；对称,不反对称；不传递.(c)自反，不反自反；反对称，不是对称；不传递.84自反性证明证明模式证明R在A上自反任取x,x

A

……………..….…….

<x,x>

R

前提推理过程结论例4证明若IA

R，则

R在A上自反.证任取x,

x

A

<x,x>

IA

<x,x>

R

因此R在A上是自反的.85对称性证明证明模式证明R在A上对称任取<x,y><x,y>

R

……………..….…….

<y,x>

R

前提推理过程结论例5证明若R=R

1,则R在A上对称.证任取<x,y>

<x,y>

R

<y,x>

R

1

<x,y>

R

因此R在A上是对称的.

86反对称性证明证明模式证明R在A上反对称任取<x,y><x,y>

R

<y,x>

R

………..……….

x=y

前提推理过程结论例6证明若R∩R

1

IA,

则R在A上反对称.证任取<x,y>

<x,y>

R

<y,x>

R

<x,y>

R

<x,y>

R

1

<x,y>

R∩R

1

<x,y>

IA

x=y

因此R在A上是反对称的.87传递性证明证明模式证明R在A上传递任取<x,y>，<y,z><x,y>

R

<y,z>

R

…..……….

<x,z>

R

前提推理过程结论例7证明若R

R

R

,

则R在A上传递.证任取<x,y>，<y,z><x,y>

R

<y,z>

R

<x,z>

R

R

<x,z>

R

因此R在A上是传递的.88运算与性质的关系自反性反自反性对称性反对称性传递性R1

1

√√√√√R1∩R2

√√√√√R1∪R2

√√√××R1

R2

×√√√×R1∘R2

√××××894.4关系的闭包闭包定义闭包的构造方法集合表示矩阵表示图表示闭包的性质90闭包定义

定义设R是非空集合A上的关系,R的自反（对称或传递）闭包是A上的关系R

,使得R

满足以下条件：

（1）R

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

（2）R

R

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

有R

R

.

一般将R的自反闭包记作r(R),对称闭包记作s(R),传递闭包记作t(R).91闭包的构造方法定理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.设关系R,r(R),s(R),t(R)的关系矩阵分别为M,Mr,Ms和Mt,则

Mr=M+EMs=M+M’

Mt=M+M2+M3+…E是和M同阶的单位矩阵,M’是M的转置矩阵.注意在上述等式中矩阵的元素相加时使用逻辑加.92闭包的构造方法（续）93闭包的构造方法（续）设关系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.94实例例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)954.5等价关系与偏序关系等价关系的定义与实例等价类及其性质商集与集合的划分等价关系与划分的一一对应偏序关系偏序集与哈斯图偏序集中的特定元素96等价关系的定义与实例定义设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的余数相等.97等价关系的验证验证模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)自反性、对称性、传递性得到验证98A上模3等价关系的关系图设A={1,2,…,8},

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

99等价类定义设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}100等价类的性质

定理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.

101实例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}102商集定义

设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}}103集合的划分定义设A为非空集合,若A的子集族π(π

P(A))满足下面条件：

(1)

π(2)

x

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

)

(3)∪π=A

则称π是A的一个划分,称π中的元素为A的划分块.104例题例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的划分.

为什么？105等价关系与划分的一一对应商集A/R就是A的一个划分不同的商集对应于不同的划分任给A的一个划分π,如下定义A上的关系R：

R={<x,y>|x,y∈A∧x与y在π的同一划分块中}

则R为A上的等价关系,且该等价关系确定的商集就是π.例2给出A＝{1,2,3}上所有的等价关系求解思路：先做出A的所有划分,然后根据划分写出对应的等价关系.106等价关系与划分之间的对应π2,π3和π3分别对应等价关系R2,R3和R4.

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

R4={<1,2>,<2,1>}∪IAπ1对应于全域关系EA，π5对应于恒等关系IA213

1

213

5213

2213

4213

3107实例例3设A={1,2,3,4}，在A

A上定义二元关系R：

<<x,y>,<u,v>>

R

x+y=u+v，求R导出的划分.

解A

A={<1,1>,<1,2>,<1,3>,<1,4>,<2,1>,<2,2>,<2,3>,<2,4>,<3,1>,<3,2>,<3,3>,<3,4>,<4,1>,<4,2>,<4,3>,<4,4>}108实例（续）根据<x,y>的x+y=2,3,4,5,6,7,8将A

A划分成7个等价类：

(A

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

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

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

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

x,y

A,x与y可比

x≼y∨y≼x.

结论：任取两个元素x和y,可能有下述情况：

x≺y(或y≺x),x＝y,x与y不是可比的.

全序关系：

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

x,y

A,x与y都是可比的，则称R为全序（或线序）实例：数集上的小于或等于关系是全序关系整除关系不是正整数集合上的全序关系111覆盖：设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.

相关概念（续）112偏序集与哈斯图定义集合A和A上的偏序关系≼一起叫做偏序集,记作<A,≼>.

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

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

>114A={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的表达式.

115偏序集的特定元素定义设<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的极大元.

116特殊元素的性质

对于有穷集，极小元和极大元必存在，可能存在多个.

最小元和最大元不一定存在，如果存在一定惟一.

最小元一定是极小元；最大元一定是极大元.

孤立结点既是极小元，也是极大元.117定义设<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的最大下界或下确界.偏序集的特定元素(续)118下界、上界、下确界、上确界不一定存在下界、上界存在不一定惟一下确界、上确界如果存在，则惟一集合的最小元就是它的下确界，最大元就是它的上确界；反之不对.特殊元素的性质119实例例6设偏序集<A,≼>如下图所示，求A的极小元、最小元、极大元、最大元.设B＝{b,c,d},求B的下界、上界、下确界、上确界.极小元：a,b,c,g；极大元：a,f,h；没有最小元与最大元.B的下界和最大下界都不存在,上界有d和f,最小上界为d.1204.6函数的定义与性质函数的定义函数定义从A到B的函数函数的像函数的性质函数的单射、满射、双射性构造双射函数应用实例：问题描述12