集合與關(guān)系節(jié)

集合與關(guān)系節(jié)第三章集合與關(guān)系3.4序偶與笛卡爾積3.5關(guān)系及其表示3.6關(guān)系的性質(zhì)3.7關(guān)系的運(yùn)算（復(fù)合關(guān)系和逆關(guān)系）3.8關(guān)系的閉包運(yùn)算3.9相容關(guān)系與覆蓋3.10等價(jià)關(guān)系與劃分3.12偏序關(guān)系第2頁,共87頁，2024年2月25日，星期天2024/5/43-4序偶與笛卡爾積關(guān)系理論歷史悠久。它與集合論、數(shù)理邏輯、組合學(xué)、圖論和布爾代數(shù)都有密切的聯(lián)系。關(guān)系是日常生活以及數(shù)學(xué)中的一個(gè)基本概念，例如：兄弟關(guān)系，師生關(guān)系、位置關(guān)系、大小關(guān)系、等于關(guān)系、包含關(guān)系等。第3頁,共87頁，2024年2月25日，星期天2024/5/43-4序偶與笛卡爾積另外，關(guān)系理論還廣泛用于計(jì)算機(jī)科學(xué)技術(shù)，如計(jì)算機(jī)程序的輸入、輸出關(guān)系；數(shù)據(jù)庫的數(shù)據(jù)特性關(guān)系；數(shù)據(jù)結(jié)構(gòu)本身就是一個(gè)關(guān)系等。在某種意義下，關(guān)系是有聯(lián)系的一些對象相互之間的各種比較行為。第4頁,共87頁，2024年2月25日，星期天2024/5/43-4序偶與笛卡爾積

序偶與笛卡爾積上,下；左，右；3<4；中國地處亞洲；平面上點(diǎn)的坐標(biāo)（x,y）等。特征：成對出現(xiàn)、具有一定的順序。定義

由兩個(gè)元素x,y按照一定的次序組成的二元組稱為有序偶對(序偶),記作<x,y>,其中x為第一個(gè)元素，y為第二個(gè)元素。第5頁,共87頁，2024年2月25日，星期天2024/5/4用序偶表示下列語句中的次序關(guān)系(1)平面上點(diǎn)A的橫坐標(biāo)是x,縱坐標(biāo)是y,其中x,y∈R；(2)成都是四川的省會；(3)英語課本在書桌上；(4)左，右關(guān)系。解各語句的序偶表示如下：(1)<x,y>，x,y∈R；(2)<成都，四川>；(3)<英語課本，書桌>；(4)<左、右>。第6頁,共87頁，2024年2月25日，星期天2024/5/4定義6.2.2給定序偶<a,b>和<c,d>，如果a=c，b=d，則<a,b>=<c,d>。1.序偶可以看作是具有兩個(gè)元素的集合，2.但是序偶中的兩個(gè)元素具有確定的次序。即<a,b>≠<b,a>但是{a,b}={b,a}.第7頁,共87頁，2024年2月25日，星期天2024/5/4N重有序組定義由n個(gè)元素a1,a2,a3,…,an按照一定次序組成的n元組稱為n重有序組(n-Type)(Vector)，記作:<a1,…,an>例用n重有序組描述下列語句。（1）中國四川成都電子科技大學(xué)計(jì)算機(jī)學(xué)院；（2）2006年9月10日18點(diǎn)16分25秒；（3）16減5再加3除以7等于2。解各語句的n重有序組表示如下：（1）<中國,四川,成都,電子科技大學(xué),計(jì)算機(jī)學(xué)院>（2）<2006,9,10,18,16,25>；（3）<16,5,3,7,2>。定義給定n重有序組<a1,a2,...,an>和<b1,b2,…，bn>。如果ai＝bi(i＝1,2,…，n)，則<a1,a2,...,an>=<b1,b2,…，bn>。第8頁,共87頁，2024年2月25日，星期天2024/5/4笛卡爾乘積定義設(shè)A，B是兩個(gè)集合，稱集合：A×B＝{<x,y>|(x∈A)∧(y∈B)}為集合A與B的笛卡爾積DescartesProduct)。注意：（1）集合A與B的笛卡兒積A×B仍然是集合；（2）集合A×B中的元素是序偶，序偶中的第一個(gè)元素取自A，第二個(gè)元素取自B。第9頁,共87頁，2024年2月25日，星期天2024/5/4例設(shè)A={a},B={b,c},C=Φ,D={1,2}，請分別寫出下列笛卡兒積中的元素。（1）A×B,B×A；（2）A×C,C×A；（3）A×(B×D),(A×B)×D。解根據(jù)笛卡兒積的定義，有（1）A×B={<a,b>,<a,c>},B×A={<b,a>,<c,a>}；（2）A×C=Φ,C×A=Φ；第10頁,共87頁，2024年2月25日，星期天2024/5/4解（續(xù)）（3）因?yàn)锽×D={<b,1>,<b,2>,<c,1>,<c,2>}，所以A×(B×D)={<a,<b,1>>,<a,<b,2>>,<a,<c,1>>,<a,<c,2>>}。同理，(A×B)×D={<<a,b>,1>,<<a,b>,2>,<<a,c>,1>,<<a,c>,2>}。第11頁,共87頁，2024年2月25日，星期天2024/5/4注意由例我們可以看出：（1）笛卡兒積不滿足交換律；（2）A×B=Φ當(dāng)且僅當(dāng)A=Φ或者B=Φ；（3）笛卡兒積不滿足結(jié)合律；（4）對有限集A,B，有|A×B|=|B×A|=|A|×|B|。第12頁,共87頁，2024年2月25日，星期天2024/5/4集合相等

