集合論II關(guān)系的概念、性質(zhì)與運(yùn)算

1、第二課 關(guān)系的概念、性質(zhì)與運(yùn)算2.1 二元關(guān)系二元關(guān)系2.2 關(guān)系的性質(zhì)關(guān)系的性質(zhì)2.3 關(guān)系的運(yùn)算關(guān)系的運(yùn)算2.4 關(guān)系的閉包關(guān)系的閉包引言 在現(xiàn)實(shí)生活中, 集合與集合之間還存在著某種聯(lián)系。 現(xiàn)實(shí)世界中的二元關(guān)系1，同一個(gè)集合中的二元關(guān)系：同學(xué)關(guān)系、同桌關(guān)系2，兩個(gè)不同集合之間的二元關(guān)系：師生關(guān)系、學(xué)生和選修課程的關(guān)系 現(xiàn)實(shí)世界中的多元關(guān)系學(xué)生、課程和任課教師的關(guān)系形式化和非形式化的描述 形式化描述數(shù)學(xué)、精確無(wú)二義、難理解 非形式化描述自然語(yǔ)言、不精確、易理解2.1 二元關(guān)系 定義2.1（二元關(guān)系） 設(shè)A和B是任意兩個(gè)集合，將AB的子集R稱(chēng)為從A到B的二元關(guān)系。A=B時(shí)，稱(chēng)R為A上的二元關(guān)系

2、。若R，則稱(chēng)a與b有關(guān)系R，記為aRb。 術(shù)語(yǔ)：R：a與b沒(méi)有關(guān)系RR=：空關(guān)系R=AB：全關(guān)系注：由于R AB R (A B) (A B) ，從A到B的關(guān)系必然是A B上的關(guān)系，本節(jié)將主要研究同一集合上的關(guān)系，而不同集合間的關(guān)系只是它的一種特殊情況。 由定義2.1，得出： 1）二元關(guān)系是集合（一種特殊的集合）； 2）二元關(guān)系的元素是有序?qū)Γɑ蛐蚺肌⒂行?元組）。2.1 二元關(guān)系 例：設(shè)A=1, 2, 3, 4, 5，A上共有多少個(gè)二元關(guān)系？ AA的子集都是A上的二元關(guān)系，反過(guò)來(lái)， A上的任意二元關(guān)系都是AA的子集，因此A上的二元關(guān)系的集合正是AA的冪集，即P(AA)。 西安交通大學(xué)1998考

3、研 解： 因?yàn)锳上的二元關(guān)系R是AA的子集，|AA|=25，|P(AA)|=225 所以A上的二元關(guān)系R的個(gè)數(shù)是225。 2.1 二元關(guān)系 定義2.2（定義域，值域） 設(shè)R是從A到B的二元關(guān)系，A的一個(gè)子集 a|存在b，使得R稱(chēng)為R的定義域，記為Dom R。B的一個(gè)子集 b|存在a，使得 R稱(chēng)為R的值域，記為Ran R。 A稱(chēng)為R的前域，B稱(chēng)為R的陪域，顯然Dom RA，Ran RB。 |(),aba bR |(),baa bR 例1 整除關(guān)系 設(shè)A=2, 3, 4, B=3, 4, 5, 6, 7, 定義從A到B的二元關(guān)系R: Ra整除b。 R=, , , , Dom R=2, 3, 4,

4、Ran R=3, 4, 6. 例2 A=1, 2, 3, 4上的小于關(guān)系R: R ab. R=, 1, 3), 1, 4), 2, 3), 2, 4), 3, 4) 練習(xí)： A=1, 2, 3, 4上的小于等于關(guān)系：R=, , , , , , , , , A=1, 2, 3, 4上的不等關(guān)系: R”=, , , , , , , , , , , 2.1 二元關(guān)系 定義2.3 （n元關(guān)系） 設(shè)A1,An是n個(gè)任意集合，定義A1An的子集R為A1,An(之間)的n元關(guān)系。 當(dāng)A1=An時(shí)，R稱(chēng)為A上的n元關(guān)系。2.2 關(guān)系的性質(zhì) 例3.1：整數(shù)集上的關(guān)系 此關(guān)系最主要的特點(diǎn)是什么? 任取整數(shù)a,b,

