離散數(shù)學(xué)-第2章-二元關(guān)系與函數(shù)

離散數(shù)學(xué)

第1篇

集合論第2章二元關(guān)系與函數(shù)2.1關(guān)系的概念一、笛卡爾積

1.笛卡爾積的定義兩個(gè)元素x、y按順序排列組成的組合稱為x、y的有序?qū)?，記?lt;x,y>

顯然，⑴當(dāng)x≠y時(shí)，<x,y>≠<y,x>⑵如<x,y>=<a,b>，則。已知集合A,B，以集合A中的元素為第一元素，集合B中的元素為第二元素構(gòu)成的所有有序?qū)M成的集合，稱為A和B的笛卡爾積，記作A×B

當(dāng)集合A=B時(shí)，A×A=A22.笛卡爾積的性質(zhì)性質(zhì)1，A×φ=φ，φ×A=φ性質(zhì)2，笛卡爾積不滿足交換律

當(dāng)A≠φ，B≠φ，A≠B時(shí)，A×B≠B×A性質(zhì)3，笛卡爾積不滿足結(jié)合律性質(zhì)4，笛卡爾積對(duì)并、交的分配律成立⑴⑵⑶⑷二、關(guān)系的基本概念若R是一個(gè)有序?qū)Φ募?，且R是集合A到B的笛卡爾積A×B的子集,則R稱為集合A到B的二元關(guān)系。若R是一個(gè)有序?qū)Φ募?，且R是笛卡爾積A×A的子集,則R稱為集合A上的二元關(guān)系。例如：二元關(guān)系有序?qū)?，則稱在R中有關(guān)系，記作，否則記作不含任何有序?qū)Φ年P(guān)系稱為空關(guān)系，包含笛卡爾積中所有有序?qū)Φ年P(guān)系稱為全關(guān)系，僅包含所有形如有序?qū)Φ年P(guān)系稱為恒等關(guān)系。三、關(guān)系矩陣和關(guān)系圖

表示關(guān)系的方法有三種：集合表達(dá)式、關(guān)系矩陣和關(guān)系圖。1．關(guān)系矩陣設(shè)則可用一個(gè)m×n矩陣MR來表示從A到B的關(guān)系R具體做法為：作一個(gè)m×n矩陣MR

，m行的編號(hào)從上到下依次為，n列的編號(hào)從左到右依次為如則，如則當(dāng)A=B時(shí)，矩陣MR為方陣，通常不再標(biāo)明各行列所表示的元素名稱。例4

設(shè)：A={a,b,c,d}，B={x,y,z}，R={<a,x>,<a,z>,<b,y>,<c,z>,<d,y>}，求關(guān)系矩陣MR解：

2。關(guān)系圖⑴對(duì)于從A到B的關(guān)系，可作如下圖示。用左邊一列結(jié)點(diǎn)表示A中的元素，右邊一列結(jié)點(diǎn)表示B中的元素，標(biāo)明元素的名稱。有關(guān)系的元素之間用一條有向弧連接，方向從A中的元素指向B中的元素。⑵對(duì)于A上的關(guān)系，可作如下圖示。在平面上用等距結(jié)點(diǎn)表示A中的元素，標(biāo)明各元素的名稱，若ai與aj有關(guān)系，則畫一條從ai指向aj的有向弧若ai與自身有關(guān)系，則在結(jié)點(diǎn)ai處畫一個(gè)自回路，表明方向。例5

求R的關(guān)系矩陣MR和關(guān)系圖。已知A={1,2,3,4}，R={<1,1>,<1,2>,<2,3>,<2,4>,<3,3>,<4,2>}。解：

243例6

已知集合A＝{a,b,c}上的二元關(guān)系R的關(guān)系矩陣MR＝，那么R＝() (A){<a,b>,<b,a>,<b,b>,<a,c>}(B){<a,b>,<b,a>,<b,b>,<c,b>}(C){<a,b>,<a,a>,<b,b>,<c,a>}(D){<a,b>,<b,a>,<b,b>,<c,a>}例7

