命題邏輯基本概念.ppt

1、1,天津城市建設學院電子與信息工程系 Email: 2010.11-2011.12,2,教育的目的 應該使每個人都充滿夢想！,3,一、緒論 二、數(shù)理邏輯簡介 三、命題邏輯的基本概念 （一）命題的概念 （二）命題表示方法 （三）聯(lián)結詞 （四）命題合式公式 （五）命題公式的翻譯,主要內容,4,漫談離散數(shù)學 Swimming in Discrete Mathematics,一、緒 論,5,數(shù)學？/數(shù)學的研究對象是什么?,心智的產(chǎn)物-珀拉圖;,研究數(shù)和量的學科-亞里士得多,數(shù)學=邏輯-羅素,邏輯是數(shù)學的少年時代; 數(shù)學是邏輯的成年時代,數(shù) 學,數(shù)學作為人類智慧的一種表達形式，反映生動活潑的意念、深入細

2、致的思考、以及完美和諧的愿望。他的基礎是邏輯和直覺、分析和推理、共性和個性。 科朗，羅賓斯（美） 數(shù)學是什么，1941年,6,離散數(shù)學-研究離散結構的數(shù)學分科。（辭海） 相對于研究連續(xù)量的微積分，離散數(shù)學是研究各種各樣的離散量的結構及離散量之間的關系的一門學科。是現(xiàn)代數(shù)學的一個重要分支，是計算機科學與技術的理論基礎，所以又稱為計算機數(shù)學。,離散數(shù)學的含義,7,一、古老 歷史: 計數(shù):自然數(shù) 發(fā)展: 圖論:Konigsberg七橋問題 二、年青 新生: 計算機:二進制運算,離散數(shù)學的由來與發(fā)展,8,離散數(shù)學-現(xiàn)代科學的重要分支,離散數(shù)學是在計算機問世之后，迅速發(fā)展起來的一門數(shù)學分支。 離散數(shù)學改

3、變了傳統(tǒng)數(shù)學中分析和代數(shù)占統(tǒng)治地位的局面。 離散數(shù)學是一門在基礎數(shù)學研究中具有極為重要地位的、綜合的數(shù)學學科。 離散數(shù)學在計算機科學、編碼和密碼學、物理、化學、生物等許多學科中均有重要應用。 離散數(shù)學特點-離散性、抽象性、邏輯性、可行性 這些特點正是離散數(shù)學難學的根本原因，也正是離散數(shù)學深具誘惑和迷人之處。,9,第一部分 數(shù)理邏輯 命題演算、謂詞演算； 公理化集合論、遞歸論、模型論、證明論 -計算機是數(shù)理邏輯和電子學相結合的產(chǎn)物 第二部分 集合論 集合：一種重要的數(shù)據(jù)結構 關系：關系數(shù)據(jù)庫的理論基礎 函數(shù)：所有計算機語言中不可缺少的一部分 第三部分 代數(shù)系統(tǒng) （運算、代數(shù)系統(tǒng)、半群、群、環(huán)、域

4、、格、布爾代數(shù)） 計算機編碼和糾錯碼理論 數(shù)字邏輯設計基礎 計算機使用的各種運算 第四部分 圖論 數(shù)據(jù)結構、操作系統(tǒng)、編譯原理、計算機網(wǎng)絡原理的基礎,離散數(shù)學的內容及與計算機的關系,10,參考教材,1.離散數(shù)學（左孝琳、李為檻、劉永才，上?？萍嘉墨I版） 2.離散數(shù)學學習指導與習題解析 耿素云屈婉玲 高等教育出版社 （2005.3） 3.離散數(shù)學及其應用（Discrete Mathematical and Its Applications) （原書第5版） Kenneth Rosen著袁崇義屈婉玲等譯機械工業(yè)出版社（2007.6）) 4.Discrete Mathematics（ Revised

