離散數(shù)學(xué)二元關(guān)系與運(yùn)算

離散數(shù)學(xué)二元關(guān)系與運(yùn)算第1頁(yè)，共60頁(yè)，2023年，2月20日，星期一1.二元有序組：由兩個(gè)元素x和y按一定順序排成二元組，記作：<x，y>?！?.1二元關(guān)系的概念如：平面直角坐標(biāo)系中點(diǎn)的坐標(biāo)一、二元關(guān)系的概念第2頁(yè)，共60頁(yè)，2023年，2月20日，星期一二元有序組的性質(zhì)(1)當(dāng)x

y時(shí)，<x，y><y，x>(2)<x，y>=<u，v>，當(dāng)且僅當(dāng)x=u，y=v(1)、(2)說(shuō)明有序組區(qū)別于集合n元有序組：由n個(gè)元素x1，x2，…，xn，按一定順序排成的n元組，記作：(x1，x2，…，xn)。第3頁(yè)，共60頁(yè)，2023年，2月20日，星期一2.一種新的集合運(yùn)算–––積運(yùn)算：設(shè)A、B為兩集合，用A中元素為第一元素，B中元素作為第二元素構(gòu)成的二元有序組的全體叫做A和B的笛卡兒積。記作：A

B符號(hào)化：A

B={<x,y>|xA

yB}第4頁(yè)，共60頁(yè)，2023年，2月20日，星期一例4.1

設(shè)A={a,b}，B={0,1,2}，求AB，BA解：根據(jù)笛卡兒積的定義知A

B={<a,0>,<a,1>,<a,2>,}B

A={<0,a>,<0,b>,}一般地：如果|A|=m，|B|=n，則|AB|=|BA|=m

n<b,0>,<b,1>,<b,2><1,a>,<1,b>,<2,a>,<2,b>第5頁(yè)，共60頁(yè)，2023年，2月20日，星期一積運(yùn)算的性質(zhì)(1)若A，B中有一個(gè)空集，則笛卡兒積是空集，即：

B=A

=(2)當(dāng)AB，且A，B都不是空集時(shí)，有ABBA

(3)當(dāng)A，B，C都不是空集時(shí)，有(AB)CA(BC)因?yàn)?AB)C中的元素<<x,y>,z>，而A(BC)中的元素為<x,<y,z>>。第6頁(yè)，共60頁(yè)，2023年，2月20日，星期一(4)A(B∪C)=(AB)∪(AC)(對(duì)∪的分配律)(B∪C)A=(BA)∪(CA)A(B∩C)=(AB)∩(AC)(B∩C)A=(BA)∩(CA)我們證明：A(B∪C)=(AB)∪(AC)(?)(?)(?)第7頁(yè)，共60頁(yè)，2023年，2月20日，星期一證明思想要證明兩個(gè)集合相等，通常有兩種方法：一是證兩個(gè)集合相互包含；二是利用已有的集合運(yùn)算的性質(zhì)(算律和已證明過(guò)的公式)，仿照代數(shù)恒等式的證明方法，一步步從左(右)邊推出右(左)邊，或從左、右邊分別推出同一個(gè)集合式子。一般說(shuō)來(lái)，最基本的集合相等關(guān)系要用第一種證法，比較復(fù)雜的集合相等關(guān)系用第二種方法更好，但第二種方法的使用取決于我們對(duì)算律和常用公式的熟練程度。第8頁(yè)，共60頁(yè)，2023年，2月20日，星期一證明：用第一種方法對(duì)于任意的<x,y>

A

(B∪C)xAy(B∪C)xA(yByC)(xAyB)(xAyC)<x,y>AB<x,y>AC<x,y>(AB)∪(AC)

A(B∪C)=(AB)∪(AC)第9頁(yè)，共60頁(yè)，2023年，2月20日，星期一例4.2

設(shè)A={1,2}，求P(A)A解：

P(A)A={，{1}，{2}，{1,2}}={<,1>，<,2>，n階笛卡兒積：={(x1,x2,…xn)|x1A1x2A2…xnAn}A1A2…An{1,2}<{1},1>，<{1},2>，<{2},1>，<{2},2>，<{1,2},1>，<{1,2},2>}第10頁(yè)，共60頁(yè)，2023年，2月20日，星期一二元關(guān)系：如果一個(gè)集合的元素都是二元有序組，則這個(gè)集合稱為一個(gè)二元關(guān)系，記作：R

。如果<x,y>R

，記作x

Ry如果<x,y>R

，記作xRy3、二元關(guān)系的數(shù)學(xué)定義第11頁(yè)，共60頁(yè)，2023年，2月20日，星期一從A到B的二元關(guān)系：設(shè)A，B為集合，A

