北大離散數(shù)學(xué)05實用教案

1、2021-11-291有序?qū)εc卡氏積有序?qū)εc卡氏積 有序?qū)?有序二元組) 有序三元組, 有序n元組 卡氏積 卡氏積性質(zhì)(xngzh)第1頁/共61頁第一頁，共62頁。2021-11-292有序?qū)τ行驅(qū)?ordered pair) 有序?qū)? = a, a,b 其中(qzhng), a是第一元素, b是第二元素. 也記作(a,b) 定理1: = a=cb=d 推論: ab 第2頁/共61頁第二頁，共62頁。2021-11-293有序?qū)τ行驅(qū)?引理引理1)引理1: x,a=x,b a=b證明(zhngmng): () 顯然. () 分兩種情況.(1) x=a. x,a=x,b a,a=a,b a=a

2、,b a=b.(2) xa. ax,a=x,b a=b. #第3頁/共61頁第三頁，共62頁。2021-11-294有序?qū)τ行驅(qū)?引理引理2)引理2: 若A=B , 則 (1) A=B (2) A=B證明(zhngmng): (1) x, xA z(zA xz) z(zB xz) xB.(2) x, xA z( zA xz ) z( zB xz ) xB. #第4頁/共61頁第四頁，共62頁。2021-11-295有序?qū)τ行驅(qū)?定理定理(dngl)1) 定理(dngl)1: = a=cb=d 證明: () 顯然. () 由引理2, = a,a,b=c,c,d a,a,b=c,c,da,b=c,

3、d. 又 a,a,b=c,c,d a,a,b=c,c,d a=c a=c. 再由引理1, 得b=d. #第5頁/共61頁第五頁，共62頁。2021-11-296有序?qū)τ行驅(qū)?推論推論(tuln) 推論: ab 證明(zhngmng): (反證) =a=b, 與ab矛盾. #第6頁/共61頁第六頁，共62頁。2021-11-297有序三元組有序三元組(ordered triple) 有序三元組: =,c 有序n(2)元組: =,an 定理(dngl)2: = ai = bi, i =1,2,n. #第7頁/共61頁第七頁，共62頁。2021-11-298卡氏積卡氏積(Cartesian prod

4、uct) 卡氏積: AB=|xAyB. 例: A=,a, B=1,2,3.AB=,.BA=,.AA= , , , .BB= , , . #第8頁/共61頁第八頁，共62頁。2021-11-299卡氏積的性質(zhì)卡氏積的性質(zhì)(xngzh) 非交換: AB BA (除非(chfi) A=B A= B=) 非結(jié)合: (AB)C A(BC) (除非(chfi) A= B= C=) 分配律: A(BC) = (AB)(AC)等 其他: AB= A=B=等第9頁/共61頁第九頁，共62頁。2021-11-2910卡氏積非交換卡氏積非交換(jiohun)性性 非交換( jiohun): AB BA (除非 A=

5、B A= B=) 反例: A=1, B=2. AB=, BA=.第10頁/共61頁第十頁，共62頁。2021-11-2911卡氏積非結(jié)合卡氏積非結(jié)合(jih)性性 非結(jié)合( jih): (AB)C A(BC) (除非 A= B= C=) 反例: A=B=C=1. (AB)C=,1, A(BC)=1,.第11頁/共61頁第十一頁，共62頁。2021-11-2912卡氏積分配律卡氏積分配律 1. A(BC) = (AB)(AC) 2. A(BC) = (AB)(AC) 3. (BC)A = (BA)(CA) 4. (BC)A = (BA)(CA) 第12頁/共61頁第十二頁，共62頁。2021-1

6、1-2913卡氏積分配律卡氏積分配律(證明證明(zhngmng)1) A(BC) = (AB)(AC). 證明(zhngmng): , A(BC) xAy(BC) xA(yByC) (xAyB)(xAyC)(AB)(AC)(AB)(AC) A(BC) = (AB)(AC). #第13頁/共61頁第十三頁，共62頁。2021-11-2914例題例題(lt)1 例題1: 設(shè)A,B,C,D是任意(rny)集合, (1) AB= A= B= (2) 若A, 則 ABAC BC. (3) AC BD ABCD, 并且當(A=B=)(AB)時, ABCD ACBD.第14頁/共61頁第十四頁，共62頁。2

