离散数学第二学期习题课集合论

1离散数学集合论复习2023/3/2222:152集合代数1.集合的表示,幂集,全集,空集.2.集合的三种关系(包含,相等,真包含)的定义及证明.3.集合的五种运算交∩，并∪，相对补－，绝对补~，对称差及相关性质.4.应用包含排斥原理.2023/3/2222:153集合代数基本概念:集合与元素,子集与真子集,空集,全集,幂集,并集,交集,相对补集(差集),绝对补集(补集)1.集合的表示,元素与集合的属于关系∈.

集合的三种表示方法:

枚举法:一一列出集合中的元素.

谓词描述法:用谓词描述集合中元素的性质.

文氏图:用一个平面区域表示.2.集合的三种关系(被包含,相等,被真包含)的定义及证明.ABx(x∈Ax∈B)A=BABBAx(x∈Ax∈B)ABABA≠Bx(x∈Ax∈B)x(x∈BxA)

2023/3/2222:1543.空集,全集,幂集空集φ:无元素的集合.x∈Φ是矛盾式.(空集是唯一的)

全集E:包含所讨论所有集合的集合.(全集不唯一)x∈E是重言式幂集:由A的所有子集构成的集合.

P(A)={X|XA}|P(A)|=2|A|

4.掌握集合的五种运算及相关性质.A∩B={x|x∈A∧x∈B}x∈A∩Bx∈A∧x∈BA∪B={x|x∈A∨x∈B}x∈A∪Bx∈A∨x∈BA-B={x|x∈A∧xB}x∈A-Bx∈A∧xB~A=E-A={x|x∈E∧xA}={x|xA}x∈~AxAA-B=A∩~BAB=(A-B)∪(B-A)={x|(x∈A∧xB)∨(x∈B∧xA)}AB=(A∪B)-(A∩B)2023/3/2222:155例1.已知全集E={Φ,{Φ}},AE,计算:a)P({Φ})P({Φ})=()b)P(A)∩P(~A)=()c)P(E)-P(~{{Φ}})=()解:a)因为任何集合A,都有AA=Φ所以

P({Φ})P({Φ})=Φb)Φ∈P(A)Φ∈P(~A)所以

P(A)∩P(~A)={Φ}c)P(E)={Φ,{Φ},{{Φ}},{Φ,{Φ}}}~{{Φ}}={Φ}P(~{{Φ}})=P({Φ})={Φ,{Φ}}P(E)-P(~{{Φ}}))={Φ,{Φ},{{Φ}},{Φ,{Φ}}}-{Φ,{Φ}}={{{Φ}},{Φ,{Φ}}}2023/3/2222:156例2

证明各式彼此等值。PQ(P∨Q)∧(P∨Q)c)A∪B=B,A∩B=A,AB,~B~A.证明.A∪B=B