兩個(gè)集合互相包含等式成立

兩個(gè)集合相等定理設(shè)A,B,C是任意三個(gè)集合，則（1）A×(B∪C)=(A×B)∪(A×C)；（2）(B∪C)×A=(B×A)∪(C×A)；（3）A×(B∩C)=(A×B)∩(A×C)；（4）(B∩C)×A=(B×A)∩(C×A)。分析顯然，待證等式兩端都是集合第13頁,共87頁，2024年2月25日，星期天2024/5/4定理分析對（1）A×(B∪C)=(A×B)∪(A×C)

A×(B∪C)

(A×B)∪(A×C),(A×B)∪(A×C)

A×(B∪C)利用按定義證明方法，首先敘述包含關(guān)系的定義，即首先敘述A×(B∪C)

(A×B)∪(A×C)的定義：對任意<x,y>∈A×(B∪C)，…，有<x,y>∈(A×B)∪(A×C)，則A×(B∪C)

(A×B)∪(A×C)。同理可分析(A×B)∪(A×C)

A×(B∪C)。第14頁,共87頁，2024年2月25日，星期天2024/5/4定理證明（1）對任意<x,y>∈A×(B∪C)，由笛卡兒積的定義知，x∈A且y∈B∪C；由并運(yùn)算定義知，y∈B或者y∈C。于是有x∈A且y∈B或者x∈A且y∈C。從而，<x,y>∈A×B或者<x,y>∈A×C。即<x,y>∈(A×B)∪(A×C)，所以，A×(B∪C)

(A×B)∪(A×C)。第15頁,共87頁，2024年2月25日，星期天2024/5/4定理證明（續(xù)）另一方面，對任意<x,y>∈(A×B)∪(A×C)，由并運(yùn)算定義知,<x,y>∈A×B或者<x,y>∈A×C。由笛卡兒積的定義知,x∈A且y∈B或x∈A且y∈C。進(jìn)一步有x∈A且y∈B∪C，從而<x,y>∈A×(B∪C)。所以(A×B)∪(A×C)

A×(B∪C)。于是，根據(jù)定理1.2.2，有A×(B∪C)=(A×B)∪(A×C)。(2)、(3)和(4)的證明作為練習(xí)，自證。第16頁,共87頁，2024年2月25日，星期天2024/5/4定理設(shè)A,B,C,D是任意四個(gè)集合，則(A×B)

(C×D)

A

C，B

D。證明充分性(

)：對任意<x,y>∈A×B，有x∈A且y∈B。又因?yàn)锳

C，B

D，所以有x∈C且y∈D，即<x,y>∈C×D，從而(A×B)

(C×D)。第17頁,共87頁，2024年2月25日，星期天2024/5/4定理證明（續(xù)）必要性(

)：對任意的x∈A，y∈B，有<x,y>∈A×B。又因?yàn)?A×B)

(C×D)，所以<x,y>∈C×D。根據(jù)笛卡兒積的定義有x∈C且y∈D，從而A

C，B

D。綜上所述，定理成立。第18頁,共87頁，2024年2月25日，星期天定理：若C，則AB(ACBC)(CACB)第19頁,共87頁，2024年2月25日，星期天2024/5/4定義設(shè)A1,A2,…,An是n個(gè)集合，稱集合A1×A2×…×An

={<a1,a2,…,an>|(ai∈Ai)∧i∈{1,2,3,…,n}}為集合A1,A2,…,An的笛卡兒積(DescartesProduct)當(dāng)A1=A2=…=An=A時(shí)，有A1×A2×…×An=An。第20頁,共87頁，2024年2月25日，星期天2024/5/4當(dāng)集合A1,A2,…,An都是有限集時(shí)，|A1×A2×…×An|=|A1|×|A2|×…×|An|。第21頁,共87頁，2024年2月25日，星期天日常生活中，大家熟知一些常見關(guān)系,例：家庭集合，有父子關(guān)系、兄弟關(guān)系等。全校同學(xué)作為一個(gè)集合，有同班關(guān)系，同組關(guān)系。把任一序偶的集合確定了一個(gè)二元關(guān)系R,R中任一序偶<a,b>可記作<a,b>

R或aRb,不在R中的序偶<x,y>可記作<x,y>

R例：一組同學(xué)為集合A，A有4名同學(xué)，其中1，2同寢室，3，4同寢室。則：R={<1，1>，<1，2>，<2，1>，<2，2>，<3，3>，<3，4>，<4，3>，<4，4>}反映了同寢室關(guān)系，

3-5關(guān)系及其表示第22頁,共87頁，2024年2月25日，星期天

關(guān)系及其表示

定義

設(shè)A，B是任意兩個(gè)集合，A×B的子集R稱為從A到B的二元關(guān)系，當(dāng)A=B時(shí)，稱R為A上的二元關(guān)系。從上述定義可以看出A到B的二元關(guān)系，也是序偶的集合。若<a,b>∈R，則稱a與b有關(guān)系R，記作aR

b。若，則稱a與b沒有關(guān)系R，記作。例如：設(shè)A={a,b,c,d},B={0,1}，則R={﹤a,0﹥,﹤b,0﹥,﹤c,1﹥}就是一個(gè)從A到B的二元關(guān)系。。第23頁,共87頁，2024年2月25日，星期天①：A×B的子集叫做A到B上的一個(gè)二元關(guān)系。