7、021-11-2915卡氏積圖示卡氏積圖示ABCA(BC) = (AB)(AC)ACBDABCDBACD第15頁/共61頁第十五頁，共62頁。2021-11-2916例題例題(lt)1(證明證明(2)(2) 若A, 則ABAC BC.證明(zhngmng): () 若 B=, 則 BC. 設(shè) B, 由A, 設(shè)xA. y, yBAB AC xAyC yC. BC第16頁/共61頁第十六頁，共62頁。2021-11-2917例題例題(lt)1(證明證明(2),續(xù)續(xù))(2) 若A, 則ABACBC.證明(zhngmng)(續(xù)): ()若B=,則AB=AC. 設(shè) B. , AB xAyB xAyC A

8、C ABAC. #討論: 在()中不需要條件 A.第17頁/共61頁第十七頁，共62頁。2021-11-2918 n維卡氏積維卡氏積 n維卡氏積: A1A2An = | x1A1x2A2xnAn An = AAA |Ai|=ni ,i =1,2,n |A1A2An| = n1n2nn. n維卡氏積性質(zhì)(xngzh)與2維卡氏積類似.第18頁/共61頁第十八頁，共62頁。2021-11-2919n維卡氏積維卡氏積(性質(zhì)性質(zhì)(xngzh) 非交換( jiohun): ABCBCA (要求A,B,C均非空,且互不相等) 非結(jié)合: (非2元運算) 分配律: 例如 AB(CD)=(ABC)(ABD) 其

9、他: 如 ABC=A=B=C=.第19頁/共61頁第十九頁，共62頁。2021-11-2920二元關(guān)系二元關(guān)系 n元關(guān)系 二元關(guān)系 A到B的二元關(guān)系 A上的二元關(guān)系 一些(yxi)特殊關(guān)系第20頁/共61頁第二十頁，共62頁。2021-11-2921 n元關(guān)系元關(guān)系(gun x)(n-ary relation) n元關(guān)系: 是集合( jh), 其元素全是有序n元組. 例1: F1=, , F1是4元關(guān)系. 例2: F2=, F2是3元關(guān)系. #第21頁/共61頁第二十一頁，共62頁。2021-11-2922二元關(guān)系二元關(guān)系(binary relation) 2元關(guān)系(gun x)(簡稱關(guān)系(g

10、un x): 是集合,其元素全是有序?qū)? 例3: R1=, R1是2元關(guān)系(gun x). 例4: R2=, R2是2元關(guān)系(gun x). 例5: A=,a,1 A不是關(guān)系(gun x). #第22頁/共61頁第二十二頁，共62頁。2021-11-2923二元關(guān)系的記號二元關(guān)系的記號(j ho) 設(shè)F是二元關(guān)系, 則 F x與y具有F關(guān)系 xFy 對比: xFy (中綴(infix)記號) F(x,y) (前綴(prefix)記號) F (后綴(huzhu)(suffix)記號) 例如: 215 (2,15) .第23頁/共61頁第二十三頁，共62頁。2021-11-2924A到到B的二元關(guān)