x(x∈A∪Bx∈B)x((xA∪Bx∈B)(x∈A∪BxB))x(((xAxB)x∈B)((x∈Ax∈B)xB))x((xAxB)x∈B)x((xAx∈B)(xBx∈B))x((xAx∈B)x(x∈Ax∈B)ABx(x∈Ax∈B)x(xBxA)x(x∈~Bx∈~A)~B~A

由A∪B=B得A(A∪B)=AB又A(A∪B)=A，所以A=AB类似由A∩B=A,可以推出A∪B=B

所以A∪B=BA∩B=A从而证得A∪B=B,A∩B=A,AB,~B~A彼此等值。12023/3/2222:157例3

令全集E为计算机学院的学生的集合,C表示计算机专业学生的集合,M表示学习了离散数学的学生的集合,D表示学习了数据结构课学生的集合,F表示一年级的学生的集合.用集合的关系式表达下面句子.“学习了离散数学和数据结构课的学生,一定是计算机专业的非一年级的学生”.

解.(M∩D)(C∩~F)2023/3/2222:158例4某年级共有200名学生，喜欢打篮球的有134人，喜欢打排球的有101人，喜欢打乒乓球的有90人，篮球、乒乓球都不喜欢的23人，篮球、排球都喜欢的54人，喜欢排球但不喜欢乒乓球的有48人，三样都喜欢的有12人。求：1。三样运动都不喜欢的有多少人？2。只喜欢一项运动的人分别有多少？2023/3/2222:159解：设某年级学生集合为全集E，喜欢打篮球的学生集合为A，喜欢打排球的学生集合为B，喜欢打乒乓球的学生集合为C。则有：|E|=200|A|=134|B|=101|C|=90|A∩B|=54|~A∩~C|=23|B∩~C|=48|A∩B∩C|=12|A∩C|=-|A∪C|+|A|+|C|=|A|+|C|-(|E|-|~(A∪C)|)=134+90-(200-23)=47|B∩C|=|B|-|B∩~C|=101-48=53所以，1.|~(A∪B∪C)|=|E|-(|A|+|B|+|C|-|A∩B|-|B∩C|-|A∩C|+|A∩B∩C|)=200-(134+101+90-54-53-47+12)=172023/3/2222:15102只喜欢一种运动的人数分别为：|A∩~B∩~C|，|~A∩B∩~C|，|~A∩~B∩C||A∩~B∩~C|=|(A-A∩B)∩~C|=|(A-A∩B)|-|(A-A∩B)∩C||~A∩B∩~C|=|(B-A∩B)∩~C|=|(B-A∩B)|-|(B-A∩B)∩C|

|~A∩~B∩C|=|(C-C∩B)∩~A|=|(C-C∩B)|-|(C-C∩B)∩A|2023/3/2222:1511例5证明：P(A)∪P(B)P(A∪B)并说明等号成立的条件。证明：因为P(A)表示由A的所有子集构成的集合.

P(A)={X|XA}

，P(B)={X|XB}

P(A∪B)={X|XA∪B}X∈P(A)∪P(B)

X∈P(A)∨X∈P(B)XA∨XB任取x∈X，则有x∈A∨x∈B，所以x∈A∪B，所以有XA∪B，即X∈P(A∪B)，因此P(A)∪P(B)P(A∪B)。但是，不一定有P(A∪B)P(A)∪P(B)（因为XA∪B不一定有XA∨XB）2023/3/2222:1512如：A={1,2}B={2,3}A∪B={1,2,3}P(A)={Φ,{1},{2},{1,2}}P(B)={Φ,{2},{3},{3,2}}P(A∪B)={Φ,{1},{2},{3},{1,2},{2,3}{3,1},{1,2,3}}{1,2,3}∈P(A∪B),但是{1,2,3}不是P(A)∪P(B)中的元素。当XA∪BXA∨XB时，等号成立。即A∪B=A，或

A∪B=B。2023/3/2222:1513例6有14位学生参加考试,9位同学数学得了优;5位同学物理得了优;4位同学化学得了优;其中物理和数学都得优的同学有4人;数学和化学都得优的同学有3人;物理和化学都得优的同学有3人;三门都得优的同学有2人;问没有得到优的有多少人?恰有两门得优的同学有多少人?解.令A、B、C分别表示数学、物理、化学得优同学集合.全集为E.于是有|E|=14|A|=9|B|=5|C|=4|A∩B|=4|A∩C|=3|B∩C|=3|A∩B∩C|=2|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|B∩C|-|B∩C|+|A∩B∩C|=9+5+4-4-3-3+2=10于是得到优的人数是10人.∴没有得到优的人数是:14-10=4人恰有两门得优的人数:(|A∩B|-|A∩B∩C|)+(|A∩C|-|A∩B∩C|)+(|B∩C|-|A∩B∩C|)=4-2+3-2+3-2=42023/3/2222:1514例7设A、B、C、D为集合，证明下列各式。1.A-B=A-A∩B2.A((B∪C)∩D)=((AB)∪(AC))∩(AD)证明：1.因为A-B=A∩~BA-A∩B=A∩~(A∩B)=A∩(~A∪~B)=(A∩~A)∪(A∩~B)=A∩~B所以A-B=A-A∩B。2.任取<x,y>A((B∪C)∩D)

xAy((B∪C)∩D

xA(yB∪C)yDxA(yB∨yC)yD(xAyB)∨(xAyC)(xAyD)<x,y>((AB)∪(AC))∩(AD)所以A((B∪C)∩D)=((AB)∪(AC))∩(AD)2023/3/2222:1515例81、若A-B=B,问A和B是什么集合？说明理由。解答：A和B必为空集。这是因为：A-B=A∩~B~B,而已知A-B=B，故有B~B，B中一定不包含任何元素。否则若存在x∈B，x∈~B同时成立，这是不可能的。由B是空集可知A也是空集。2023/3/2222:1516例9求证：若(A-B)∪(B-A)=C,则A(B-C)∪(C-B)的充要条件是A∩B∩C=Φ.证明：(充分性)：即已知A∩B∩C=Φ，证明A(B-C)∪(C-B)。B∪C=B∪(A-B)∪(B-A)=B∪(A∩~B)∪(~

A∩B)=B∪A∪(~

A∩B)=B∪A。故AB∪C。而A∩B∩C=Φ，因此对于任意的x∈A，有x∈B∪C∧xB∩C，即x∈(B∪C)-(B∩C).又(B-C)∪(C-B)=(B∩~C)∪(~B∩C)=(B∪C)-(B∩C),所以x∈(B-C)∪(C-B)，即A(B-C)∪(C-B)2023/3/2222:1517(必要性)：即已知A(B-C)∪(C-B)，证明A∩B∩C=Φ。因为A(B-C)∪(C-B)，所以A(B∪C)-(B∩C)，所以对于任意的x∈A，有x∈B∪C∧xB∩C，因此A∩B∩C=Φ。证毕。2023/3/2222:1518

二元关系1.关系的概念,表示方法.2.二元关系的性质的定义,熟练掌握性质的判断及证明.3.掌握关系的复合,求逆及闭包运算(计算方法及有关性质)4.掌握等价关系的判断,证明,求等价类和商集.5.掌握相容关系的概念

6.偏序关系的判断,会画Hasse图,会求一个子集的极小(大)元,最小(大)元,上界与下界,最小上界及最大下界.

注意本章证明题的证明过程的思路2023/3/2222:1519一.关系的概念,表示方法,三个特殊关系.1.集合的笛卡尔积

A×B={<x,y>|x∈A∧y∈B}|A|=m,|B|=n|A×B|=mn

设A={0,1}，B={a,b}，求AB。

AB={<0,a>,<0,b>,<1,a>,<1,b>}2.二元关系的概念定义1:设A、Ｂ是集合,如果ＲA×B,则称R是一个从A到

B的二元关系。如果RA×A,则称R是A上的二元关系.

如果|A|=m|B|=n则可以确定2mn个从A到B的不同关系.定义2:任何序偶的集合，都称之为一个二元关系。2023/3/2222:15203.关系的表示方法1).枚举法:

即将关系中所有序偶一一列举出，写在大括号内.

如:R={<1,2>,<3,4>,<4,2>}2).(描述法)谓词公式法：即用谓词公式描述序偶中元素的关系。例如