②：A1×A2×A3的子集叫做A1×A2×A3上的一個(gè)二元關(guān)系。

③:A1×A2×…An的子集叫做A1×A2×…An上的一個(gè)n元關(guān)系。

④:A×A×A×…A的子集叫做A上的n元關(guān)系。關(guān)系及其表示

第24頁,共87頁，2024年2月25日，星期天

關(guān)系及其表示

定義設(shè)A，B是兩個(gè)集合，R是從A到B上的二元關(guān)系，則(1)若存在b∈B，使得<a,b>∈R，則所有這樣的a∈A組成的集合，稱為二元關(guān)系R的定義域。記作dom(R)或D(R)，即

(2)若存在a∈A，使得<a,b>∈R，則所有這樣的b∈B組成的集合，稱為二元關(guān)系R的值域。記作ran(R)或R(R)，即

R的定義域和值域一起稱作R的域，記作FLDR，即FLDR=dom(R)∪ran(R)從X到Y(jié)的二元關(guān)系R，也可以用圖解的方式表示，X和Y是兩個(gè)集合。xi是集合X中的元素，yj是集合Y中的元素，當(dāng)且僅當(dāng)xiRyj時(shí)，才有一條從xi指向yj的有向邊。第25頁,共87頁，2024年2月25日，星期天

關(guān)系及其表示圖4.1.1圖解表示法第26頁,共87頁，2024年2月25日，星期天例

設(shè)R1={<x，y>|（x，y

Z）∧(x≥y)} R2={<x，y>|（x，y

Z）∧(y=2x+1)} R3={<x，y>|（x，y

Z）∧(|x|=|y|=5)}都是定義在整數(shù)集Z上的關(guān)系，求他們的定義域，值域和域。解：

domR1=Z，ranR1=Z， fldR1=Z；

domR2=Z，ranR2={2y+1|y∈Z}，fldR2=Z；

domR3={5，-5}，ranR3={5，-5}，fldR3={5，-5}。例

設(shè)R={<1，2>，<1，3>，<2，4>，<4，3>}，則解：

domR={1，2，4}ranR={2，3，4}fldR={1，2，3，4}第27頁,共87頁，2024年2月25日，星期天定義

設(shè)R是A×A

×…×A的子集，若R=

,則稱R為A的空關(guān)系。若R=A×A×…×A,則稱R為A的全域關(guān)系。

R={<x,x>|x

A}稱為A上恒等關(guān)系，記為IA

關(guān)系及其表示----幾個(gè)特殊關(guān)系第28頁,共87頁，2024年2月25日，星期天

關(guān)系及其表示

定理若R和S是從集合A到B上的兩個(gè)二元關(guān)系，則R和S的并、交、補(bǔ)、差也是A到B上的二元關(guān)系。證明：因?yàn)镽和S是從集合A到B上的二元關(guān)系所以有R?A×B，S?A×B。從而有

即A∩B和A∪B都是A到B上的二元關(guān)系。又因?yàn)?/p>

所以~R和~S也是A到B上的二元關(guān)系。由于

故R-S也是A到B上的二元關(guān)系。第29頁,共87頁，2024年2月25日，星期天

關(guān)系的矩陣表示設(shè)X={a,b,c},Y={0,1,2,3}，R={<a,1>,

<b,2>,<c,0>}?？傻藐P(guān)系R的矩陣表示如下：

由上例看出，給定從有限集X到Y(jié)的二元關(guān)系R，就可以構(gòu)造出它的關(guān)系矩陣。給定兩個(gè)有限集合和，并且R是從X到Y(jié)的二元關(guān)系。如果有

則稱矩陣是R的關(guān)系矩陣，并記作。

第30頁,共87頁，2024年2月25日，星期天例

設(shè)X={x1，x2，x3，x4}，Y={y1，y2，y3}。X到Y(jié)的關(guān)系R為R={<x1，y1>，<x1，y3>，<x2，y3>，<x4，y2>}。則R的關(guān)系矩陣是例

設(shè)A={1，2，3，4}，A上的大于關(guān)系“＞”定義為={<2，1>，<3，1>，<3，2>，<4，1>，<4，2>，<4，3>}。則關(guān)系＞的關(guān)系矩陣是集合A中元素的排序是1，2，3，4，即1對應(yīng)第1行、第1列，例如<2，1>就是第2行與第1列相交處的點(diǎn)，依此類推。第31頁,共87頁，2024年2月25日，星期天關(guān)系及其表示--關(guān)系的圖形表示設(shè)畫出R的關(guān)系圖。解：R的關(guān)系圖如圖所示。

R的關(guān)系圖

第32頁,共87頁，2024年2月25日，星期天3-6關(guān)系的性質(zhì)定義3.6.1設(shè)R是集合A上的二元關(guān)系。若對任意一個(gè)a∈A，都有aRa，即<a,a>∈R

，則稱R是自反的。即R是自反的。也就是說，在自反關(guān)系中，每個(gè)元素都和自己有關(guān)系。例如，設(shè)R是整數(shù)集上的≥關(guān)系，則R是自反的。因?yàn)閷τ谌我庖粋€(gè)整數(shù)a，都有a≥a成立。

定義3.6.2

設(shè)R是集合A上的二元關(guān)系。若對任意一個(gè)a∈A,都有，即，則稱R是反自反的。即R是反自反的。也就是說，在反自反關(guān)系中，每個(gè)元素都和自己沒有關(guān)系。例如，設(shè)R是整數(shù)集上的<關(guān)系，則R是反自反的。因?yàn)閷τ谌我庹麛?shù)a，都有a<a