5、c，若ab且bc，必定有ac。這種特點(diǎn)可以概括為傳遞性傳遞性（原本a,b之間有關(guān)系，當(dāng)b,c之間也有同樣關(guān)系時(shí)，這一關(guān)系就會(huì)傳遞到a,c之間）。 “若ab且bc，必定有ac”是因?yàn)樵凇盿b且bc”和“ac”之間有因果推論關(guān)系，這種關(guān)系來(lái)源于“小于”的語(yǔ)義。故上述傳遞性的確切稱(chēng)謂是語(yǔ)義傳遞性語(yǔ)義傳遞性。 例3.2：浙科院14級(jí)學(xué)生集合上的“入學(xué)分?jǐn)?shù)”關(guān)系R R是否具有語(yǔ)義傳遞性？ 任取浙科院14級(jí)學(xué)生x，y和z，若R（即x入學(xué)分?jǐn)?shù)低于y的）， R，必定可以推出R。這是一個(gè)因果推論，因此R具有語(yǔ)義傳遞性。 例3.3：A=a,b,c上的關(guān)系R=, R是不是語(yǔ)義傳遞的？ 不是。這就需要給出一個(gè)反例。

6、由于A和R是抽象的，需要給出它們的一個(gè)具體的解釋?zhuān)沟肦不具有語(yǔ)義傳遞性。 假設(shè)a,b,c表示3個(gè)學(xué)生，而 R表示在某次考試中x的分?jǐn)?shù)高于y（這當(dāng)然要求兩人都未缺考從而都有成績(jī)）。假設(shè)共有3次考試。第1次a的分?jǐn)?shù)高于b, 而c缺考；第2次b的分?jǐn)?shù)高于c，而a缺考；第3次a的分?jǐn)?shù)高于c，而b缺考。 由第1次grade(a)grade(b)， R；由第2次grade(b)grade(c) ， R；由第3次grade(a) grade(c) ， R；R中不再有別的有序?qū)Α?但是，在“ R且 R”和“ R”之間沒(méi)有因果關(guān)系。以上述解釋為例，沒(méi)有任何一次考試同時(shí)出現(xiàn)a分?jǐn)?shù)高于b，且b分?jǐn)?shù)高于c的情況，因

7、此無(wú)法僅憑因果推論得出“在某次考試中a分?jǐn)?shù)高于c”。 繼續(xù)例3.3 但是在形式上，對(duì)任意x,y,z A，若 R且 R，則R。這是可以檢驗(yàn)的。 對(duì)任意x,y,z A， “ R且 R”的情況只有一種，即 R且 R ，此時(shí)我們查看一下R，發(fā)現(xiàn)也在其中，這就說(shuō)明：對(duì)任意x,y,z A，若 R且 R，則R。 在前提：“ R且 R”和結(jié)論：“R”之間，雖然不具有必然的因果推論關(guān)系，但是具有可檢驗(yàn)的形式推論關(guān)系（形式檢驗(yàn)的方法是：先看前提是否成立，若其成立，檢查結(jié)論是否成立，若結(jié)論也成立，則形式推論關(guān)系成立）。 對(duì)任意x,y,z A， 根據(jù)“ R且 R” 都可以形式地推論出“R”，這也是一種傳遞性。對(duì)于關(guān)系

8、的這種特點(diǎn)，我們將其定義為一個(gè)新的概念形式傳遞性形式傳遞性。 繼續(xù)例3.3 由于集合論中的關(guān)系是形式定義的（只有形式描述不方便的時(shí)候，才給出語(yǔ)義描述，例如整數(shù)集上的小于關(guān)系），通常無(wú)法獲得關(guān)系的語(yǔ)義信息，因此無(wú)法判斷其語(yǔ)義傳遞性，而只能驗(yàn)證其有沒(méi)有形式傳遞性。 但是，形式傳遞性是語(yǔ)義傳遞的抽象（一個(gè)關(guān)系是語(yǔ)義傳遞的，一定是形式傳遞的，反之未必）或推廣，對(duì)形式傳遞性的一切研究，所得結(jié)論都完全適用于語(yǔ)義傳遞性。 綜合上述兩點(diǎn)，集合論只定義和研究形式傳遞性。 關(guān)于形式傳遞性的定義，還有一點(diǎn)不清楚的地方：在對(duì)任意x,y,z A檢驗(yàn)從“,都 R”到“ R”的形式推論關(guān)系的時(shí)候，若發(fā)現(xiàn)根本不存在,都 R的