R={<x,y>|x<y}3).有向图法：1。2。

3。

4。。。。ABabcR1:1。。4。。23R2:2023/3/2222:15214).矩阵表示法：(实际上就是图论中的邻接矩阵)

设A={a1,a2,,am}，B={b1,b2,,bn}是个有限集，

RA×B，定义R的m×n阶矩阵

MR=(rij)m×n，其中4.三个特殊关系1).空关系Φ：

ΦA×B，(或ΦA×A)，即无任何元素的关系.

它的关系图中只有结点,无任何边；它的矩阵中全是0。2).完全关系(全域关系)

（完全图）

A×B(或A×A)本身是一个从A到B(或A上)的完全关系.

即含有全部序偶的关系。它的矩阵中全是1。1若<ai,bj>∈R0若<ai,bj>∈R(1≤i≤m,1≤j≤n)rij=2023/3/2222:15223).恒等关系IA（单位矩阵）

IAA×A,且IA={<x,x>|x∈A}称之为A上的恒等关系。例如A={1,2,3},则IA={<1,1>,<2,2>,<3,3>}A上的Φ、完全关系A×A及IA的关系图及矩阵如下：MIA=1000100013×31。2。。31。2。。31111111113×31。。2。30000000003×3MΦ=MA×A=ΦA×AIA2023/3/2222:1523二.关系的性质:

熟练掌握性质的判断及证明.1.自反性定义:设R是集合A中的关系，如果对于任意x∈A都有

<x,x>∈R(xRx)，则称R是A中自反关系。即

R是A中自反的x(xAxRx)2.反自反性定义：设R是集合A中的关系，如果对于任意的x∈A都有

<x,x>R，则称R为A中的反自反关系。即

R是A中反自反的x(xA<x,x>R)3.对称性定义:R是集合A中关系,若对任何x,y∈A,如果有xRy,必有

yRx,则称R为A中的对称关系。

R是A上对称的xy((xAyAxRy)yRx)2023/3/2222:15244.反对称性定义:设R为集合A中关系,若对任何x,y∈A,如果有xRy,和

yRx,就有x=y,则称R为A中反对称关系。R是A上反对称的xy((xAyAxRyyRx)

x=y)xy((xAyAxy<x,y>∈R)<y,x>R)5.传递性定义:R是A中关系，对任何x,y,z∈A,如果有xRy,和yRz,就

有xRz,则称R为A中传递关系。即R在A上传递xyz((xAyAzAxRyyRz)xRz)2023/3/2222:1525自反性反自反性对称性传递性反对称性每个结点都有环主对角线全是1每个结点都无环主对角线全是0不同结点间如果有边,则有方向相反的两条边.是以对角线为对称的矩阵不同结点间,最多有一条边.以主对角线为对称的位置不会同时为1如果有边<a,b>,<b,c>,则也有边<a,c>.或者使得前件为假.如果aij=1,且ajk=1,则aik=1从关系的矩阵从关系的有向图

性质判定:2023/3/2222:1526

判断下面关系的性质：Y-有N-无1。2。。1。2。。1。2。。1。2。。3333R2R1R3R4自反性反自反性对称性反对称性传递性R1YNNYYR2NYNYNR3YNYNYR4YNYYY2023/3/2222:1527R5NYNYYR6NNYNNR7NNNNNR8NYYYY1。2。。1。2。。1。2。。1。2。。3333R5R6R7R8自反性反自反性对称性反对称性传递性2023/3/2222:1528三.掌握关系复合,求逆及闭包运算(计算方法及性质)(一)关系的复合

1.定义:设RX×Y，SY×Z，则RSX×Z。

RS={<x,z>|xXzZy(yY<x,y>R<y,z>S)}2.计算方法(俗称过河拆桥法)

⑴枚举法R={<a,b>,<b,c>,<c,a>}S={<a,b>,<b,c>,<b,b>,<c,a>}RS={<a,c>,<a,b>,<b,a>,<c,b>}

⑵有向图a。b。

c。X。。。YabcRS。。。Zabc。。。Zabca。b。

