二元關(guān)系和函數(shù)

二元關(guān)系和函數(shù)第1頁，共80頁，2023年，2月20日，星期三2第4章二元關(guān)系與函數(shù)4.1集合的笛卡兒積與二元關(guān)系4.2關(guān)系的運(yùn)算4.3關(guān)系的性質(zhì)4.4關(guān)系的閉包4.5等價(jià)關(guān)系和偏序關(guān)系4.6函數(shù)的定義和性質(zhì)4.7函數(shù)的復(fù)合和反函數(shù)第2頁，共80頁，2023年，2月20日，星期三34.1集合的笛卡兒積和二元關(guān)系

有序?qū)Φ芽▋悍e及其性質(zhì)二元關(guān)系的定義二元關(guān)系的表示第3頁，共80頁，2023年，2月20日，星期三4

有序?qū)Φ男再|(zhì)：1）有序性<x,y><y,x>（當(dāng)xy時(shí)）

2）<x,y>與<u,v>相等的充分必要條件是

<x,y>=<u,v>x=uy=v例4.1<2,x+5>=<3y4,y>，求x,y.解3y4=2,x+5=y

y=2,x=3

§4.1二元關(guān)系的概念1.有序?qū)?序偶：由兩個(gè)元素x和y按一定順序排成二元組，記作：<x，y>。其中x稱作第一個(gè)元素；y稱作第二個(gè)元素。第4頁，共80頁，2023年，2月20日，星期三5

實(shí)例：1.空間直角坐標(biāo)系中的坐標(biāo)

<3，5，－6>是有序三元組2.圖書館記錄<書類別，書號(hào)，書名，作者，出版社，年份>是一個(gè)有序六元組.2.有序n元組：一個(gè)有序n(n3)元組<x1,x2,…,xn>是一個(gè)有序?qū)?，其中第一個(gè)元素是一個(gè)有序n-1元組，即

<<x1,x2,…,xn-1>,xn>=

<x1,x2,…,xn>。我們將來的研究重點(diǎn)為有序二元組，即有序?qū)?序偶第5頁，共80頁，2023年，2月20日，星期三6例4.2A={1,2,3},B={a,b,c},C=

AB={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,<3,a>,<3,b>,<3,c>}

BA={<a,1>,<b,1>,<c,1>,<a,2>,<b,2>,<c,2>,<a,3>,<b,3>,<c,3>}AA={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>}AC=CA=3.笛卡兒積：設(shè)A,B為集合，用A中元素為第一個(gè)元素，B中元素為第二個(gè)元素，構(gòu)成有序?qū)?所有這樣的有序?qū)M成的集合叫做

A與B的笛卡兒積記作AB,即AB={<x,y>|xAyB}。第6頁，共80頁，2023年，2月20日，星期三7笛卡兒積的性質(zhì)：1.不適合交換律ABBA(AB,A,B)2.若A或B中有一個(gè)為空集，則AB就是空集.

A=B=

3.若|A|=m,|B|=n,則|AB|=mn

4.不適合結(jié)合律(AB)CA(BC)(A,B,C)例：A={1},B={2},C={3}AB={<1,2>},(AB)C={<<1,2>,3>}={<1,2,3>}BC={<2,3>},A(BC)={<1,<2,3>>}{<1,2,3>}第7頁，共80頁，2023年，2月20日，星期三8二元關(guān)系：集合中兩個(gè)元素之間的某種關(guān)系例3甲、乙、丙3個(gè)人進(jìn)行乒乓球比賽，任何兩個(gè)人之間都要比賽一場。假設(shè)比賽結(jié)果是乙勝甲，甲勝丙，乙勝丙。比賽結(jié)果可表示為：{<乙,甲>，<甲,丙>，<乙,丙>}，其中<x,y>表示x勝y，它表示了集合{甲,乙,丙}中元素之間的一種勝負(fù)關(guān)系.例4有A、B、C3個(gè)人和四項(xiàng)工作G1、G2、G3、G4，已知A可以從事工作G1和G4，B可以從事工作G3，C可以從事工作G1和G2.