9、情況，R的形式傳遞性應(yīng)如何定義？也就是說(shuō)，是否應(yīng)當(dāng)認(rèn)為R有形式傳遞性？ 既然形式傳遞是語(yǔ)義傳遞的抽象，我們應(yīng)該首先對(duì)語(yǔ)義傳遞的同樣情形進(jìn)行考查，再來(lái)決定如何完成抽象。 例3.4：2,3上的關(guān)系 這個(gè)關(guān)系是不是語(yǔ)義傳遞的？ 寫(xiě)出這個(gè)關(guān)系 此關(guān)系中找不到ab且bc，但仍是語(yǔ)義傳遞的 例3.5：hou，zhu，yang上的“入學(xué)分?jǐn)?shù)”關(guān)系S，設(shè)hou和zhu分?jǐn)?shù)相同，都低于yang 這個(gè)關(guān)系在語(yǔ)義上是不是傳遞的？ 寫(xiě)出這個(gè)關(guān)系 S=, 找不到R且R，但這個(gè)關(guān)系在語(yǔ)義上仍然是傳遞的 由于形式傳遞是語(yǔ)義傳遞的抽象，若不存在,都 R的情況，也應(yīng)當(dāng)認(rèn)為R具有形式傳遞性。 定義2.4（關(guān)系的傳遞性） 設(shè)R是集

10、合A上的二元關(guān)系，任取a, b, cA，若aRb且bRc，必有aRc，則稱(chēng)R是傳遞的。 這種傳遞性指的是形式傳遞性，不要求“aRb且bRc”和“aRc”之間具有因果推論關(guān)系，但要求其形式推論關(guān)系。特別地，當(dāng)“aRb且bRc”不成立時(shí)，形式推論關(guān)系成立。 任何語(yǔ)義上傳遞的關(guān)系都必然具有形式傳遞性 我們只研究如上定義的這種（形式）傳遞性，但其結(jié)論完全適用于例3.1和3.2那種“真正的、無(wú)可置疑的”傳遞性，即語(yǔ)義上的傳遞性。 例4：判斷A=1, 2, 3, 4上的以下關(guān)系是否傳遞。R1=, , 是傳遞的；R2=, 是傳遞的；R3=是傳遞的；R4=, 不是傳遞的； 如果在如果在A上的二元關(guān)系上的二元關(guān)

11、系R中，存在中，存在aRb且且bRc，但，但 R，則，則R不是傳遞的；否則不是傳遞的；否則R是傳遞的。是傳遞的。 A上的二元關(guān)系上的二元關(guān)系R，或者是傳遞的，或者不是，或者是傳遞的，或者不是傳遞的（非傳遞）。傳遞的（非傳遞）。以正難則反思想理解關(guān)系傳遞性 通過(guò)命題的雙否（正難則反的一種體現(xiàn)）表述來(lái)判斷命題是否成立。所謂雙否表述，就是相反再相反，例如：你是大學(xué)生,可表述為你并非不是大學(xué)生。 傳遞性的正面定義是：任取a, b, cA，如果aRb且bRc，必有aRc，則稱(chēng)R是傳遞的。請(qǐng)以雙否方式表述同樣含義 首先要知道該命題的相反表述：存在a, b, cA， aRb且bRc，但是aRc不成立。對(duì)這種