c。X2023/3/2222:1529⑶矩阵3.性质1).满足结合律:RA×BSB×CTC×D则

R(ST)=(RS)T2).RA×BSB×CTB×C⑴R(S∪T)=(RS)∪(RT)⑵R(S∩T)(RS)∩(RT)3).R是从A到B的关系，则

RIB=IAR=R

推论:RA×A,则RIA=IAR=R(IA是运算的幺元)4).关系的乘幂R0=IA，RA×A,

RmRn=Rm+n(Rm)n=Rmn(m,n为非负整数)MRS=010001100010011100=0111000102023/3/2222:1530(二).逆关系1.定义

:设RX×Y，R的逆关系RC={<y,x>|<x,y>R}<y,x>∈RC<x,y>R2.计算方法

1).R={<1,2>,<2,3>,<3,4>,<4,5>}RC={<2,1>,<3,2>,<4,3>,<5,4>}2).RC的有向图:是将R的有向图的所有边的方向颠倒.3).RC的矩阵MRC=(MR)T即为R矩阵的转置3.性质令R、S都是从X到Y的关系，则

1).(RC)C=R

2).(R∪S)C=RC∪SC

。

3).(R∩S)C=RC∩SC

。

4).(R-S)C=RC-SC

。2023/3/2222:15315).RSRC

SC

。

6).(~R)C=~RC7).令R是从X到Y的关系，S是Y到Z的关系，则

(RS)C=SC

RC

。

8).R是A上关系，则⑴R是对称的，当且仅当RC=R⑵R是反对称的，当且仅当R∩RCIA。

2023/3/2222:1532(三).闭包运算1.定义：给定A中关系R,若A上另一个关系R’，满足：⑴RR’；⑵R’是自反的(对称的、传递的)；⑶R’是“最小的”，即对于任何A上自反(对称、传递)的关系R”,如果RR”,就有R’R”。则称R’是R的自反(对称、传递)闭包。记作r(R)、(s(R)、t(R))(reflexive、

symmetric、transitive)2.计算方法给定A中关系R

r(R)=R∪IA。

s(R)=R∪RC。

t(R)=R∪R2∪R3∪...

。2023/3/2222:1533闭包的运算有三种形式:如A={a,b,c}RA×AR={<a,b>,<b,c>,<c,a>}

a).集合形式.

r(R)=R∪IA={<a,b>,<b,c>,<c,a>}{<a,a>,<b,b>,<c,c>}={<a,b>,<b,c>,<c,a>,<a,a>,<b,b>,<c,c>}s(R)=R∪RC={<a,b>,<b,c>,<c,a>}{<b,a>,<c,b>,<a,c>}={<a,b>,<b,c>,<c,a>,<b,a>,<c,b>,<a,c>}R2={<a,c>,<b,a>,<c,b>}R3={<a,a>,<b,b>,<c,c>}

t(R)=R∪R2∪R3={<a,b>,<b,c>,<c,a>}∪{<a,c>,<b,a>,<c,b>}∪{<a,a>,<b,b>,<c,c>}={<a,b>,<b,c>,<c,a>,<a,c>,<b,a>,<c,b>.<a,a>,<b,b>,<c,c>}2023/3/2222:1534b)有向图形式.bacR3RbacbacIA∪=r(R)bac∪RbacbR2act(R)bac∪=c∪Rbac=bRCas(R)bac2023/3/2222:1535c)矩阵形式.Mr(R)=MR∨MIA=010001100100010001∨=111110011Ms(R)=MR∨MRC010001100001100010∨=011101110Mt(R)=M∨M∨M=010001100001100010∨=111111111R2R3R∨1000100012023/3/2222:15363.性质1).R是A上关系，则⑴R是自反的，当且仅当r(R)=R.⑵R是对称的，当且仅当s(R)=R.⑶R是传递的，当且仅当t(R)=R.2).R是A上关系，则⑴R是自反的，则s(R)和t(R)也自反。⑵R是对称的，则r(R)和t(R)也对称。⑶R是传递的，则r(R)也传递。*3).设R是A上关系，则

⑴

sr(R)=rs(R)

⑵tr(R)=rt(R)

⑶st(R)ts(R)2023/3/2222:1537四.等价关系

掌握等价关系的判断,证明,求等价类和商集.

1.了解集合的划分与覆盖的概念.

例X={1,2,3},A1={{1,2,3}},A2={{1},{2},{3}},A3={{1,2},{3}},A4={{1,2},{2,3}},A5={{1},{3}}A1,

A2,A3,A4是覆盖。A1,

A2,A3也是划分。

2.等价关系定义:设R是A上关系,若R是自反的、对称的和传递的，则称R是A中的等价关系。

3.等价关系R的有向图:可能由若干个独立子图构成的，每个独立子图都是完全关系图。1。2。。3R11。2。。3R21。2。。R32023/3/2222:15384.等价类：1).定义:R是A上的等价关系,a∈A,由a确定的集合[a]R[a]R={x|x∈A∧<a,x>∈R}