不成立。一個(gè)關(guān)系不是自反的，不一定就是反自反的。同樣，一個(gè)關(guān)系不是反自反的，也不一定就是自反的。例如：在集合上定義的二元關(guān)系既不是自反的也不是反自反的。第33頁,共87頁，2024年2月25日，星期天3-6關(guān)系的性質(zhì)定義3.6.3設(shè)R是集合A上的二元關(guān)系。若對任意的a,b∈A，當(dāng)<a,b>∈R時(shí)，就有<b,a>∈R，則稱R是對稱的。即

R是對稱的

例如，平面上各三角形集合中，三角形的相似關(guān)系是對稱的。

定義3.6.4

設(shè)R是集合A上的二元關(guān)系。若對任意的a,b∈A，當(dāng)<a,b>∈R且<b,a>∈R時(shí)，有a=b，則稱R是反對稱的。即

R是反對稱的上述定義也可表述為：對任意的a,b∈A，若<a,b>∈R且a≠

b，則。例如，在A的冪集中各元素之間的?關(guān)系是反對稱的。實(shí)數(shù)集合上的≤關(guān)系也都是反對稱的。值得注意的是，存在既是對稱的又是反對稱的二元關(guān)系。如，恒等關(guān)系就是對稱關(guān)系，同時(shí)也是反對稱關(guān)系。又如，R既是對稱的，也是反對稱的。也有既不是對稱的，又不是反對稱的關(guān)系存在??！

第34頁,共87頁，2024年2月25日，星期天3-6關(guān)系的性質(zhì)

定義3.6.5設(shè)R是集合A上的二元關(guān)系。若對任意的a,b,c∈A，當(dāng)<a,b>∈R且<b,c>∈R時(shí)，就有<a,c>∈R，則稱R是傳遞的。即

R是傳遞的在判定關(guān)系的傳遞性時(shí)，要對所有的有序?qū)Χ紮z查之后，才能判斷一個(gè)關(guān)系的傳遞性是否成立，因此，判斷傳遞性是比較復(fù)雜的。例如，設(shè)，則關(guān)系R滿足傳遞性。例

在所有人集合P上的關(guān)系，說明R的性質(zhì)。解：R是自反的，因?yàn)槊總€(gè)人和自己有同一祖先；R是對稱的，因?yàn)槿绻缀鸵矣型蛔嫦?，那么乙和甲也有同一祖先；R是傳遞的，因?yàn)槿艏缀鸵矣型蛔嫦?，乙和丙有同一祖先，那么甲和丙也有同一祖先。?5頁,共87頁，2024年2月25日，星期天3-6關(guān)系的性質(zhì)

判別關(guān)系的性質(zhì)，也可以從關(guān)系矩陣和關(guān)系圖上給予驗(yàn)證。（1）若關(guān)系是自反的，當(dāng)且僅當(dāng)在關(guān)系矩陣中，對角線上的所有元素都是1；在關(guān)系圖上，每個(gè)節(jié)點(diǎn)都有一條自己到自己的邊（或稱圈）。（2）若關(guān)系是反自反的，當(dāng)且僅當(dāng)關(guān)系矩陣中對角線上的元素都為零；在關(guān)系圖中，每個(gè)節(jié)點(diǎn)都沒有自己到自己的邊。（3）若關(guān)系是對稱的，當(dāng)且僅當(dāng)其關(guān)系矩陣是對稱的；在關(guān)系圖上，任意兩個(gè)節(jié)點(diǎn)間若有弧，必定是成對出現(xiàn)的。（4）若關(guān)系是反對稱的，當(dāng)且僅當(dāng)關(guān)系矩陣以主對角線為對稱的元素不能同時(shí)為1，且在關(guān)系圖上兩個(gè)不同節(jié)點(diǎn)間的弧不能成對出現(xiàn)。第36頁,共87頁，2024年2月25日，星期天任何集合上的相等關(guān)系實(shí)數(shù)集合上的小于等于關(guān)系非空集合上的空關(guān)系基數(shù)大于1的集合上的全域關(guān)系xRy

(x-y)/2是整數(shù)自反性反自反性對稱性反對稱性傳遞性Y

N

Y

Y

Y

Y

N

N

N

Y

NYYY

YYNYNYYNYNY舉例第37頁,共87頁，2024年2月25日，星期天3-7關(guān)系的運(yùn)算(復(fù)合關(guān)系和逆關(guān)系)

定義4.3.1

設(shè)R是從集合X到集合Y的二元關(guān)系，如果將R中每一對序偶的元素順序互換，所得到的新的集合則稱為R的逆關(guān)系，記作，即

由逆關(guān)系的定義可知，的關(guān)系圖可以通過將R的關(guān)系圖的所有有向弧逆轉(zhuǎn)得到，它的關(guān)系矩陣可以通過將R的關(guān)系矩陣轉(zhuǎn)置得到。例4.3.1設(shè)，求。解：。第38頁,共87頁，2024年2月25日，星期天3-7關(guān)系的運(yùn)算(復(fù)合關(guān)系和逆關(guān)系)

定理

設(shè)R和S都是從X到Y(jié)的二元關(guān)系，則下列各式成立。（1）（2）（3）（4），這里~R表示（5）（6）若，則第39頁,共87頁，2024年2月25日，星期天3-7關(guān)系的運(yùn)算(復(fù)合關(guān)系和逆關(guān)系)

