离散数学2市公开课一等奖省赛课获奖

二元关系性质

设R是A上关系,R性质主要有以下5种：自反性反自反性对称性反对称性传递性1第1页

二元关系性质

设Ｒ是Ａ上二元关系，Ｒ=(rij)n*n

(1)自反性:对

ａ∈Ａ，（ａ，ａ）∈Ｒ，则Ｒ称为自反二元关系。显然，rii＝1（ｉ＝１，２，…，n)反自反性:对

ａ∈Ａ，（ａ，ａ）

Ｒ，则Ｒ称为反自反二元关系。即rii＝０（ｉ＝１，２，…，n)2第2页注:

自反和反自反性互斥，但不互补。如：rii中现有0又有1，则R既不是自反也不是反自反。

对应于关系图：自反性：每个顶点都有自回路反自反性：每个顶点都没有自回路3第3页(2）对称性：若ａ≠ｂ,

（ａ，ｂ）∈Ｒ,必有（ｂ，ａ）∈Ｒ，称Ｒ为对称二元关系即Ｒ关系矩阵为对称阵，ａij＝ａji关系图对称性：任二个顶点间或没有边，或有二条方向相正确有向边.（例2.4.2）4第4页反对称性：若ａ≠ｂ，（ａ，ｂ）∈Ｒ,则（ｂ，ａ）

Ｒ，称Ｒ为反对称二元关系。注意:（1）Ｒ相关矩阵是反对称，即rij∧rji＝０（ｉ≠ｊ）（2）若rij＝１，则rji＝０，但rij＝０时，不要求rji＝１，即rij＝rji＝０是允许。(3)对称性与反对称性既不互斥，又不互补关系图：任二个顶点至多只有一条有向边；（例2.4.3）5第5页6第6页注:rij，rjk中有一个不是１,则=1,rik就能够任意。即若(ａ，ｂ),(b，c)中有1个不属于R，则讨论（a,c)是否属于R，无意义。即没有传递条件，就不需讨论传递结果。如:Ａ＝｛a,b,c,d｝，Ｒ＝｛（ａ，ｂ）,（ｃ，ｄ）｝7第7页传递性：若ｘ到ｙ有边，ｙ到ｚ有边，则ｘ到ｚ必有边。8第8页二元关系性质对应于关系图，有：（1）自反性：每个顶点都有自回路，（2）反自反性：每个顶点都没有自回路；（3）对称性：任二个顶点间或没有边，或有二条方向相反有向边；（4）反对称性：任二个顶点至多只有一条有向边；（也即：或没有边，或只有一条有向边）（5）传递性：若ｘ到ｙ有边，ｙ到ｚ有边，则ｘ到ｚ必有边。9第9页10第10页定理2.4.1设R是集合A上二元关系，则(1)Ｒ是自反当且仅当I

Ｒ(2)Ｒ是对称当且仅当Ｒ=Ｒ-1(3)Ｒ是反对称当且仅当Ｒ∩Ｒ-1I(4)Ｒ是传递当且仅当Ｒ２

Ｒ11第11页例：分析集合A={1,2,3}上下述四个关系，判断是否自反、对称、反对称、传递：(1)R={(1,1),(1,2),(1,3),(3,3)};反对称、可传递(2)S={(1,1),(1,2),(2,1),(2,2),(3,3)};自反、对称、可传递(3)T={(1,1),(1,2),(2,2),(2,3)};反对称(4)A×A自反、对称、可传递12第12页判断A上关系性质：

全域关系自反、对称和传递恒等关系自反、对称和传递整除关系自反、反对称和传递小于等于关系自反、反对称和传递幂集上包含关系自反、反对称和传递13第13页举出A={1,2,3}上关系R例子，使其含有下述性质：A)既是对称,又是反对称；B)R既不是对称,又不是反对称；C)R是可传递。解：A)R={(1,1),(2,2),(3,3)}B)R={(1,2),(2,1),(2,3)}C)R={(1,2),(2,1),(1,1),(2,2),(3,3)}14第14页设R1,R2是A上关系,假如经过某种运算后仍保持原来性质,则划√,不然划×。15第15页例：设R1,R2为A上对称关系,证实R1∩R2也是A上对称关系。证实：对于任意<x,y><x,y>