称集合[a]R为由a形成的R等价类。2).由等价关系图求等价类：R图中每个独立子图上的结点构成一个等价类。不同的等价类个数=独立子图个数。3).等价类性质

R是A上等价关系，任意a,b,c∈A

⑴同一个等价类中的元素，彼此有等价关系R。⑵

[a]R∩[b]R=Φ，当且仅当<a,b>R。⑶

[a]R=[b]R当且仅当<a,b>∈R。⑷A中任何元素a,a必属于且仅属于一个等价类。⑸任意两个等价类

[a]R,[b]R,

要么[a]R=[b]R，要么[a]R∩[b]R=Φ

。⑹R的所有等价类构成的集合是A的一个划分。2023/3/2222:15395.商集:定义：R是A上等价关系，由R的所有等价类构成的集合称之为A关于R的商集。记作A/R。即

A/R={[a]R|a∈A}6.商集应用.1)按照集合的等势关系(是等价关系)“~”对集合族S进行划分，得到商集S/~，进而得到基数类的概念。S={0,Φ,1,{1},{a},…,2,{0,1},{a,b},…,3,{0,1,2},…,N,I,…R,..}S/~={[0],[1],[2],[3],…,[N],[R],...}2).无向图结点之间的连通关系是个等价关系.

令G=<V,E>是无向图,R是V上连通关系,即

R={<u,v>|u和v是连通的}例.给定图G如右上图所示:V/R={{a,b,g},{c,d,e,f},{h}}无元素1个元素2个元素3个元素可数集不可数集...ghabefcd2023/3/2222:15403).图的同构关系≌是个等价关系.

令上述图构成的集合A={a,b,c,d,e,f,g,h,i,j,},求商集A/≌.A/≌={{a,h},{b,i},{c,e},{d},{f},{g,j}}abcdefghij2023/3/2222:1541例1.R和S都是A上等价关系,下面哪个是A上等价关系?证明或举反例说明.

a)R∪Sb)R∩Sc)~R(即A×A-R)d)R-Se)R2f)r(R-S)g)Rc解.a)c)d)f)不是.请看反例:R。a。cb。。a。cb。。a。cb。SR∪S。a。cb。~R。a。cb。R’。a。cb。R’-S。a。cb。r(R’-S)2023/3/2222:1542b)R∩S是等价关系.证明：1.证明R∩S的自反性方法1

用自反定义证：任取x∈A,(证出<x,x>∈R∩S)因R和S都自反，所以有<x,x>∈R，<x,x>∈S，于是有<x,x>∈R∩S，所以R∩S也自反。方法2

用恒等关系IA证：(证出IA

R)因R和S都自反，所以IA

R，IA

S，所以IA

R∩S所以R∩S也自反。方法3

用自反闭包证：

(证出r(R∩S)=R∩S,即(R∩S)∪IA=R∩S)因R和S都自反，所以r(R)=R,r(S)=S,r(R∩S)=(R∩S)∪IA=(R∪IA)∩(S∪IA)=r(R)∩r(S)=R∩S所以R∩S也自反。2023/3/2222:15432.证明R∩S的对称性：方法1

用对称定义证：任取x,y∈A,设<x,y>∈R∩S,(证出<y,x>∈R∩S.)则<x,y>∈R，<x,y>∈S，因为R和S对称，所以有<y,x>∈R，<y,x>∈S，于是<y,x>∈R∩S。∴R∩S对称。方法2

用求逆关系证：(证出(R∩S)c=R∩S.)因为R和S对称，所以有Rc=R，Sc=S，而(R∩S)c=Rc∩Sc=R∩S

，∴R∩S对称。方法3

用对称闭包证：(证出s(R∩S)=R∩S,)因为R和S对称，所以s(R)=R,s(S)=Ss(R∩S)=(R∩S)∪(R∩S)c=(R∩S)∪(Rc∩Sc)=(R∪Rc)∩(R∪Sc)∩(S∪Sc)∩(S∪Rc)

=(s(R)∩(R∪Sc))∩(s(S)∩(S∪Rc))=(R∩(R∪Sc))∩(S∩(S∪Rc))=R∩S(吸收律)∴R∩S对称。2023/3/2222:15443.证明R∩S的传递性：方法1

用传递定义证：任取x,y,z∈A,

设<x,y>∈R∩S,<y,z>∈R∩S,(证出<x,z>∈R∩S)<x,y>∈R∩S∧<y,z>∈R∩S<x,y>∈R∧<x,y>∈S∧<y,z>∈R∧<y,z>∈S(<x,y>∈R∧<y,z>∈R)∧(<x,y>∈S∧<y,z>∈S)

<x,z>∈R∧<x,z>∈S

（因为R、S传递）<x,z>∈R∩S所以R∩S传递。所以R∩S是A上等价关系.2023/3/2222:1545e)证明.R2是等价关系.方法1.如果R自反和传递,则R2=R,所以R2也是等价关系.方法2.①证R2自反:任取a∈A,因为R自反,所以<a,a>∈R,根据关系的复合得,<a,a>∈RR,即<a,a>∈R2,所以R2自反。②证R2对称:(R2)c=(Rc)2=R2(由R对称得Rc=R)∴R2对称③证R2传递:任取a,b,c∈A,设有<a,b>∈R2,<b,c>∈R2,

