左孝凌離散數(shù)學3.4序偶與笛卡爾積-3.5關(guān)系及其表

離散數(shù)學(DiscreteMathematics)2024/1/312024/1/313-4序偶與笛卡爾積一、序偶二、笛卡爾積。1.定義兩個元素x,y按給定順序組成的2元組稱為一個序偶〔有序?qū)Α常涀?lt;x，y>:其中x是它的第一元素，y是它的第二元素。序偶主要用來表示兩個個體之間的聯(lián)系例：平面直角坐標系中的一個點的坐標就構(gòu)成為一個有序序偶，我們可用<x，y>表示。，一、序偶(有序2元組)2.序偶的性質(zhì)如果x≠y,那么<x,y>≠<y,x>兩個序偶相等，<x，y>=<u，v>，當且僅當x=u且y=v。注：序偶是有次序的。例：<1，3>和<3，1>是表示平面上兩個不同的點，這與集合不同，{1，3}和{3，1}是兩個相等的集合。序偶中的兩個元素可以相等例：<x,x>代表一個序偶，而在集合中{x，x}與{x}相同。序偶的概念可以擴展到三元組的情況一、序偶(有序2元組)3.有序３元組:<<x，y>，z>=<x，y，z>4.有序n元組：

<<x1,x2,…,xn-1>,xn>=<x1,x2,…,xn-1,xn><x1，x2，…，xn-1，xn>=<y1，y2，…，yn-1，yn>的充要條件是xi=yi，i=1，2，…，n。注N元組的第一個分量應(yīng)該是n-1元組<<x1,x2>,x3>=<x1,x2,x3>≠

<x1,<x2,x3>>序偶中的兩個元素可以來自不同集合

例：<牛，水>表示牛要喝水因此任給兩個集合A和B，我們可以定義一種序偶的集合。一、序偶1.定義：設(shè)A和B是任意兩個集合，由A中元素作第一元素，B中元素作第二元素構(gòu)成序偶，所有這樣序偶的集合稱集合A和B的笛卡爾積或直積。記作AB。即AB={<x，y>|xA∧yB}二、笛卡爾積所以AB表示：來自A的元素與來自B的元素所構(gòu)成的所有序偶的集合例題假設(shè)A={，}，B={1，2，3}，求AB，BA，AA，BB以及(AB)(BA)。解：AB={<,1>,<,2>,<,3>,<,1>,<,2>,<,3>}BA={<1,>,<1,>,<2,>,<2,>,<3,>,<3,>}AA={<,>,<,>,<,>,<,>}BB={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>}(AB)(BA)=注意：1〕假設(shè)A、B均是有限集，|A|=m，|B|=n，那么|AB|=mn2〕一般，AB與BA不相等，即集合的笛卡爾積運算不滿足交換律。反例:A={1},B={2}.AB={<1,2>},BA={<2,1>}.二、笛卡爾積約定：假設(shè)A=或B=，那么AB=，BA=2.n個集合的笛卡爾積：集合A1，A2，…，An，那么特別地，二、笛卡爾積例：設(shè)A，B，C，D是任意集合，判斷以下命題是否正確？(1)ABACBC不正確，當A，BC時，AB=AC=。(2)A-(BC)=(A-B)(A-C)不正確，當A=B={1}，C={2}時，A-(BC)={1}-{<1,2>}={1}，而(A-B)(A-C)={1}=。(3)A=C，B=DAB=CD正確，由定義可以證明，在非空前提下是充要條件。(4)存在集合A使得AAA正確，當A=時，AAA。(5)(AB)C=A(BC)錯。當A=B=C={1}.(AB)C={<<1,1>,1>},A(BC)={<1,<1,1>>}.(除非A=B=C=)二、笛卡爾積設(shè)x∈A,y∈B,所以<x,y>∈

A

BA=C,B=D,所以x∈C,y∈D所以<x,y>∈

CD得證不滿足結(jié)合律3、笛卡爾積的性質(zhì)對于任意集合A，A=，A=。笛卡爾積運算不滿足交換律，當A

，B，AB時A

BBA。笛卡爾積運算不滿足結(jié)合律，即當A，B，C均非空時(AB)CA(BC)。二、笛卡爾積定理1：對任意三個集合A、B、C，有(a)A

(B

C)=(A

B)

(A

C)(b)A

(B

C)=(A

B)

(A

C)(c)(B

C)

