北大离散数学05公开课一等奖省优质课大赛获奖课件

第5讲二元关系基本概念

北京大学内容提要1.有序对与卡氏积2.二元关系3.二元关系基本运算/10/101《集合论与图论》第5讲有序对与卡氏积有序对(有序二元组)有序三元组,有序n元组卡氏积卡氏积性质/10/102《集合论与图论》第5讲有序对(orderedpair)有序对:<a,b>={{a},{a,b}}

其中,a是第一元素,b是第二元素.<a,b>也记作(a,b)定理1:<a,b>=<c,d>a=cb=d推论:ab<a,b><b,a>/10/103《集合论与图论》第5讲有序对(引理1)引理1:{x,a}={x,b}a=b证实:()显然.()分两种情况.(1)x=a.{x,a}={x,b}{a,a}={a,b}{a}={a,b}a=b.(2)xa.a{x,a}={x,b}a=b.#/10/104《集合论与图论》第5讲有序对(引理2)引理2:若A=B,则(1)∪A=∪B(2)

∩A=∩B证实:(1)x,x∪A

z(zA

xz)z(zB

xz)

x∪B.(2)x,x∩A

z(zA

xz)z(zB

xz)

x∩B.#/10/105《集合论与图论》第5讲有序对(定理1)定理1:<a,b>=<c,d>a=cb=d证实:()显然.()由引理2,<a,b>=<c,d>{{a},{a,b}}={{c},{c,d}}∪{{a},{a,b}}=∪{{c},{c,d}}{a,b}={c,d}.又{{a},{a,b}}={{c},{c,d}}∩{{a},{a,b}}=∩{{c},{c,d}}{a}={c}a=c.再由引理1,得b=d.#/10/106《集合论与图论》第5讲有序对(推论)推论:ab<a,b><b,a>证实:(反证)<a,b>=<b,a>a=b,与ab矛盾.#/10/107《集合论与图论》第5讲有序三元组(orderedtriple)有序三元组:<a,b,c>=<<a,b>,c>有序n(2)元组:<a1,a2,…,an>=<<a1,a2,…,an-1>,an>定理2:<a1,a2,…,an>=<b1,b2,…,bn>ai

=bi,i=1,2,…,n.#/10/108《集合论与图论》第5讲卡氏积(Cartesianproduct)卡氏积:AB={<x,y>|xAyB}.例:A={,a},B={1,2,3}.AB={<,1>,<,2>,<,3>,<a,1>,<a,2>,<a,3>}.BA={<1,>,<1,a>,<2,>,<2,a>,<3,>,<3,a>}.AA={<,>,<,a>,<a,>,<a,a>}.BB={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>}.#/10/109《集合论与图论》第5讲卡氏积性质非交换:AB

BA(除非A=BA=B=)非结合:(AB)CA(BC)(除非A=B=C=)分配律:A(BC)=(AB)(AC)等其它:AB=A=B=等/10/1010《集合论与图论》第5讲卡氏积非交换性非交换:AB

BA(除非A=BA=B=)反例:A={1},B={2}.AB={<1,2>},BA={<2,1>}./10/1011《集合论与图论》第5讲卡氏积非结合性非结合:(AB)CA(BC)(除非A=B=C=)反例:A=B=C={1}.(AB)C={<<1,1>,1>},A(BC)={<1,<1,1>>}./10/1012《集合论与图论》第5讲卡氏积分配律1.A(BC)=(AB)(AC)2.A(BC)=(AB)(AC)3.(BC)A=(BA)(CA)4.(BC)A=(BA)(CA)

/10/1013《集合论与图论》第5讲卡氏积分配律(证实1)A(BC)=(AB)(AC).证实:<x,y>,<x,y>A(BC)xAy(BC)xA(yByC)(xAyB)(xAyC)(<x,y>AB)(<x,y>AC)<x,y>(AB)(AC)

