計算機科學導論-基于計算思維的思想與方法（第4版） 課件【ch09】問題求解的離散結構

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

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