那么，人和工作之間的對(duì)應(yīng)關(guān)系可以記作

R＝

{<A,G1>,<A,G4>,<B,G3>,<C,G1>,<C,G2}它表示了工人集合{A,B,C}到工作集合{G1,G2,G3,G4}之間的關(guān)系第8頁，共80頁，2023年，2月20日，星期三如<x,y>∈R,可記作xRy；如果<x,y>R,則記作xRy實(shí)例：R1={<1,2>,<a,b>},R2=

,R3={<1,2>,3,4}，R4={<x,y>|x∈N∧y∈Z}R1,R2,R4是二元關(guān)系；R3不是二元關(guān)系。4.

二元關(guān)系：如果一個(gè)集合滿足以下條件之一：（1）集合非空,且它的元素都是有序?qū)?以有序?qū)樵氐募?（2）集合是空集則稱該集合為一個(gè)二元關(guān)系,簡稱為關(guān)系，記作R.第9頁，共80頁，2023年，2月20日，星期三105.從A到B的關(guān)系與A上的關(guān)系設(shè)A,B為集合,A×B的任何子集所定義的二元關(guān)系叫做從A到B的二元關(guān)系,當(dāng)A=B時(shí)則叫做

A上的二元關(guān)系.例5A={0,1},B={1,2,3},R1={<0,2>},R2=A×B,R3=,R4={<0,1>}.那么R1,R2,R3,R4是從A到B的二元關(guān)系,R3和R4同時(shí)也是A上的二元關(guān)系.

計(jì)數(shù)：|A|=n,|B|=m,|A×B|=n×m,A×B的子集有個(gè).所以A到B上有個(gè)不同的二元關(guān)系.|A|=n,|A×A|=

,A×A的子集有個(gè).所以A上有個(gè)不同的二元關(guān)系.例如|A|=3,則A上有512個(gè)不同的二元關(guān)系.

第10頁，共80頁，2023年，2月20日，星期三11A上重要關(guān)系的實(shí)例設(shè)A為任意集合，是A上的關(guān)系，稱為空關(guān)系EA,IA分別稱為全域關(guān)系與恒等關(guān)系，定義如下：EA={<x,y>|x∈A∧y∈A}=A×A

IA={<x,x>|x∈A}

例如,A={1,2},則

EA={<1,1>,<1,2>,<2,1>,<2,2>}

IA={<1,1>,<2,2>}

注：{<1,1>}≠IA;{<2,2>}≠IA第11頁，共80頁，2023年，2月20日，星期三12A上重要關(guān)系的實(shí)例（續(xù)）小于等于關(guān)系LA,整除關(guān)系DA,包含關(guān)系R定義：

LA={<x,y>|x,y∈A∧x≤y},

DA={<x,y>|x,y∈A∧x整除y},R={<x,y>|x,y∈P(A)∧xy},A是某集合.類似的還可以定義大于等于關(guān)系,小于關(guān)系,大于關(guān)系,真包含關(guān)系等等.第12頁，共80頁，2023年，2月20日，星期三13實(shí)例例如A={1,2,3},B={a,b},則

LA={<1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3>}

DA={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}

P(B)={,{a},,{a,b}},則B上的包含關(guān)系是R={<,>,<,{a}>,<,>,<,{a,b}>,<{a},{a}>,<{a},{a,b}>,<,>,<,{a,b}>,<{a,b},{a,b}>}

第13頁，共80頁，2023年，2月20日，星期三14關(guān)系的表示表示方式：關(guān)系的集合表達(dá)式、關(guān)系矩陣、關(guān)系圖關(guān)系矩陣：若A={x1,x2,…,xm}，B={y1,y2,…,yn}，R是從A到B的關(guān)系，以A元素為行，B元素為列，MR=[rij]mn,其中rij

