北大離散數(shù)學(xué)05

內(nèi)容提要1.與卡氏積2.二元關(guān)系3.二元關(guān)系的基本運(yùn)算2023/7/111北大離散數(shù)學(xué)05有序?qū)εc卡氏積有序?qū)?有序二元組)有序三元組,有序n元組卡氏積卡氏積性質(zhì)2023/7/112北大離散數(shù)學(xué)05有序?qū)?orderedpair)有序?qū)?<a,b>={{a},{a,b}}

其中,a是第一元素,b是第二元素.<a,b>也記作(a,b)定理1:<a,b>=<c,d>a=cb=d推論:ab<a,b><b,a>2023/7/113北大離散數(shù)學(xué)05有序?qū)?引理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.#2023/7/114北大離散數(shù)學(xué)05有序?qū)?引理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.#2023/7/115北大離散數(shù)學(xué)05有序?qū)?定理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.#2023/7/116北大離散數(shù)學(xué)05有序?qū)?推論)推論:ab<a,b><b,a>證明:(反證)<a,b>=<b,a>a=b,與ab矛盾.#2023/7/117北大離散數(shù)學(xué)05有序三元組(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.#2023/7/118北大離散數(shù)學(xué)05卡氏積(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>}.#2023/7/119北大離散數(shù)學(xué)05卡氏積的性質(zhì)非交換:AB

BA(除非A=BA=B=)非結(jié)合:(AB)CA(BC)(除非A=B=C=)分配律:A(BC)=(AB)(AC)等其他:AB=A=B=等2023/7/1110北大離散數(shù)學(xué)05卡氏積非交換性非交換:AB

BA(除非A=BA=B=)反例:A={1},B={2}.AB={<1,2>},BA={<2,1>}.2023/7/1111北大離散數(shù)學(xué)05卡氏積非結(jié)合性非結(jié)合:(AB)CA(BC)(除非A=B=C=)反例:A=B=C={1}.(AB)C={<<1,1>,1>},A(BC)={<1,<1,1>>}.2023/7/1112北大離散數(shù)學(xué)05卡氏積分配律1.A(BC)=(AB)(AC)2.A(BC)=(AB)(AC)3.(BC)A=(BA)(CA)4.(BC)A=(BA)(CA)

2023/7/1113北大離散數(shù)學(xué)05卡氏積分配律(證明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).#2023/7/1114北大離散數(shù)學(xué)05例題1例題1:設(shè)A,B,C,D是任意集合,(1)AB=A=B=(2)若A,則ABACBC.(3)ACBDABCD,并且當(dāng)(A=B=)(AB)時(shí),ABCD

ACBD.2023/7/1115北大離散數(shù)學(xué)05卡氏積圖示ABCA(BC)=(AB)(AC)ACBDABCDBACD2023/7/1116北大離散數(shù)學(xué)05例題1(證明(2))(2)若A,則ABACBC.證明:()若B=,則BC.設(shè)B,由A,設(shè)xA.y,yB<x,y>AB<x,y>ACxAyCyC.BC2023/7/1117北大離散數(shù)學(xué)05例題1(證明(2),續(xù))(2)若A,則ABACBC.證明(續(xù)):()若B=,則AB=AC.設(shè)B.<x,y>,<x,y>AB

xAyBxAyC<x,y>ACABAC.#討論:在()中不需要條件A.2023/7/1118北大離散數(shù)學(xué)05

n維卡氏積n維卡氏積:A1A2…An

={<x1,x2,…,xn>|x1A1x2A2…xnAn}An=AA…A|Ai|=ni,i=1,2,…,n|A1A2…An|=n1n2…nn.n維卡氏積性質(zhì)與2維卡氏積類(lèi)似.2023/7/1119北大離散數(shù)學(xué)05n維卡氏積(性質(zhì))非交換:ABCBCA(要求A,B,C均非空,且互不相等)非結(jié)合:(非2元運(yùn)算)分配律:例如AB(CD)=(ABC)(ABD)其他:如ABC=A=B=C=.2023/7/1120北大離散數(shù)學(xué)05二元關(guān)系n元關(guān)系二元關(guān)系A(chǔ)到B的二元關(guān)系A(chǔ)上的二元關(guān)系一些特殊關(guān)系2023/7/1121北大離散數(shù)學(xué)05n元關(guān)系(n-aryrelation)n元關(guān)系:是集合,其元素全是有序n元組.例1:F1={<a,b,c,d>,<1,2,3,4>,<物理,化學(xué),生物,數(shù)學(xué)>},