A(BC)=(AB)(AC).#/10/1014《集合论与图论》第5讲例题1例题1:设A,B,C,D是任意集合,(1)AB=A=B=(2)若A,则ABACBC.(3)ACBDABCD,而且当(A=B=)(AB)时,ABCD

ACBD./10/1015《集合论与图论》第5讲卡氏积图示ABCA(BC)=(AB)(AC)ACBDABCDBACD/10/1016《集合论与图论》第5讲例题1(证实(2))(2)若A,则ABACBC.证实:()若B=,则BC.设B,由A,设xA.y,yB<x,y>AB<x,y>ACxAyCyC.BC/10/1017《集合论与图论》第5讲例题1(证实(2),续)(2)若A,则ABACBC.证实(续):()若B=,则AB=AC.设B.<x,y>,<x,y>AB

xAyBxAyC<x,y>ACABAC.#讨论:在()中不需要条件A./10/1018《集合论与图论》第5讲

n维卡氏积n维卡氏积:A1A2…An

={<x1,x2,…,xn>|x1A1x2A2…xnAn}An=AA…A|Ai|=ni,i=1,2,…,n|A1A2…An|=n1n2…nn.n维卡氏积性质与2维卡氏积类似./10/1019《集合论与图论》第5讲n维卡氏积(性质)非交换:ABCBCA(要求A,B,C均非空,且互不相等)非结合:(非2元运算)分配律:比如AB(CD)=(ABC)(ABD)其它:如ABC=A=B=C=./10/1020《集合论与图论》第5讲二元关系n元关系二元关系A到B二元关系A上二元关系一些特殊关系/10/1021《集合论与图论》第5讲n元关系(n-aryrelation)n元关系:是集合,其元素全是有序n元组.例1:F1={<a,b,c,d>,<1,2,3,4>,<物理,化学,生物,数学>},

F1是4元关系.例2:F2={<a,b,c>,<,,>,<大李,小李,老李>}

F2是3元关系.#/10/1022《集合论与图论》第5讲二元关系(binaryrelation)2元关系(简称关系):是集合,其元素全是有序对.例3:R1={<1,2>,<,>,<a,b>}R1是2元关系.例4:R2={<1,2>,<3,4>,<白菜,小猫>}R2是2元关系.例5:A={<a,b>,<1,2,3>,a,,1}

A不是关系.#/10/1023《集合论与图论》第5讲二元关系记号设F是二元关系,则<x,y>Fx与y含有F关系xFy对比:xFy

(中缀(infix)记号)

F(x,y)(前缀(prefix)记号)

<x,y>F(后缀(suffix)记号)比如:2<15<(2,15)<2,15><./10/1024《集合论与图论》第5讲A到B二元关系A到B二元关系:是AB任意子集.R是A到B二元关系RABRP(AB)若|A|=m,|B|=n,则|AB|=mn,故|P(AB)|=2mn即A到B不一样二元关系共有2mn个/10/1025《集合论与图论》第5讲A到B二元关系(举例)例:设A={a1,a2},B={b},则A到B二元关系共有4个:R1=,R2={<a1,b>},R3={<a2,b>},

R4={<a1,b>,<a2,b>}.

B到A二元关系也有4个:R5=,R6={<b,a1>},R7={<b,a2>},

R8={<b,a1>,<b,a2>}.#/10/1026《集合论与图论》第5讲A上二元关系A上二元关系:是AA任意子集R是A上二元关系RAARP(AA)若|A|=m,则|AA|=m2,故|P(AA)|=即A上不一样二元关系共有个/10/1027《集合论与图论》第5讲A上二元关系(例1)例1:设A={a1,a2},则A上二元关系共有16个:R1=,R2={<a1,a1>},R3={<a1,a2>},R4={<a2,a1>},R5={<a2,a2>},/10/1028《集合论与图论》第5讲A上二元关系(例1,续1)R6={<a1,a1>,<a1,a2>},R7={<a1,a1>,<a2,a1>},