定理

設(shè)R是A上的二元關(guān)系，則（1）R在A上是自反的，當(dāng)且僅當(dāng)。（2）R在A上是反自反的，當(dāng)且僅當(dāng)。（3）R在A上是對稱的，當(dāng)且僅當(dāng)。（4）R在A上是反對稱的，當(dāng)且僅當(dāng)。第40頁,共87頁，2024年2月25日，星期天3-7

關(guān)系的運(yùn)算(復(fù)合關(guān)系和逆關(guān)系)

定義

設(shè)R是從集合X到集合Y的二元關(guān)系，S是從集合Y到Z的關(guān)系，則R?

S稱為R和S的合成關(guān)系，定義為

R?

S稱為關(guān)系的合成運(yùn)算。設(shè)R是從集合到集合的關(guān)系，S是從集合到集合的關(guān)系，則是一個(gè)的矩陣，是一個(gè)的矩陣。依照普通矩陣乘法的運(yùn)算，可以定義兩個(gè)關(guān)系矩陣的合成運(yùn)算。第41頁,共87頁，2024年2月25日，星期天3-7關(guān)系的運(yùn)算(復(fù)合關(guān)系和逆關(guān)系)由上述前兩個(gè)矩陣可以構(gòu)造這兩個(gè)矩陣的合成矩陣，記作。元素可由下式得到：其中?！藕汀牡倪\(yùn)算規(guī)則如下：

兩個(gè)關(guān)系的合成運(yùn)算，就是將布爾關(guān)系矩陣做乘法，所得結(jié)果即為合成關(guān)系矩陣。

第42頁,共87頁，2024年2月25日，星期天3-7關(guān)系的運(yùn)算(復(fù)合關(guān)系和逆關(guān)系)定理設(shè)X,Y,Z和W都是集合。R是從集合X到Y(jié)的關(guān)系，S是從集合Y到Z的關(guān)系，T是從集合Z到W的關(guān)系。于是有(R?

S)?

T=R?(S

?

T)即關(guān)系的合成運(yùn)算滿足結(jié)合律。證明：對任意的<x,w>∈(R?

S)?

T，根據(jù)合成關(guān)系的定義可知，必然存在z∈Z，使得<x,z>∈(R?

S)，<z,w>∈T。又因?yàn)?lt;x,z>∈(R?

S)，故必存在y∈Y，使得<x,y>∈R并且<y,z>∈S。由<y,z>∈S且<z,w>∈T，根據(jù)合成關(guān)系的定義知<y,w>∈(S

?

T)，又因?yàn)?lt;x,y>∈R且<y,w>∈S

?

T，得到<x,w>∈R?(S

?

T)。故由<x,w>的任意性可知(R?

S)?

T?

R?(S

?

T)。同理可證R?(S?

T)?(R?

S)?

T。綜上所述，得到(R?

S)?

T=R?(S

?

T)，即關(guān)系的合成運(yùn)算滿足結(jié)合律。

一般來說，關(guān)系的合成運(yùn)算是不滿足交換律的，即R?

S

≠S

?

R。

第43頁,共87頁，2024年2月25日，星期天3-7關(guān)系的運(yùn)算(復(fù)合關(guān)系和逆關(guān)系)定義設(shè)R是集合X中的二元關(guān)系，n∈N（N是自然數(shù)集），于是R的n次冪定義為：（1），即是R中的恒等關(guān)系。（2）。定理設(shè)R是集合X中的二元關(guān)系。設(shè)m,n∈N。則有（1）（2）第44頁,共87頁，2024年2月25日，星期天3-7關(guān)系的運(yùn)算(復(fù)合關(guān)系和逆關(guān)系)定理：設(shè)T為A到B的關(guān)系，S為B到C的關(guān)系，

證明：第45頁,共87頁，2024年2月25日，星期天3-7關(guān)系的運(yùn)算(復(fù)合關(guān)系和逆關(guān)系)定理設(shè)A為含有n個(gè)元素的集合，R是A上的二元關(guān)系，則必存在s和t，使得

定理設(shè)R是A上的二元關(guān)系，則R在A上是傳遞的，當(dāng)且僅當(dāng)

第46頁,共87頁，2024年2月25日，星期天

例題設(shè)R是A上的一個(gè)二元關(guān)系，（1）如果R是自反的，則Rc一定是自反的嗎？（2）如果R是對稱的，則Rc一定是對稱的嗎？（3）如果R是傳遞的，則Rc一定是傳遞的嗎？(4)如果R是反自反的，則Rc一定是反自反的嗎？(5)如果R是反對稱的，則Rc一定是反對稱的嗎？第47頁,共87頁，2024年2月25日，星期天3.8

關(guān)系的閉包運(yùn)算

定義3.8.1設(shè)R是集合A上的二元關(guān)系。如果有另一A上的關(guān)系R’

滿足：（1）R’是自反的；（2）R’

?R；（3）對A上的任意自反關(guān)系R’’，若R’’?R，則R’’?R’。那么稱R’是R的自反閉包，并記作r(R)。定義3.8.2設(shè)R是集合A上的二元關(guān)系。如果有另一A上的關(guān)系R’滿足：（1）R’是對稱的；（2）R’

?R；（3）對A上的任意對稱關(guān)系R’’，若R’’?R，則R’’?R’。那么稱R’是R的對稱閉包，并記作s(R)。定義3.8.3設(shè)R是集合A上的二元關(guān)系。如果有另一A上的關(guān)系R’滿足：（1）R’是傳遞的；（2）R’