A=(B

A)

(C

A)(d)(B

C)

A=(B

A)

(C

A)由以上兩條有：A

(B

C)

(A

B)

(A

C)證明兩個集合相等，可以證明它們互相包含。那么aA，bBC，即aA，bB，且bC，證明：(b)

<a，b>

A

(B

C)，即<a，b>

A

B且<a，b>

A

C，有<a，b>

(A

B)

(A

C)，得A

(B

C)

(A

B)

(A

C)

<a，b>

(A

B)

(A

C)，那么<a，b>AB且<a，b>AC，那么aA，bB，且aA，bC，那么bBC。所以<a，b>

A

(B

C)，所以(A

B)

(A

C)

A

(B

C)二、笛卡爾積定理2：對于任意集合A、B、C，假設(shè)C，那么1)ABACBC2)ABCACB證明：1)設(shè)xA，因C，設(shè)yC，有<x，y>AC，因為AB，xB所以<x，y>BC,所以ACBC設(shè)<x，y>AC，那么xA，yC，又因ACBC，所以<x,y>BC，所以xB,yC，所以AB同樣，定理的第二局部ABCACB可以類似地證明。二、笛卡爾積定理3：對任意四個非空集合，A

B

C

D的充分必要條件是A

C，B

D。證明：充分性。設(shè)A

C，B

D。由定理2，因B

D，A

，所以A

B

A

D。

又A

C，D

，所以A

D

C

D，所以A

B

C

D。必要性。設(shè)A

B

C

D。

x

A，y

B，所以<x，y>

A

B，又因A

B

C

D，所以<x，y>

C

D，所以x

C，y

D，所以A

C，B

D證明定理3用到集合包含的傳遞性：(AB)∧(BC)

(AC)二、笛卡爾積練習105頁(2)-(5)105頁〔2〕設(shè)A={a,b}，構(gòu)成集合

P(A)

A。解

P(A)={,{a},,{a,b}}P(A)

A={<

,a>,<

,b>,<{a},a>,<{a},b>,<,a>,<,b>,<{a,b},a>,<{a,b},b>,}105頁〔3〕以下各式中哪些成立？哪些不成立？為什么？a)(A∪B)(C∪D)=(AC)∪(BD)b)(A-B)(C-D)=(AC)-(BD)c)(AB)(CD)=(AC)(BD)d)(A-B)C=(AC)-(BC)e)(AB)C=(AC)(BC)a)(A∪B)(C∪D)=(AC)∪(BD)不成立。設(shè)A={a}，B=，C={c}，D=pezyblv，那么A∪B={a，b}，C∪D={c，d}，(A∪B)(C∪D)={<a,c>,<a,d>,<b,c>,<b,d>}，AC={<a,c>}，BD={<b,d>}，(AC)∪(BD)={<a,c>,<b,d>}故(AB)(CD)(AC)(BD)b)(A-B)(C-D)=(AC)-(BD)不成立。設(shè)A={a,e}，B={a,b}，C={c,f}，D=apdjwcq，那么A-B={e}，C-D={c，f}，(A-B)(C-D)={<e,c>,<e,f>}，AC={<a,c>,<a,f>,<e,c>,<e,f>}，BD={<a,d>,<b,d>}，(AC)-(BD)={<a,c>,<a,f>,<e,c>,<e,f>}，故(A-B)(C-D)(AC)-(BD)c)(AB)(CD)=(AC)(BD)不成立。設(shè)A={a}，B=，C={c}，D=dpyzcnr，那么AB={a，b}，CD={c，d}，(AB)(CD)={<a,c>,<a,d>,<b,c>,<b,d>}，AC={<a,c>}，BD={<b,d>}，(AC)(BD)={<a,c>,<b,d>}故(AB)(CD)(AC)(BD)d)(A-B)

C=(A

C)-(BC)成立.證明因為(A-B)

C={<x,y>|(x

A-B)∧y

C}所以

<x,y>

(A-B)

C

x(A-B)∧y

C

x

A∧x

B∧y

C

(x

A∧y

C∧x

B)

∪(x

A∧y

C∧y

C))

(x

A∧y

C)∧(x

B∪y

C)

(x

A∧y

C)∧┐(x

B∧y

C)

<x,y>

A

C∧

<x,y>

B

C

<x,y>