R8={<a1,a1>,<a2,a2>},R9={<a1,a2>,<a2,a1>},R10={<a1,a2>,<a2,a2>},R11={<a2,a1>,<a2,a2>},/10/1029《集合论与图论》第5讲A上二元关系(例1,续2)R12={<a1,a1>,<a1,a2>,<a2,a1>}R13={<a1,a1>,<a1,a2>,<a2,a2>}R14={<a1,a1>,<a2,a1>,<a2,a2>}R15={<a1,a2>,<a2,a1>,<a2,a2>}

R16={<a1,a1>,<a1,a2>,<a2,a1>,<a2,a2>}.#/10/1030《集合论与图论》第5讲A上二元关系(例2)例2:设B={b},则B上二元关系共有2个:R1=,R2={<b,b>}.#例3:设C={a,b,c},则C上2元关系共有29=512个!#/10/1031《集合论与图论》第5讲一些特殊关系空关系恒等关系全域关系整除关系小于等于关系,…包含关系,真包含关系/10/1032《集合论与图论》第5讲特殊关系设A是任意集合,则能够定义A上:空关系:恒等关系:IA

={<x,x>|xA}全域关系:EA

=AA={<x,y>|xAyA}/10/1033《集合论与图论》第5讲特殊关系(续)设AZ,则能够定义A上:整除关系:DA={<x,y>|xAyAx|y}例:A={1,2,3,4,5,6},则DA={<1,1>,<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<2,2>,<2,4>,<2,6>,<3,3>,<3,6>,<4,4>,<5,5>,<6,6>}.#/10/1034《集合论与图论》第5讲特殊关系(续)设AR,则能够定义A上:小于等于(lessthanorequalto)关系:LEA={<x,y>|xAyAxy}小于(lessthan)关系,LA={<x,y>|xAyAx<y}大于等于(greaterthanorequalto)关系大于(greatthan)关系,…/10/1035《集合论与图论》第5讲特殊关系(续)设A为任意集合,则能够定义P(A)上:包含关系:A

={<x,y>|xAyAxy}真包含关系:A

={<x,y>|xAyAxy}/10/1036《集合论与图论》第5讲与二元关系相关概念定义域,值域,域逆,合成(复合)限制,象单根,单值/10/1037《集合论与图论》第5讲定义域,值域,域对任意集合R,能够定义:定义域(domain)

:domR={x|y(xRy)}值域(range):ranR={y|x(xRy)}域(field):fldR=domRranR/10/1038《集合论与图论》第5讲定义域,值域,域图示ABdom

R

ran

R

/10/1039《集合论与图论》第5讲定义域,值域,域(举例)例:R1={a,b},R2={a,b,<c,d>,<e,f>},R3={<1,2>,<3,4>,<5,6>}.

当a,b不是有序对时,R1和R2不是关系.domR1=,ranR1=,fldR1=domR2={c,e},ranR2={d,f},fldR2={c,d,e,f}domR3={1,3,5},ranR3={2,4,6},fldR3={1,2,3,4,5,6}.#/10/1040《集合论与图论》第5讲逆,合成(复合)对任意集合F,G,能够定义:逆(inverse)

:F-1={<x,y>|yFx}合成(复合)(composite):F○G={<x,y>|z(xGz

zFy)}xzyGF/10/1041《集合论与图论》第5讲关于合成次序合成(右合成):F○G={<x,y>|z(xFzzGy)}逆序合成(左合成):F○G={<x,y>|z(xGzzFy)}/10/1042《集合论与图论》第5讲限制,象对任意集合F,A,能够定义:限制(restriction):FA={<x,y>|xFyxA}象(image):F[A]=ran(FA)F[A]

=