5、 Edition: Biggs ) 5.離散數(shù)學常見題型解析及模擬題 傅彥西北工業(yè)大學出版社 （2004 ）,11,課程地位,離散數(shù)學課程設置： 計算機系核心課程、信息類專業(yè)必修課程、其它類專業(yè)的重要選修課程,離散數(shù)學的后繼課程： 數(shù)據(jù)結構、編譯系統(tǒng)、人工智能、數(shù)據(jù)庫、操作系統(tǒng)、軟件工程與方法學、計算機網(wǎng)絡、程序設計,12,（1）它給后繼課提供必要的數(shù)學基礎；為以后計算機的軟、硬件學習和研究開發(fā)工作，打下堅實的數(shù)學基礎； （2）通過離散數(shù)學課程的學習，可以培養(yǎng)數(shù)學抽象能力；用數(shù)學語言描述問題的能力；邏輯思維能力；數(shù)學論證能力。即培養(yǎng)抽象、表示、推理、論證的能力； （3）寫出優(yōu)秀的程序來解決實際

6、問題； （4）能夠針對科研和生產(chǎn)中產(chǎn)生的問題來建立數(shù)學模型，設計新的算法并論證算法的有效性；,學習目的,13,典型實例,離散數(shù)學無處不在，主要應用于在各種復雜的關系中找出最優(yōu)方案。 離散數(shù)學完全可以看成是一門量化了的關系學，量化了的運籌學，量化了的管理學。 例如：世界近代三大數(shù)學難題、出差派遣問題、船夫過河問題、工作調度和安排問題、航空調度和航班設定問題、交通規(guī)劃與管理問題、中國郵路問題、工程工序管理問題、地面鋪磚問題、網(wǎng)絡布局問題、金融分析問題、哥尼斯堡七橋問題、一筆畫問題、螞蟻比賽問題,14,典型實例,1、四色猜想問題 一張世界地圖，若用一種顏色對一個國家著色，那么只需四種顏色，即可以保證

7、每兩個相鄰的國家顏色不同。 世界近代三大數(shù)學難題之一。1852年，英國弗南西斯格思里(Francis Guthrie)提出四色猜想。 1976年，在J. Koch的算法的支持下，美國數(shù)學家阿佩爾(Kenneth Appel)與哈肯(Wolfgang Haken)在美國伊利諾斯大學的兩臺不同的電子計算機上，用了1200個小時，作了100億判斷，終于完成了四色定理的證明。最近人們發(fā)現(xiàn)了更簡單的證明。,15,A，B，C，D四人中要派兩個人出差，按下述三個條件有幾種派法？ 如何派？ 若A去則C和D中要去一個人； B和C不能都去； C去則D要留下,2.出差派遣問題,典型實例,3.船夫過河問題,船夫要把一

8、匹狼、一只羊和一棵白菜運過河。只要船夫不在場,羊就會吃白菜、狼就會吃羊。船夫的船每次只能運送一種東西。怎樣才能把三者都運過河?,16,4、工作調度和安排問題,如在生產(chǎn)原子彈的曼哈頓計劃中，涉及到很多工序、很多人員安排、很多元件生產(chǎn)。 怎樣合理調度各種人員的工作？ 怎樣科學安排各種工序間的銜接？ 怎樣計劃使整個工期的時間盡可能短？,5、航空調度和航班設定問題,怎樣周密設定各個航班，以滿足不同旅客轉機的需求？ 怎樣同時也使得每個機場的各個航班的起降分布合理？ 在一些航班有延誤的特殊情況下，怎樣作出科學的調整？,典型實例,17,6、交通規(guī)劃與管理問題,哪些地方可能是阻塞要地？ 哪些地方應設單行道？

