離散數(shù)學(xué)課件-第4章

離散數(shù)學(xué)課件-第4章目錄CONTENTS集合論基礎(chǔ)關(guān)系圖論初步離散概率論邏輯初步01集合論基礎(chǔ)010204集合的定義與表示理解集合的基本概念和表示方法集合是由確定的、不同的元素所組成的總體。常用大括號(hào){}來(lái)表示集合，元素之間用逗號(hào)隔開?？占硎緵]有任何元素的集合，常用希臘字母?表示。03一個(gè)集合中的所有元素都是另一個(gè)集合中的元素，則稱這個(gè)集合為另一個(gè)集合的子集。子集超集補(bǔ)集一個(gè)集合的所有元素都屬于另一個(gè)集合，則稱這個(gè)集合為另一個(gè)集合的超集。一個(gè)集合中不屬于另一個(gè)集合的元素組成的集合稱為另一個(gè)集合的補(bǔ)集。030201子集、超集與補(bǔ)集兩個(gè)集合中共同的元素組成的集合稱為這兩個(gè)集合的交集。交運(yùn)算兩個(gè)集合中所有元素組成的集合稱為這兩個(gè)集合的并集。并運(yùn)算從一個(gè)集合中去除另一個(gè)集合中的元素后得到的集合稱為這兩個(gè)集合的差集。差運(yùn)算集合的運(yùn)算：交、并、差02關(guān)系總結(jié)詞關(guān)系的定義與表示是離散數(shù)學(xué)中的基本概念，它們?yōu)楹罄m(xù)學(xué)習(xí)提供了基礎(chǔ)。詳細(xì)描述在離散數(shù)學(xué)中，關(guān)系被定義為兩個(gè)集合之間的映射關(guān)系，通常用笛卡爾積來(lái)表示。關(guān)系可以用多種方式表示，如矩陣、圖等。關(guān)系在集合論、邏輯、數(shù)據(jù)庫(kù)等領(lǐng)域有著廣泛的應(yīng)用。關(guān)系的定義與表示關(guān)系的性質(zhì)是關(guān)系的基本特征，它們決定了關(guān)系的內(nèi)在規(guī)律?？偨Y(jié)詞自反關(guān)系是指集合中的元素與其自身有映射關(guān)系；對(duì)稱關(guān)系是指對(duì)于任意兩個(gè)元素，如果它們之間有關(guān)系，則它們之間的關(guān)系是對(duì)稱的；傳遞關(guān)系是指如果元素A和元素B有關(guān)系，且元素B和元素C有關(guān)系，則元素A和元素C有關(guān)系。這些性質(zhì)在邏輯推理、集合運(yùn)算等領(lǐng)域有著重要的應(yīng)用。詳細(xì)描述關(guān)系的性質(zhì)：自反、對(duì)稱、傳遞總結(jié)詞閉包運(yùn)算是離散數(shù)學(xué)中處理關(guān)系的重要工具，它能夠描述關(guān)系的擴(kuò)展和限制。詳細(xì)描述閉包運(yùn)算是一種將關(guān)系進(jìn)行轉(zhuǎn)換的操作，通過(guò)閉包運(yùn)算可以獲得原關(guān)系的擴(kuò)展或限制。閉包運(yùn)算在數(shù)據(jù)庫(kù)設(shè)計(jì)、集合運(yùn)算等領(lǐng)域有著廣泛的應(yīng)用，它可以用于處理關(guān)系的并、交、差等運(yùn)算，以及解決一些復(fù)雜的關(guān)系問題。關(guān)系的閉包運(yùn)算03圖論初步節(jié)點(diǎn)邊定向圖與無(wú)向圖權(quán)重圖的基本概念01020304圖中的頂點(diǎn)稱為節(jié)點(diǎn)。連接兩個(gè)節(jié)點(diǎn)的線段稱為邊。邊是否有方向決定圖是有向圖還是無(wú)向圖。邊的權(quán)重表示兩個(gè)節(jié)點(diǎn)之間的距離或連接強(qiáng)度。一系列的邊和節(jié)點(diǎn)，其中每條邊都有一個(gè)方向。路徑有方向的路徑，起點(diǎn)和終點(diǎn)是同一個(gè)節(jié)點(diǎn)?；芈穬蓚€(gè)節(jié)點(diǎn)之間的最短路徑是路徑長(zhǎng)度最小的一條路徑。最短路徑至少經(jīng)過(guò)圖中的每條邊一次的路徑，不一定經(jīng)過(guò)所有節(jié)點(diǎn)。歐拉路徑路徑與回路如果圖中任意兩個(gè)節(jié)點(diǎn)之間都存在一條路徑，則圖是連通的。連通性有向圖中，如果任意兩個(gè)節(jié)點(diǎn)都存在有向路徑，則為強(qiáng)連通圖；無(wú)向圖中，任意兩個(gè)節(jié)點(diǎn)都存在路徑，則為弱連通圖。強(qiáng)連通圖與弱連通圖表示一個(gè)圖連通性的度量，表示需要多少個(gè)節(jié)點(diǎn)或邊才能將圖分割成不連通的子圖。連通度一個(gè)連通無(wú)向圖中，連接所有節(jié)點(diǎn)且邊的權(quán)值和最小的樹稱為最小生成樹。最小生成樹圖的連通性04離散概率論描述隨機(jī)事件發(fā)生的可能性大小的量度。概率必然事件不可能事件互斥事件概率等于1的事件，表示一定會(huì)發(fā)生。概率等于0的事件，表示一定不會(huì)發(fā)生。兩個(gè)事件不能同時(shí)發(fā)生。概率的基本概念一個(gè)事件在另一個(gè)事件已經(jīng)發(fā)生的條件下的發(fā)生概率。條件概率兩個(gè)事件之間沒有相互影響，一個(gè)事件的發(fā)生不影響另一個(gè)事件的發(fā)生概率。獨(dú)立性計(jì)算復(fù)雜事件的概率，通過(guò)將其分解為若干個(gè)互斥事件的概率的和。全概率公式條件概率與獨(dú)立性取值可以一一列舉的隨機(jī)變量。離散隨機(jī)變量描述離散隨機(jī)變量取每個(gè)可能值的概率。分布列離散隨機(jī)變量的所有可能取值的概率加權(quán)和。期望值描述離散隨機(jī)變量取值分散程度的量度。方差離散隨機(jī)變量及其分布05邏輯初步命題一個(gè)具有真假意義的陳述句?；久}永真、永假和可變真假三種類型。復(fù)合命題由基本命題通過(guò)邏輯聯(lián)結(jié)詞組合而成的命題。邏輯聯(lián)結(jié)詞與、或、非、蘊(yùn)含等。命題邏輯謂詞邏輯是命題邏輯的擴(kuò)展，它引入了變量和謂詞的概念，可以更精確地描述事物之間的關(guān)系。謂詞：表示某個(gè)事物的性質(zhì)或關(guān)系的詞。變量：表示某個(gè)事物的符號(hào)。謂詞邏輯中的命題由謂詞、變量和量詞組成。01020304謂詞邏輯演繹推理從特殊到一般的推理方式，即從個(gè)別性命題推導(dǎo)出普遍性命題。歸納推理反證法枚舉