=1<xi,yj>R，否則rij

=0。關(guān)系圖：若A={x1,x2,…,xm}，R是從A上的關(guān)系，R的關(guān)系圖是GR=<A,R>,以A中元素為結(jié)點(diǎn)，如果<xi,xj>

R，則從xi

到xj有一條有向邊.注意：A,B為有窮集，關(guān)系矩陣適于表示從A到B的關(guān)系或者A上的關(guān)系，關(guān)系圖僅適于表示A上的關(guān)系

第14頁，共80頁，2023年，2月20日，星期三15實(shí)例A={1,2,3,4},R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},R的關(guān)系矩陣MR和關(guān)系圖GR如下：習(xí)題：4.1第15頁，共80頁，2023年，2月20日，星期三練習(xí)1.令A(yù)={1,2,3};B={a,b},求R1={<1,a>,<1,b>,<2,b>,<3,a>}的關(guān)系矩陣。2.令A(yù)={1,2,3};求R2={<1,1>,<1,3>,<2,1>,<3,2>}的關(guān)系圖。3.令F={<1,2>,<2,3>,<3,1>,<1,3>}，G={<2,1>,<2,2>,<2,3>,<1,4>}求F°G,G°F,F°F。（方法自選）第16頁，共80頁，2023年，2月20日，星期三17基本運(yùn)算定義定義域、值域、域逆、合成、限制、像基本運(yùn)算的性質(zhì)冪運(yùn)算定義求法性質(zhì)4.2關(guān)系的運(yùn)算第17頁，共80頁，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)系的定義域與值域關(guān)系R的域：

fldR=domR

ranR

第18頁，共80頁，2023年，2月20日，星期三19關(guān)系的基本運(yùn)算定義例1R={<1,2>,<1,3>,<2,4>,<4,3>},則domR={1,2,4}ranR={2,3,4}fldR={1,2,3,4}第19頁，共80頁，2023年，2月20日，星期三20關(guān)系的基本運(yùn)算定義（續(xù)）

R1={<y,x>|<x,y>R}

R°S=|<x,y>|

z(<x,z>S<z,y>R)}例2R={<1,2>,<2,3>,<1,4>,<2,2>}

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

R1={<2,1>,<3,2>,<4,1>,<2,2>}

R°S={<1,2>,<1,4>,<3,2>,<3,3>}S°R={<1,3>,<2,2>,<2,3>}二.逆與合成第20頁，共80頁，2023年，2月20日，星期三21合成運(yùn)算的圖示方法

利用圖示（不是關(guān)系圖）方法求合成R={<1,2>,<2,3>,<1,4>,<2,2>}

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

R°S={<1,2>,<1,4>,<3,2>,<3,3>}

S°R={<1,3>,<2,2>,<2,3>}RSSRS○R≠R○S第21頁，共80頁，2023年，2月20日，星期三22實(shí)例R={<1,2>,<3,2>,<1,4>,<2,2>}

R?{1}={<1,2>,<1,4>}

R[{1}]={2,4}R?{1,2}={<1,2>,<1,4>,<2,2>}

R?=

R[{1,2}]={2,4}

三限制和像：已知二元關(guān)系F和集合A

F在A上的限制

F?A={<x,y>|xFy

xA}

A在F下的像

F[A]=ran(F?A)

注意：F?AF,F[A]ranF第22頁，共80頁，2023年，2月20日，星期三23四.關(guān)系運(yùn)算的基本性質(zhì)(1)

(2)

(3)不滿足交換律：

F○G≠G○F(4)滿足結(jié)合律：

F○G○

H=F○

(G○H)(5)第23頁，共80頁，2023年，2月20日，星期三第24頁，共80頁，2023年，2月20日，星期三25五.A上關(guān)系的冪運(yùn)算設(shè)R為A上的關(guān)系,n為自然數(shù),則R的n次冪定義為：