[(A

C)-(BC)]e)(AB)C=(AC)(BC)成立。證明(AB)C=[(A-B)(B-A)]C=[(A-B)C][(B-A)]C]=[(AC〕-〔BC〕][(BC〕-〔AC〕]=(AC)(BC)〔定理1c)〕d)(A-B)

C=(A

C)-(BC)105頁〔4〕證明：假設(shè)XX=YY，那么X=Y。提示：證明XY且YX證明：設(shè)任意xX，那么<x,x>XX，因為XX=YY<x,x>YY，xY，所以XY。同理可證YX。故X=Y105頁〔5〕證明：假設(shè)XY=XZ，且X，那么Y=Z。證明：假設(shè)Y=，那么XY=，從而XZ=，即Z=，所以Y=Z。假設(shè)Y，設(shè)任意yY，因為X，令aX，那么<a,y>XY，即<a,y>XZ，故yZ，所以YZ。同理可證ZY。即Y=Z

作業(yè)1.證明：AB=BA(A=)∨(B=)∨(A=B)。離散數(shù)學(DiscreteMathematics)2024/1/3252024/1/325一、二元關(guān)系二、幾個特殊的二元關(guān)系三、關(guān)系的運算四、二元關(guān)系的表示3-5關(guān)系及其表示2024/1/3263-5關(guān)系及其表示關(guān)系舉例：1〕兄弟關(guān)系、長幼關(guān)系、同學關(guān)系、鄰居關(guān)系，上下級關(guān)系等。2〕在數(shù)學上有大于關(guān)系、小于關(guān)系，整除關(guān)系。例如：“3小于5〞，“x大于y〞，“點a在b與c之間〞我們知道序偶可以表達兩個客體、三個客體或n個客體之間的聯(lián)系，因此用序偶表達這個概念是非常自然的。一、二元關(guān)系例如：火車票與座位之間有對號關(guān)系。設(shè)X表示火車票的集合，Y表示座位的集合，那么對于任意的xX和yY，必定有x與y有“對號〞關(guān)系x與y沒有“對號〞關(guān)系。二者之一令R表示“對號〞關(guān)系，那么上述問題可以表示為xRy或xRy。亦可表示為<x,y>R或<x,y>R，因此我們看到對號關(guān)系是一個序偶的集合。.1.二元關(guān)系定義1任一序偶的集合稱為一個二元關(guān)系，簡稱關(guān)系，記作R。如果<a,b>R,可記作：aRb，稱為a與b有關(guān)系R；如果<a,b>R,可記作：aRb，稱為a與b沒有關(guān)系R；這種記法稱為中綴記法。例：R={<a,1>,<b,1>,<b,2>}那么中綴記法為：aR1,bR2,bR2,a一、二元關(guān)系例1:在自然數(shù)中關(guān)系“≥〞可記作R=“≥〞={<x,y>|x,yN且x≥y}。<3,2>R,即3R2，讀作“3大于2〞例2:R1={<1,2>,<,>,<a,b>}R1是二元關(guān)系.例3:A={<a,b>,<1,2,3>,a,1}A不是關(guān)系.說明：1〕我們把關(guān)系R這種無形的聯(lián)系同集合這種“有形〞的實體來描述，在今后的描述和論證帶來方便2〕有序?qū)κ侵v究次序的，如<a,b>R未必有<b,a>R，即a與b有關(guān)系R,b與a有關(guān)系R.例：甲與乙有父與子的關(guān)系，那么乙與甲肯定沒有父與子的關(guān)系。一、二元關(guān)系2.二元關(guān)系定義2AB的任何子集R稱為A到B的二元關(guān)系。R是A到B的二元關(guān)系RABRP(AB)〔冪集〕假設(shè)|A|=m,|B|=n,那么|AB|=mn,故|P(AB)|=2mn，即A到B不同的二元關(guān)系共有2mn個一、二元關(guān)系3.二元關(guān)系定義3A上的二元關(guān)系：AA的任意子集R稱為A上的二元關(guān)系RAARP(AA)。假設(shè)|A|=m,那么|AA|=m2,故|P(AA)|=2m2，即A上不同的二元關(guān)系共有2m2個。

一、二元關(guān)系A(chǔ)到B的二元關(guān)系舉例1:設(shè)A={a1,a2},B=,那么A到B的二元關(guān)系共有22×1=4個:R1=,R2={<a1,b>},R3={<a2,b>},R4={<a1,b>,<a2,b>}B到A的二元關(guān)系也有4個:R5=,R6={<b,a1>},R7={<b,a2>},R8={<b,a1>,<b,a2>}。

