




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
離散數(shù)學(xué)第三章復(fù)習(xí)與總結(jié)第三章復(fù)習(xí)與總結(jié)基本概念計算方法基本概念集合:子集、冪集、集合的運(yùn)算(交叉并補(bǔ))性質(zhì):冪等律 AA=A,AA=A結(jié)合律 ABC=A(BC)=(AB)CABC=A(BC)=(AB)C交換律 AB=BAAB=BA分配律 A(BC)=(AB)(AC)A(BC)=(AB)(AC)同一/零律 A=A A=排中/矛盾律 AA=EAA=吸收律(大吃小) A(BA)=A,A(BA)=A德摩律 (AB)=AB(AB)=AB雙重否定 A=A
基本概念序偶
定義3.4.1將具有次序的兩對象寫在一塊,稱為序偶即有秩序的二個對象,記為<對象1,對象2>或<x,y>。三元組、n元組
定義3.4.3如果<x,y>是序偶,且<<x,y>,z>也是一個序偶,則稱<x,y,z>為三元組。
定義3.4.4如果<x1,x2,…,xn-1>是n-1元組,而<<x1,x2,…,xn-1>,xn>是序偶,則稱為<x1,x2,…,xn-1,xn>為n元組。笛卡爾積關(guān)系
將笛卡爾積中前后兩個元素之間存在某種關(guān)系的序偶檢出來,便得到一個關(guān)系?;靖拍铌P(guān)系矩陣、關(guān)系圖123abc基本概念關(guān)系復(fù)合
設(shè)F,G為二元關(guān)系,G對F的右復(fù)合記為FG,定義
FG={<x,y>|t(<x,t>F,<t,y>G)}
乘法是合取,加法是析取,復(fù)合性質(zhì):(1)結(jié)合律 (PR)S=P(RS);(2)復(fù)合的逆 (PR)-1=R-1P-1;
(3)不滿足交換率;基本概念關(guān)系的性質(zhì)與分類
自反關(guān)系:xA<x,x>RIAR
反自反關(guān)系:xA<x,x>RIAR=
對稱關(guān)系:<x,y>R<y,x>RR=R-1
反對稱關(guān)系:<x,y>R,<y,x>Rx=y
<x,y>R且xy<y,x>RRR-1IA
傳遞關(guān)系:<x,y>R,<y,z>R<x,z>RR2R
自反:主對角線均為1反自反:主對角線均為0
對稱:M=MT。反對稱:MMT后只有主對角非0
傳遞:R2R即M2M基本概念等價關(guān)系
自反、對稱、可傳遞的關(guān)系稱為等價關(guān)系。等價類
彼此有等價關(guān)系的元素的集合,稱為等價類.
如:{1、4、7},{2、5、8},{3、6}商集
設(shè)RAA,R是等價關(guān)系,A0,A1,…,Ak是基于R得到的等價類,則稱集合{A0,A1,…,Ak}為A關(guān)于R的商集,記為A/R。
如:A={1、2、3、4、5、6、7、8},R={<x,y>|x-y=3k}劃分
若A=A0A1…Ak,且不相交,則稱A的劃分?;靖拍钇蜿P(guān)系
自反、反對稱、可傳遞的關(guān)系。廣義的“小于等于”關(guān)系,記為。全序(線序):
x,yA,x與y都可比。偏序集<A,>:<集合A、偏序關(guān)系>。如:A={,{1,2}}
R1={<x,y>:xy,xA,yA},
<A,R1>
A={,{1},{2},{1,2}}R2={<x,y>:xy,xA,yA},<A,R2>哈斯圖
去掉箭頭;
去掉自旋箭頭;
去掉復(fù)合邊;蓋住:
xA,yA,x<y,
zA,使得x<z<y,則稱y蓋住x.{1,2}{1}{2}{1,2}{1}{2}基本概念最大元、最小元、極大元、極小元
設(shè)<A,R>是偏序集,BA,y0B,若xB,均有<x,y0>R,則y0是B的最大元。
極大元:不存在x使<y0,x>R.上界、下界、上確界、下確界
在偏序集<A,R>中,BA,yA,若任意xB都有<x,y>R,則稱y是B的上界。
在偏序集<A,R>中,BA,設(shè)C為B的所有上界元的集合,若C中有最小元則該最小元稱為B的上確界abcgdfeh123574869第三章復(fù)習(xí)與總結(jié)基本概念計算方法笛卡爾積與復(fù)合的算法:乘法是合取,加法是析取,算法:性質(zhì):(1)結(jié)合律 (PR)S=P(RS)(2)復(fù)合的逆 (PR)-1=R-1P-1MRS=MR
MS=[Cij]計算方法集合計數(shù)
|A1A2
…
|
=
|Ai|-|AiAj|
+|AiAjAk|
-
|AiAjAkAL|
….
+(-1)n-1|A1A2…An|例題在[1,300]整數(shù)中能被3或5或7整除的整數(shù)的個數(shù)。解:A3示能被3整除的數(shù),A5能被5整除,A7能被7整除.能被3整除的個數(shù):|A3|=300/3=100能被5整除的個數(shù):|A5|=300/5=60能被7整除的個數(shù):|A7|=300/7=42能被3與5同時整除的個數(shù):|A3A5|=300/15=20能被3與7同時整除的個數(shù):|A3A7|=300/21=100/7=14能被5與7同時整除的個數(shù):|A5A7|=300/35=60/7=8能被3、5、7同時整除的個數(shù):|A3A5A7|=2能被3或被5或被7整除的個數(shù):|A3A5A7|=|A3|+|A5|+|A7|-|A3A5|-|A3A7|-|A5A7|+|A3A5A7|=100+60+42-20-14-8+2=162計算方法閉包的計算:自反閉包:r(R)=RIA對稱閉包:s(R)=RRT傳遞閉包:t(R)=RR2R3...Rn-1.任何兩點(diǎn)最多n-1步
=MM2M3...Mn-1.t(R)=RR2R3...Rn-1.任何兩點(diǎn)最多n-1步達(dá)=MM2M3...Mn-1.例A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>}t(R)={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>,<a,a>,<a,c>,<b,b>,<b,d>,<c,b>,<d,a>,<d,c>,<a,b>,<a,d>,<b,a>,<b,c>,<b,b>,<c,a>,<c,c>,<d,b>,<d,d>}abcdt(R)=RR2R3...Rn-1.任何兩點(diǎn)最多n-1步達(dá)=MM2M3...Mn-1.效率比較低!Warshall算法for(j=1;j<n;j++){//第1列到最后列for(i=1;i<n;i++{//第j列從第1行到最后行if(M(i,j)=1){第i行=第i行第j行;}}}計算方法等價關(guān)
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- Unit 1 More practice &Culture corner 教學(xué)設(shè)計 2023-2024學(xué)年滬教牛津版英語七年級下冊英語
- 乳腺結(jié)節(jié)診療規(guī)范
- 千圖網(wǎng)與人民幣知識普及
- 2025年河北省保定市徐水區(qū)中考一模語文試題(原卷版+解析版)
- 二零二四年11月種鴿交易電子合同防篡改水印標(biāo)準(zhǔn)
- 普通家庭住宅裝修合同
- 2025年網(wǎng)絡(luò)廣告投放合同模板
- 2025企業(yè)辦公租賃合同簡易版
- 與銀行簽正式合同標(biāo)準(zhǔn)文本
- 保健器械租賃合同標(biāo)準(zhǔn)文本
- GB/T 2272-2020硅鐵
- 可吸收絲素修復(fù)膜(CQZ1900597)
- FZ/T 72016-2012針織復(fù)合服用面料
- 猴子補(bǔ)船看圖寫話-1資料講解課件
- 四川省高等教育自學(xué)考試畢業(yè)生登記表【模板】
- EPC項目設(shè)計管理操作指南
- IEC 61000-4-5 電磁兼容測試標(biāo)準(zhǔn)
- 保潔服務(wù)禮儀培訓(xùn)(共55張)課件
- DB41∕T 1836-2019 礦山地質(zhì)環(huán)境恢復(fù)治理工程施工質(zhì)量驗(yàn)收規(guī)范
- 錫礦選廠生產(chǎn)承包合同
- 企業(yè)員工職務(wù)犯罪培訓(xùn)ppt課件
評論
0/150
提交評論