設(shè)集合X={a,b,c,d}，定義X上的二元關(guān)系R的關(guān)系圖如右，試寫出R的表達(dá)式和關(guān)系矩陣。解：

adbc2.2關(guān)系的運(yùn)算一、關(guān)系的集合運(yùn)算關(guān)系的集合運(yùn)算有關(guān)系的并、交、差、補(bǔ)和對(duì)稱差。1。關(guān)系的并、交由關(guān)系R、S中所有的有序?qū)M成的集合稱為關(guān)系R與S的并，記作。由關(guān)系R、S中相同的有序?qū)M成的集合稱為關(guān)系R與S的交，記作。例如R={<1,1>,<1,3>,<2,3>}，S={<1,2>,<2,3>,<3,1>}

2。關(guān)系的差

由所有屬于關(guān)系R但不屬于S的有序?qū)M成的集合稱為關(guān)系R與S的差，記作R－S。例如R={<1,1>,<1,3>,<2,3>}，S={<1,2>,<2,3>,<3,1>}R－S={<1,1>,<1,3>}，S－R={<1,2>,<3,1>}

3。關(guān)系的補(bǔ)由笛卡爾積中所有不屬于R的有序?qū)M成的集合稱為關(guān)系R的補(bǔ)，記作~R。

例如，A={1,2,3}，R={<1,1>,<1,3>,<2,3>}，~R={<1,2>,<2,1>,<2,2>,<3,1>,<3,2>,<3,3>}二、復(fù)合關(guān)系1。復(fù)合關(guān)系的定義設(shè)R是集合A到B的二元關(guān)系，aiRbj，S是集合B到C的二元關(guān)系，bjSck，則ai與ck之間存在一個(gè)二元關(guān)系T，表示為T=R·S例如，A={1,2,3,4,5}，B={3,4,5}，C={1,2,3}R={<a,b>|a+b=6}，S={<b,c>|b-c=2}，求復(fù)合關(guān)系R·S解：R={<1,5>,<2,4>,<3,3>}

S={<3,1>,<4,2>,<5,3>}1→5→3，2→4→2，3→3→1

R·S={<1,3>,<2,2>,<3,1>}

復(fù)合關(guān)系不滿足交換律，即R·S≠S·R例如，A={a,b,c,d}，R={<a,b>,<b,b>,<c,d>}S={<b,a>,<c,a>,<d,b>}R·S={<a,a>,<b,a>,<c,b>}，S·R={<b,b>,<c,b>,<d,b>}2。復(fù)合關(guān)系的矩陣運(yùn)算設(shè)R的關(guān)系矩陣為MR，S的關(guān)系矩陣為MS，

則MR·S=MR×MS，運(yùn)算要用布爾運(yùn)算，1+1=1如：

[2004年1月計(jì)算題16]

設(shè)集合A＝{1,2,3,4}，A上的一個(gè)二元關(guān)系R={<1,2>,<3,2>,<2,3>,<3,4>}⑴求出R2，R3的集合表達(dá)式；⑵畫出R2的關(guān)系圖。解:⑴故R2={<1,3>,<2,2>,<2,4>,<3,3>}，

R3={<1,2>,<1,4>,<2,3>,<3,2>,<3,4>}(2).如右圖。

1

4

2

3三、逆關(guān)系1。逆關(guān)系的定義把二元關(guān)系R中所有的有序?qū)χ械牡谝辉嘏c第二元素交換位置，所得到的集合稱為R的逆關(guān)系，記作R-1。逆關(guān)系的矩陣是原關(guān)系矩陣的轉(zhuǎn)置，即

