集合論第二課關(guān)系的概念、性質(zhì)與運算

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

2、。若R，則稱a與b有關(guān)系R，記為aRb。 若R，則稱a與b沒有關(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上共有多少個二元關(guān)系？ AA的子集都是A上的二元關(guān)系，反過來， A上的任意二元關(guān)系都是AA的子集，因此A上的二元關(guān)系的集合正是AA的冪集，即P(AA)。 西安交通大學(xué)1998考

3、研 解： 因為A上的二元關(guān)系R是AA的子集，|AA|=25，|P(AA)|=225 所以A上的二元關(guān)系R的個數(shù)是225。 2.1 二元關(guān)系 定義2.2（定義域，值域） 設(shè)R是從A到B的二元關(guān)系，A的一個子集 a|存在b，使得R稱為R的定義域，記為Dom R。B的一個子集 b|存在a，使得 R稱為R的值域，記為Ran R。 A稱為R的前域，B稱為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個任意集合，定義A1An的子集R為A1,An(之間)的n元關(guān)系。 當A1=An時，R稱為A上的n元關(guān)系。2.2 關(guān)系的性質(zhì) 例2.1：整數(shù)集上的關(guān)系 此關(guān)系有一個明顯的特點：若a,b之間有關(guān)系，

5、當b,c之間也有同樣關(guān)系時，這一關(guān)系就會傳遞到a,c之間，因此將這種特點稱為傳遞性傳遞性。 例2.2：浙科院14級學(xué)生集合上的“入學(xué)分數(shù)”關(guān)系R 任取浙科院14級學(xué)生x，y和z，若R（即x入學(xué)分數(shù)低于y的）， R，必定可以推出R，因此R具有傳遞性。 定義2.4 稱二元關(guān)系R是傳遞的，當且僅當對任意a, b, c，若aRb且bRc，則aRc。 定義的核心是一個推論命題： “若aRb且bRc，則aRc” ， 其中“aRb且bRc”是前提，aRc”是結(jié)論?！叭魟t”表示從前提到結(jié)論的推論關(guān)系。這類命題的準確涵義是什么？ 請判斷以下推論命題是不是真的。 i：若32，則3+12+1 ii：若雪是白的，則太

6、陽從東方升起 iii: 若水被加熱到100，則其會沸騰 （標準大氣壓） 命題iii為真是毫無異議的。下面就從它入手對推論命題進行分析。若水被加熱到100，則其會沸騰 因果推論：前提和結(jié)論之間有內(nèi)在的因果關(guān)系 在形式上（只考慮前提和結(jié)論的真假而非內(nèi)容）有明顯特點： 水被加熱到100 時（前提真），必然會沸騰（結(jié)論真），推論為真。 水沒被加熱到100 時（前提假），并不妨害“若水被加熱到100 ，則其會沸騰”的正確性，因此推論也為真。 概括為性質(zhì)P：或者前提為假，或者前提為真且結(jié)論為真 這是一個可以形式地檢驗的性質(zhì)：任給一“若A則B”推論，先檢查A的真假，為假時，已經(jīng)符合P，為真時，再檢查B的真假

7、，若也為真，則符合P，否則不符合。 形式推論：符合性質(zhì)P的推論。非形式推論：前提真，并且結(jié)論假因果推論必為形式推論，非形式推論必非因果推論 數(shù)學(xué)中使用的“推論”，都是形式推論，而未必是因果推論 只要前提為真，從形式推論得出的結(jié)果一定為真，如從雪是白的推出太陽東升，結(jié)果沒有錯。至于這樣的推論是否有意義，要靠人來把握。 沒有人會從假命題出發(fā)進行任何嚴肅的推論，因此“若32，則3+12+1”這樣的形式推論是無害的。 設(shè)A=1,2,3，R是A上的二元關(guān)系，判斷如下R是否具有傳遞性： R=, R=, R= R= 設(shè)A是你家的男孩集合，R是A上的兄弟關(guān)系，判斷如下情形時R是否具有傳遞性： 你家共有三個男孩

8、：你哥、你、你弟 你家共有兩個男孩：你哥、你 你家只有一個男孩：你 以下關(guān)系是否傳遞？父子關(guān)系、朋友關(guān)系、整數(shù)不等關(guān)系。 例4：判斷A=1, 2, 3, 4上的以下關(guān)系是否傳遞。R1=, , 是傳遞的；R2=, 是傳遞的；R3=是傳遞的；R4=, 不是傳遞的； 如果在如果在A上的二元關(guān)系上的二元關(guān)系R中，存在中，存在aRb且且bRc，但，但 R，則，則R不是傳遞的；否則不是傳遞的；否則R是傳遞的。是傳遞的。 A上的二元關(guān)系上的二元關(guān)系R，或者是傳遞的，或者不是，或者是傳遞的，或者不是傳遞的（非傳遞）。傳遞的（非傳遞）。以正難則反思想理解關(guān)系傳遞性 通過命題的雙否表述來判斷命題是否成立。例如：“

9、你是大學(xué)生”，其雙否表述為“你并非不是大學(xué)生”。 傳遞性的正面定義是：任取a, b, cA，如果aRb且bRc，必有aRc，則稱R是傳遞的。請以雙否方式表述同樣含義 首先，該命題的相反表述：存在a, b, cA， aRb且bRc，但并非aRc。對這種取反的方式，舉例: 任取大學(xué)生x，如果x學(xué)計算機專業(yè)，則x需要學(xué)離散反義：存在大學(xué)生x，x學(xué)計算機專業(yè)，但x不必學(xué)離散 然后前面加一個并非或不，反義的反義便回到原義。 例：不存在大學(xué)生x，x學(xué)計算機但不學(xué)離散傳遞性雙否表述：不存在a, b, cA， aRb且bRc，但并非aRc也就是不存在a, b, cA， aRb，bRc，且 并非 aRc以此來分

10、析例4： R2=, 傳遞嗎？ R3= 呢 R4=, 呢 例5. 下面的二元關(guān)系哪個是傳遞的？（ ） A) 父子關(guān)系 B) 朋友關(guān)系 C) 集合的包含關(guān)系 D) 實數(shù)的不等關(guān)系 /*重慶大學(xué)1998年考研試題*/2.2 關(guān)系的性質(zhì) 定義2.4(關(guān)系的其它性質(zhì)) 設(shè)R是集合A上的二元關(guān)系。(1)如果任取aA，有aRa，則稱R是自反的。(2)如果任取aA，有R，則稱R是反自反的。注意反自反不是非自反，請根據(jù)(1)給出非自反的定義。 存在a A，并非aRa。(3)任取a, bA，如果aRb必有bRa，則稱R是對稱的。(4)任取a, bA，如果aRb且bRa，必有a=b，則稱R是反對稱的。 注意反對稱不