11、系的二元關(guān)系 A到B的二元關(guān)系: 是AB的任意(rny)子集. R是A到B的二元關(guān)系 RAB RP(AB) 若|A|=m,|B|=n, 則|AB|=mn, 故 |P(AB)|=2mn 即A到B不同的二元關(guān)系共有2mn個22m第24頁/共61頁第二十四頁，共62頁。2021-11-2925A到到B的二元關(guān)系的二元關(guān)系(舉例舉例(j l) 例: 設(shè) A=a1,a2, B=b, 則A到B的二元關(guān)系共有(n yu)4個: R1=, R2=, R3=, R4=,. B到A的二元關(guān)系也有4個: R5=, R6=, R7=, R8=,. #22m第25頁/共61頁第二十五頁，共62頁。2021-11-292

12、6A上的二元關(guān)系上的二元關(guān)系 A上的二元關(guān)系: 是AA的任意(rny)子集 R是A上的二元關(guān)系 RAA RP(AA) 若|A|=m, 則|AA|=m2, 故 |P(AA)|= 即A上不同的二元關(guān)系共有 個22m22m22m第26頁/共61頁第二十六頁，共62頁。2021-11-2927A上的二元關(guān)系上的二元關(guān)系(例例1) 例1: 設(shè) A=a1,a2, 則A上的二元關(guān)系共有(n yu)16個: R1 = , R2 = , R3 = , R4 = , R5 = ,22m第27頁/共61頁第二十七頁，共62頁。2021-11-2928A上的二元關(guān)系上的二元關(guān)系(例例1,續(xù)續(xù)1) R6 = , , R

13、7 = , , R8 = , , R9 = , , R10 = , , R11 = , , 22m第28頁/共61頁第二十八頁，共62頁。2021-11-2929A上的二元關(guān)系上的二元關(guān)系(例例1,續(xù)續(xù)2) R12 = , R13 = , R14 = , , R15 = , R16 = ,. #22m第29頁/共61頁第二十九頁，共62頁。2021-11-2930A上的二元關(guān)系上的二元關(guān)系(例例2) 例2: 設(shè) B=b, 則B上的二元關(guān)系共有(n yu)2個: R1=, R2=. # 例3: 設(shè) C=a,b,c, 則C上的2元關(guān)系共有(n yu)29=512個! #22m第30頁/共61頁第三

14、十頁，共62頁。2021-11-2931一些一些(yxi)特殊關(guān)系特殊關(guān)系 空關(guān)系 恒等關(guān)系 全域關(guān)系 整除關(guān)系 小于等于(dngy)關(guān)系, 包含關(guān)系, 真包含關(guān)系第31頁/共61頁第三十一頁，共62頁。2021-11-2932特殊特殊(tsh)關(guān)系關(guān)系設(shè)A是任意集合, 則可以(ky)定義A上的: 空關(guān)系: 恒等關(guān)系: IA = | xA 全域關(guān)系: EA = AA = | xA yA第32頁/共61頁第三十二頁，共62頁。2021-11-2933特殊特殊(tsh)關(guān)系關(guān)系(續(xù)續(xù))設(shè)AZ, 則可以(ky)定義A上的:整除關(guān)系: DA = | xA yA x|y 例: A=1,2,3,4,5,6

15、, 則 DA=,. #第33頁/共61頁第三十三頁，共62頁。2021-11-2934特殊特殊(tsh)關(guān)系關(guān)系(續(xù)續(xù))設(shè)AR, 則可以定義(dngy)A上的:小于等于(less than or equal to)關(guān)系:LEA = | xA yA xy 小于(less than)關(guān)系,LA = | xA yA xy 大于等于(greater than or equal to)關(guān)系大于(great than)關(guān)系,第34頁/共61頁第三十四頁，共62頁。2021-11-2935特殊特殊(tsh)關(guān)系關(guān)系(續(xù)續(xù))設(shè)A為任意集合, 則可以(ky)定義P(A)上的:包含關(guān)系: A = | xA yA

16、xy 真包含關(guān)系: A = | xA yA xy 第35頁/共61頁第三十五頁，共62頁。2021-11-2936與二元關(guān)系有關(guān)與二元關(guān)系有關(guān)(yugun)的概念的概念 定義域, 值域, 域 逆, 合成(hchng)(復(fù)合) 限制, 象 單根, 單值第36頁/共61頁第三十六頁，共62頁。2021-11-2937定義域定義域,值域值域,域域?qū)θ我饧蟁, 可以(ky)定義:定義域(domain) : dom R = x | y(xRy) 值域(range):ran R = y | x(xRy) 域(field):fld R = dom R ran R第37頁/共61頁第三十七頁，共62頁。20

17、21-11-2938定義域定義域,值域值域,域圖示域圖示ABdom R ran R 第38頁/共61頁第三十八頁，共62頁。2021-11-2939定義域定義域,值域值域,域域(舉例舉例(j l) 例: R1=a,b, R2=a,b, R3=,. 當a,b不是(b shi)有序?qū)r, R1和R2不是(b shi)關(guān)系. dom R1=, ran R1=, fld R1= dom R2=c,e, ran R2=d,f, fld R2=c,d,e,f dom R3=1,3,5, ran R3=2,4,6, fld R3=1,2,3,4,5,6. #第39頁/共61頁第三十九頁，共62頁。2021-

18、11-2940逆逆, 合成合成(hchng)(復(fù)合復(fù)合)對任意(rny)集合F,G, 可以定義:逆(inverse) : F-1 = | yFx 合成(復(fù)合)(composite):FG = | z( xGz zFy ) xzyGF第40頁/共61頁第四十頁，共62頁。2021-11-2941關(guān)于關(guān)于(guny)合成合成 順序(shnx)合成(右合成): FG = | z( xFz zGy ) 逆序合成(左合成): FG = | z( xGz zFy ) 第41頁/共61頁第四十一頁，共62頁。2021-11-2942限制限制(xinzh),象象對任意集合F,A, 可以定義(dngy):限制(

19、restriction): FA = | xFy xA 象(image): FA = ran(FA)FA = y | x(xA xRy) 第42頁/共61頁第四十二頁，共62頁。2021-11-2943單根單根,單值單值對任意集合F, 可以(ky)定義:單根(single rooted): F是單根的y( yran F !x( xdom F xFy ) ) (yran F)(!xdom F)(xFy)單值(single valued): F是單值的x( xdom F !y( yran F xFy ) ) (xdom F)(!yran F)(xFy)第43頁/共61頁第四十三頁，共62頁。202