逆關(guān)系的關(guān)系圖是原關(guān)系圖中所有有向弧反向。如RR-12。逆關(guān)系的運(yùn)算律2.3關(guān)系的性質(zhì)關(guān)系的性質(zhì)有自反性、對(duì)稱性、傳遞性。一、自反性和反自反性若對(duì)于集合A中所有的元素，都有,則稱R具有自反性，若對(duì)于集合A中所有的元素，都有,則稱R具有反自反性。若，則R具有自反性。IA是A上最小的自反關(guān)系若，則R具有反自反性。E－IA是A上最大的反自反關(guān)系，φ是A上最小的反自反關(guān)系。從關(guān)系矩陣上看，主對(duì)角線上的元素都是1的矩陣具有自反性，主對(duì)角線上的元素都是0的矩陣具有反自反性。從關(guān)系圖上看，每個(gè)元素都有自回路的具有自反性，每個(gè)元素都沒有自回路的具有反自反性。若R、S都是A上的自反關(guān)系，則也是A上的自反關(guān)系，若R、S都是A上的反自反關(guān)系，則也是A上的反自反關(guān)系。二、對(duì)稱性和反對(duì)稱性若在二元關(guān)系R中，如有aRb，則必有bRa，則稱R具有對(duì)稱性，若在二元關(guān)系R中，當(dāng)a≠b時(shí),如有aRb，則必沒有bRa，則稱R具有反對(duì)稱性。全關(guān)系EA(即集合A上的笛卡爾積A×A)是A上最大的對(duì)稱關(guān)系。恒等關(guān)系IA和空關(guān)系φ既具有對(duì)稱性，又具有反對(duì)稱性。從關(guān)系矩陣上看，若MR是對(duì)稱矩陣，則R具有對(duì)稱性，若MR轉(zhuǎn)置后除主對(duì)角線上的元素外，原來為1的元素都變?yōu)榱?，則R具有反對(duì)稱性。從關(guān)系圖上看，若不同結(jié)點(diǎn)間的有向弧成對(duì)出現(xiàn)，則R具有對(duì)稱性。若任意兩個(gè)不同結(jié)點(diǎn)間都沒有成對(duì)的有向弧，則R具有反對(duì)稱性。若R、S都是A上的對(duì)稱關(guān)系，則也是A上的對(duì)稱關(guān)系，若R、S都是A上的反對(duì)稱關(guān)系，則也是A上的反對(duì)稱關(guān)系，但不一定是A上的反對(duì)稱關(guān)系。例如，R={<1,2>}，S={<2,1>}三、傳遞性如果在二元關(guān)系R中既有aRb，又有bRc，則必有aRc，則稱R具有傳遞性。若，則R具有傳遞性。注意：若在二元關(guān)系R中只有aRb而沒有bRc，則無論是否有aRc，傳遞性都成立。在具有傳遞性的關(guān)系圖上，若有a指向b的有向弧，又有b指向c的有向弧，則應(yīng)有a指向c的有向弧，若有a指向b的有向弧，又有b指向a的有向弧，則a、b都應(yīng)有自回路。

若R、S都是A上的傳遞關(guān)系，則也是A上的傳遞關(guān)系,但不一定是A上的傳遞關(guān)系。例如，R={<1,2>},S={<2,3>}，不具有傳遞性。例8

如果和是A上的自反關(guān)系，則，和中自反關(guān)系有

個(gè)。解：一定是A上的自反關(guān)系，一定不是A上的自反關(guān)系，故有2個(gè)是A上的自反關(guān)系例9

如果關(guān)系是傳遞的，則

。

例10

設(shè)二元關(guān)系R1、R2的關(guān)系圖如下，指出它們各自具有的性質(zhì)。

解：R1的各結(jié)點(diǎn)均有自回路，所以R1具有自反性，不同結(jié)點(diǎn)間沒有有向弧，具有對(duì)稱性和反對(duì)稱性，具有傳遞性。