R1∩R2(<x,y>)

R1)

(<x,y>

R2)(<y,x>

R1)(<y,x>

R2)<y,x>R1∩R2所以,R1∩R2在A上是对称。16第16页作业：设X={1,2,3,4},R是X上二元关系，R={(1,1),(1,2),(1,3),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3)}(1)画出R关系图(2)写出R关系矩阵(3)说明R是否是自反、反自反、对称、传递17第17页关系闭包定义：设R是非空集合A上关系,R自反闭包(对称闭包或传递闭包)是A上关系R’,且R’满足以下条件:(1)R’是自反(对称或传递)；(2)R

R’；(3)对A上任何包含R自反关系(对称或传递关系)S都有R’

S.即满足（1）（2）最小者；普通将R自反闭包reflexive记作r(R),对称闭包symmetric记作s(R),传递闭包transitive记t(R)。18第18页教材P43例2.5.1例：设A＝{a,b,c,d},R＝{<a,b>,<b,a>,<b,c>,<c,d>},则R和r(R),s(R),t(R)关系图如图所表示,例P43

19第19页A上关系R闭包定理2.5.2设R为A上二元关系,则(1)r(R)＝I∪R；(2)s(R)＝R∪R-1；(3)t(R)=R∪R2∪R3∪…(4)A是含有n个元素集合t(R)=R∪R2∪R3∪…∪Rn闭包矩阵表示20第20页例:设A＝{a,b,c,d},R＝{<a,b>,<b,a>,<b,c>,<c,d>},则r(R),s(R),t(R)有解:(1)r(R)＝I∪R

={<a,b>,<b,a>,<b,c>,<c,d>}∪{<a,a>,<b,b>,<c,c>,<d,d>}={<a,b>,<b,a>,<b,c>,<c,d>,<a,a>.<b,b>,<c,c>,<d,d>}(2)s(R)＝R∪R-1={<a,b>,<b,a>,<b,c>,<c,d>}∪{<b,a>,<a,b>,<c,b>,<d,c>}={<a,b>,<b,a>,<b,c>,<c,d>,<c,b>,<d,c>}21第21页(3)t(R)=R∪R2∪R3∪R4={<a,b>,<b,a>,<b,c>,<c,d>}∪{<a,a>,<a,c>,<b,b>,<b,d>}∪{<a,b>,<a,d>,<b,a>,<b,c>}∪R4={<a,a>,<a,b>,<a,c>,<a,d>,<b,a>,<b,b>,<b,c>,<b,d>,<c,d>}22第22页闭包矩阵表示Mr＝M＋EMs=M+M’Mt=M+M2+M3+…

其中E表示同阶单位矩阵(主对角线元素为1,其它元素都是0)M‘表示M转置,而+均表示矩阵中对应元素逻辑加（即：或运算）。Mt中幂数不超出集合A中元素数23第23页在上例中3个结果矩阵是:24第24页求传递闭包--Warshall算法设集合基数为n，结构n+1个矩阵W0,W1,W2,…Wn,W0为t(R)关系矩阵,Wn即为t(R)关系矩阵(1)令W0=MR(2)设Wi-1已求出，现求Wi考虑Wi-1第i列，列中为1元素分别位于P1,P2…行，同时考虑第i行，该行中为1元素位于q1,q2…列，则：把Wi中第PS行qt列元素改为1；(3)重复(2)过程，直到求出Wn(4)依据Wn写出t(R)（见书上例2.5.3）25第25页定理2.5.3设A为集合，R1,R2

A×A.若R1

R2则(1)r(R1)

r(R2);(2)s(R1)

s(R2);(3)t(R1)

t(R2)等价关系26第26页作业：1.集合A={1,2…,10}上关系R={(x,y)|x+y=10,x∈A,y∈A},则R性质为().A.自反B.对称C.传递,对称D.反自反，传递2.设A={a,b,c}上关系以下，有传递性有().A.P1={(a,c),(c,a),(a,b),(b,a)}B.P2={(a,c),(c,a)}C.P3={(a,b),(c,c),(b,a),(b,c)}D.P4={(a,a)}27第27页3.设集合A={a,b,c,d}上关系R={(a,b),(a,c),(d,c),(b,c),(c,d)}1)用矩阵运算求出R自反、对称、传递闭包;2)用warshall算法，求出R传递闭包28第28页