9、立交橋建在哪里最合適？ 紅綠燈怎樣設置最合理？,7、中國郵路問題,一個郵遞員送信，要走完他負責投遞的全部街道，完成任務后回到郵局，應按怎樣的路線走，他所走的路程才會最短？ 由我國數(shù)學家管梅谷在1962年首先提出的，因此，在國際上稱為中國郵路問題。,典型實例,18,8、工程工序管理問題,世界著名的假日飯店在其科學管理中嚴格規(guī)定了有關工序： 清潔工第一步是換什么，洗什么？第二步又做什么？同時需要確保他進出房間的次數(shù)最少？ 一個如此簡單的工作都要講究工程工序管理，那么更復雜的的工作就更不用說了。,9、地面鋪磚問題,用形狀相同的方形磚塊，無疑可將地面鋪滿（不考慮邊緣的特殊情況）而如用不同形狀，又非方形

10、的磚塊來鋪地面時，能否鋪滿？ 這一常見的實際的簡單問題，也涉及到很深的數(shù)學原理。,典型實例,19,10、網(wǎng)絡布局問題,一個通信網(wǎng)絡怎樣布局最節(jié)省？ 美國的貝爾實驗室和IBM公司都有世界一流的組合數(shù)學家在研究這個問題。該問題關系到巨大的經(jīng)濟效益。,11、金融分析問題,投資方案的確定 怎樣找出好的投資組合以降低投資風險。 南開大學組合數(shù)學研究中心開發(fā)出“金沙股市風險分析系統(tǒng)”，已投放市場，為短線投資者提供有效的風險防范工具。,典型實例,20,12、一筆畫問題,所謂一筆畫，就是從圖形上的某點出發(fā)，筆不離開紙，而且每條線都只畫一次不準重復。什么樣的圖形能一筆畫成呢？,21,13、螞蟻比賽問題,甲乙兩只

11、螞蟻進行比賽： 從他們所在的結點出發(fā)，在圖中走過所有的點，最后到達C處，如果他們的速度相同，問誰先到達目的地？,22,14、哥尼斯堡七橋問題,18世紀時，歐洲有一個風景秀麗的小城哥尼斯堡，那里有七座橋。如圖所示。當時哥尼斯堡的居民中流傳著一道難題：一個人怎樣才能一次走遍七座橋，每座橋只走過一次，最后回到出發(fā)點？,23,15、環(huán)游世界問題,從正十二面體的一個頂點出發(fā)，沿著正十二面體的棱前進，要把二十個頂點無一遺漏地全部通過，而且每個頂點恰好只通過一次，最后回到出發(fā)點，這樣，便是哈密爾頓周游世界問題。,24,教學要求： 通過該課程的學習，學生應當了解并掌握計算機科學中普遍采用的離散數(shù)學中的一些基本

12、概念、基本思想、基本方法。 自學要求： 通過反復看書及做課后習題，來加深對該課程中的一些基本概念的理解，逐步提高自己的抽象思維和邏輯推理能力。,學習要求,25,離散數(shù)學課程的學習方法: 強調：邏輯性、抽象性； 注重：概念、方法與應用 離散數(shù)學的學習要領： 概念（正確） 必須掌握好離散數(shù)學中大量的概念 判斷（準確） 根據(jù)概念對事物的屬性進行判斷 推理（可靠） 根據(jù)多個判斷推出一個新的判斷,學習方法,26,第一部分 數(shù)理邏輯,數(shù)理邏輯,27,歷史使人聰明， 詩歌使人機智， 數(shù)學使人精細， 哲學使人深邃， 道德使人嚴肅， 邏輯與修辭使人善辯。,數(shù)理邏輯,28,- 一套符號體系 + 一組規(guī)則,邏 輯

13、學：舊稱“名學”、“論理學”，是研究推理的一門學科； 數(shù)理邏輯：用數(shù)學方法研究推理的形式結 構和規(guī)律的一門數(shù)學學科,數(shù)學方法：建立一套符號來描述和討論問題，避免歧義性； 推 理： 就是研究前提和結論之間的關系和 思維規(guī)律，亦即符號之間的關系,數(shù)理邏輯,29,數(shù)理邏輯的創(chuàng)始人是Leibniz，為了實現(xiàn)把推理變?yōu)檠菟愕南敕?，他把?shù)學引入了形式邏輯。其后，又經(jīng)多人努力，逐漸使得數(shù)理邏輯成為一門專門的學科。 上個世紀30年代以后，數(shù)理邏輯進入一個嶄新的發(fā)展階段，邏輯學不僅與數(shù)學結合，還與計算機科學等密切關聯(lián)。 1931年Godel不完全性定理的提出，以及遞歸函數(shù)可計算性的引入，促使了1936年Turi