R2的各結(jié)點(diǎn)均沒有自回路，所以R2具有反自反性，所有的不同結(jié)點(diǎn)間都僅有一條有向弧，具有反對(duì)稱性，具有傳遞性。四、閉包閉包有自反閉包r(R)、對(duì)稱閉包s(R)、傳遞閉包t(R)。若在二元關(guān)系R中添加一些有序?qū)Φ玫叫碌年P(guān)系R’，使R’是具有自反性的最小集合，則稱R’是R的自反閉包。若在二元關(guān)系R中添加一些有序?qū)Φ玫叫碌年P(guān)系R’，使R’是具有對(duì)稱性的最小集合，則稱R’是R的對(duì)稱閉包。若在二元關(guān)系R中添加一些有序?qū)Φ玫叫碌年P(guān)系R’，使R’是具有傳遞性的最小集合，則稱R’是R的傳遞閉包。例11

設(shè)集合A={1,2,3,4}，集合A上的二元關(guān)系R={<1,1>,<1,2>,<1,3>,<2,1>,<2,3>,<3,3>,<3,4>,<4,4>},求自反閉包r(R)、對(duì)稱閉包s(R)、傳遞閉包t(R)。解：自反閉包r(R)={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,3>,<3,4>,<4,4>}

對(duì)稱閉包S(R)={<1,1>,<1,2>,<1,3>,<2,1>,<2,3>,<3,1>,<3,2>,<3,3>,<3,4>,<4,3>,<4,4>}

傳遞閉包t(R)={<1,1>,<1,2>,<1,3>,<1,4>,<2,1>,<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>}2.4等價(jià)關(guān)系一、等價(jià)關(guān)系1。等價(jià)關(guān)系的定義設(shè)R是非空集合A上的一個(gè)二元關(guān)系，如果R是自反的、對(duì)稱的、傳遞的，則稱R是A上的等價(jià)關(guān)系如果，則稱a等價(jià)于b，記作a~b。

非空集合A上的恒等關(guān)系IA和全關(guān)系EA都是等價(jià)關(guān)系。證明一個(gè)關(guān)系R是等價(jià)關(guān)系的方法就是證明R同時(shí)具有自反性、對(duì)稱性、傳遞性。一、相容關(guān)系1。相容關(guān)系的定義設(shè)R是非空集合A上的一個(gè)二元關(guān)系，如果R具有自反性、對(duì)稱性，則稱R是A上的相容關(guān)系。等價(jià)關(guān)系是具有傳遞性的相容關(guān)系，但相容關(guān)系不都是等價(jià)關(guān)系。例如，A={1,2,3}，R是A上的二元關(guān)系，R={<1,1>,<1,2>,<2,2>,<2,1>,<2,3>,<3,2>,<3,3>}，顯然R是自反的，對(duì)稱的，因此R是A上的相容關(guān)系由于R中包含<1,2>,<2,3>,但不包含<1,3>，所以R不是傳遞的，因此不是等價(jià)關(guān)系。2.5序關(guān)系二、偏序關(guān)系1。偏序關(guān)系的定義設(shè)R是非空集合A上的一個(gè)二元關(guān)系，如果R具有自反性、反對(duì)稱性、傳遞性，則稱R是A上的偏序關(guān)系，記作≤，如果≤，記作a≤b。自然數(shù)集上的小于等于關(guān)系和整除關(guān)系都是典型的偏序關(guān)系。例如，A={1,2,3,4,6}，R是A上的整除關(guān)系，即R={<1,1>,<1,2>,<1,3>,<1,4>,<1,6>,<2,2>,<2,4>,<2,6>,<3,3>,<3,6>,<4,4>,<6,6>}，就是一個(gè)偏序關(guān)系。注意:偏序關(guān)系中的a≤b和實(shí)數(shù)間比較大小是不同的2。偏序集集合A和集合A上的偏序關(guān)系≤組成的有序?qū)?，稱為偏序集，記作<A,≤>。如果R是A上的偏序關(guān)系，則<A，R>是偏序集3。哈斯圖對(duì)于偏序集可以用哈斯圖來表示各元素之間的偏序關(guān)系。方法是：⑴去掉關(guān)系圖中的自回路，用空心點(diǎn)表示所有結(jié)點(diǎn)⑵適當(dāng)排列所有結(jié)點(diǎn)的順序，如a≤b，則將a排在b的下方，⑶若a≤b，則在a、b之間畫一條連線，⑷若a≤b，b≤c，則去掉a、c之間的連線。