12、取反的方式，舉例: 任取大學(xué)生x，如果x學(xué)計(jì)算機(jī)專(zhuān)業(yè)，則x需要學(xué)離散反義：存在大學(xué)生x，x學(xué)計(jì)算機(jī)專(zhuān)業(yè)，但x不必學(xué)離散 然后前面加一個(gè)并非或不，反義的反義便回到原義。例：不存在大學(xué)生x，x學(xué)計(jì)算機(jī)但不學(xué)離散傳遞性雙否表述：不存在a, b, cA， aRb且bRc，但aRc不成立也就是不存在a, b, cA， aRb，bRc，且 并非 aRc以此來(lái)分析例4： R2=, 傳遞嗎？ R3= 呢 R4=, 呢 例5. 下面的二元關(guān)系哪個(gè)是傳遞的？（ ） A) 父子關(guān)系 B) 朋友關(guān)系 C) 集合的包含關(guān)系 D) 實(shí)數(shù)的不等關(guān)系 /*重慶大學(xué)1998年考研試題*/2.2 關(guān)系的性質(zhì) 定義2.4(關(guān)系的其

13、它性質(zhì)) 設(shè)R是集合A上的二元關(guān)系。(1)如果任取aA，有aRa，則稱(chēng)R是自反的。(2)如果任取aA，有R，則稱(chēng)R是反自反的。注意反自反不是非自反，請(qǐng)根據(jù)(1)給出非自反的定義。 存在a A，并非aRa。(3)任取a, bA，如果aRb必有bRa，則稱(chēng)R是對(duì)稱(chēng)的。(4)任取a, bA，如果aRb且bRa，必有a=b，則稱(chēng)R是反對(duì)稱(chēng)的。 注意反對(duì)稱(chēng)不是非對(duì)稱(chēng)。非對(duì)稱(chēng)的涵義是： 存在a, b A， aRb，且并非bRa。 例6：自反與反自反自反與反自反 自反：小于等于關(guān)系 反自反：小于關(guān)系設(shè)A=1, 2, 3, 4上的關(guān)系R=, , 則R既不是自反，也不是反自反的；所以，A上的二元關(guān)系R可以既不是

14、自反的，也不是反自反的。 例7：對(duì)稱(chēng)與反對(duì)稱(chēng) 對(duì)稱(chēng)：自然數(shù)集N上的不等關(guān)系 反對(duì)稱(chēng)：自然數(shù)集N上的小于關(guān)系 A=1, 2, 3, 4上的關(guān)系R=, , , 則R既不是對(duì)稱(chēng)，也不是反對(duì)稱(chēng)；所以，A上的二元關(guān)系R可以既不是對(duì)稱(chēng)，也不是反對(duì)稱(chēng)以正難則反思想理解關(guān)系反對(duì)稱(chēng) 根據(jù)命題的逆否（另一種正難則反）表述來(lái)判斷命題是否成立。例：若你學(xué)計(jì)算機(jī)專(zhuān)業(yè)，則你必學(xué)離散。逆否表述是：若你不學(xué)離散，則你一定不是學(xué)計(jì)算機(jī)專(zhuān)業(yè)的。 正面表述：任取a, bA，如果aRb且bRa，必有a=b，則稱(chēng)R是反對(duì)稱(chēng)的。 逆否表述一：如果aRb且ab，必有R 。 逆否表述二：如果bRa且ab，必有R 。 逆否表述：如果ab，則a

15、Rb和bRa不同時(shí)成立 逆否等價(jià)性的證明：若命題A成立，則命題B成立等價(jià)于：若命題B不成立，則命題A不成立。用反證法很容易證。假設(shè)若命題B不成立，但命題A成立，導(dǎo)出矛盾。 應(yīng)用逆否定義判斷關(guān)系的反對(duì)稱(chēng)性 前述例7： 自然數(shù)集N上的關(guān)系，是反對(duì)稱(chēng)的 用正面定義： 是反對(duì)稱(chēng)的 當(dāng)且僅當(dāng) 任取a,b N，若ab且ba，必有a=b。由于不可能有ab且ba的情況，似乎難以根據(jù)正面定義來(lái)判斷。怎么辦？ 正難則反！ 逆否定義：b或ba。由此就可以很明確地得出結(jié)論： 是反對(duì)稱(chēng)的！ 例8 集合A的冪集P(A)上的包含關(guān)系，具有哪些基本性質(zhì)？自反，反對(duì)稱(chēng)，傳遞2.2 關(guān)系的性質(zhì) 定義2.5.1（關(guān)系矩陣） 設(shè)A和