一、二元關(guān)系A(chǔ)到B的二元關(guān)系舉例2:設(shè)A={a,b,c,d,e,f}，為學生集合B={β,δ,ω}為課程集合,那么定義如下三個二元關(guān)系:R1={<a,β>,<a,δ>,<c,ω>,<f,β>}可以是一個從A到B的選課關(guān)系；R2={<a,b>,<c,d>,<e,f>}為一個A上的二元關(guān)系，可表示上下鋪關(guān)系；R3={<β,δ>,<δ,ω>}為一個B上的二元關(guān)系，可表示先修課關(guān)系。

一、二元關(guān)系A(chǔ)上的二元關(guān)系(舉例)例1:設(shè)A={a1,a2},那么A上的二元關(guān)系共有16個:

R1=,R2={<a1,a1>},

R3={<a1,a2>},R4={<a2,a1>},

R5={<a2,a2>},R6={<a1,a1>,<a1,a2>},

R7={<a1,a1>,<a2,a1>},

R8={<a1,a1>,<a2,a2>},一、二元關(guān)系R9={<a1,a2>,<a2,a1>},R10={<a1,a2>,<a2,a2>},R11={<a2,a1>,<a2,a2>},R12={<a1,a1>,<a1,a2>,<a2,a1>}，R13={<a1,a1>,<a1,a2>,<a2,a2>}，R14={<a1,a1>,<a2,a1>,<a2,a2>}，R15={<a2,a1>,<a2,a1>,<a2,a2>}，R16={<a1,a1>,<a1,a2>,<a2,a1>,<a2,a2>}一、二元關(guān)系例2:設(shè)B=,

那么B上的二元關(guān)系共有2個:

R1=,R2={<b,b>}.例3:設(shè)C={a,b,c},

那么C上的二元關(guān)系共有29=512個!

一、二元關(guān)系A(chǔ)上的二元關(guān)系(舉例)4.前域和值域定義：關(guān)系R中所有序偶的：第一元素的集合稱為關(guān)系R的前域記作Dom〔R〕第二元素的集合稱為關(guān)系R的前域記作Ran〔R〕如果R是A到B的關(guān)系，那么D(R)A,R(R)BR的前域和值域一起稱作R的域，記作FLDR。一、二元關(guān)系4.前域和值域例:A={a,b,c},B={1,2,3}R1={<a,1>,<b,2>,<a,3>}是A到B上的一個關(guān)系R2={<1,1>,<2,3>,<1,3>}是B上的一個關(guān)系寫出這兩個關(guān)系的前域和值域D(R1)={a,b}A,R(R1)={1,2,3}BD(R2)={1,2}B,R(R2)={1,3}B一、二元關(guān)系4.前域和值域P106例題1

設(shè)A={1，2，3，5}，B={1，2，4}，H={<1，2>，<1，4>，<2，4>，<3，4>}，求domH，ranH，F(xiàn)LDH。解：domH={1，2，3}，ranH={2，4}，F(xiàn)LDH={1，2，3，4}P107例題2設(shè)X={1，2，3，4}，求X上的關(guān)系>及dom>，ran>。解：>={<2，1>，<3，1>，<4，1>，

<3，2>，<4，2>，<4，3>}dom>={2，3，4}，ran>={1，2，3}一、二元關(guān)系二、幾個特殊的二元關(guān)系設(shè)A是任意集合，1.稱為A上的空關(guān)系2.IA={<a,a>|a

A}稱為A上的恒等關(guān)系3.UA=A

A={<x,y>|x

A

y

A}稱為A上的全域關(guān)系例如：設(shè)集合A={0,1,2}UA={<0,0>,<0,1>,<0,2>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<2,2>},是A上的全關(guān)系IA={<0,0>,<1,1>,<2,2>},是A上的恒等關(guān)系|UA|=|AA|=9,|IA|=|A|=3P107例題3假設(shè)H={f，m，s，d}表示一個家庭的父、母、子、女，確定H上的全域關(guān)系和空關(guān)系，另外再確定H上的一個關(guān)系，指出該關(guān)系的值域和前域。解：設(shè)H上的同一家庭成員的關(guān)系為H1，H上的互不相識的關(guān)系為H2，那么H1為全域關(guān)系，為H2空關(guān)系，設(shè)H上的長幼關(guān)系為H3，H3={<f，s>，<f，d>，<m，s>，<m，d>}，domH3={f，m}，ranH3={s，d}二、幾個特殊的二元關(guān)系2024/1/342三、關(guān)系的運算定理：假設(shè)Z和S是從集合X到集合Y的兩個關(guān)系，那么Z和S的并、交、補、差仍是X到Y(jié)的關(guān)系。