14、ng機的產(chǎn)生，十年后，第一臺電子計算機問世。,數(shù)理邏輯,30,數(shù)理邏輯在計算機科學中的作用,硬件開發(fā) -硬件電路的表示、分析和設計 軟件設計 -程序算法數(shù)據(jù) -算法邏輯控制,為什么要研究數(shù)理邏輯？ “邏輯是不可戰(zhàn)勝的，因為要反對邏輯還得使用邏輯?！盤.Boutroux 計算機可處理大量信息，要利用計算機就要學會編制“程序”：,31,著名計算機軟件設計大師E.W.Dijkstra曾經(jīng)這樣說：“我現(xiàn)在年紀大了，搞了這么多年軟件，錯誤不知犯了多少，現(xiàn)在覺悟了。我想，假如我早年在數(shù)理邏輯上好好下點功夫的話，我就不會犯這么多的錯誤。不少東西邏輯學家早就說了，可我不知道。要是我能年輕20歲的話，就要回去學

15、邏輯?！?我國著名數(shù)理邏輯學家甚至說得更加直截了當：“事實上，程序設計或者就是數(shù)理邏輯，或者是用計算機語言書寫的數(shù)理邏輯，或者是數(shù)理邏輯在計算機上的應用。”可以說計算機的本質結構就是邏輯結構。,數(shù)理邏輯在計算機科學中的作用,32,數(shù)理邏輯與計算機學、控制論、人工智能的相互滲透推動了其自身的發(fā)展，模糊邏輯、概率邏輯、歸納邏輯、時態(tài)邏輯等都是目前比較熱門的研究領域。 本章和下一章我們只從語義出發(fā)，對數(shù)理邏輯中的命題邏輯與謂詞邏輯等作一簡單的、直接的、非形式化的介紹，將不涉及任何公理系統(tǒng)。,數(shù)理邏輯,33,任何基于命題分析的邏輯稱為命題邏輯。命題是研究思維規(guī)律的科學中的一項基本要素，它是一個判斷的語

16、言表達。,第一章 命題邏輯的基本概念,（一）命題的概念 （二）命題表示方法 （三）聯(lián)結詞 （四）命題合式公式 （五）命題公式的翻譯,34,命題與真值 命 題： 判斷結果是否惟一的陳述句 命題的真值： 判斷的結果 真值的取值： 真與假 真命題與假命題 注意： 感嘆句、祈使句、疑問句都不是命題; 悖論，判斷結果不惟一確定的不是命題.,一、 命題的概念,35,例1 下列句子中那些是命題？ (1) 是有理數(shù). (2) 2 + 5 = 7. (3) x + 5 3. (4) 你去教室嗎？ (5) 這個蘋果真大呀！ (6) 請不要講話！ (7) 2050年元旦下大雪. (8) 我正在說謊。,假命題,真命題