16、B是兩個(gè)有限集A=a1, , am，B=b1, , bn，R是從A到B的二元關(guān)系，稱(chēng)m n階矩陣MR=(mij)為R的關(guān)系矩陣，其中若R， mij =1若R，mij =0 例9 整除關(guān)系的關(guān)系矩陣 A=2, 3, 4, B=3, 4, 5, 6, 70 1 0 1 01 0 0 1 00 1 0 0 0RM2.2 關(guān)系的性質(zhì) 定義2.5.2 （關(guān)系圖） 設(shè)A=a1, , an，R是A上的二元關(guān)系。A中每個(gè)元素ai用一個(gè)點(diǎn)表示，稱(chēng)該點(diǎn)為頂點(diǎn)ai 。 如果aiRaj，則從頂點(diǎn)ai到頂點(diǎn)aj存在一條有向弧。 如果aiRai，則從頂點(diǎn)ai到頂點(diǎn)ai存在一條封閉有向?。ㄓ邢颦h(huán)）。以這種方式來(lái)表示R關(guān)系的

17、圖形，稱(chēng)為R的關(guān)系圖。2 .3 關(guān)系的運(yùn)算 定義2.6 （關(guān)系的運(yùn)算） 設(shè)R1和R2是從A到B的兩個(gè)二元關(guān)系，則R1R2、 R1R2 、 R1-R2、 1也是從A到B的二元關(guān)系，其含義是：任取aA，bB， a(R1R2)b aR1b或aR2b； a(R1R2)b aR1b且aR2b； a(R1-R2)b aR1b且(a, b)R2; a 1b(a,b)(AB)-R1。2 .3 關(guān)系的運(yùn)算逆運(yùn)算 定義2.7（逆關(guān)系） 設(shè)R是從A到B的二元關(guān)系，則從B到A的二元關(guān)系R-1定義為R-1 =|R，稱(chēng)R-1為R的逆關(guān)系。 練習(xí)： 寫(xiě)出R=,的逆關(guān)系2 .3 關(guān)系的運(yùn)算 定理2.1（1）(R-1)-1=R

18、;（2）(R1R2)-1= R1-1 R2-1; （3）(R1R2)-1= R1-1 R2-1;（4） (AB)-1= B-1A-1；（5） -1=；（6）()-1= ;（7） (R1-R2)-1= R1-1-R2-1；（8）若R1R2，則R1-1 R2-1 。1()R證明方法（1）證明兩個(gè)關(guān)系相等，因?yàn)殛P(guān)系是集合，可采用證明集合相等的方法（基本法或公式法）證明關(guān)系相等。例如用基本法：任取a,b A左式右式; 則左式右式；右式左式; 則右式左式；則左式=右式。（2）證明關(guān)系滿足某一性質(zhì) 根據(jù)該性質(zhì)的定義進(jìn)行求證。 例如，要證明集合A上的二元關(guān)系R是自反的，就是證明對(duì)于任意的aA，R。證明兩個(gè)關(guān)

19、系相等 (3) 基本法證明： (R1R2)-1 (R1R2) R1且 R2 R1-1且R2-1 R1-1 R2-1 所以，(R1R2)-1= R1-1 R2-1。 (1), (2)類(lèi)似, 證明見(jiàn)教材或參考書(shū)。 (4)類(lèi)似。 (5)反證法。 設(shè)-1，則存在-1, 那么. 導(dǎo)致矛盾。 (6), (7), (8)基本法或公式法證明。 2 .3 關(guān)系的運(yùn)算 定理2.2 R是A上的二元關(guān)系，則R是對(duì)稱(chēng)的R=R-1。證明：R是對(duì)稱(chēng)的 R=R-1：（證明兩個(gè)關(guān)系相等證明兩個(gè)關(guān)系相等） R, 因?yàn)镽是對(duì)稱(chēng)的，所以R, 則R-1; 所以RR-1。同理，R-1R。則R=R-1。R=R-1 R是對(duì)稱(chēng)的：（證明關(guān)系滿