(1)R0={<x,x>|x∈A}=IA

(2)Rn+1=Rn○R

注意：對(duì)于A上的任何關(guān)系R1和R2都有

R10=R20=IA

對(duì)于A上的任何關(guān)系R都有

R1=R第25頁，共80頁，2023年，2月20日，星期三26(1)定義法：對(duì)于集合表示的關(guān)系R，計(jì)算Rn就是n個(gè)R左復(fù)合.(2)矩陣乘法：矩陣表示就是n個(gè)矩陣相乘,其中相加采用邏輯加.（線性代數(shù)，邏輯乘法）(3)關(guān)系圖法：若點(diǎn)a經(jīng)k(k=1,2,…,n)條線可到達(dá)點(diǎn)b，則在的關(guān)系圖上，a到b有線相連。例3設(shè)A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>},求R的各次冪,分別用矩陣和關(guān)系圖表示.

解R與R2的關(guān)系矩陣分別為六.冪的求法：第26頁，共80頁，2023年，2月20日，星期三27同理，R0=IA,R3和R4的矩陣分別是：因此M4=M2,即R4=R2.因此可以得到

R2=R4=R6=…,R3=R5=R7=…第27頁，共80頁，2023年，2月20日，星期三28R0,R1,R2,R3,…的關(guān)系圖如下圖所示關(guān)系圖法結(jié)論：僅當(dāng)A有回路時(shí)，上述結(jié)論成立。第28頁，共80頁，2023年，2月20日，星期三當(dāng)圖中沒有回路時(shí)：第29頁，共80頁，2023年，2月20日，星期三30七.冪的性質(zhì)：當(dāng)關(guān)系圖有回路時(shí)：

(2)

(3)

第30頁，共80頁，2023年，2月20日，星期三31證明（2）：用數(shù)學(xué)歸納法

若n=0,則有

Rm○R0=Rm○IA=Rm=Rm+0假設(shè)Rm○Rn=Rm+n,則有

Rm○Rn+1=Rm○

(Rn○R)=(Rm○Rn)○R=Rm+n+1

。冪運(yùn)算的性質(zhì)（續(xù)）證明（3）：

若n=0,則有假設(shè)則有課后習(xí)題：4.2，4.3，4.13第31頁，共80頁，2023年，2月20日，星期三第32頁，共80頁，2023年，2月20日，星期三第33頁，共80頁，2023年，2月20日，星期三第34頁，共80頁，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第35頁，共80頁，2023年，2月20日，星期三例1：A={1,2,3},R1={<1,1>,<2,2>}R2={<1,1>,<2,2>,<3,3>}R3={<1,1>,<2,2>,<3,3>,<2,3>}R4={<1,1>,<1,2>,<2,3>}R5={<1,2>,<2,3>}既不是自反的也不是非自反的自反的自反的既不是自反的也不是非自反的反自反的例1：是自反的一定不是反自反的；是反自反的一定不是自反的！在自反性方面R有3種可能：自反的；反自反的；既非自反又非反自反的第36頁，共80頁，2023年，2月20日，星期三對(duì)稱性：若<x,y>R，則<y,x>R

關(guān)系矩陣：對(duì)稱陣(aij=aji)關(guān)系圖：如果兩個(gè)頂點(diǎn)之間有邊，一定是一對(duì)方向相反的邊。反對(duì)稱性：若<x,y>R且xy，則<y,x>R

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

=1，且ij，則rji