例12

畫出集合A={1,2,…,9}上整除關(guān)系的哈斯圖。解：R={<1,1>,<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<1,7>,<1,8>,<1,9>,<2,2>,<2,4>,<2,6>,<2,8>,<3,3>,<3,6>,<3,9>,<4,4>,<4,8>,<5,5>,<6,6>,<7,7>,<8,8>,<9,9>}6。最大元、最小元、極大元、極小元

設(shè)<A，R>是偏序集，B是集合A的一個(gè)子集，⑴若B中有元素b，滿足B中的其它元素都與b有關(guān)系，且它們都≤b，則稱b是B上的最大元，⑵若B中有元素b，滿足B中的其它元素都與b有關(guān)系，且b都≤它們，則稱b是B上的最小元，⑶若B中有元素b，滿足B中凡是與它有關(guān)系的元素都≤b，則稱b是B上的極大元，⑷若B中有元素b，滿足B中凡是與它有關(guān)系的元素，b都≤它們，則稱b是B上的極小元。

因此，如果在集合B中，不是所有的元素之間都有關(guān)系，則可能不存在最大元或最小元。

如果在集合B中存在最大元或最小元，則它們是唯一的。

在有限集合B中，極大元和極小元一定存在，且可能是不唯一的。例如，在上述的試題中，A中就不存在最大元，9不是最大元，因?yàn)?,4,5,6,7,8與9沒有關(guān)系，但9是極大元，同時(shí)5,6,7,8也是極大元，極大元不唯一。

1是A中的極小元，同時(shí)也是A中的最小元。例13

設(shè)偏序集<A,≤>的哈斯圖。(1)試寫出集合A和≤的集合表達(dá)式，(2)求偏序集<A,≤>的極大元、極小元、最大元和最小元。解：(1)A={a,b,c,d,e,f}≤={<e,a>,<e,c>,<e,d>,<e,b>,<a,b>,<c,b>,<d,b>}(2)b,f

是極大元，e,f是極小元，無最大和最小元。例14偏序集<A,R>的哈斯圖如圖所示試寫出A和R的集合表達(dá)式，并求A的極大元和最大元。

abcfde7。上、下界，上、下確界

設(shè)<A,R>是偏序集，B是A的一個(gè)子集，a是A中的某一元素(不一定在B中)。

⑴若，都有b≤a，則稱a是B的上界，⑵若，都有a≤b，則稱a是B的下界，因此，B的上界或下界可能不在B中，而且B的上界或下界也可能不唯一。

B上界中的最小元素稱為B的最小上界或上確界，

B下界中的最大元素稱為B的最大下界或下確界。

再看上面提到過的例題，

A={1,2,3,4,5,6,7,8,9}，R是A上的整除關(guān)系。

R={<1,1>,<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<1,7>,<1,8>,<1,9>,<2,2>,<2,4>,<2,6>,<2,8>,<3,3>,<3,6>,<3,9>,<4,4>,<4,8>,<5,5>,<6,6>,<7,7>,<8,8>,<9,9>}

哈斯圖如下：

A={1,2,3,4,5,6,7,8,9}，假設(shè)B={2,4}。則8是B的上界，不在B中，4也是B的上界，它在B中，4是B的上確界，但9不是B的上界，因?yàn)锽中的2,4和9沒關(guān)系。

1是B的下界，不在B中，2也是B的下界，它在B中，2是B的下確界。再假如B={1,2,3,6}。則6是B的上界在B中，同時(shí)也是B的上確界，1是B的下界在B中，同時(shí)也是B的下確界。2.6函數(shù)的概念及性質(zhì)一、函數(shù)的基本概念1。函數(shù)的定義