F1是4元關(guān)系.例2:F2={<a,b,c>,<,,>,<大李,小李,老李>}

F2是3元關(guān)系.#2023/7/1122北大離散數(shù)學(xué)05二元關(guān)系(binaryrelation)2元關(guān)系(簡(jiǎn)稱(chēng)關(guān)系):是集合,其元素全是有序?qū)?例3:R1={<1,2>,<,>,<a,b>}R1是2元關(guān)系.例4:R2={<1,2>,<3,4>,<白菜,小貓>}R2是2元關(guān)系.例5:A={<a,b>,<1,2,3>,a,,1}

A不是關(guān)系.#2023/7/1123北大離散數(shù)學(xué)05二元關(guān)系的記號(hào)設(shè)F是二元關(guān)系,則<x,y>Fx與y具有F關(guān)系xFy對(duì)比:xFy

(中綴(infix)記號(hào))

F(x,y)(前綴(prefix)記號(hào))

<x,y>F(后綴(suffix)記號(hào))例如:2<15<(2,15)<2,15><.2023/7/1124北大離散數(shù)學(xué)05A到B的二元關(guān)系A(chǔ)到B的二元關(guān)系:是AB的任意子集.R是A到B的二元關(guān)系RABRP(AB)若|A|=m,|B|=n,則|AB|=mn,故|P(AB)|=2mn即A到B不同的二元關(guān)系共有2mn個(gè)2023/7/1125北大離散數(shù)學(xué)05A到B的二元關(guān)系(舉例)例:設(shè)A={a1,a2},B=,則A到B的二元關(guān)系共有4個(gè):R1=,R2={<a1,b>},R3={<a2,b>},

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

B到A的二元關(guān)系也有4個(gè):R5=,R6={<b,a1>},R7={<b,a2>},

R8={<b,a1>,<b,a2>}.#2023/7/1126北大離散數(shù)學(xué)05A上的二元關(guān)系A(chǔ)上的二元關(guān)系:是AA的任意子集R是A上的二元關(guān)系RAARP(AA)若|A|=m,則|AA|=m2,故|P(AA)|=即A上不同的二元關(guān)系共有個(gè)2023/7/1127北大離散數(shù)學(xué)05A上的二元關(guān)系(例1)例1:設(shè)A={a1,a2},則A上的二元關(guān)系共有16個(gè):R1=,R2={<a1,a1>},R3={<a1,a2>},R4={<a2,a1>},R5={<a2,a2>},2023/7/1128北大離散數(shù)學(xué)05A上的二元關(guān)系(例1,續(xù)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>},2023/7/1129北大離散數(shù)學(xué)05A上的二元關(guān)系(例1,續(xù)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>}.#2023/7/1130北大離散數(shù)學(xué)05A上的二元關(guān)系(例2)例2:設(shè)B=,則B上的二元關(guān)系共有2個(gè):R1=,R2={<b,b>}.#例3:設(shè)C={a,b,c},則C上的2元關(guān)系共有29=512個(gè)!#2023/7/1131北大離散數(shù)學(xué)05一些特殊關(guān)系空關(guān)系恒等關(guān)系全域關(guān)系整除關(guān)系小于等于關(guān)系,…包含關(guān)系,真包含關(guān)系2023/7/1132北大離散數(shù)學(xué)05特殊關(guān)系設(shè)A是任意集合,則可以定義A上的:空關(guān)系:恒等關(guān)系:IA

={<x,x>|xA}全域關(guān)系:EA

=AA={<x,y>|xAyA}2023/7/1133北大離散數(shù)學(xué)05特殊關(guān)系(續(xù))設(shè)AZ,則可以定義A上的:整除關(guān)系: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>}.#2023/7/1134北大離散數(shù)學(xué)05特殊關(guān)系(續(xù))設(shè)AR,則可以定義A上的:小于等于(lessthanorequalto)關(guān)系:LEA={<x,y>|xAyAxy}小于(lessthan)關(guān)系,LA={<x,y>|xAyAx<y}大于等于(greaterthanorequalto)關(guān)系大于(greatthan)關(guān)系,…2023/7/1135北大離散數(shù)學(xué)05特殊關(guān)系(續(xù))設(shè)A為任意集合,則可以定義P(A)上的:包含關(guān)系:A