根据关系的复合得,(d∈A∧<a,d>∈R∧<d,b>∈R)∧(e∈A∧<b,e>∈R∧<e,c>∈R),由于R传递,所以有<a,b>∈R,<b,c>∈R,∴<a,c>∈R2所以R2传递。最后得R2是等价关系。2023/3/2222:1546g).

R是A上等价关系,则Rc也是A上等价关系.证明1)

证Rc自反。因为任取x∈A,因R自反，所以<x,x>∈R,∴<x,x>∈Rc2)R对称，证Rc也对称。因为R对称，所以Rc=R∴

Rc也对称。3)R传递，证Rc也传递。方法1.任取x,y,z∈A,且有<x,y>∈Rc,<y,z>∈Rc,于是<y,x>∈R,<z,y>∈R，因R传递，∴<z,x>∈R,于是有<x,z>∈Rc，∴Rc传递。方法2.t(Rc)=Rc∪(Rc)2∪(Rc)3∪…=Rc∪(R2)c∪(R3)c∪…=(R∪R2∪R3∪…)c=(t(R))c=Rc所以Rc传递。所以Rc是A上等价关系.2023/3/2222:1547例2.设X={1,2,3}Y={1,2},在X的幂集P(X)上定义二元关系R如下:对于任何A,B∈P(X),ARB当且仅当AY=BY1.画出关系R的有向图.2.R是等价关系吗?如果是,请写出商集P(X)/R.如果不是请说明原因解.1.关系R的有向图.2.从R有向图看出R有自反,对称和传递性,故是等价关系

P(X)/R={{,{1},{2},{1,2}},{{3},{1,3},{2,3},{1,2,3}}}{1,3}{1,2,3}{2,3}{3}{1}{2}{1,2}2023/3/2222:1548五.偏序关系判断,会画Hasse图,会求一个子集的极小(大)元,最小(大)元,上界与下界,最小上界及最大下界.1.定义：R是A上自反、反对称和传递的关系，则称R是A上的偏序关系。并称<A,R>是偏序集。2.x与y是可比较的：<A,≤>是偏序集，x,y∈A，如果要么x≤y,要么y≤x,则称x与y是可比较的。3.定义：<A,≤>是偏序集，任何x,y∈A，如果x与y都是可比较的，则称≤是全序关系(线序、链)。4.偏序集Hasse图的画法：令<A,≤>是偏序集，

1).用“”表示A中元素。

2).如果x≤y,且x≠y，则结点y要画在结点x的上方。

3).如果x≤y,且y盖住x，x与y之间连一直线。

