計(jì)算機(jī)科學(xué)導(dǎo)論-基于計(jì)算思維的思想與方法（第4版） 課件【ch09】問(wèn)題求解的離散結(jié)構(gòu)

計(jì)算機(jī)科學(xué)導(dǎo)論基于計(jì)算思維的思想與方法問(wèn)題求解的離散結(jié)構(gòu)第九章新工科建設(shè)之路·計(jì)算機(jī)類系列教材01數(shù)理邏輯數(shù)理邏輯01一、命題邏輯在數(shù)理邏輯中，能夠分辨真假但不能同時(shí)既真又假的陳述句的內(nèi)容被稱為命題。命題是具有唯一判斷結(jié)果(有明確的對(duì)錯(cuò)之分)的陳述句，而不是類似感嘆的抒情句、祈使句等。命題一定是通過(guò)陳述句來(lái)表達(dá)的，但是陳述句并不一定都是命題。只有明確“真”“假”可言的陳述句才是命題。1.命題和真值數(shù)理邏輯01一、命題邏輯在命題邏輯中，可以通過(guò)連接詞由已知命題產(chǎn)生新的命題，我們把這個(gè)連接命題與命題的字詞稱為命題連接詞。把由簡(jiǎn)單命題通過(guò)連接詞而成的陳述句被稱為復(fù)合命題。構(gòu)成復(fù)合命題的連接詞有5個(gè)，分別為：否定、合取、析取、蘊(yùn)含、等價(jià)，并且此順序?yàn)檫壿嬤\(yùn)算的優(yōu)先級(jí)。2.命題連接詞數(shù)理邏輯01一、命題邏輯3.命題公式數(shù)理邏輯01一、命題邏輯[定義9-7]根據(jù)命題公式A在命題變?cè)娜魏握嬷抵概上缕渲档男再|(zhì)，可分為3種。(1)永真式：如果命題公式A在命題變?cè)娜魏握嬷抵概上缕渲岛銥檎?，則稱A為永真式或重言式，并常用1表示永真式。(2)永假式：如果命題公式A在命題變?cè)娜魏握嬷抵概上缕渲岛銥榧伲瑒t稱A為永假式或矛盾式，常用0表示永假式。(3)可滿足式：如果命題公式A至少有一組命題變?cè)恼嬷抵概墒蛊渲禐檎?，則稱A為可滿足式或可能式。4.命題公式分類定積分的近似計(jì)算01一、數(shù)理邏輯5.邏輯等價(jià)關(guān)系在所有可能的情況下具有相同真值的兩個(gè)復(fù)合命題稱為邏輯等價(jià)。T表示永遠(yuǎn)為真，F(xiàn)表示永遠(yuǎn)為假，則復(fù)合命題的等價(jià)關(guān)系如表9-6所示。定積分的近似計(jì)算01二、謂詞邏輯1.個(gè)體詞(IndividualWord)[定義9-8]在命題邏輯中，個(gè)體詞是指所研究對(duì)象中可以獨(dú)立存在的具體或抽象的客體。在命題邏輯中，個(gè)體詞具有以下三要素。(1)個(gè)體常元；(2)個(gè)體變?cè)?3)個(gè)體域。2.謂詞(PredicateWord)[定義9-9]在命題邏輯中，謂詞是指用來(lái)刻畫個(gè)體詞的性質(zhì)或個(gè)體詞之間相互關(guān)系的詞。定積分的近似計(jì)算01二、謂詞邏輯3.量詞(MeasureWord)[定義9-10]在命題邏輯中，量詞是指表示個(gè)體常元(項(xiàng))或個(gè)體變?cè)?項(xiàng))之間數(shù)量關(guān)系的詞。為了區(qū)分命題中的“所有的”和“有一些”，量詞又分為“全稱量詞”和“存在量詞”。4.謂詞推理(VerbReasoning)謂詞推理是利用命題公式間的各種等價(jià)關(guān)系、蘊(yùn)含關(guān)系，通過(guò)一些推理規(guī)則，從已知命題公式推出一些新的公式。因此，謂詞推理是命題邏輯推理的推廣。定積分的近似計(jì)算01二、謂詞邏輯4.謂詞推理(VerbReasoning)由于謂詞推理不是以整個(gè)命題為推理對(duì)象的，它的推理對(duì)象通常有量詞限制，因而具有以下規(guī)則。(1)全稱量詞消去規(guī)則(2)存在量詞消去規(guī)則(3)全稱量詞引入規(guī)則(4)存在量詞引入規(guī)則定積分的近似計(jì)算01三、數(shù)理邏輯在計(jì)算機(jī)科學(xué)中的應(yīng)用數(shù)理邏輯對(duì)于計(jì)算機(jī)科學(xué)理論的研究有著非常重要的作用，主要體現(xiàn)在以下幾方面。1.培養(yǎng)邏輯思維通過(guò)對(duì)數(shù)理邏輯中所揭示的思維規(guī)律和所用方法的學(xué)習(xí)，能培養(yǎng)自己嚴(yán)密的邏輯思維能力，為計(jì)算機(jī)科學(xué)后繼課程的學(xué)習(xí)奠定良好的基礎(chǔ)。2.作為理論支撐02集合論集合論021.集合的表示集合通常用大寫的英文字母A、B、C、……表示，它的元素通常用小寫的英文字母a、b、c、……表示。表示一個(gè)集合的方法通常有列舉法和描述法。(1)列舉法：也稱枚舉或窮舉法，就是列舉出集合的所有元素，元索之間用逗號(hào)隔開(kāi)，并把它們用“{}”括起來(lái)。(2)描述法：不要求列出集合中的所有元素，只要把集合中的元素具有的性質(zhì)或滿足的條件用文字或字符描述出來(lái)。一、集合的表示與運(yùn)算集合論022.集合間的關(guān)系一、集合的表示與運(yùn)算集合論022.集合間的關(guān)系一、集合的表示與運(yùn)算集合論023.集合的基本運(yùn)算一、集合的表示與運(yùn)算集合論023.集合的基本運(yùn)算一、集合的表示與運(yùn)算集合論02一、集合的表示與運(yùn)算4.集合的文氏圖表示集合之間的運(yùn)算也可以用文氏圖(VennDiagram)來(lái)描述，即用一個(gè)矩形表示全集E，在矩形內(nèi)用圓表示子集，這種表示方法被稱為文氏圖表示法。集合并、集合交、集合差、集合對(duì)稱差、集合補(bǔ)的文氏圖如圖9-3所示。集合論02一、集合的表示與運(yùn)算5.集合運(yùn)算恒等式集合運(yùn)算具有與邏輯運(yùn)算等價(jià)相似的運(yùn)算規(guī)則，集合運(yùn)算的恒等式如表9-9所示。集合論02一、集合的表示與運(yùn)算6.有限集合的計(jì)數(shù)集合論02二、二元關(guān)系1.笛卡爾積集合論02二、二元關(guān)系2.二元關(guān)系定義集合論02二、二元關(guān)系3.二元關(guān)系表示二元關(guān)系通常用三種方式表示有限集之間的關(guān)系：集合表示法、矩陣表示法和關(guān)系圖表示法。集合表示法關(guān)系也是一種特殊的結(jié)合，所以集合兩種基本的表示法也可以用到關(guān)系的表示中，即可用列舉法和描述法來(lái)表示關(guān)系。集合論02二、二元關(guān)系4.二元關(guān)系運(yùn)算集合論02二、二元關(guān)系5.二元關(guān)系的性質(zhì)集合論02二、二元關(guān)系6.二元關(guān)系的特征(1)等價(jià)關(guān)系在實(shí)數(shù)之間的相等關(guān)系、集合之間的相等關(guān)系、謂詞公式之間的等值關(guān)系具有類似的性質(zhì)，它們都具有自反性、對(duì)稱性和傳遞性，具有這三種性質(zhì)的關(guān)系稱為等價(jià)關(guān)系。(2)偏序關(guān)系事物之間的次序常常是事物群體的重要特征，決定事物之間的次序是事物間的關(guān)系一偏序關(guān)系，具有傳遞性，因此可根據(jù)這個(gè)特性來(lái)研究集合中各元素的排序關(guān)系。集合論02三、函數(shù)1.函數(shù)定義集合論02三、函數(shù)2.函數(shù)性質(zhì)如圖9-11所示。集合論02四、集合論在計(jì)算機(jī)科學(xué)中的應(yīng)用1.在程序語(yǔ)言中的應(yīng)用計(jì)算機(jī)內(nèi)部的所有信息、各種編碼都是字符的集合。2.在數(shù)據(jù)結(jié)構(gòu)中的應(yīng)用數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。一個(gè)數(shù)據(jù)結(jié)構(gòu)有兩個(gè)要素：數(shù)據(jù)元素的集合、關(guān)系的集合。3.在數(shù)據(jù)庫(kù)中的應(yīng)用集合在關(guān)系數(shù)據(jù)庫(kù)中有著廣泛的應(yīng)用，數(shù)據(jù)庫(kù)的數(shù)據(jù)模型是以集合、二元關(guān)系、多元關(guān)系和關(guān)系代數(shù)為理論基礎(chǔ)的。03邏輯代數(shù)邏輯代數(shù)03一、邏輯代數(shù)的表示1.邏輯代數(shù)與命題邏輯的區(qū)別邏輯代數(shù)03一、邏輯代數(shù)的表示2.布爾變量及其基本運(yùn)算布爾變量運(yùn)算只有“·”(與)“+”(或)“-”(非)三種?！啊芭c”運(yùn)算：又稱為邏輯乘，兩個(gè)變量“與”運(yùn)算的邏輯關(guān)系可表示為C=A·B?！盎颉边\(yùn)算：又稱為邏輯加，兩個(gè)變量“或”運(yùn)算的邏輯關(guān)系可表示為C=A+B.“非”運(yùn)算：又稱為邏輯反，對(duì)一個(gè)變量“非”運(yùn)算的邏輯關(guān)系可表示為