={<x,y>|xAyAxy}真包含關(guān)系:A

={<x,y>|xAyAxy}2023/7/1136北大離散數(shù)學(xué)05與二元關(guān)系有關(guān)的概念定義域,值域,域逆,合成(復(fù)合)限制,象單根,單值2023/7/1137北大離散數(shù)學(xué)05定義域,值域,域?qū)θ我饧蟁,可以定義:定義域(domain)

:domR={x|y(xRy)}值域(range):ranR={y|x(xRy)}域(field):fldR=domRranR2023/7/1138北大離散數(shù)學(xué)05定義域,值域,域圖示ABdom

R

ran

R

2023/7/1139北大離散數(shù)學(xué)05定義域,值域,域(舉例)例:R1={a,b},R2={a,b,<c,d>,<e,f>},R3={<1,2>,<3,4>,<5,6>}.

當(dāng)a,b不是有序?qū)r(shí),R1和R2不是關(guān)系.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}.#2023/7/1140北大離散數(shù)學(xué)05逆,合成(復(fù)合)對(duì)任意集合F,G,可以定義:逆(inverse)

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

zFy)}xzyGF2023/7/1141北大離散數(shù)學(xué)05關(guān)于合成順序合成(右合成):F○G={<x,y>|z(xFzzGy)}逆序合成(左合成):F○G={<x,y>|z(xGzzFy)}2023/7/1142北大離散數(shù)學(xué)05限制,象對(duì)任意集合F,A,可以定義:限制(restriction):FA={<x,y>|xFyxA}象(image):F[A]=ran(FA)F[A]

=

{y|x(xAxRy)}2023/7/1143北大離散數(shù)學(xué)05單根,單值對(duì)任意集合F,可以定義:單根(singlerooted):F是單根的y(yranF!x(xdomFxFy))(yranF)(!xdomF)(xFy)單值(singlevalued):F是單值的x(xdomF!y(yranFxFy))(xdomF)(!yranF)(xFy)2023/7/1144北大離散數(shù)學(xué)05例題2例2:設(shè)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(yǎng),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}}].2023/7/1145北大離散數(shù)學(xué)05例題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>}.2023/7/1146北大離散數(shù)學(xué)05例題2(解(2))已知:B={a,b,<c,d>},R={<a,b>,<c,d>},G={<b,e>,<d,c>}.求:(2)B○R-1,G○B(yǎng),G○R,R○G.解:(2)B○R-1={<d,d>},G○B(yǎng)={<c,c>},G○R={<a,e>,<c,c>},R○G={<d,d>}.2023/7/1147北大離散數(shù)學(xué)05例題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>}.2023/7/1148北大離散數(shù)學(xué)05例題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}.#2023/7/1149北大離散數(shù)學(xué)05例題3設(shè)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}.#2023/7/1150北大離散數(shù)學(xué)05定理3定理3:設(shè)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)2023/7/1151北大離散數(shù)學(xué)05定理3(證明(1))(1)dom(FG)=domFdomG證明:(1)x,xdom(FG)y(x(FG)y)y(xFyxGy)y(xFy)y(xGy)xdomFxdomGxdomFdomGdom(FG)=domFdomG.2023/7/1152北大離散數(shù)學(xué)05定理3(證明(4))(4)ran(FG)ranFranG證明:(4)x,xran(FG)y(y(FG)x)y(yFxyGx)y(yFx)

y(yGx)xranFxranGxranFranGran(FG)ranFranG.2023/7/1153北大離散數(shù)學(xué)05定理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).#2023/7/1154北大離散數(shù)學(xué)05定理4定理4:設(shè)F是任意集合,則(1)domF-1=ranF;(2)ranF-1=domF;(3)(F-1)-1

F,當(dāng)F是關(guān)系時(shí),等號(hào)成立.2023/7/1155北大離散數(shù)學(xué)05定理4(證明(1))(1)domF-1=ranF;證明:(1)x,xdomF-1y(xF