11、是非對稱。非對稱的涵義是： 存在a, b A， aRb，且并非bRa。 例6：自反與反自反自反與反自反 自反：小于等于關(guān)系 反自反：小于關(guān)系設(shè)A=1, 2, 3, 4上的關(guān)系R=, , 則R既不是自反，也不是反自反的；所以，A上的二元關(guān)系R可以既不是自反的，也不是反自反的。 例7：對稱與反對稱 對稱：自然數(shù)集N上的不等關(guān)系 反對稱：自然數(shù)集N上的小于關(guān)系 A=1, 2, 3, 4上的關(guān)系R=, , , 則R既不是對稱，也不是反對稱；所以，A上的二元關(guān)系R可以既不是對稱，也不是反對稱以正難則反思想理解關(guān)系反對稱 根據(jù)命題的逆否表述來判斷命題是否成立。例：若你學(xué)計算機專業(yè)，則你必學(xué)離散。逆否表述是

12、：若你不學(xué)離散，則你一定不是學(xué)計算機專業(yè)的。 正面表述：任取a, bA，如果aRb且bRa，必有a=b，則稱R是反對稱的。 逆否表述：如果ab，則aRb和bRa不同時成立 逆否表述一：如果ab且aRb ，必有R 。 逆否表述二：如果ab且bRa，必有R 。 逆否等價性：若命題A成立，則命題B成立等價于：若命題B不成立，則命題A不成立。用反證法很容易證這種等價性。左推出：假設(shè)若命題B不成立，但命題A成立，導(dǎo)出矛盾。右推出： 應(yīng)用逆否定義判斷關(guān)系的反對稱性 前述例7： 自然數(shù)集N上的關(guān)系，是反對稱的 用正面定義： 是反對稱的 當且僅當 任取a,b N，若ab且ba，必有a=b。由于不可能有ab且b

13、a的情況，似乎難以根據(jù)正面定義來判斷。怎么辦？ 正難則反！ 逆否定義：b或ba。由此就可以很明確地得出結(jié)論： 是反對稱的！ 例8 集合A的冪集P(A)上的包含關(guān)系，具有哪些基本性質(zhì)？自反，反對稱，傳遞2.2 關(guān)系的性質(zhì) 定義2.5.1（關(guān)系矩陣） 設(shè)A和B是兩個有限集A=a1, , am，B=b1, , bn，R是從A到B的二元關(guān)系，稱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 （