。邏輯代數(shù)03一、邏輯代數(shù)的表示3.布爾函數(shù)與布爾表達(dá)式布爾代數(shù)的函數(shù)定義與普通代數(shù)的函數(shù)定義極為相似，設(shè)x，y為輸入F為輸出，輸入和輸出之間的邏輯關(guān)系可表示為F=f(x，y)，則稱C是x，y的邏輯函數(shù)，F(xiàn)=f(x，y)為邏輯函數(shù)表達(dá)式。邏輯代數(shù)03一、邏輯代數(shù)的表示4.布爾代數(shù)的恒等關(guān)系布爾代數(shù)運(yùn)算的恒等式如表9-11所示。邏輯代數(shù)03二、邏輯電路的簡(jiǎn)化1.邏輯電路部件把實(shí)現(xiàn)邏輯函數(shù)的電路稱為邏輯電路；把實(shí)現(xiàn)邏輯變量之間的運(yùn)算稱為邏輯運(yùn)算；把由基本邏輯部件組成的電路稱為邏輯電路，邏輯電路中的常用邏輯部件如圖9-13所示。邏輯代數(shù)03三、代數(shù)系統(tǒng)在計(jì)算機(jī)科學(xué)中的應(yīng)用1.提供精簡(jiǎn)的形式化語(yǔ)言2.提供嚴(yán)密的邏輯推理工具3.提供定量分析和計(jì)算方法4.為數(shù)據(jù)通信實(shí)現(xiàn)數(shù)據(jù)編碼5.為生物學(xué)研究提供數(shù)學(xué)支撐04圖論圖論04一、圖論的基本概念1.圖的定義圖論04一、圖論的基本概念2.無(wú)向圖和有向圖圖論04二、圖的矩陣表示1.鄰接矩陣(AdjacencyMatrix)圖論04二、圖的矩陣表示2.關(guān)聯(lián)矩陣(IncidenceMatrix)圖論04三、路徑回路與連通圖1.路徑圖論04三、路徑回路與連通圖2.回路與通路圖論04三、路徑回路與連通圖3.連通圖[定義9-42]在無(wú)向圖G中，節(jié)點(diǎn)u與v之間若存在一條路，則節(jié)點(diǎn)u和v稱為是連通的。若圖G=<V，E>的任意兩個(gè)節(jié)點(diǎn)均有路徑連通，則G稱為連通圖(ConnectedGraph)，否則稱為非連通圖(UnconnectedGraph)。圖論04三、路徑回路與連通圖4.計(jì)算節(jié)點(diǎn)之間的通路數(shù)在一個(gè)圖G中兩個(gè)節(jié)點(diǎn)之間的通路數(shù)可以用這個(gè)圖的鄰接矩陣A來(lái)確定，A相對(duì)于圖中的節(jié)點(diǎn)v1，vn(允許帶有無(wú)向邊、有向邊、多重邊和環(huán))，從vi到Vj長(zhǎng)度為r的不同通