B的任何子集所定義的二元關(guān)系叫做從A到B的二元關(guān)系。若A=B，叫做A上的二元關(guān)系；若|A|＝n，則|AA|＝n2。就是說(shuō)，A上有個(gè)不同的二元關(guān)系，其中包括空關(guān)系、全域關(guān)系UA和恒等關(guān)系IA。AA的所有子集有個(gè)。第12頁(yè)，共60頁(yè)，2023年，2月20日，星期一例4.3

設(shè)A={a,b}，寫出P(A)上的包含關(guān)系R

：解：

P(A)={,{a},{a,b}}R={<,>,<,{a}>,<{,>,<{a,b}>,<{a},{a}>,<{a},{a,b}>,<,>,<,{a,b}>,<{a,b},{a,b}>}第13頁(yè)，共60頁(yè)，2023年，2月20日，星期一A上關(guān)系的表示法1.關(guān)系矩陣：設(shè)A={x1,x2,…,xn)，R是A上的關(guān)系，rij

=1若xi

R

xj0若xi

Rxj(i,j=1,2,…,n)則(rij)nxn=是R的關(guān)系矩陣令：二、二元關(guān)系的表示方法第14頁(yè)，共60頁(yè)，2023年，2月20日，星期一2.關(guān)系圖：以E={<xi,xj>|xiAxjAxiRxj}為有向邊集組成的有向圖G=<V,E>以V=A={x1,x2,…,xn}為頂點(diǎn)集，第15頁(yè)，共60頁(yè)，2023年，2月20日，星期一例4.4

設(shè)A={1,2,3,4}，R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>}是A上的關(guān)系，試寫出R的關(guān)系矩陣并畫出關(guān)系圖：解：關(guān)系矩陣：0011000001001100關(guān)系圖：1342第16頁(yè)，共60頁(yè)，2023年，2月20日，星期一§4.2關(guān)系的運(yùn)算關(guān)系R的定義域：

domR={x|(y)<x,y>R}(即R中有序組的第一個(gè)元素構(gòu)成的集合)關(guān)系R的值域：

ranR={y|(x)<x,y>R}(即R中有序組的第二個(gè)元素構(gòu)成的集合)一、關(guān)系的定義域與值域第17頁(yè)，共60頁(yè)，2023年，2月20日，星期一例4.5

下列關(guān)系都是整數(shù)集Z上的關(guān)系，分別求出它們的定義域和值域：(1)R1={<x,y>|x,y

Z

xy}(2)R2={<x,y>|x,y

Z

x2+y2=1}(3)R3={<x,y>|x,y

Z

y=2x}(4)R4={<x,y>|x,y

Z

|x|=|y|=3}第18頁(yè)，共60頁(yè)，2023年，2月20日，星期一解：

domR1=ranR1=Z解：

R2={<0,1>,<0,1>,domR2=(?)ranR2=(?)(1)R1={<x,y>|x,y

Z

xy}(2)R2={<x,y>|x,y

Z

x2+y2=1}<1,0>,<1,0>}第19頁(yè)，共60頁(yè)，2023年，2月20日，星期一解：

domR3=Z，ranR3={偶數(shù)}解：

domR4=ranR4=(?)(3)R3={<x,y>|x,y

Z

y=2x}(4)R4={<x,y>|x,y

Z

|x|=|y|=3}第20頁(yè)，共60頁(yè)，2023年，2月20日，星期一二、關(guān)系的常用運(yùn)算F是任意關(guān)系，F(xiàn)的逆F1={<x,y>|yFx}

F、G是任意兩個(gè)關(guān)系，F(xiàn)與G的合成記作：FG={<x,y>|(z)(xGzzFy)} 關(guān)系F在集A上的限制，記作：F|

A={<x,y>|xFyxA}集A在關(guān)系F下的象F[A]=ran(F

|A)(1)逆：(2)合成：(3)限制：(4)象：第21頁(yè)，共60頁(yè)，2023年，2月20日，星期一例4.6

設(shè)F，G是N上的關(guān)系，其定義為：F={<x,y>|x,yNy=x2}G={<x,y>|x,yNy=x+1}求G1，F(xiàn)G，GF，F(xiàn)

|{1,2}，F(xiàn)[{1,2}]解：由定義知：G1={<y,x>|y,xNy=x+1}列出G1

中的元素就是G1={<1,0>,<2,1>,<3,2>,…,<x+1,x>,…}第22頁(yè)，共60頁(yè)，2023年，2月20日，星期一為了求F

G，可以先直觀表示如下：對(duì)任何xNx