{y|x(xAxRy)}/10/1043《集合论与图论》第5讲单根,单值对任意集合F,能够定义:单根(singlerooted):F是单根y(yranF!x(xdomFxFy))(yranF)(!xdomF)(xFy)单值(singlevalued):F是单值x(xdomF!y(yranFxFy))(xdomF)(!yranF)(xFy)/10/1044《集合论与图论》第5讲例题2例2:设A={a,b,c,d},B={a,b,<c,d>},R={<a,b>,<c,d>},F={<a,b>,<a,{a}>,<{a},{a,{a}}>},G={<b,e>,<d,c>}.求:(1)A-1,B-1,R-1.(2)B○R-1,G○B,G○R,R○G.(3)F{a},F{{a}},F{a,{a}},F-1{{a}}.(4)F[{a}],F[{a,{a}}],F-1[{a}],F-1[{{a}}]./10/1045《集合论与图论》第5讲例题2(解(1))已知:A={a,b,c,d},B={a,b,<c,d>},R={<a,b>,<c,d>},求:(1)A-1,B-1,R-1.解:(1)A-1=,B-1={<d,c>},R-1={<b,a>,<d,c>}./10/1046《集合论与图论》第5讲例题2(解(2))已知:B={a,b,<c,d>},R={<a,b>,<c,d>},G={<b,e>,<d,c>}.求:(2)B○R-1,G○B,G○R,R○G.解:(2)B○R-1={<d,d>},G○B={<c,c>},G○R={<a,e>,<c,c>},R○G={<d,d>}./10/1047《集合论与图论》第5讲例题2(解(3))已知:F={<a,b>,<a,{a}>,<{a},{a,{a}}>},求:(3)F{a},F{{a}},F{a,{a}},F-1{{a}}.解:(3)F{a}={<a,b>,<a,{a}>},F{{a}}={<{a},{a,{a}}>},F{a,{a}}=F,F-1{{a}}={<{a},a>}./10/1048《集合论与图论》第5讲例题2(解(4))已知:F={<a,b>,<a,{a}>,<{a},{a,{a}}>},求:(4)F[{a}],F[{a,{a}}],F-1[{a}],F-1[{{a}}].解:(4)F[{a}]={b,{a}},F[{a,{a}}]={b,{a},{a,{a}}

},F-1[{a}]=,F-1[{{a}}]={a}.#/10/1049《集合论与图论》第5讲例题3设R={<x,y>|x,yZy=|x|

},A={0,1,2},B={0,-1,-2}求:(1)R[AB]和R[A]R[B];(2)R[A]-R[B]和R[A-B].解:(1)R[AB]=R[{0}]={0},R[A]R[B]={0,1,2}{0,1,2}={0,1,2};(2)R[A]-R[B]={0,1,2}-{0,1,2}=,

R[A-B]=R[{1,2}]={1,2}.#/10/1050《集合论与图论》第5讲定理3定理3:设F,G是任意集合,则(1)dom(FG)=domFdomG(2)ran(FG)=ranFranG(3)dom(FG)domFdomG(4)ran(FG)ranFranG(5)domF-domGdom(F-G)(6)ranF-ranGran(F-G)/10/1051《集合论与图论》第5讲定理3(证实(1))(1)dom(FG)=domFdomG证实:(1)x,xdom(FG)y(x(FG)y)y(xFyxGy)y(xFy)y(xGy)xdomFxdomGxdomFdomGdom(FG)=domFdomG./10/1052《集合论与图论》第5讲定理3(证实(4))(4)ran(FG)ranFranG证实:(4)x,xran(FG)y(y(FG)x)y(yFxyGx)y(yFx)

y(yGx)xranFxranGxranFranGran(FG)ranFranG./10/1053《集合论与图论》第5讲定理3(证实(5))(5)domF-domGdom(F-G)证实:(5)x,xdomF-domGxdomFxdomG

y(xFy)y(xGy)y(xFy)y(xGy)y(x(F-G)y)xdom(F-G)domF-domGdom(F-G).#/10/1054《集合论与图论》第5讲定理4定理4:设F是任意集合,则(1)domF-1=ranF;(2)ranF-1=domF;(3)(F-1)-1

F,当F是关系时,等号成立./10/1055《集合论与图论》第5讲定理4(证实(1))(1)domF-1=ranF;证实:(1)x,xdo