14、關(guān)系圖） 設(shè)A=a1, , an，R是A上的二元關(guān)系。A中每個元素ai用一個點表示，稱該點為頂點ai 。 如果aiRaj，則從頂點ai到頂點aj存在一條有向弧。 如果aiRai，則從頂點ai到頂點ai存在一條封閉有向?。ㄓ邢颦h(huán)）。以這種方式來表示R關(guān)系的圖形，稱為R的關(guān)系圖。2 .3 關(guān)系的運算 定義2.6 （關(guān)系的運算） 設(shè)R1和R2是從A到B的兩個二元關(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(

15、a,b)(AB)-R1。2 .3 關(guān)系的運算逆運算 定義2.7（逆關(guān)系） 設(shè)R是從A到B的二元關(guān)系，則從B到A的二元關(guān)系R-1定義為R-1 =|R，稱R-1為R的逆關(guān)系。 練習(xí)： 寫出R=,的逆關(guān)系2 .3 關(guān)系的運算 定理2.1（1）(R-1)-1=R;（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. 證明兩個關(guān)系相等，因為關(guān)系是集合，可采用證明集合相等的方法（基

16、本法或公式法）證明關(guān)系相等。例如用基本法：任取a,b A左式右式; 則左式右式；右式左式; 則右式左式；則左式=右式。2. 證明關(guān)系滿足某一性質(zhì) 根據(jù)該性質(zhì)的定義進行求證。 例如，要證明集合A上的二元關(guān)系R是自反的，就是證明對于任意的aA，R。證明兩個關(guān)系相等 (3) 基本法證明： (R1R2)-1 (R1R2) R1且 R2 R1-1且R2-1 R1-1 R2-1 所以，(R1R2)-1= R1-1 R2-1。 (1), (2)類似, 證明見教材或參考書。 (4)類似。 (5)反證法。 設(shè)-1，則存在-1, 那么. 導(dǎo)致矛盾。 (6), (7), (8)基本法或公式法證明。 2 .3 關(guān)系的

17、運算 定理2.2 R是A上的二元關(guān)系，則R是對稱的R=R-1。證明：R是對稱的 R=R-1：（證明兩個關(guān)系相等證明兩個關(guān)系相等） R, 因為R是對稱的，所以R, 則R-1; 所以RR-1。同理，R-1R。則R=R-1。R=R-1 R是對稱的：（證明關(guān)系滿足某一性質(zhì)）證明關(guān)系滿足某一性質(zhì)）如果R, 因為R=R-1，所以R-1，則R。所以R是對稱的。（根據(jù)對稱的定義）（根據(jù)對稱的定義）2 .3 關(guān)系的運算復(fù)合運算 定義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稱R1R

18、2為R1和R2的復(fù)合關(guān)系。2 .3 關(guān)系的運算 定理2.3（結(jié)合律） (R1R2)R3 = R1(R2R3) 證明方法：采用基本法，證明兩個關(guān)系相等。即： (R1R2)R3R1(R2R3)，則(R1R2)R3 R1(R2R3) ； R1(R2R3) (R1R2)R3 ，則R1(R2R3) (R1R2)R3 。具體證明步驟見教材或參考書。 注意：關(guān)系的復(fù)合運算不滿足交換律，即R1R2 R2R12 .3 關(guā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=

19、RnR。 定理2.4 (1) Rm Rn=Rm+n (2) (Rm)n= Rmn證明方法：采用歸納法進行證明 設(shè)性質(zhì)為P。 歸納基礎(chǔ)：證明P(1)為真； 歸納步驟：對每一個i1，假設(shè)P(i)為真，并且利用這一假設(shè)證明P(i+1)為真。 證明：(1) 歸納基礎(chǔ)：設(shè)n=1, 則根據(jù)冪運算的定義，RmR1= Rm+1； 歸納步驟：設(shè)n=k, Rm Rk=Rm+k成立；n=k+1時, Rm Rk+1= Rm RkR1=Rm+kR1 =Rm+k+1。 所以Rm Rn=Rm+n。 (2)歸納基礎(chǔ)：設(shè)n=1, 則根據(jù)冪運算的定義， (Rm)1= Rm。 歸納步驟：設(shè)n=k, (Rm)k= Rmk成立；設(shè)n=

20、k+1, (Rm)k+1= (Rm)k (Rm)=Rmk Rm= Rmk+m=Rm(k+1). 歸納證明的思想 / 思維過程 歸納基礎(chǔ)證明P(1)為真； 根據(jù)歸納步驟，因為P(1)為真，所以P(2)為真；因為P(2)為真，所以P(3)為真；這個過程對所有的自然數(shù)繼續(xù)下去，于是對于任意的自然數(shù)k，P(k)為真。2 .4 關(guān)系的閉包 定義2.11（自反，對稱，傳遞閉包） 設(shè)R是A上的二元關(guān)系，R的自反（對稱，傳遞）閉包，記為 R，滿足下列三個條件：（1）R是自反的（對稱的，傳遞的）；（2）RR；（3）對任一自反（對稱，傳遞關(guān)系）R”，R”R, 均有RR”?，F(xiàn)在，將R的自反、對稱，傳遞閉包分別記為r

21、(R)，s(R)，t(R)。2 .5 關(guān)系的閉包基本性質(zhì)定理2.5 設(shè)R是A上的二元關(guān)系，則R是自反的 r(R)=R；R是對稱的 s(R)=R；(1) R是傳遞的 t(R)=R； 證明思想1：采用基本法進行證明，以R是自反的 r(R)=R為例： R是自反的 r(R)=R：因為根據(jù)r(R)的定義，r(R)是自反的，所以R是自反的； R是自反的 r(R)=R：根據(jù)r(R)的定義，Rr(R) ，需證明r(R)R; 由于RR，且R 是自反的，由自反閉包的定義可知r(R)R 。 證明思想2: （證明滿足某一性質(zhì)）證明滿足某一性質(zhì)） 根據(jù)自反，對稱和傳遞閉包定義進行證明，以R是自反的 r( R )=R:

22、R是自反的 r( R )=R , 就是證明R符合R的自反閉包定義的3個條件: (1)R是自反的；(2) R R ；(3)對任一自反關(guān)系R”，若 R” R ，則R R”。 r( 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(

23、R2)。（2）,（3）證明類似。2 .5 關(guān)系的閉包 三 計算 定理2.7 r(R)=R IA證明思想：根據(jù)自反閉包定義要滿足的性質(zhì)進行證明。 證明：設(shè)R=RIA，所以R R，而且R是自反的；假設(shè)R”是A上的自反關(guān)系并且RR”，對于R，因為R=RIA，所以R或者IA；如果R，則R”；如果IA，因為R”是自反的，所以R”，即RR”。 所以R=r(R)=RIA。 定理2.8 s(R)=RR-1證明思想：根據(jù)對稱閉包定義要滿足的性質(zhì)進行證明。 證明：令R=RR-1。由于(RR-1)-1=RR-1 ，根據(jù)定理2.2，可知R=RR-1是對稱的，且RR。假設(shè)R”是A上的對稱關(guān)系，并且RR”。對于R有R或者

24、R-1。如果R，由于RR”，那么R”；如果R-1，則R，所以R”。因為R”是對稱的，所以R”。因此RR”。所以R=s(R)= RR-1。 例9 設(shè)A=a, b, c，R是A上的二元關(guān)系，且R=, , ，則s(R)= 。 /*重慶大學(xué)1999考研*/ 定理2.9 t(R)=RR2R3 /*證明思想：根據(jù)傳遞閉包定義要滿足的性質(zhì)進行證明：令R=RR2R3，證明R滿足傳遞閉包定義的3個條件。*/ 證明： /*R是傳遞的，即如果R, R, 則R*/ 因為R，必存在整數(shù)n，使Rn；同理，因為R，必存在整數(shù)k，使Rk；因為Rn Rk=Rn+k，所以Rn+k，所以R。 證明：（續(xù)） /* RR */ 因為R

25、=RR2R3，所以RR。 證明：（續(xù)） /*對于傳遞關(guān)系R”，如果R”R, 則R”R. */ 如果a,bA, R, 則存在正整數(shù)j，使Rj, 即存在j-1個元素c1, c2,cj-1使得R, R, R. 由于R”R, 所以R”, R”, R”. 又因為R”是傳遞的，因此R”。由此證得R”R。由傳遞閉包的定義可知：R=t(R)，即t(R) =RR2R3 。 定理2.10 R是A上的二元關(guān)系，且|A|=n，則t(R)=RR2R3Rn /* 證明思想：基本法：由定理2.9可知，RR2R3Rnt(R)；只要證明對任意的k0，RkRR2R3Rn。*/ 證明：/*分而治之*/ 對于kn，必有RkRR2R3Rn 。 對于kn，若Rk，則存在元素個數(shù)為k+1的元素序列c0, c1, , ck, c0=a, ck=b, 并且對1ik，R。由于kn ，所以在元素序列中必有元素ci不止出現(xiàn)一次，即, , , , , , , , R，在刪去, , 這一段后，如果序列中元素個數(shù)仍大于n，則