x+1=G即y=(x+1)2因此FG={<x,y>|x,yNy=(x+1)2}同理可求GF={<x,y>|(?)}(自己做！)發(fā)現(xiàn)F

G

G

FF

|{1,2}={<1,1>,<2,4>}F

[{1,2}]=ran(F

|{1,2})={1,4}F

Z

Z2=y第23頁(yè)，共60頁(yè)，2023年，2月20日，星期一關(guān)系運(yùn)算的性質(zhì)：設(shè)F、G、H、為任意關(guān)系，則有：(1)(F1)1=F(2)domF1=ranF，ranF1=domF(3)(F

G)

H=F(G

H)(4)(FG)1=G1

F1(5)F

(G∪H)=F

G∪F

H(對(duì)∪的分配律)(6)F

(G∩H)

F

G∩F

H(對(duì)∩的半分配律)(7)(G∪H)

F=GF∪H

F(8)(G∩H)

F

G

F∩H

F(?)(?)第24頁(yè)，共60頁(yè)，2023年，2月20日，星期一任取<x,y><x,y>(F

G)1<y,x>F

G(z)(<y,z>G<z,x>F)(z)(<z,y>G1<x,z>F1)<x,y>G1

F1(4)(F

G)1=G1

F1的證明：第25頁(yè)，共60頁(yè)，2023年，2月20日，星期一任取<x,y><x,y>F(G∪H)(z)(<x,z>(G∪H)<z,y>F)(z)((<x,z>G∪<x,z>H)<z,y>F)(注意對(duì)括號(hào)的順序)(z)(<x,z>G<z,y>F>∪(<x,z>H<z,y>F))<x,y>FG∪<x,y>F

H∴F

(G∪H)=F

G∪F

H(5)F

(G∪H)=F

G∪F

H的證明：第26頁(yè)，共60頁(yè)，2023年，2月20日，星期一§4.3關(guān)系的性質(zhì)R的關(guān)系矩陣：主對(duì)角線元素全是1R的關(guān)系圖：每個(gè)頂點(diǎn)都有環(huán)自反性：xA

有<x,x>R(R是A上的關(guān)系)關(guān)系矩陣：主對(duì)角線元素全是0關(guān)系圖：每個(gè)頂點(diǎn)都沒有環(huán)反自反性：xA<x,x>R第27頁(yè)，共60頁(yè)，2023年，2月20日，星期一對(duì)稱性：若<x,y>R，則<y,x>R

關(guān)系矩陣：對(duì)稱陣關(guān)系圖：如果兩個(gè)頂點(diǎn)之間有邊，一定是一對(duì)方向相反的邊。第28頁(yè)，共60頁(yè)，2023年，2月20日，星期一反對(duì)稱性：若<x,y>R且xy，則<y,x>R

關(guān)系矩陣：如果rij

=1，且ij，則rji

=0關(guān)系圖：如果兩個(gè)頂點(diǎn)之間有邊，一定是只有一條有向邊。第29頁(yè)，共60頁(yè)，2023年，2月20日，星期一傳遞性：若<x,y>R且<y,z>R，則<x,z>R

關(guān)系圖：如果頂點(diǎn)xi到xj有邊，

xj到xk有邊，則從xi到xk有邊第30頁(yè)，共60頁(yè)，2023年，2月20日，星期一例4.7

設(shè)A={1,2,…,10}，對(duì)于A上的關(guān)系R={<x,y>|(xy)/3I}I為整數(shù)集，問(wèn)R有哪些性質(zhì)？第31頁(yè)，共60頁(yè)，2023年，2月20日，星期一解：逐條性質(zhì)加以驗(yàn)證R={<x,y>|(xy)/3I}任取A中元素x，由于(xx)/3=0，所以R是自反的；又設(shè)A中任意兩個(gè)元素x,y，如果xRy，即xy可被3整除，則yx也一定可被3整除，即yRx，從而R是對(duì)稱的；如果A中三個(gè)元素x，y，z滿足xRy，yRz，則xy，yz被3整除，由于xz=(xy)+(yz)，所以xz被3整除，從而xRz即R具有傳遞性。第32頁(yè)，共60頁(yè)，2023年，2月20日，星期一§4.4關(guān)系的閉包運(yùn)算閉包：設(shè)RAA，自反閉包記作r(R)對(duì)稱閉包記作s(R)傳遞閉包記作t(R)由A求r(R)，s(R)，t(R)的過(guò)程叫閉包運(yùn)算。那么，包含R而使之具有自反性質(zhì)的最小關(guān)系，稱之為R的自反閉包；包含R而使之具有對(duì)稱性質(zhì)(傳遞性質(zhì))的最小關(guān)系，稱之為R的對(duì)稱(傳遞)閉包。一、定義第33頁(yè)，共60頁(yè)，2023年，2月20日，星期一冪運(yùn)算：設(shè)RAA，kN，約定(1)R0=IA={<x,x>|xA}(2)R1=R(3)Rk+1=Rk