20、足某一性質(zhì)）證明關(guān)系滿足某一性質(zhì)）如果R, 因?yàn)镽=R-1，所以R-1，則R。所以R是對(duì)稱(chēng)的。（根據(jù)對(duì)稱(chēng)的定義）（根據(jù)對(duì)稱(chēng)的定義）2 .3 關(guān)系的運(yùn)算復(fù)合運(yùn)算 定義2.8（復(fù)合關(guān)系） 設(shè)R1是從A到B的二元關(guān)系， R2是從B到C的二元關(guān)系，則從A到C的二元關(guān)系R1R2定義為 R1R2 = | aA, cC, 且 存在bB使 R1, R2稱(chēng)R1R2為R1和R2的復(fù)合關(guān)系。2 .3 關(guān)系的運(yùn)算 定理2.3（結(jié)合律） (R1R2)R3 = R1(R2R3) 證明方法：采用基本法，證明兩個(gè)關(guān)系相等。即： (R1R2)R3R1(R2R3)，則(R1R2)R3 R1(R2R3) ； R1(R2R3) (R

21、1R2)R3 ，則R1(R2R3) (R1R2)R3 。具體證明步驟見(jiàn)教材或參考書(shū)。 注意：關(guān)系的復(fù)合運(yùn)算不滿足交換律，即R1R2 R2R12 .3 關(guān)系的運(yùn)算冪運(yùn)算 定義2.9（冪關(guān)系） 設(shè)R是A上的二元關(guān)系，nN，R的n次冪記為Rn，定義如下： (1) R0是A上的恒等關(guān)系（即R0 = | aA），記為IA，又R1=R； (2)Rn+1= RnR。 定理2.4 (1) Rm Rn=Rm+n (2) (Rm)n= Rmn證明方法：采用歸納法進(jìn)行證明 設(shè)性質(zhì)為P。 歸納基礎(chǔ)：證明P(1)為真； 歸納步驟：對(duì)每一個(gè)i1，假設(shè)P(i)為真，并且利用這一假設(shè)證明P(i+1)為真。 證明：(1) 歸納

22、基礎(chǔ)：設(shè)n=1, 則根據(jù)冪運(yùn)算的定義，RmR1= Rm+1； 歸納步驟：設(shè)n=k, Rm Rk=Rm+k成立；n=k+1時(shí), Rm Rk+1= Rm RkR1=Rm+kR1 =Rm+k+1。 所以Rm Rn=Rm+n。 (2)歸納基礎(chǔ)：設(shè)n=1, 則根據(jù)冪運(yùn)算的定義， (Rm)1= Rm。 歸納步驟：設(shè)n=k, (Rm)k= Rmk成立；設(shè)n=k+1, (Rm)k+1= (Rm)k (Rm)=Rmk Rm= Rmk+m=Rm(k+1). 歸納證明的思想 / 思維過(guò)程 歸納基礎(chǔ)證明P(1)為真； 根據(jù)歸納步驟，因?yàn)镻(1)為真，所以P(2)為真；因?yàn)镻(2)為真，所以P(3)為真；這個(gè)過(guò)程對(duì)所有

23、的自然數(shù)繼續(xù)下去，于是對(duì)于任意的自然數(shù)k，P(k)為真。2 .4 關(guān)系的閉包 定義2.11（自反，對(duì)稱(chēng)，傳遞閉包） 設(shè)R是A上的二元關(guān)系，R的自反（對(duì)稱(chēng)，傳遞）閉包，記為 R，滿足下列三個(gè)條件：（1）R是自反的（對(duì)稱(chēng)的，傳遞的）；（2）RR；（3）對(duì)任一自反（對(duì)稱(chēng)，傳遞關(guān)系）R”，RR”，均有RR”?，F(xiàn)在，將R的自反、對(duì)稱(chēng)，傳遞閉包分別記為r(R)，s(R)，t(R)。2 .5 關(guān)系的閉包基本性質(zhì)定理2.5 設(shè)R是A上的二元關(guān)系，則R是自反的 r(R)=R；R是對(duì)稱(chēng)的 s(R)=R；(1) R是傳遞的 t(R)=R； 證明思想1：采用基本法進(jìn)行證明，以R是自反的 r(R)=R為例： R是自反的