20、1-11-2944例題例題(lt)2 例2: 設(shè) A=a,b,c,d, B=a,b, R= , , F= , , , G= , .求: (1) A-1, B-1,R-1. (2) BR-1, GB, GR, RG. (3) Fa, Fa, Fa,a, F-1a. (4) Fa, Fa,a, F-1a, F-1a.第44頁/共61頁第四十四頁，共62頁。2021-11-2945例題例題(lt)2(解解(1) 已知: A=a,b,c,d, B=a,b, R= , , 求: (1) A-1, B-1,R-1.解: (1) A-1 = , B-1 = , R-1 = ,.第45頁/共61頁第四十五頁，

21、共62頁。2021-11-2946例題例題(lt)2(解解(2) 已知: B=a,b, R= , , G= , .求: (2) BR-1, GB, GR, RG.解: (2) BR-1=, GB=, GR=, RG=.第46頁/共61頁第四十六頁，共62頁。2021-11-2947例題例題(lt)2(解解(3) 已知: F= , , ,求: (3) Fa, Fa, Fa,a, F-1a.解: (3) Fa = , , Fa = , Fa,a = F, F-1a= .第47頁/共61頁第四十七頁，共62頁。2021-11-2948例題例題(lt)2(解解(4) 已知: F= , , ,求: (4

22、) Fa, Fa,a, F-1a, F-1a.解: (4) Fa = b, a , Fa,a = b, a, a,a , F-1a = , F-1a = a . #第48頁/共61頁第四十八頁，共62頁。2021-11-2949例題例題(lt)3 設(shè) R= | x,yZ y=|x| , A= 0, 1, 2, B= 0, -1, -2 求: (1) RAB 和 RARB; (2) RA-RB 和 RA-B.解: (1) RAB=R0=0, RARB=0,1,20,1,2=0,1,2; (2) RA-RB=0,1,2-0,1,2= , RA-B=R1,2=1,2. #第49頁/共61頁第四十九頁

23、，共62頁。2021-11-2950定理定理(dngl)3 定理(dngl)3: 設(shè)F,G是任意集合, 則 (1) dom(FG) = domF domG (2) ran(FG) = ranF ranG (3) dom(FG) domF domG (4) ran(FG) ranF ranG (5) domF-domG dom(F-G) (6) ran F-ranG ran(F-G)第50頁/共61頁第五十頁，共62頁。2021-11-2951定理定理(dngl)3(證明證明(1) (1) dom(FG) = domF domG 證明(zhngmng): (1) x, xdom(FG) y( x

24、(FG)y ) y(xFy xGy) y(xFy)y(xGy) xdomF xdomG x domF domG dom(FG) = domF domG. 第51頁/共61頁第五十一頁，共62頁。2021-11-2952定理定理(dngl)3(證明證明(4) (4) ran(FG) ranF ranG 證明(zhngmng): (4) x, xran(FG) y( y(FG)x ) y(yFx yGx) y(yFx) y(yGx) xranF xranG x ranF ranG ran(F G) ranF ranG. 第52頁/共61頁第五十二頁，共62頁。2021-11-2953定理定理(dn

25、gl)3(證明證明(5) (5) domF-domG dom(F-G) 證明(zhngmng): (5) x, xdomF-domG xdomF xdomG y(xFy)y(xGy) y(xFy)y(xGy) y( x(F-G)y ) x dom(F-G) domF-domG dom(F-G). #第53頁/共61頁第五十三頁，共62頁。2021-11-2954定理定理(dngl)4 定理(dngl)4: 設(shè)F是任意集合, 則 (1) domF-1 = ranF; (2) ranF-1 = domF; (3) (F-1)-1 F, 當F是關(guān)系時, 等號成立.第54頁/共61頁第五十四頁，共62

26、頁。2021-11-2955定理定理(dngl)4(證明證明(1) (1) domF-1 = ranF; 證明(zhngmng): (1) x, xdomF-1 y(xF-1 y) y(yFx) xranF domF-1 = ranF. (2)可類似證明(zhngmng).第55頁/共61頁第五十五頁，共62頁。2021-11-2956定理定理(dngl)4(證明證明(3) (3) (F-1)-1 F, 當F是關(guān)系時, 等號成立. 證明(zhngmng): (1) 設(shè)F是關(guān)系, 則 , (F-1)-1 x(F-1)-1y yF-1x xFy. 這時 (F-1)-1 = F. 當F不是關(guān)系時, (F-1)-1F, 例如, 設(shè) F=,a, 則 F-1=, (F-1)-1 = F (F-1)-1 F. #第56