?R；（3）對A上的任意對稱關(guān)系R’’，若R’’?R，則R’’?R’。那么稱R’是R的傳遞閉包，并記作t(R)(也記作R+)。

第48頁,共87頁，2024年2月25日，星期天3.8

關(guān)系的閉包運(yùn)算

定理3.8.1設(shè)R是集合A上的二元關(guān)系，則：(1)

自反閉包

(2)

對稱閉包

（3）傳遞閉包特別地，若則

例3.8.1設(shè)X={1,2,3}，R是X中的二元關(guān)系，R={<1,2>,<2,3>,<3,1>}。求r(R)、s(R)和t(R)

第49頁,共87頁，2024年2月25日，星期天3.8

關(guān)系的閉包運(yùn)算求關(guān)系R的傳遞閉包t(R)(也就是R+)的Warshall算法：(1)置新矩陣A:=MR(2)置i:=1(3)對所有j如果A[j,i]=1,則對k=1,2,…,nA[j,k]:=A[j,k]+A[i,k](4)i:=i+1(5)如果i≤n，則轉(zhuǎn)到步驟(3),否則停止。第50頁,共87頁，2024年2月25日，星期天3.8

關(guān)系的閉包運(yùn)算定理3.8.2設(shè)R是集合A上的二元關(guān)系，則（1）R是自反的，當(dāng)且僅當(dāng)r(R)=R；（2）R是對稱的，當(dāng)且僅當(dāng)s(R)=R；（3）R是傳遞的，當(dāng)且僅當(dāng)t(R)=R。定理3.8.3設(shè)R是集合A上的二元關(guān)系，則（1）若R是自反的，則s(R)和t(R)也是自反的。（2）若R是對稱的，則r(R)和t(R)也是對稱的。（3）若R是傳遞的，則r(R)也是傳遞的。第51頁,共87頁，2024年2月25日，星期天3.8

關(guān)系的閉包運(yùn)算定理3.8.4設(shè)R1和R2是集合A上的二元關(guān)系，且，則（1）（2）（3）二元關(guān)系的閉包仍然是二元關(guān)系，還可以求它的閉包。例如，R是A上的二元關(guān)系，r(R)是它的自反閉包，還可以求r(R)的對稱閉包。r(R)的對稱閉包記為s(r(R))，簡記為sr(R)，讀作R的自反閉包的對稱閉包。其余類似。定理3.8.5設(shè)R是集合A上的二元關(guān)系，則（1）（2）（3）第52頁,共87頁，2024年2月25日，星期天3-9集合的劃分和覆蓋定義3-9.1設(shè)A為非空集合，S={S1,S2,…,Sm},其中SiA，Si≠，i=1,2,…m且則集合S稱為集合A的覆蓋。如果除了以上條件外，還滿足Si

Sj=

(i≠j)，則集合S稱為集合A的劃分。第53頁,共87頁，2024年2月25日，星期天3-9集合的劃分和覆蓋

定義3-9.2若{A1,A2,…,Ar}和{B1,B2,…,Bs}都是集合A的劃分，則其中所有Ai

Bj≠

組成的集合，稱為是原來兩種劃分的交叉劃分。定理3-9.1若{A1,A2,…,Ar}和{B1,B2,…,Bs}都是集合A的劃分，則其交叉劃分也是原集合A的一種劃分。第54頁,共87頁，2024年2月25日，星期天3-9集合的劃分和覆蓋定義3-9.3給定集合A的任意兩個(gè)劃分{A1,A2,…,Ar}和{B1,B2,…,Bs}，若對于每一個(gè)Aj均有Bk使Aj

Bk,則劃分{A1,A2,…,Ar}稱為劃分{B1,B2,…,Bs}的加細(xì)。定理3-9.2任何兩種劃分的交叉劃分，都是原來各劃分的一種加細(xì)。第55頁,共87頁，2024年2月25日，星期天3-9集合的劃分和覆蓋--例題例題1設(shè){A1,A2,…,Am}是集合A的一個(gè)劃分，我們定義A上的二元關(guān)系R,使<a,b>∈R當(dāng)且僅當(dāng)a和b在這個(gè)劃分的同一塊中，證明：R是自反的、對稱的、傳遞的。例題2設(shè){A1,A2,…,An}是集合A的劃分,若A

B≠

，1≤i≤n,試證明{A1

B,A2

B,…,Ar

B}是集合A

B的劃分。第56頁,共87頁，2024年2月25日，星期天3.10等價(jià)關(guān)系與等價(jià)類

定義3.10.1設(shè)R是定義在集合A上的二元關(guān)系，若R是自反的、對稱的和傳遞的，則稱R是等價(jià)關(guān)系。顯然，若關(guān)系R是等價(jià)關(guān)系，則也必然是相容關(guān)系。反之，則不一定成立。例設(shè)，在集合A上定義關(guān)系R如下證明R是等價(jià)關(guān)系并畫出其關(guān)系圖。解：由R的定義可知，

R的關(guān)系圖為：第57頁,共87頁，2024年2月25日，星期天3.10等價(jià)關(guān)系與等價(jià)類