R顯然Rm

Rn

=Rm+n

(Rm)n

=Rmn二、計(jì)算方法為了有效地計(jì)算關(guān)系R的各種閉包，先引進(jìn)關(guān)系的冪運(yùn)算概念。第34頁(yè)，共60頁(yè)，2023年，2月20日，星期一閉包運(yùn)算的方法：設(shè)R是A上的任一關(guān)系，則(1)r(R)

=R∪IA(2)s(R)

=R∪R(3)t(R)

=R∪R2∪R3∪…∪Rn∪…第35頁(yè)，共60頁(yè)，2023年，2月20日，星期一矩陣形式：(M為R的關(guān)系矩陣)(1)Mr=M+E(2)Ms=M+M'(M'是M的轉(zhuǎn)置)(3)Mt=M+M2+M3……其中“+”均表示“邏輯加”第36頁(yè)，共60頁(yè)，2023年，2月20日，星期一例4.8

設(shè)A={a,b,c,d}，A上的關(guān)系求r(R)，s(R)和t(R)解：

r(R)=R∪IA={<a,b>,<b,c>,<c,d>,<d,c,>,<a,a>,<b,b>,<c,c>,<d,d>}R={<a,b>,<b,c>,<c,d>,<d,c>,<a,a>}=R∪{<a,a>,<b,b,><c,c>,<d,d>}三、實(shí)例第37頁(yè)，共60頁(yè)，2023年，2月20日，星期一s(R)=R∪R={<a,b>,<b,c>,<c,d>,<d,c>,<b,a>,<c,b>,<a,a>}t(R)=R∪R2∪R3∪……=R∪{<b,a>,<c,b>,<d,c>,<c,d>,<a,a>}第38頁(yè)，共60頁(yè)，2023年，2月20日，星期一而R2=R

RR3=R2

RR4=R3

R={<a,c>,<b,d><c,c>,<d,d>,<a,b>,<a,d>,<a,a>}={<a,d>,<b,c>,<c,d>,<d,c>,<a,b>,<a,c>,<a,a>}={<a,c>,<b,d>,<c,c>,<d,d>,<a,b>,<a,a>}實(shí)際上，看到當(dāng)k

4時(shí)，已有R4

R∪R2∪R3故t(R)=

R∪R2∪R3={<a,b>,<b,c><c,d>,<d,c>,<a,d>,<a,c>,

<b,d>,<c,c>,<d,d>,<a,a>}第39頁(yè)，共60頁(yè)，2023年，2月20日，星期一四、閉包運(yùn)算的性質(zhì)設(shè)A是有限集且|A|=n，RAA，則：第40頁(yè)，共60頁(yè)，2023年，2月20日，星期一§4.6等價(jià)關(guān)系和偏序關(guān)系等價(jià)關(guān)系：集A上的關(guān)系R是自反的,對(duì)稱的和傳遞的。等價(jià)類：

R是集A上的等價(jià)關(guān)系，對(duì)于任一aA，[a]R={x|aRx,xA}被稱為a的等價(jià)類。即A中所有和a有R關(guān)系的元素的集合。一、等價(jià)關(guān)系及用途第41頁(yè)，共60頁(yè)，2023年，2月20日，星期一等價(jià)類的性質(zhì)：R是非空集合，對(duì)任意的x，yA，下面的結(jié)論成立：(1)[x]且[x]A(等價(jià)類為A的子集)(2)若xRy，則[x]=[y](3)若x\Ry，則[x]∩[y]=

第42頁(yè)，共60頁(yè)，2023年，2月20日，星期一集A在等價(jià)關(guān)系R下的商集：設(shè)R為非空集A上的等價(jià)關(guān)系，以R的不交的等價(jià)類為元素的集合叫做A在R下的商集，記作A/R.即：A/R={[x]R|xA}第43頁(yè)，共60頁(yè)，2023年，2月20日，星期一集A的劃分：設(shè)A是非空集合，(1)(2)中任意兩個(gè)元素不交