4).从最下层结点(全是射出的边与之相连，逐层向上画，直到最上层结点(全是射入的边与之相连)。2023/3/2222:1549例如2。。1。。642。。1。。84１。２。４。６。１。２。４。８。2023/3/2222:15505.重要元素y是B的极小元y(y∈B∧x(x∈B∧x≠y∧x≤y))

(在B中没有比y更小的元素了，y就是极小元)y是B的极大元y(y∈B∧x(x∈B∧x≠y∧y≤x))

(在B中没有比y更大的元素了，y就是极大元)y是B的最小元y(y∈B∧x(x∈By≤x))

(最小元y是B中元素，该元素比B中所有元素都小)y是B的最大元y(y∈B∧x(x∈Bx≤y))(最大元y是B中元素，该元素比B中所有元素都大)y是B的上界y(y∈A∧x(x∈Bx≤y))

(上界y是A中元素，该元素比B中所有元素都大)y是B的下界y(y∈A∧x(x∈By≤x))

(下界y是A中元素，该元素比B中所有元素都小)2023/3/2222:1551y是B的上界，并且对B的所有上界x,都有y≤x,则称y是B的最小上界(上确界)，记作LUBB=y。

(即y是上界中最小的。如果B有上确界，则是唯一的)y是B的下界，并且对B的所有下界x,都有x≤y,则称y是B的最大下界(下确界)，记作GLBB=y。

(即y是下界中最大的。如果B有上确界，则是唯一的)例如B={2,3,6}B的极小元:2,3极大元:6

最小元:无最大元:6

下界:1上界:6,12,18

下确界:1上确界:6１。6。18。12。2。。32023/3/2222:1552

例1设R是集合A上的二元关系，定义S={(a,b)|c∈A,(a,c)∈R,(c,b)∈R}.证明：若R是A上的等价关系，则S也是A上的等价关系，且S=R。【分析】本题考察集合的等价关系的定义及判别，要证明S是A上的等价关系，可通过证明S满足自反性、对称性、传递性三个条件。题中所给的关系S是通过等价关系R来定义的，因而在证明过程中要利用R的性质来证明。在证明R和S相等时，因为R和S是两个集合，故可使用最常用的方法，即证明它们相互包含。2023/3/2222:1553【解答】先证明S也是A上的等价关系：(1)S是自反的：因为R是自反的，对任意a∈A，有<a,a>∈R,根据S的定义，有<a,a>∈S，所以S是自反的。(2)S是对称的：若<a,b>∈S,则存在c∈A，使<a,c>∈R<c,b>∈R，因为R是对称的，故有<c,a>∈R,(b,c)∈R,根据S的定义，有<b,a>∈S,所以S是对称的。(3)S是传递的：如果<a,b>∈S，<b,c>∈S，则存在d∈A使<a,d>∈R且<d,b>∈R。因为R是传递的，所以<a,b>∈R。且存在e∈A,使(b,e)∈R且(e,c)∈R。因为R是传递的，所以<b,c>∈R。故S是传递的。综上所述，S也是A上的等价关系。2023/3/2222:1554

下面证明S=R。对于任意的<a,b>∈S，由S的定义知存在c∈A，使<a,c>∈R<c,b>∈R，因为R是A上的等价关系，故R有传递性，因此<a,b>∈R，即SR。对于任意的<a,b>∈R，因为R是A上的等价关系，故R有自反性，即<a,a>∈R,此时存在a∈A，满足<a,a>∈R且<a,b>∈R。由S的定义知，<a,b>∈S,即RS。综上所述，S=R。2023/3/2222:1555

例2用集合A上的关系定义一个新关系T满足：任意a,b∈A，有aTbaRb∧bRa。关系R至少要具备哪些性质，才能使得T是等价关系，并证明你的结论。[解答]要使T是等价关系，T必须满足自反性、对称性和传递性三个条件。（1）自反性：若T有自反性，则对于任意a∈A，有aTaaRa∧aRa成立，即R有自反性。（2）对称性：任意a,b∈A，有aTbaRb∧bRabRa∧aRbaTb因此T具有对称性。由此可见，T的对称性是由其定义决定的，与R的性质无关。2023/3/2222:1556

（3）传递性：若T有传递性，则对于任意的a,b,c∈A,aTb∧bTcaTc,而aTbaRb∧bRa，bTcbRc∧cRb，所以有aRb∧bRa∧bRc∧cRb应能推出aRc∧cRa,这是为使T有传递性，R应具有的性质。综上所述，若要T为等价关系，R至少要有的性质是：i)自反性；ii)若aRb∧bRa∧bRc∧cRb，则有aRc∧cRa。下面证明这两条也是充分条件。设R是自反的，由（1）可见R自反与T自反是等价的，故T也是自反的。设ii)成立，则对任意的aTb,bTc由T的定义有(aRb∧bRa)∧(bRc∧cRb),可得aRc∧cRa，即aTc,T是传递的。2023/3/2222:1557例31)、设A、B、C、D为非空集合，则

ABCD的充分必要条件是

2)、设A={a,b,c},R是A上的二元关系，且给定R={<a,b>,<b,c>,<c,a>},则R的对称闭包S(R)=AC∧BD.={<a,b>,<b,c>,<c,a>,<b,a>,<c,b>,<a,c>}2023/3/2222:1558例4设有偏序集<A,≤>如下图，又设A的子集B={3,6}，试求B的最大元，最小元，极大元，极小元，上界，下界，上确界，下确界。26182793解：B的最大元为：6；最小元为3；极大元为6，极小元为3；上界为6，18，下界为3，上确界6，下确界3。2023/3/2222:1559例5设有偏序集<A,≤>如下图，又设A的子集B={c,d,e}，试求B的上界，下界，上确界，下确界。解：B的上界为e,f，下界为a,b，上确界e，下确界无。becfda2023/3/2222:1560例6设A为集合，B=P(A)-{Φ}-{A},且B≠Φ，求偏序集<B,>的极大元、极小元、最大元和最小元。[解答]若A=Φ,或A中只有一个元素，则B=Φ，不满足题目要求；所以A中至少含有2个元素。x∈A，设x为A中的单个元素，则不存在y∈A，使得y≠x且{y}{x},所以对A中的单个元素x,{x}为极小元。因为A的幂集P(A)中含元素最多的为A,其元素个数为|A|，而B中元素最多包含|A|-1个元素，x∈A，A-{x}∈P(A),A-{x}中含有|A|-1个元素，且对于y∈A，y≠x，A-{y}中也含有|A|-1个元素，且A-{x}和A-{y}互不包含，所以A中任意单个元素，A-{x}为极大元。2023/3/2222:1561