下面來證明R是等價(jià)關(guān)系：（1）對于任意的，因?yàn)閍-a可被3整除，故，因此R是自反的。（2）對于任意的，若，則a-b可被3整除，又因?yàn)閎-a=-(a-b)，故b-a也可被3整除。即，因此R是對稱的。（3）對于任意的，若，，則a-b和b-c均可被3整除，又因?yàn)閍-c=(a-b)+(b-c)，故a-c也可被3整除。即，因此R是傳遞的。綜上所述，知R是等價(jià)關(guān)系。第58頁,共87頁，2024年2月25日，星期天3.10等價(jià)關(guān)系與等價(jià)類定義3.10.2設(shè)R是集合A上的等價(jià)關(guān)系，對于任一，集合稱為元素a形成的等價(jià)類。定理4.6.1設(shè)R是集合A上的等價(jià)關(guān)系，則有（1），是A的非空子集。（2），如果，則。（3），如果，則。（4）。（5）aRb當(dāng)且僅當(dāng)[a]R=[b]R定義4.6.3設(shè)R是非空集合A上的等價(jià)關(guān)系。由A中各元素生成的關(guān)于R的等價(jià)類的集合，稱為A關(guān)于R的商集，記作。例如，例1中的集合A關(guān)于R的商集為

第59頁,共87頁，2024年2月25日，星期天練習(xí)題設(shè)集合A={1,2,3,4,5,6,7},說明A上的下列二元關(guān)系哪些是等價(jià)關(guān)系并求其等價(jià)類,如果不是說明原因。(1)R={<1,2>,<2,1>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<6,6>,<7,7>}(2)S={<1,1>,<2,2>,<3,3>,<4,5>,<5,4>,<6,7>,<7,6>,<4,4>,<5,5>,<6,6>,<7,7>}(3)T={<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<6,6>,<7,7>,<1,2>,<3,4>,<5,6>,<6,7>}第60頁,共87頁，2024年2月25日，星期天3.10等價(jià)關(guān)系與等價(jià)類給定非空集合A，若有集合，其中，，且，同時(shí)有則稱S是A的劃分。定理3.10.2設(shè)R是非空集合A上的等價(jià)關(guān)系，則A關(guān)于R的商集A/R是集合A上的一種劃分。

定理3.10.2給出了根據(jù)集合的等價(jià)關(guān)系求出其相應(yīng)劃分的方法。

定理3.10.3設(shè)S是非空集合A中的一種劃分。,

在集合A上定義關(guān)系R如下：

則R是集合A中的等價(jià)關(guān)系。定理3.10.3給出了由集合的劃分求等價(jià)關(guān)系的方法。第61頁,共87頁，2024年2月25日，星期天3.10等價(jià)關(guān)系與等價(jià)類注1：集合A上的等價(jià)關(guān)系R，決定了A的一個(gè)劃分，該劃分就是商集A/R注2：集合A的一個(gè)劃分確定了A的元素之間的一個(gè)等價(jià)關(guān)系。定理：設(shè)R1和R2是非空集合A上的等價(jià)關(guān)系，則R1=R2當(dāng)且僅當(dāng)A/R1=A/R2其中A/R1={[a]R1|a∈A},A/R2={[a]R2|a∈A}第62頁,共87頁，2024年2月25日，星期天練習(xí)題一、已知集合A={1,2,3,4,5,6}上的劃分S={{1,2},{3,4,5},{6}},求由此劃分所確定的A上的等價(jià)關(guān)系。二、已知集合A={1,2,3,4,5,6}上的等價(jià)關(guān)系R={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>,<4,4>,<4,5>,<5,4>,<5,5>,<6,6>},求由此等價(jià)關(guān)系所確定的A上的劃分。第63頁,共87頁，2024年2月25日，星期天3-11

相容關(guān)系定義3.11.1設(shè)R是集合A上的二元關(guān)系，若R是自反的和對稱的，則稱R是相容關(guān)系。例設(shè)A={cat,teacher,cold,desk,knife,by},在A上定義關(guān)系R如下

試畫出R的關(guān)系圖和關(guān)系矩陣，并說明R是相容關(guān)系。解：令則

的關(guān)系圖如下面圖4.5.1所示第64頁,共87頁，2024年2月25日，星期天3-11

相容關(guān)系

圖4.5.1關(guān)系矩陣

從關(guān)系圖和關(guān)系矩陣中可以看出，關(guān)系R是相容關(guān)系。因?yàn)樵陉P(guān)系圖中，每個(gè)節(jié)點(diǎn)都有環(huán)且任意兩個(gè)節(jié)點(diǎn)之間如有連線，必有雙向線；在關(guān)系矩陣中，其對角線上各元素均為1，且關(guān)系矩陣以對角線為軸對稱。約定：相容關(guān)系的關(guān)系圖上，不畫出每個(gè)元素的環(huán)、每對雙向線，只畫出無向連線。相容關(guān)系的關(guān)系矩陣中，只畫出主對角線以下的下三角矩陣。第65頁,共87頁，2024年2月25日，星期天3-11

相容關(guān)系

圖4.5.2關(guān)系圖圖4.5.3關(guān)系矩陣第66頁,共87頁，2024年2月25日，星期天3.11相容關(guān)系

給定非空集合A，設(shè)有集合，其中，且，，且，則稱集合S為集合A的覆蓋。由覆蓋可以構(gòu)造相容關(guān)系。例如，設(shè)，，，則S和T均是A的覆蓋，且兩者不同。定理3.11.1給定集合A上的一個(gè)覆蓋，由它確定的關(guān)系是相容關(guān)系。

從這個(gè)定理可以看出，給定集合A上的任一覆蓋，就可以構(gòu)造出與此覆蓋相對應(yīng)的一個(gè)相容關(guān)系。但是，請注意：