(3)中所有元素的并集為A則為A的劃分。如果存在一個(gè)A的子集族，P(A)滿足以下條件：第44頁(yè)，共60頁(yè)，2023年，2月20日，星期一由等價(jià)類的性質(zhì)和商集的定義可知，商集A/R是A的劃分，稱之為由R誘導(dǎo)的劃分。反過(guò)來(lái)，給定A的任一劃分，則A被分割成若干個(gè)劃分塊。若定義A上的二元關(guān)系R：x，yA且x,y屬的同一塊，則xRy，那么R是A上的等價(jià)關(guān)系，稱之為由誘導(dǎo)的等價(jià)關(guān)系。集A上的等價(jià)關(guān)系與劃分是一一對(duì)應(yīng)的。第45頁(yè)，共60頁(yè)，2023年，2月20日，星期一例4.9

設(shè)A={1,2,3}，求出A上所有的等價(jià)關(guān)系：解：先求A的各種劃分：只有1個(gè)劃分塊的劃分1，具有兩個(gè)劃分塊的劃分2，3，和4，具有3個(gè)劃分塊5。1={A}2={{1},{2,3}}，4={{3},{1,2}}，3={{2},{1,3}}，5={{1},{2},{3}}第46頁(yè)，共60頁(yè)，2023年，2月20日，星期一設(shè)對(duì)應(yīng)于劃分i的等價(jià)關(guān)系Ri，i=1,2,…5，則有R5={<1,1>，<2,2>，<3,3>}R1={<1,1>，<1,2>，<1,3>，R2={<1,1>，R3={<2,2>，R4={<3,3>，<2,2>，<2,1>，<2,3>，<3,3>，<3,1>，<3,2>}<2,2>，<2,3>，<3,3>，<3,2>}<1,1>，<1,3>，<3,3>，<3,1>}<2,2>，<2,1>}<1,1>，<1,2>，第47頁(yè)，共60頁(yè)，2023年，2月20日，星期一偏序關(guān)系：集A上的關(guān)系R是自反的，反對(duì)稱的和傳遞的，記作“”，且稱<A,)為偏序集。二、偏序關(guān)系及用途第48頁(yè)，共60頁(yè)，2023年，2月20日，星期一例4.10

設(shè)A={2,4,6,8}，A上關(guān)系R是通常意義下的小于或等于關(guān)系，試寫出R并驗(yàn)證它是偏序關(guān)系。解：R={<2,2>,<2,4>,<2,6>,<2,8>,(1)自反性：(2)反對(duì)稱性：(3)傳遞性：<8,8>}<6,6>,<6,8>,<4,4>,<4,6>,<4,8>,<2,2>,<4,4><6,6>,<8,8>均屬于R對(duì)任意的<x,y>R，必有xy，當(dāng)xy時(shí)，

y>x，從而<y,x>R對(duì)任意的<x,y>R，<y,z>R,由于xyyz

，所以xz，從而<x,z>R。第49頁(yè)，共60頁(yè)，2023年，2月20日，星期一例4.11

設(shè)C={{a,b},{a},,}，C上關(guān)系T是集合的“包含于”，試寫出T，并驗(yàn)證它是偏序關(guān)系。解：

同例4.10類似，自己做！第50頁(yè)，共60頁(yè)，2023年，2月20日，星期一偏序集的哈斯圖(1)用小圓圈表示偏序集的元素(稱為結(jié)點(diǎn))；(2)按每個(gè)元素在偏序中的次序從底向上列結(jié)點(diǎn)位置；(3)對(duì)于偏序集中任意兩個(gè)元素x和y，如果xy且不存在另一個(gè)元素a，使xaay，則在x與y兩結(jié)點(diǎn)之間劃上一杠，即“|”(x在下，y在上)第51頁(yè)，共60頁(yè)，2023年，2月20日，星期一全序關(guān)系：設(shè)<A,>是偏序集，(x)(y)(xAyA(xyyx))成立，則稱<A,)為全序集，這時(shí)的偏序關(guān)系叫全序關(guān)系。全序集<A,)中全部元素可以排序，它的哈斯圖為一條直線。如果第52頁(yè)，共60頁(yè)，2023年，2月20日，星期一偏序集中的一些特殊元素設(shè)<A,>是偏序集，BA(1)

如果yB，使得(x)(xByx)為真，則y是B的最小元(“小于”

B中所有元)(2)

如果yB，使得(x)(xBxy)為真，則y是B的最大元(“大于”B中所有元)第53頁(yè)，共60頁(yè)，2023年，2月20日，星期一(4)

若yB，使得(x)(xBxy)，則稱y是B的極大元(B中沒有比y大的其他元)(5)

若yA，使得(x)(xB

xy)為真，則稱y是B的上界(3)

若yB，使得(x)(xBxy)，則稱y是B的極小元(B中找不到x小于y)第54頁(yè)，共60頁(yè)，2023年，2月20日，星期一(6)