又x,y∈A,y≠x,{x},{y}均为极小元，且{x}和{y}互不包含，所以不存在一个包含于其他所有集合的集合，因而不存在最小元。同理，不存在最大元。从题中可以看出，对于抽象的集合也可求其最大、最小元与极大、极小元，解此类题目可先举例考虑，然后再将其推广到一般情况。2023/3/2222:1562例7设R1和R2是集合S中的等价关系，C1和C2是它们产生的划分，证明：当且仅当C1的每个划分块都包含在C2的某个划分块中，R1R2。证明：令划分C1={A1,A2,…Ak,…},C2={B1,B2,…Be,…}.(充分性)先证明若R1R2，则C1的每个划分块都包含在C2的某个划分块中。对于Ak∈C1，即Ak为C1中的任一划分块，所以Ak≠Φ。在Ak中任意取一个元素a∈Ak，因为C2是S的划分且a∈S，所以存在Be∈C2，使得a∈Be。对于任意的b∈Ak，有aR1b，又因为R1R2，所以aR2b。根据划分的定义得b∈Be，所以AkBe。由Ak的任意性知，C1的每一个划分块都包含在C2的某个划分块中。2023/3/2222:1563(必要性)对于任意的aR1b，有a，b在C1的同一块划分中，根据题设，必有a,b在C2的同一块划分中，故aR2b成立，所以R1R2。2023/3/2222:1564练习：2023/3/2222:1565练习：2.设A={1,2,3,4,5,6,7,8,9,10,11,12}，R是A上的整除关系，B={2,4,6}．（1）写出关系R的表示式；

（2）画出关系R的哈斯图；

（3）求出集合B的最大元、最小元．（1）R=I{<1,2>,<1,3>,…,<1,12>,<2,4>,<2,6>,<2,8>,<2,10>,<2,12>,<3,6>,<3,9>,<3,12>,<4,8>,<4,12>,<5,10>,<6,12>}

（2）关系R的哈斯图如图四：

（3）集合B没有最大元，最小元是：22023/3/2222:1566

函数1.函数的定义.2.函数的类型,会判断,会证明.3.会计算函数的复合(左复合),求逆函数.知道有关性质.2023/3/2222:1567一.概念1.定义：X与Y集合，f是从X到Y的关系，如果任何x∈X，都存在唯一y∈Y，使得<x,y>∈f,则称f是从X到Y的函数，(变换、映射)，记作f:XY.

如果f:XX是函数,也称f是X上的函数.

要求会判断某些给定关系是否是函数.2.函数相等:f:AB,g:CD,f=gA=CB=Df(x)=g(x)3.从X到Y函数的集合YX：

YX={f|f:XY}YX：它是由所有的从X到Y函数构成的集合.4.特殊函数

1).常值函数：函数f:XY，如果y0∈Y,使得对x∈X,有f(x)=y0,即ranf={y0},称f是常值函数。

2).恒等函数：恒等关系IX是X到X函数，即IX:XX,称之为恒等函数。显然对于x∈X，有IX(x)=x。2023/3/2222:15685.函数的类型,会判断,会证明.1).满射的：f:XY是函数，如果Rf=Y,则称f是满射的。证明方法:任取y∈Y,看是否能够找到对应的自变量

x∈X,使得y=f(x).2).映内的：f:XY是函数，如果RfY则称f是映内的。3).单射的：f:XY是函数，如果对于任何x1,x2∈X,如果x1≠x2

有f(x1)≠f(x2),(或者若f(x1)=f(x2),则x1=x2),则称f是单射的，也称f是入射的，也称f是一对一的。证明的方法:如定义中所说.4).双射的：f:XY是函数，如果f既是满射的，又是

单射的，则称f是双射的，也称f是一一对应的。双射是个重要概念,我们用双射定义了如下概念:集合的等势关系“~”;代数系统的同构关系“≌”图的同构关系“≌”2023/3/2222:1569练习题:R是实数集合，给定R上的五个关系如下:R1={<x,y>|x=y2}R2={<x,y>|y=x+6}R3={<x,y>|y=(x-1)-1}R4={<x,y>|y=2x}R5={<x,y>|x2+y2=4}上述五个关系中，哪些是从R到R的函数。如果是函数，说明它是属于什么类型的（指满射、单射、双射）。如果不是函数，说明理由。解.R1不是从R到R的函数,x是负数时无定义,另外当x>0时,有两个y值与之对应.R2是从R到R的函数,是双射的.R3不是从R到R的函数,因为x=1时,无定义.R4是从R到R的函数,是单射的,不是满射的.R5不是从R到R的函数,因为|x|>2时,无定义.|x|<2时对应的函数值不唯一.xy2023/3/2222:1570二.会计算函数复合(左复合),求逆函数.知道有关性质.1.函数的复合1)定义:f:XY,g:YZ是函数,则定义

g

f={<x,z>|xXzZy(yY<x,y>f<y,z>g)}

则称g

f

为f与g的复合函数(左复合).

注意:这里把g写在f的左边了.所以叫左复合.g

f:XZ,即g

f

是X到Z的函数.这样写是为了照顾数学习惯:g

f(x)=g(f(x))x∈X2).复合函数的计算计算方法同复合关系的计算.

但要注意是左复合.3).函数复合的性质

(1).满足可结合性。f:XY,g:YZ,h:ZW是函数,则(hg)f=h(gf)2023/3/2222:1571(2).定理5-2.2f:XY,g:YZ是两个函数,则

a).如果f和g是满射的，则g

f

也是满射的；

b).如果f和g是单射的，则g

f

也是单射的；

c).如果f和g是双射的，则g

f

也是双射的。(3).⑴如果gf是满射的，则g是满射的；⑵如果gf是单射的，则f是单射的；

⑶如果gf是双射的，则f是单射的和g是满射的。(4).