§2.6等价关系

[定义1]

等价关系:Ａ上二元关系Ｒ，假如Ｒ是(1）自反(2）对称(3)传递称Ｒ为等价关系。（ａ，ｂ）∈Ｒ，称ａ与ｂ等价，记作ａ～ｂ。29第29页恒等关系、全关系、三角形全等关系以及三角形相同关系均为等价关系。例：设集合A={1,2,3,4},R={(1,1),(1,4),(4,1),(4,4),(2,2),(2,3),(3,2),(3,3)}验证关系R是A上等价关系。30第30页例：设R为计算机系全部学生组成集合上“同住一个宿舍关系”，则R为等价关系。31第31页例2.6.2A＝{1,2,…,8},

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

其中x≡y(mod3)含义就是x-y能够被3整除.R为A上等价关系,它关系图以下所表示：32第32页把模3等价关系推广,设Z为整数集合，取一个固定整数m>0,要求Z元素间一个关系R：(a,b)∈R当且仅当m|(a-b)，这个关系称为模m同余关系.我们用

a≡b(modm)

来表示，同余关系为等价关系。33第33页定义2.6.2若把一个非空集合A分成若干个叫做类子集，使得A每个元素属于而且只属于一个类，那么这些类全体叫做集合A一个分类（或划分）.A1A2A3A434第34页定理2.6.1

集合A上一个等价关系R决定A一个分类.定理2.6.2

集合A上一个分类决定A上一个等价关系.例：设集合A中有4个元素，则A上不一样等价关系个数为（）A.12个B.14个C.15个D.17个35第35页等价类：设R为集合A上等价关系。对任何a

A，称集合[a]R=｛x

x

A,xRa｝为a关于R等价类，a称为[a]R代表元素。等价类[a]R是全部与a含有R关系元素组成集合。设A={1,2,3,4,5}，R是A上“模3同余”关系，求其等价类。解：R={(1,1),(1,4),(4,1),(4,4),(2,2),(2,5),(5,2),(3,3),(5,5)}A上关于R有三个等价类：[1]R={1,4}=[4]R[2]R={2,5}=[5]R[3]R={3}36第36页例：设N是自然数集合，定义N上二元关系R：R={(x,y)|x∈N,y∈N,x+y是偶数}证实R是一个等价关系；37第37页等价类性质定理

设R是非空集合A上等价关系,对任意x,y∈A,下面结论成立.（1）任取x∈A,[x]R≠

；（2）若x,y∈A,或者[x]R=[y]R,或者[x]R

∩[y]R＝

；（3）=A.38第38页商集定义2.6.3设R为集合A上等价关系,以R全部等价类为元素集合叫做A关于R商集,记作A／R,

A／R＝{｜x∈A}.在上例中,A在R下商集是A/R={[1],[2],[3]}={{1,4},{2,5},{3}}

39第39页在整数集合z上关于模m同余等价关系,其等价类是[0]＝{0,±m,±2m,···}={mz|z∈Z}＝[mZ],[1]＝{1,±m＋1,±2m＋1,…}={mz＋1｜z∈Z}＝[mZ＋1][2]＝{2,±m＋2,±2m十2,…}＝{mz＋2｜z∈Z}＝[mZ＋2],······[m－1]＝{m－1,±m+m－1,±2m＋m－1,···｝={mz+m－1｜zZ}=[mZ+m－1].商集为{[0],[1],…,[m－1]｝40第40页例2.6.6设A＝{1,2,3},求出A上全部等价关系.解:

先求A各种划分:只有1个划分块划分

1,含有两个划分块划分

2,

3和

4,含有3个划分块划分

5,请看下列图

41第41页设对应于划分

i等价关系为Ri,i＝1,2,…,5.则有R1＝{(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)}∪IA＝EA；R2＝{(2,3),(3,2)}∪IA；.R3＝{(1,3),(3,1)}∪IA；R4＝{(1,2),(2,1)}∪IA.R5＝{(1,1),(2,2),(3,3)}＝IA；42第42页2.7偏序关系定义2.7.1

设R为集合A上二元关系,假如R是自反、反对称和传递,则称R是A上偏序关系.简称偏序,记作≤.含有偏序关系集合A称为偏序集，记作(A,≤)例：判断以下集合是否是偏序集合:(a)(I,≤),其中≤是整数集合上小于等于关系；(b)(P(A),

),其中是集合上包含关系;(c)(I,|),其中|是整除关系;(d)(I,<),其中<是小于关系.43第43页设(A,≤)为偏序集,对于任意x,y∈A可比:假如x≤y或者y≤x成立,则称x与y是可比.盖住（覆盖关系）:假如x≤y,x≠y,且不存在z

A使得x≤z≤y,则称y盖住x.而且记COVA={(x,y)|x,y∈A;y盖住x}例1:设A={2,3,6,12,24,36},“|”是A上整除关系,COVA=?COVA={(2,6),(3,6),(6,12),(12,24),(12,36)}例2：集合A={a,b,c},偏序集合(P(A),

)中,判断A以下子集是否盖住{a}.（1）

（2）{b,c}（3）{a,b}（4）{a,b,c}44第44页偏序关系图形表示—哈斯图哈斯图画法以下：（1）用小圆圈代表元素。（2）假如x≤y且x≠y，则将代表y小圆圈画在代表x小圆圈之上。（3）假如(x,y)∈COVA,则在x与y之间用直线连接。

练习:A={a,b},画出偏序集合(P(R),

)哈斯图：45第45页画偏序集哈斯图46第46页比如：画A={a,b,c},(P(R),

)哈斯图：47第47页例:设偏序集<A,≤>哈斯图如图所表示,求出集合A偏序≤.解A＝{a,b,c,d,e,f,g,h}.≤＝{(a,c),(a,d),(a,e),(b,c),(b,d),(b,e),(c,e),(d,e),(f,g)}∪IA.ecdabgfh48第48页最大元,最小元,极大元,极小元设(A,≤)为偏序集合,B

A.最大元:假如a∈B,若x∈B,都有x≤a,则称a为集合B最大元；最小元:假如a∈B,若x∈B,都有a≤x,则称a为集合B最小元；极大元：若x∈B，且由a≤x可推出a=x,则称a为B极大元；极小元：若x∈B，且由x≤a可推出x=a,则称a为B极小元；(区分见P57）49第49页上界,下界,上确界,下确界定义2.7.4

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

A,B≠,a∈A(1)若x∈B,都有x≤a,则称a为B上界.(2)若x∈B,都有a≤x,则称a为B下界.(3)若a是B上界，且对B任意上界b都有a≤b，则称a为B最小上界或上确界(4)若a是B下界，且对B任意下界b都有b≤a，则称a为B最大下界或下确界（例2.7.6）50第50页1、对于有穷集，极小元和极大元一定存在，还可能存在多个。2、最小元和最大元不一定存在，假如存在一定唯一。3、最小元一定是极小元；最大元一定是极大元。4、孤立结点既是极小元，也是极大元。最小元、最大元、极小元、极大元含有下述性质：51第51页上界、下界、最大上界与最小上界存在下述性质：1、下界、上界、最大下界、最小上界不一定存在。2、假如下界、上界存在，也不一定是唯一。3、最大下界、最小上界假如存在，则是唯一。4、子集B最小元就是它最大下界，最大元就是它最小上界；反之不对(最大下界、最小上界可能不在集合B中)。52第52页例：整数集上整除关系不是全序关系，但大小关系是全序关系。集合{,{a},{a,b},{a,b,c},{a,b,c,d}}上包含关系就是全序关系自然数集N大小元关系是良序集。53第53页作业：设集合P={x1,x2,x3,x4,x5}上偏序关系如图，找出P最大元、最小元、极大元、极小元。找出{x2,x3,x4}、{x3,x4,x5}和{x1,x2,x3}上界、下界、上确界、下确界。x2x4x3x5x154第54页2.8映射定义2.8.1设A、B是任意两个非空集合，fA×B，若对于A中每个元素a都存在唯一元素b∈B，使（a,b)∈f,则称f为A到B映射(函数).

x为y在f下原象，y为x在f下象.

集合A称为定义域，记作Domf,即Domf=A.而f(A)={f(a)|a∈A}称为f值域，记作Ranf,由定义有RanfB.55第55页

例:设A={x1,x2,x3}，B={y1,y2}，以下关系F1＝{(x1,y1)

,(x2,y1),(x3,y2)}是不是映射？是映射F2＝{(x1,y1),(x1,y2),(x2,y1),(x3,y2)｝呢？不是映射,因为对于x1domF有x1Fy1,x1Fy2同时成立.

56第56页例：判断以下关系中哪些能组成映射（函数）？

(a)f={(x1,x2)|x1,x2∈N，x1+x2<10}；(b)f={(y1,y2)|y1,y2∈R，y22=y1}；(c)f={(y1,y2)|y1,y2∈N，y2=y12+1}定义2.8.2设函数f:A→B，g:C→D，假如A=C，B=D，且对全部x

A和xC，都有f(x)=g(x)，则称函数f等于函数g,记为f=g。57第57页特殊映射

定义2.8.4设映射f:A→B.(1)若ranf＝B,则称f是满射；(2)若对于任何x1,x2∈A,x1≠x2,都有f(x1)≠f(x2),则称f是单射；(3)若f既是满射,又是单射,则称f是双射或一一对应.

例：判断以下函数类型。(a)s:N→N,s(n)=n+1;(b)h:R→R,h(x)=x3+2x2；(c)a,b∈R且a<b，g:[0,1]→[a,b],g(x)=(b-a)x+a.(a)中s是单射非满射;(b)中h是满射非单射;(c)g是双射58第58页比如,函数f:{1,2}→{0},f(1)＝f(2)＝0,那么f是满射,但不是单射.函数f:N→N,f(x)＝2x是单射,但不是满射,因为ranf不含有奇数,即ranfN.而函数f:Z→Z,f(x)=x＋1是双射.59第59页定理设f是从集合X到Y映射.（1）若f是满射，则必有|X|≥|Y|（2）若f是单射，则必有|X|≤|Y|（3）若f是双射，则必有|X|=|Y|（4）若|X|=|Y|，则有f是单射当且仅当f是满射.例：设x和y都是有限集合，且有|x|=m,|y|=n.问x到y上有多少个不一样映射(函数)？

f={(x1,□),(x2,□),…(xm,□)}共有nm种不一样函数.（例2.8.9）60第60页2.9复合映射与逆映射定理设f:A→B；g:B→C为两个映射，则f与g复合映射gf是一个从A到C映射，即(gf)(a)=g(f(a))，a∈A.或用集合表示为gf={(a,c)|存在b∈B使(a,b)∈f,(b,c)∈g}61第61页例：设R为实数集，R到R映射定义为：f(x)=x+2,g(x)=x-2,h(x)=3x,则gf(x)=g(x+2)=(x+2)-2=xfg(x)=f(x-2)=(x-2)+2=xff(x)=f(x+2)=x+2+2=x+4gg(x)=g(x-2)=(x-2)-2=x-4(fgh)(x)=(fg)(h(x))=fg(3x)=f(3x-2)=3x62第62页定理2.9.1:设f:A→B，g:B→C，h:C→D均为映射，则h(gf)=(hg)f.63第63页逆映射定理设f:A→B是双射,则f-1是从B到A双射.称f-1是f逆映射.例：设A={1,2,3},B={a,b,c},f:A→B是映射，f={(1,a),(2,c),(3,b)}.求f-1解：f-1={(a,1),(c,2),(b,3)}.定理设双射函数f:A→B，有逆映射f-1:B→A,则有(1)(f-1)-1=f

(2)f-1◦f＝IA,(3)f◦f-1=IB

64第64页定义2.9.2设g：x→y和h:x→y是映射，若h◦g=Ix，则称h是g左逆映射,g是h右逆映射.见教材P65.定理2.9.2设f:A→B是映射，则(1)f左可逆<=>f是单射.(2)假如f右可逆<=>f是满射.假如f是双射映射，那么f-1◦f

=Ix且f◦f-1=Iy，所以f-1既是f左逆，又是f右逆。（例P652.9.3)65第65页定理2.9.3设f:A→B，g:B→C为映射，则(1)若f,g都是满射，则gf也是满射；(2)若f,g都是单射，则gf也是单射；(3)若f,g都是双射，则gf也是双射.定理2.9.4设f:A→B，g:B→C为映射，则(1)若gf是满射，则g是满射；(2)若gf是单射，则f是单射；(3)若gf都是双射，则f是单射，g是满射.66第66页本章重点集合笛卡尔积与二元关系关系运算和关系性质关系闭包等价关系和偏序关系映射定义和性质及映射复合和逆映射单射,满射,双射67第67页

a

b

c

a

b

cv

a

b

c

a

b

c

1、指出下列图中各关系是不是映射，并说明理由68第68页2,设X={a,b,c,d},Y={1,2,3},f={(a,1),(b,2),(c,3)},则下面命题中唯一正确是（）A.f是从X到Y二元关系，但不是从X到Y函数B.f是从X到Y函数，但不是满射，也不是单射C.f是从X到Y满射，但不是单射D.f是从X到Y双射3.以下各关系中含有自反性和对称性关系是（）A.R1是自然数集合N上关系，且xR1y当且仅当x+y是偶数B.R2是自然数集合N上关系，且xR2y当且仅当x>y或y>xC.R3是自然数集合Q上关系，且xR3y当且仅当y=x+2B.R4是自然数集合N上关系，且xR4y当且仅当x*y=469第69页4.A={1,2,3},B={4,5,6,8},R与S是从A到B关系，且XRY当且仅当gcd(x,y)=1,即x与y最大条约数等于1，xRy当且仅当x+y<8,则R与S交=？5.设<A,R>为偏序集，其中A={1,2,3,4,6,9,24,54},R是A上整除关系.(1)画出<A,R>哈斯图；(2)求A中极大元；(3)令B={4,6,9}，求B上确界和下确界.6.设A={a,b,c},R={<a,b>,<a,c>}(1)给出R关系矩阵；(2)说明含有性质（自反性、反自反性、对称性、反对称性、传递性）70第70页7、考虑以下实数集上函数：f(x)=2x2+1，g(x)=-x+7，h(x)=2x，k(x)=sinx求g◦f，f◦g，f◦f，g◦g，f◦h，f◦k，k◦h解析式。71第71页第3章集合基数72第72页集合基数希尔伯特饭店(“无穷饭店”

)关于无穷大悖论故事

“无穷饭店”是我们银河系中心一家巨大旅馆。它拥有没有穷多个房间，这些房间经过黑洞伸展到更高级时空领域。房间号从1开始，无限制地排下去。旅店每个房间恰能住一位旅客，并已经客满。当日又有一位旅客投宿，店主欣然接纳…希尔伯特（1862～1943)

123……73第73页无穷集概念定义3.1.1设A,B为两个集合，假如存在A到B一个双射函数f：A→B，则称A与B等势(等基数)，

记作A∽B例：对集合A和B，结构一个从A到B双射，以说明A和B含有相同势.(1)A=(0,1),B=(0,2)

f:A→B,使得f(x)=2x,x∈A(2)A=R,B=(0,∞)

f:A→B,使得f(x)=ex,x∈R(3)A=[0,1),B=(1/4,1/2]

f:A→B,使得f(x)=-(1/4)x+1/2,x∈[0,1)74第74页有限集与无限集定义3.1.2设n为一个正整数，若集合A是空集或A与集合{1，2，3,…，n}等势，称集合A为有限集；不然称A为无限集。即：若A为空集或

存在集合{1，2，3,…，n}到A，或A到该集合双射，称集合A为有限集；不然称A为无限集。

自然数集是无限集。

证实正整数集合与自然数集合等势定义函数：f：N→I+，f(x)=x+175第75页等势（等基数）相关概念

定义：集合A与集合B等势(等基数)，当且仅当，A与B之间存在双射（一一对应）。

在此意义下，刻画了两个无穷集合比较“多少”一个方法。