17、,不是命題,不是命題,不是命題,不是命題,命題，但真值現(xiàn)在不知道,悖論，不是命題,36,一個人說：“我正在說謊”。 1)結論：如果他是說謊(命題為T），則他是講真話。 （他認為他是說謊，他實際上是在說真話） 2)結論：如果他講真話(命題為F），則他是在說謊。 (如果他講真話，則他說的是真的，也就是他是在說謊) 此話既不是說謊也不是講真話，不能判斷它的真假值。,不能判斷真假的陳述語句叫悖論（非命題）。,37,再例 A：數(shù)學是一門科學（T） B：四川是一個省 （T） C：2+3=6 （F） D：地球是不動的 （F） E：2010年人將到達火星（T/F） F：今天是十月一日（T/F） G：這菜辣了

18、（T/F）,38,以上所討論的命題在數(shù)理邏輯中稱為簡單命題，或稱為原子命題，用p、q、r、pi、qi、ri等符號表示（亦可用其它小寫的英文字母表示）。如： p：4是偶數(shù)。 在命題邏輯的符號化過程中，通常的要求是每一個引進的表示命題的符號都表示一個原子命題。 例如：將下列命題符號化 杭州不是中國的首都。 解 令P：杭州是中國的首都。則命題“杭州不是中國的首都”符號化為：P,二、 命題的表示方法,39,【例】 下列命題特點： （1）4是偶數(shù)且是2的倍數(shù)。 （2）北京不是個小城市。 （3）小王或小李考試得第一。 （4）如果你努力，則你能成功。 （5）三角形是等邊三角形，當且僅當三內角相等。,由命題和

19、聯(lián)結詞構成的命題稱為復合命題。構成復合命題的可以是原子命題，也可以是另一個復合命題。一個復合命題的真值不僅與構成復合命題的命題的真值有關，而且也與所用聯(lián)結詞有關。,命題分類：簡單命題和復合命題,40,三、聯(lián)結詞（邏輯運算符）,定義1.3 設p, q為兩個命題，復合命題“p或q”稱作p與q的析取式，記作pq，稱作析取聯(lián)結詞. 規(guī)定pq為假當且僅當p與q同時為假.,定義1.1 設 p為命題，復合命題“非p”(或“p的否定”)稱為p的否定式，記作p，符號稱作否定聯(lián)結詞. 規(guī)定p 為真當且僅當p為假.,定義1.2 設p,q為兩個命題，復合命題“p并且q”(或“p與 q”)稱為p與q的合取式，記作pq，

20、稱作合取聯(lián)結詞. 規(guī)定pq為真當且僅當p與q同時為真.自然語言中的表示“并且”意思的聯(lián)結詞，如“既又”、“不但而且”、“雖然但是”、“一面一面”等都可以符號化為。,41,例 將下列命題符號化. （1）設P 表示“整數(shù)都是自然數(shù)”，則P表示：,否定聯(lián)結詞的實例,“并非整數(shù)都是自然數(shù)”或“整數(shù)不都是自然數(shù)”， 而不是“整數(shù)都不是自然數(shù)”。,（2）設P表示“昨天張三去看球賽了”P表示：,“昨天張三沒有去看球賽 若昨天張三去看球賽了，命題P是真的，那么新命題P必然是假的反之，若命題P是假的，那么P就是真的,42,例2 將下列命題符號化. (1) 吳穎既用功又聰明. (2) 吳穎不僅用功而且聰明. (3

21、) 吳穎雖然聰明，但不用功. (4) 張輝與王麗都是三好生. (5) 張輝與王麗是同學.,合取聯(lián)結詞的實例,43,解 令p:吳穎用功, q:吳穎聰明 (1) pq (2) pq (3) pq (4) 設p:張輝是三好生, q:王麗是三好生 pq (5) p:張輝與王麗是同學 (1)(3) 說明描述合取式的靈活性與多樣性 (4)(5) 要求分清 “與” 所聯(lián)結的成分,合取聯(lián)結詞的實例,44,例3 將下列命題符號化 (1) 2 或 4 是素數(shù). (2) 2 或 3 是素數(shù). (3) 4 或 6 是素數(shù). (4) 小元元只能拿一個蘋果或一個梨. (5) 王小紅生于 1975 年或 1976 年.,析

22、取聯(lián)結詞的實例,45,解 (1) 令p:2是素數(shù), q:4是素數(shù), pq (2) 令p:2是素數(shù), q:3是素數(shù), pq (3) 令p:4是素數(shù), q:6是素數(shù), pq (4) 令p:小元元拿一個蘋果, q:小元元拿一個梨 (pq)(pq) (5) p:王小紅生于 1975 年, q:王小紅生于1976 年, (pq)(pq) 或 pq (1)(3) 為相容或 (4)(5) 為排斥或, 符號化時(5)可有兩種形式，而(4)則不能,析取聯(lián)結詞的實例,46,定義1.4 設p, q為兩個命題，復合命題“如果p, 則q”稱作p與q的蘊涵式，記作pq，并稱p是蘊涵式的前件，q為蘊涵式的后件，稱作蘊涵聯(lián)結

23、詞. 規(guī)定：pq為假當且僅當p為真q為假.,蘊涵聯(lián)結詞,(1) pq 的邏輯關系：q為 p 的必要條件 (2) “如果 p, 則 q” 有很多不同的表述方法： 若p，就q 只要p，就q p僅當q 只有q 才p 除非q, 才p 或 除非q，否則非p， (3) 當 p 為假時，pq恒為真，稱為空證明 (4) 常出現(xiàn)的錯誤：不分充分與必要條件,47,例4 設 p：天冷，q：小王穿羽絨服，將下列命題符號化 (1) 只要天冷，小王就穿羽絨服. (2) 因為天冷，所以小王穿羽絨服. (3) 若小王不穿羽絨服，則天不冷. (4) 只有天冷，小王才穿羽絨服. (5) 除非天冷，小王才穿羽絨服. (6) 除非小

24、王穿羽絨服，否則天不冷. (7) 如果天不冷，則小王不穿羽絨服. (8) 小王穿羽絨服僅當天冷的時候.,蘊涵聯(lián)結詞的實例,pq,注意： pq 與 qp 等值（真值相同）,pq,pq,qp,qp,pq,qp,qp,48,說明：數(shù)理邏輯中的聯(lián)結詞是對日常語言中的聯(lián)結詞的一種邏輯抽象，日常語言中聯(lián)結詞所聯(lián)結的句子之間是有一定內在聯(lián)系的，但在數(shù)理邏輯中，聯(lián)結詞所聯(lián)結的命題可以毫無關系。 如與自然語言的不同： 前件與后件可以沒有任何內在聯(lián)系！ p：天下雨了； r：三七二十一。則 pr：如果天下雨，則三七二十一。,49,定義1.5 設 p, q為兩個命題，復合命題“p當且僅當q”稱作p與q的等價式，記作p

25、q，稱作等價聯(lián)結詞. 規(guī)定pq為真當且僅當p與q同時為真或同時為假. pq 的邏輯關系：p與q互為充分必要條件,等價聯(lián)結詞,例5 求下列復合命題的真值 (1) 2 + 2 4 當且僅當 3 + 3 6. (2) 2 + 2 4 當且僅當 3 是偶數(shù). (3) 2 + 2 4 當且僅當 太陽從東方升起. (4) 2 + 2 4 當且僅當 美國位于非洲. (5) 函數(shù) f (x) 在 x0 可導的充要條件是 它在 x0 連續(xù).,1,0,0,1,0,50,取反,均為真,至少一個為真,相同為真,51,總結,以上5種最基本、最常用、最重要的聯(lián)結詞可以組成一個集合 ，成為一個聯(lián)結詞集，其運算的優(yōu)先級為： ， ，對于同一級者，先出現(xiàn)者先運算。,52,補充：,小明和小亮既是兄弟又是同學。,PQ,如果你和他不都是白癡，則你倆都不會去干此傻事。,無論你和他去不去，我去。,53,四、命題合式公式,為了用數(shù)學的方法研究命題，就必須像數(shù)學處理問題那樣將命題公式化，并討論對于這些公式的演算（推理）規(guī)則，以期由給定的公式推導出新的命題公式來。,54,定義1 簡單命題/命題常項/命題常元：真值唯一確定的陳述句。 定義2命題變項/變元：真值可以變化的陳述句。 命題