=0關(guān)系圖：如果兩個(gè)頂點(diǎn)之間有邊，一定是只有一條有向邊。！R={<x,x>|xR}既是對(duì)稱關(guān)系又是反對(duì)稱關(guān)系第37頁，共80頁，2023年，2月20日，星期三例2：A={1,2,3},R1={<1,1>,<2,2>,<3,3>,<2,1>}R2={<1,1>,<2,2>,<3,3>}R3={<1,1>,<1,2>,<2,1>}R4={<1,1>,<1,2>,<3,1>}R5={<1,2>,<2,1>,<3,1>}反對(duì)稱的既對(duì)稱又反對(duì)稱的對(duì)稱的反對(duì)稱的既非對(duì)稱又非反對(duì)稱的！在對(duì)稱性方面R有4種可能：對(duì)稱的；反對(duì)稱的；既對(duì)稱又反對(duì)稱的；既非對(duì)稱又非反對(duì)稱的第38頁，共80頁，2023年，2月20日，星期三傳遞性：若<x,y>R且<y,z>R，則<x,z>R

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

xj到xk有邊，則從xi到xk有邊！若a可經(jīng)過兩條或兩條以上的線到達(dá)b，則<a,b>R

第39頁，共80頁，2023年，2月20日，星期三例3：A={1,2,3,4},R1={<1,1>,<2,2>,<3,3>}R2={<1,2>,<3,4>}R3={<1,1>,<1,2>,<2,1>}R4={<1,2>,<2,3>,<1,3>,<2,2>}R5={<1,2>,<2,1>,<3,1>,<1,3>,<3,3>}傳遞的傳遞的非傳遞的傳遞的非傳遞的！在傳遞性方面，R有兩種可能：傳遞的；非傳遞的。第40頁，共80頁，2023年，2月20日，星期三練習(xí)：自反的對(duì)稱的反對(duì)稱的傳遞的自反的對(duì)稱的傳遞的反自反的反對(duì)稱的反對(duì)稱的傳遞的課后習(xí)題：4.4，4.12根據(jù)關(guān)系圖判斷關(guān)系的綜合性質(zhì)：第41頁，共80頁，2023年，2月20日，星期三§4.4關(guān)系的閉包運(yùn)算閉包：設(shè)RAA，自反閉包記作r(R)對(duì)稱閉包記作s(R)傳遞閉包記作t(R)那么，包含R而使之具有自反性質(zhì)的最小關(guān)系，稱之為R的自反閉包；包含R而使之具有傳遞性質(zhì)的最小關(guān)系，稱之為R的傳遞閉包。一、定義包含R而使之具有對(duì)稱性質(zhì)的最小關(guān)系，稱之為R的對(duì)稱閉包。第42頁，共80頁，2023年，2月20日，星期三冪運(yùn)算：設(shè)RAA，kN，約定(1)R0=IA={<x,x>|xA}(2)R1=R(3)Rk+1=Rk

R二、計(jì)算方法為了有效地計(jì)算關(guān)系R的各種閉包，先引進(jìn)關(guān)系的冪運(yùn)算概念。第43頁，共80頁，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-1第44頁，共80頁，2023年，2月20日，星期三２．矩陣形式：(M為R的關(guān)系矩陣)(1)Mr=M+E（單位矩陣）(2)Ms=M+M'(M'是M的轉(zhuǎn)置)(3)Mt=M+M2

+….+Mn-1其中“+”均表示“邏輯加”第45頁，共80頁，2023年，2月20日，星期三３．關(guān)系圖法：(1)自反閉包圖：對(duì)沒有加環(huán)的點(diǎn)加環(huán)(2)對(duì)稱閉包圖：單邊的加方向相反的邊(3)傳遞閉包圖：若Ai經(jīng)過兩條或兩條以上的邊可到達(dá)Aj，且無邊<Ai,Aj>則加邊<Ai,Aj>第46頁，共80頁，2023年，2月20日，星期三例4.10

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

r(R)=R∪IA={<a,b>,<b,a>,<b,c>,<c,d>,<a,a>,<b,b>,<c,c>,<d,d>}R={<a,b>,<b,a>,<b,c>,<c,d>}=R∪{<a,a>,<b,b><c,c>,<d,d>}三、實(shí)例第47頁，共80頁，2023年，2月20日，星期三={<a,b>,<b,a>,<b,c>,<c,d>,<c,b>,<d,c>}=R∪{<b,a>,<a,b><c,b>,<d,c>}s(R)