不同的覆蓋可以構(gòu)造出相同的相容關(guān)系。第67頁,共87頁，2024年2月25日，星期天相容類：設(shè)r是集合A上的相容關(guān)系，若C

A，如果對于C中任意兩個(gè)元素a1,a2有a1ra2，稱C是由相容關(guān)系r產(chǎn)生的相容類。第68頁,共87頁，2024年2月25日，星期天3-11

相容關(guān)系定義3.11.3設(shè)R是集合A中的相容關(guān)系，若有，使得對于任意的，必有，并且在中，沒有任何一個(gè)元素與中的所有元素都有R關(guān)系，則稱是由R產(chǎn)生的最大相容類。例如，例4.5.1中的相容關(guān)系有以下4個(gè)最大相容類：

由R所產(chǎn)生的所有最大相容類所構(gòu)成的集合，稱為集合A的完全覆蓋。根據(jù)任意一個(gè)給定的集合A的相容關(guān)系R，求它的完全覆蓋有兩種常用的方法。第69頁,共87頁，2024年2月25日，星期天

在相容關(guān)系圖中，最大完全多邊形的頂點(diǎn)集合，就是最大相容類。所謂完全多邊形，就是其每個(gè)頂點(diǎn)都與其它頂點(diǎn)連接的多邊形。例如一個(gè)三角形是完全多邊形，一個(gè)四邊形加上兩條對角線就是完全多邊形。第70頁,共87頁，2024年2月25日，星期天求最大相容關(guān)系的關(guān)系圖法例3.11.2設(shè)集合上的相容關(guān)系的簡化關(guān)系圖如圖4.5.4所示，求出其完全覆蓋。圖4.5.4解：從圖中可以看出，它的最大相容類為，則其完全覆蓋為。第71頁,共87頁，2024年2月25日，星期天3-12偏序關(guān)系

定義3.12.1設(shè)R是集合A上的二元關(guān)系，若關(guān)系R滿足自反性、反對稱性和傳遞性，則稱R是集合A上的一個(gè)偏序關(guān)系，并記作“≤”。集合A和集合A上的偏序關(guān)系“≤”所構(gòu)成的序偶<A，≤>稱作偏序集。例3.12.1在實(shí)數(shù)集P上，證明大于等于關(guān)系“≥”是偏序關(guān)系。證明：（1）對于任意的實(shí)數(shù)x，都有x≥x，故“≥”在實(shí)數(shù)集上是自反的。（2）對于任意的實(shí)數(shù)x和y，若有x≥y且y≥x，則必有x=y，故“≥”在實(shí)數(shù)集上是反對稱的。（3）對于任意的實(shí)數(shù)x、y和z，若有x≥y，y≥z，則必有x≥z。故“≥”在實(shí)數(shù)集上是傳遞的。綜上所述，“≥”是實(shí)數(shù)集上的偏序關(guān)系。<P，≥>是一個(gè)偏序集。第72頁,共87頁，2024年2月25日，星期天3-12偏序關(guān)系由于偏序關(guān)系滿足自反性、反對稱性和傳遞性，其關(guān)系圖中的各元素就會呈現(xiàn)出一定的層次關(guān)系。因此，為了突出偏序關(guān)系中各元素的層次性，我們按如下規(guī)定對偏序關(guān)系的關(guān)系圖進(jìn)行化簡，從而得到一種簡明的關(guān)系圖。（1）省略關(guān)系圖中表示自反性的自己到自己的邊（2）省略關(guān)系圖中，可以通過傳遞關(guān)系表示出來的邊。按上述約定化簡了的關(guān)系圖稱為哈斯圖（Hasse）下面給出其相關(guān)定義及畫法。

第73頁,共87頁，2024年2月25日，星期天3.12偏序關(guān)系定義3.12.2在偏序集<A，≤>中，如果有x,y∈A，x≤y且，并且不存在其他元素，使得x≤z，z≤y，則稱元素y蓋住元素x。COVA={<x,y>|x,y∈A;y蓋住x}畫法：在哈斯圖中，若有元素y蓋住元素x，則將代表y的圓圈畫在代表x的圓圈的上方。并且在y和x之間用直線相連。例3.12.2設(shè)集合，R是集合A上的整除關(guān)系。試畫出<A，≤>的哈斯圖。解：<A，≤>的哈斯圖如下圖所示。第74頁,共87頁，2024年2月25日，星期天3-12偏序關(guān)系定義3.12.3設(shè)R是集合A上的二元關(guān)系，若R關(guān)系滿足反自反性和傳遞性，則稱R是A上的擬序關(guān)系，并把

<

A，R

>稱為擬序集，記作<

A，<

>。由擬序關(guān)系的定義可知，若R是擬序關(guān)系，則R必是反對稱的。。在實(shí)數(shù)集上的小于關(guān)系“＜”和大于關(guān)系“＞”，集合A的冪集上的真包含關(guān)系“”等都是擬序關(guān)系。通過比較擬序關(guān)系和偏序關(guān)系，可以發(fā)現(xiàn)：擬序關(guān)系和偏序關(guān)系都是反對稱的、可傳遞的。但前者是反自反的，后者是自反的。第75頁,共87頁，2024年2月25日，星期天鏈：設(shè)<A,≤>為偏序集，在A的一個(gè)子集中，如果每兩個(gè)元素都有關(guān)系，則稱這個(gè)子集為鏈。反鏈