證明見書108頁。解：H={<1，1>，<1，3>，<2，2>，<2，4>，

<3，3>，<3，1>，<4，4>，<4，2>}S={<4，1>}H

S={<1，1>，<1，3>，<2，2>，<2，4>，<3，3>，

<3，1>，<4，4>，<4，2>，<4，1>}H

S=

XX={<1，1>，<1，2>，<1，3>，<1，4>，<2，1>，

<2，2>，<2，3>，<2，4>，<3，1>，<3，2>，<3，3>，<3，4>，<4，1>，<4，2>，<4，3>，<4，4>}

H={<1，2>，<1，4>，<2，1>，<2，3>，<3，2>，

<3，4>，<4，1>，<4，3>S-H={<4，1>}P107例題4設(shè)X={1，2，3，4}，假設(shè)H={<x，y>|(x-y)/2是整數(shù)}，S={<x，y>|(x-y)/3是正整數(shù)}，求HS，HS，H，S-H。四、二元關(guān)系的表示1.序偶集合的形式表達為直觀地表示A到B的關(guān)系,我們采用如下的圖示:用大圓圈表示集合A和B,里面的小圓圈表示集合中的元素;假設(shè)a∈A,b∈B,且(a,b)∈ρ,那么在圖示中將表示a和b的小圓圈用直線或弧線連接起來,并加上從結(jié)點a到結(jié)點b方向的箭頭。此例中的ρ1和ρ2的圖示如圖1所示。例設(shè)A＝｛1,2,3,4,5｝,B＝｛a,b,c｝,那么ρ1＝｛(1,a),(1,b),(2,b),(3,a)｝是A到B的關(guān)系,而ρ2＝｛(a,2),(c,4),(c,5)｝是B到A的關(guān)系。其集合表示法如下：圖1上例用圖四、二元關(guān)系的表示2關(guān)系矩陣表示法：設(shè)A={a1,a2,…,an},B={b1,b2,…,bm},RAB,那么R的關(guān)系矩陣MR=(rij)nm,其中rij=1,aiRbj或<ai,bj>R

0,aiRbj或<ai,bj>R例題：例如:A={2,3,4,5,6},A上關(guān)系R1={<a,b>|a是b的倍數(shù)}寫出R1的關(guān)系矩陣解：1={<2,2>,<3,3>,<4,2>,<4,4>,<5,5>,<6,2>,<6,3>,<6,6>}MR1=

10000010001010000010110012345623456說明：1〕空關(guān)系的關(guān)系矩陣MΦ的所有元素為02〕全關(guān)系的關(guān)系矩陣MU的所有元素為13〕恒等關(guān)系的關(guān)系矩陣MI的所有對角元素為1其他均為0，稱為單位矩陣，記作I.108頁例題例題5設(shè)X={x1,x2,x3,x4},Y={y1,y2,y3},R={<x1,y1>,<x1,y3>,<x2,y2>,<x2,y3>,<x3,y1>,<x4,y1>,<x4,y2>}，寫出關(guān)系矩陣MR。例題6設(shè)A={1,2,3,4}，寫出集合A上大于關(guān)系>的關(guān)系矩陣。3.關(guān)系圖表示法：A={a1,a2,…,an}，B={b1,b2,…,bn}，RAB,1〕首先在平面上做結(jié)點a1,a2,…,an，b1,b2,…,bn以“〞表示(稱為頂點)，2〕假設(shè)aiRbj，那么從結(jié)點ai向結(jié)點bj畫有向邊<ai,bj>，箭頭指向bj，假設(shè)aiRbj,那么ai與bj之間沒有線段連接，這樣得到的圖稱為R的關(guān)系圖GR。P109例題7四、二元關(guān)系的表示四、二元關(guān)系的表示3.關(guān)系圖表示法：109頁例題7設(shè)X={x1,x2,x3,x4},Y={y1,y2,y3},R={<x1,y1>,<x1,y3>,<x2,y2