=R∪Rt(R)

=R∪R2∪R3∪…∪Rn-1=R∪{<a,a>,<a,c><b,b>,<b,d>}∪{<a,b>,<a,d><b,a>,<b,c>}={<a,b>,<b,a>,<b,c>,<c,d>,<a,a>,<a,c><b,b>,<b,d>,<a,d>}R={<a,b>,<b,a>,<b,c>,<c,d>}第48頁，共80頁，2023年，2月20日，星期三2.矩陣運(yùn)算：

R={<a,b>,<b,a>,<b,c>,<c,d>}第49頁，共80頁，2023年，2月20日，星期三3.關(guān)系圖方法：

課后習(xí)題：4.14Rr(R)t(R)s(R)第50頁，共80頁，2023年，2月20日，星期三第51頁，共80頁，2023年，2月20日，星期三§4.5等價(jià)關(guān)系和偏序關(guān)系等價(jià)關(guān)系：集A上的關(guān)系R是自反的,對(duì)稱的和傳遞的。一、等價(jià)關(guān)系及用途例4.5.1：A={1,2,3,…,8}，R={<x,y>|x≡y(mod3)}則1～4～7，2～5～8，3～6設(shè)R是一個(gè)等價(jià)關(guān)系,若<x,y>∈R,稱x等價(jià)于y,記做x～y.第52頁，共80頁，2023年，2月20日，星期三相容關(guān)系：

R是集A上的關(guān)系，且R是自反的，對(duì)稱的(1)在一群人的集合上年齡，姓名相同的關(guān)系是等價(jià)關(guān)系,而朋友關(guān)系是相容關(guān)系，因?yàn)樗赡懿皇莻鬟f的.

(2)動(dòng)物是按種屬分類的；“具有相同種屬性”的關(guān)系是動(dòng)物集合上的等價(jià)關(guān)系.(3)集合上的恒等關(guān)系和全域關(guān)系都是等價(jià)關(guān)系.(4)在同一平面上三角形之間的相似關(guān)系是等價(jià)關(guān)系,但直線間的平行關(guān)系不是等價(jià)關(guān)系也不是相容關(guān)系,因?yàn)樗皇亲苑吹?例子：！等價(jià)關(guān)系一定是相容關(guān)系；相容關(guān)系不一定是等價(jià)關(guān)系第53頁，共80頁，2023年，2月20日，星期三等價(jià)類：

R是集A上的等價(jià)關(guān)系，對(duì)于任一aA，[a]R={x|aRx,xA}被稱為a的等價(jià)類。即：[x]R={y|x~y}在例4.5.1中：[1]R

=[4]R=[7]R={1,4,7};[2]R

=[5]R=[8]R={2,5,8};[3]R

=[6]R=[9]R={3,6,9};第54頁，共80頁，2023年，2月20日，星期三等價(jià)類的性質(zhì)：R是非空集合，對(duì)任意的x，yA，下面的結(jié)論成立：(1)[x]R

且[x]R

A(等價(jià)類為A的子集)(2)若x~y則[x]R

=[y]R，反之成立。(3)若xRy，則[x]R

∩[y]R

=