24、 r(R)=R：因?yàn)楦鶕?jù)r(R)的定義，r(R)是自反的，所以R是自反的； R是自反的 r(R)=R：根據(jù)r(R)的定義，Rr(R) ，需證明r(R)R; 由于RR，且R （左側(cè)的R ）是自反的，由自反閉包的定義可知r(R)R （右側(cè)的R ） 。 證明思想2: （證明滿足某一性質(zhì)）證明滿足某一性質(zhì)） 根據(jù)自反，對(duì)稱(chēng)和傳遞閉包定義進(jìn)行證明，以R是自反的 r( R )=R: R是自反的 r( R )=R , 就是證明R符合R的自反閉包定義的3個(gè)條件: (1)R（哪個(gè)R？）是自反的；(2) RR （分別是哪個(gè)R？） ；(3)對(duì)任一自反關(guān)系R”，若R （哪個(gè)R？） R”，則R （哪個(gè)R？） R”。 r

25、( R )=R R是自反的. 定理2.6 設(shè)R1和R2是A上的二元關(guān)系，若R1R2則 r(R1) r(R2)； s(R1) s(R2)；(1)t(R1) t(R2)。證明思想：反證法：（1）假設(shè)r(R1), 但r(R2)，則xy，從而r(R1) (x, y)也是自反的；如果R1，則R2，那么r(R2)，導(dǎo)致矛盾，所以 R1。則r(R1) (x, y) R1，則r(R1)不是R1的自反閉包。矛盾。 r(R2)。r(R1) r(R2)。（2）,（3）證明類(lèi)似。2 .5 關(guān)系的閉包 三 計(jì)算 定理2.7 r(R)=R IA證明思想：根據(jù)自反閉包定義要滿足的性質(zhì)進(jìn)行證明。 證明：設(shè)R=RIA，所以R

26、R，而且R是自反的；假設(shè)R”是A上的自反關(guān)系并且RR”，對(duì)于R，因?yàn)镽=RIA，所以R或者IA；如果R，則R”；如果IA，因?yàn)镽”是自反的，所以R”，即RR”。 所以R=r(R)=RIA。 定理2.8 s(R)=RR-1證明思想：根據(jù)對(duì)稱(chēng)閉包定義要滿足的性質(zhì)進(jìn)行證明。 證明：令R=RR-1。由于(RR-1)-1=RR-1 ，根據(jù)定理2.2，可知R=RR-1是對(duì)稱(chēng)的，且RR。假設(shè)R”是A上的對(duì)稱(chēng)關(guān)系，并且RR”。對(duì)于R有R或者R-1。如果R，由于RR”，那么R”；如果R-1，則R，所以R”。因?yàn)镽”是對(duì)稱(chēng)的，所以R”。因此RR”。所以R=s(R)= RR-1。 例9 設(shè)A=a, b, c，R是A

27、上的二元關(guān)系，且R=, , ，則s(R)= 。 /*重慶大學(xué)1999考研*/ 定理2.9 t(R)=RR2R3 /*證明思想：根據(jù)傳遞閉包定義要滿足的性質(zhì)進(jìn)行證明：令R=RR2R3，證明R滿足傳遞閉包定義的3個(gè)條件。*/ 證明： /*R是傳遞的，即如果R, R, 則R*/ 因?yàn)镽，必存在整數(shù)n，使Rn；同理，因?yàn)镽，必存在整數(shù)k，使Rk；因?yàn)镽n Rk=Rn+k，所以Rn+k，所以R。 證明：（續(xù)） /* RR */ 因?yàn)镽=RR2R3，所以RR。 證明：（續(xù)） /*對(duì)于傳遞關(guān)系R”，如果R”R, 則R”R. */ 如果a,bA, R, 則存在正整數(shù)j，使Rj, 即存在j-1個(gè)元素c1, c2,cj-1使得R, R, R. 由于R”R, 所以R”, R”, R”. 又因?yàn)镽”是傳遞的，因此R”。由此證得R”R。由傳遞閉包的定義可知：R=t(R)，即t(R) =RR2R3 。 定理2.10 R是A上的二元關(guān)系，且|A|=n，則t(R)=RR2R3Rn /* 證明思想：基本法：由定理2.9可知，RR2R3Rnt(R)；只要證明對(duì)任意的k0，RkRR2R3Rn。*/ 證明：/*分而治之*/ 對(duì)于kn，必有RkRR2R3Rn 。 對(duì)于kn，若Rk，則存在元素個(gè)數(shù)為k+1的元素序列c0, c1, , ck, c0=a, ck=b,