北大離散數(shù)學(xué).ppt
《北大離散數(shù)學(xué).ppt》由會員分享，可在線閱讀，更多相關(guān)《北大離散數(shù)學(xué).ppt（52頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。
2019/12/24,《集合論與圖論》第7講,1,第7講關(guān)系冪運(yùn)算與關(guān)系閉包北京大學(xué),內(nèi)容提要關(guān)系冪(power)運(yùn)算關(guān)系閉包(closure),2019/12/24,《集合論與圖論》第7講,2,關(guān)系的冪運(yùn)算,n次冪的定義指數(shù)律冪指數(shù)的化簡,2019/12/24,《集合論與圖論》第7講,3,關(guān)系的n次冪,關(guān)系的n次冪(nthpower):設(shè)R?A?A,n?N,則(1)R0=IA;(2)Rn+1=Rn○R,(n?1).Rn表示的關(guān)系,是R的關(guān)系圖中長度為n的有向路徑的起點(diǎn)與終點(diǎn)的關(guān)系.,,,,,,,,,,,,1,2,n,n-1,2019/12/24,《集合論與圖論》第7講,4,關(guān)系冪運(yùn)算(舉例),例:設(shè)A={a,b,c},R?A?A,R={,,},求R的各次冪.解:,,,,,,,b,a,c,,,,b,a,c,,,,,,,G(R),G(R0),2019/12/24,《集合論與圖論》第7講,5,關(guān)系冪運(yùn)算(舉例,續(xù)),解(續(xù)):R0=IA,R1=R0○R=R={,,},R2=R1○R={,,},,,,,,,,b,a,c,,,,b,a,c,,,,,G(R),G(R2),,2019/12/24,《集合論與圖論》第7講,6,關(guān)系冪運(yùn)算(舉例,續(xù)2),解(續(xù)):R0=IA,R1=R0○R=R={,,},R2=R1○R={,,},R3=R2○R={,,}=R1,,,,,,,,b,a,c,,,,b,a,c,G(R),G(R3),,,,2019/12/24,《集合論與圖論》第7講,7,關(guān)系冪運(yùn)算(舉例,續(xù)3),解(續(xù)):R4=R3○R=R1○R=R2,R5=R4○R=R2○R=R3=R1,一般地,R2k+1=R1=R,k=0,1,2,…,R2k=R2,k=1,2,…,.#,,,,,,,b,a,c,,,,b,a,c,G(R),G(R5),,,,,,,b,a,c,,,,,G(R4),,2019/12/24,《集合論與圖論》第7講,8,關(guān)系冪運(yùn)算是否有指數(shù)律?,指數(shù)律:(1)Rm○Rn=Rm+n;(2)(Rm)n=Rmn.說明:對實(shí)數(shù)R來說,m,n?N,Z,Q,R.對一般關(guān)系R來說,m,n?N.對滿足IA?R且A?domR?ranR的關(guān)系R來說,m,n?N,Z,例如R2○R-5=R-3,因?yàn)榭梢远xR-n=(R-1)n=(Rn)-1?,2019/12/24,《集合論與圖論》第7講,9,定理17,定理17:設(shè)R?A?A,m,n?N,則(1)Rm○Rn=Rm+n;(2)(Rm)n=Rmn.說明:可讓m,n?Z,只需IA?domR?ranR(此時(shí)IA=R○R-1=R-1○R)并且定義R-n=(R-1)n=(Rn)-1.回憶:(F○G)-1=G-1○F-1(R2)-1=(R○R)-1=R-1○R-1=(R-1)2,2019/12/24,《集合論與圖論》第7講,10,定理17(證明(1)),(1)Rm○Rn=Rm+n;證明:(1)給定m,對n歸納.n=0時(shí),Rm○Rn=Rm○R0=Rm○IA=Rm=Rm+0.假設(shè)Rm○Rn=Rm+n,則Rm○Rn+1=Rm○(Rn○R1)=(Rm○Rn)○R1=Rm+n○R=R(m+n)+1=Rm+(n+1).(2)同樣對n歸納.#,2019/12/24,《集合論與圖論》第7講,11,R0,R1,R2,R3,…是否互不相等?,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,R0,R1,R2,R3,R4,R5,R6,R7,R8,R0,R1,R2,R3,R4,R5=R19=R33=R47=…,R6=R20=R34=R48=…,R7=R21=R35=R49=…,R8=R22=R36=…,R15,R9,R10,R11,R14,R16,R17,2019/12/24,《集合論與圖論》第7講,12,定理16,定理16:設(shè)|A|=n,R?A?A,則?s,t?N,并且,使得Rs=Rt.證明:P(A?A)對冪運(yùn)算是封閉的,即?R,R?P(A?A)?Rk?P(A?A),(k?N).|P(A?A)|=,在R0,R1,R2,…,這個(gè)集合中,必有兩個(gè)是相同的.所以?s,t?N,并且,使得Rs=Rt.#,2019/12/24,《集合論與圖論》第7講,13,鴿巢原理(pigeonholeprinciple),鴿巢原理(pigeonholeprinciple):若把n+1只鴿子裝進(jìn)n只鴿巢,則至少有一只鴿巢裝2只以上的鴿子.又名抽屜原則(Dirichletdrawerprinciple),(PeterGustavLejeuneDirichlet,1805~1859)推廣形式:若把m件物品裝進(jìn)k只抽屜,則至少有一只抽屜裝只以上的物品.?1.8?=2,?1.8?=1,?-1.8?=-1,?-1.8?=-2.,2019/12/24,《集合論與圖論》第7講,14,定理18,定理18:設(shè)R?A?A,若?s,t?N(st-1?s,則令q=s+kp+i,其中k,i?N,p=t-s,s+i下載提示(請認(rèn)真閱讀)
- 1.請仔細(xì)閱讀文檔，確保文檔完整性，對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔，不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入（下載+內(nèi)容+預(yù)覽）歸上傳者、原創(chuàng)作者；如果您是本文檔原作者，請點(diǎn)此認(rèn)領(lǐng)！既往收益都?xì)w您。
文檔包含非法信息？點(diǎn)此舉報(bào)后獲取現(xiàn)金獎勵！
下載文檔到電腦，查找使用更方便
14.9 積分
| 下載 |
還剩頁未讀，繼續(xù)閱讀
- 配套講稿：
如PPT文件的首頁顯示word圖標(biāo)，表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制：
部分文檔作品中含有的國旗、國徽等圖片，僅作為作品整體效果示例展示，禁止商用。設(shè)計(jì)者僅對作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞：
- 北大 離散數(shù)學(xué)
裝配圖網(wǎng)所有資源均是用戶自行上傳分享，僅供網(wǎng)友學(xué)習(xí)交流，未經(jīng)上傳用戶書面授權(quán)，請勿作他用。
相關(guān)資源
更多
正為您匹配相似的精品文檔
相關(guān)搜索
鏈接地址：http://www.hcyjhs8.com/p-3789596.html