第55頁，共80頁，2023年，2月20日，星期三集A在等價(jià)關(guān)系R下的商集：設(shè)R為非空集A上的等價(jià)關(guān)系，A在R下的商集記作A/R，A/R={[x]R

|xA}.(集合的集合）例4.5.1的商集為：A/R={{1,4,7},{2,5,8},{3,6,9}}注意：A/EA={A}

A/IA={{x}|x∈A}第56頁，共80頁，2023年，2月20日，星期三集A的劃分：令=A/R，滿足以下性質(zhì)：(1)(2)中任意兩個(gè)元素不交

(3)中所有元素的并集為A則為A的劃分。集合A上的劃分是不唯一的第57頁，共80頁，2023年，2月20日，星期三對(duì)于集合A，若給定一個(gè)等價(jià)關(guān)系，則我們可唯一確定一個(gè)商集集合A上的等價(jià)關(guān)系與劃分是一一對(duì)應(yīng)的。集合A上的一個(gè)商集可唯一確定A上的一個(gè)劃分第58頁，共80頁，2023年，2月20日，星期三例4.5.2

設(shè)A={1,2,3}，求出A上所有的等價(jià)關(guān)系：解：先求A的各種劃分：只有1個(gè)劃分塊的劃分1，具有兩個(gè)劃分塊的劃分2，3，和4，具有3個(gè)劃分塊5。第59頁，共80頁，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>，第60頁，共80頁，2023年，2月20日，星期三偏序關(guān)系：集合A上的關(guān)系R是自反的，反對(duì)稱的和傳遞的，記作“”。二、偏序關(guān)系及用途設(shè)R為偏序關(guān)系,如果<x,y>R,則記作xy,讀作“x小于等于y”.注意:這里的“小于等于”不是指數(shù)的大小,而是在偏序關(guān)系中的順序性.第61頁，共80頁，2023年，2月20日，星期三例4.5.3

設(shè)A={1,2,3}，求出A上的大于等于關(guān)系：解：={<1,1>,<2,1>,<2,2>,<3,1>,<3,2>,<3,3>}其中：11,

21,22,31,32,33第62頁，共80頁，2023年，2月20日，星期三偏序關(guān)系例子：（1）任何集合A上的恒等關(guān)系（2）集合A的冪集P(A)上的包含關(guān)系（4）正整數(shù)集上的整除關(guān)系都是偏序關(guān)系.（3）實(shí)數(shù)集上的小于等于，大于等于關(guān)系,第63頁，共80頁，2023年，2月20日，星期三相關(guān)概念：偏序集：集合A和偏序關(guān)系R≤

構(gòu)成一個(gè)偏序集，記作<A,R≤

>。如：<A,R

>,<A,R整除>等可比：對(duì)于任意兩個(gè)元素x和y，若x≤y或y≤x，則x與y是可比的全序關(guān)系與全序集：若A中任意兩個(gè)元素都是可比的，則R≤為全序關(guān)系；<A,R≤>為全序集。第64頁，共80頁，2023年，2月20日，星期三蓋住：如果x≤y，且不存在z使x≤z≤y(不是間接的),則稱y能蓋住x。例：鍋，籠屜，鍋蓋火車臥鋪的下鋪，中鋪，上鋪第65頁，共80頁，2023年，2月20日，星期三例4.5.4

設(shè)A={1,2,3,4}，求出A上的整除關(guān)系：解:R整除={<1,1>,<1,2>,<1,3>,<1,4>,<2,2>,<2,4>,<3,3>,<4,4>}則：2,3能蓋住1；4能蓋住2；4不能蓋住1第66頁，共80頁，2023年，2月20日，星期三偏序集的哈斯圖(1)去掉箭頭；（蓋?。?2)去掉間接關(guān)系；（傳遞）(3)去掉環(huán)。（自反的）第67頁，共80頁，2023年，2月20日，星期三哈斯圖實(shí)例例4.5.5：畫出<{1,2,3,4,5,6,7,8,9},R整除>

和<P({a,b,c}),R>第68頁，共80頁，2023年，2月20日，星期三全序關(guān)系的哈斯圖：全序集中全部元素可以排序，它的哈斯圖為一條直線。也稱為線序集。集合A上的偏序關(guān)系與哈斯圖是一一對(duì)應(yīng)的。課后習(xí)題：4.16第69頁，共80頁，2023年，2月20日，星期三第70頁，共80頁，2023年，2月20日，星期三(2)

若yA，使得(x)(xAyx)，則稱y是A的極大元

(沒有比我大的)(1)

若yA，使得(x)(xA