命題邏輯基本概念.ppt

《命題邏輯基本概念.ppt》由會員分享，可在線閱讀，更多相關《命題邏輯基本概念.ppt（58頁珍藏版）》請在裝配圖網上搜索。

1,,天津城市建設學院電子與信息工程系Email:yangf1918@2010.11-2011.12,2,教育的目的應該使每個人都充滿夢想！,3,一、緒論二、數(shù)理邏輯簡介三、命題邏輯的基本概念（一）命題的概念（二）命題表示方法（三）聯(lián)結詞（四）命題合式公式（五）命題公式的翻譯,主要內容,4,,漫談離散數(shù)學SwimminginDiscreteMathematics,一、緒論,5,,數(shù)學？/數(shù)學的研究對象是什么?,心智的產物--珀拉圖;,研究數(shù)和量的學科--亞里士得多,數(shù)學==邏輯--羅素,邏輯是數(shù)學的少年時代;數(shù)學是邏輯的成年時代,數(shù)學,數(shù)學作為人類智慧的一種表達形式，反映生動活潑的意念、深入細致的思考、以及完美和諧的愿望。他的基礎是邏輯和直覺、分析和推理、共性和個性?？评剩_賓斯（美）《數(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ù)學改變了傳統(tǒng)數(shù)學中分析和代數(shù)占統(tǒng)治地位的局面。離散數(shù)學是一門在基礎數(shù)學研究中具有極為重要地位的、綜合的數(shù)學學科。離散數(shù)學在計算機科學、編碼和密碼學、物理、化學、生物等許多學科中均有重要應用。離散數(shù)學特點--離散性、抽象性、邏輯性、可行性這些特點正是離散數(shù)學難學的根本原因，也正是離散數(shù)學深具誘惑和迷人之處。,9,第一部分數(shù)理邏輯命題演算、謂詞演算；公理化集合論、遞歸論、模型論、證明論---------計算機是數(shù)理邏輯和電子學相結合的產物第二部分集合論集合：一種重要的數(shù)據結構關系：關系數(shù)據庫的理論基礎函數(shù)：所有計算機語言中不可缺少的一部分第三部分代數(shù)系統(tǒng)（運算、代數(shù)系統(tǒng)、半群、群、環(huán)、域、格、布爾代數(shù)）計算機編碼和糾錯碼理論數(shù)字邏輯設計基礎計算機使用的各種運算第四部分圖論數(shù)據結構、操作系統(tǒng)、編譯原理、計算機網絡原理的基礎,離散數(shù)學的內容及與計算機的關系,10,參考教材,1.離散數(shù)學（左孝琳、李為檻、劉永才，上?？萍嘉墨I版）2.離散數(shù)學學習指導與習題解析耿素云屈婉玲高等教育出版社（2005.3）3.離散數(shù)學及其應用（DiscreteMathematicalandItsApplications)（原書第5版）KennethRosen著袁崇義屈婉玲等譯機械工業(yè)出版社（2007.6）)4.DiscreteMathematics（RevisedEdition:Biggs)5.離散數(shù)學—常見題型解析及模擬題傅彥西北工業(yè)大學出版社（2004）,11,,課程地位,離散數(shù)學課程設置：計算機系核心課程、信息類專業(yè)必修課程、其它類專業(yè)的重要選修課程,離散數(shù)學的后繼課程：數(shù)據結構、編譯系統(tǒng)、人工智能、數(shù)據庫、操作系統(tǒng)、軟件工程與方法學、計算機網絡、程序設計……,12,（1）它給后繼課提供必要的數(shù)學基礎；為以后計算機的軟、硬件學習和研究開發(fā)工作，打下堅實的數(shù)學基礎；（2）通過離散數(shù)學課程的學習，可以培養(yǎng)數(shù)學抽象能力；用數(shù)學語言描述問題的能力；邏輯思維能力；數(shù)學論證能力。即培養(yǎng)抽象、表示、推理、論證的能力；（3）寫出優(yōu)秀的程序來解決實際問題；（4）能夠針對科研和生產中產生的問題來建立數(shù)學模型，設計新的算法并論證算法的有效性；,學習目的,13,典型實例,離散數(shù)學無處不在，主要應用于在各種復雜的關系中找出最優(yōu)方案。離散數(shù)學完全可以看成是一門量化了的關系學，量化了的運籌學，量化了的管理學。例如：世界近代三大數(shù)學難題、出差派遣問題、船夫過河問題、工作調度和安排問題、航空調度和航班設定問題、交通規(guī)劃與管理問題、中國郵路問題、工程工序管理問題、地面鋪磚問題、網絡布局問題、金融分析問題、哥尼斯堡七橋問題、一筆畫問題、螞蟻比賽問題,14,典型實例,1、四色猜想問題一張世界地圖，若用一種顏色對一個國家著色，那么只需四種顏色，即可以保證每兩個相鄰的國家顏色不同。世界近代三大數(shù)學難題之一。1852年，英國弗南西斯格思里(FrancisGuthrie)提出四色猜想。1976年，在J.Koch的算法的支持下，美國數(shù)學家阿佩爾(KennethAppel)與哈肯(WolfgangHaken)在美國伊利諾斯大學的兩臺不同的電子計算機上，用了1200個小時，作了100億判斷，終于完成了四色定理的證明。最近人們發(fā)現(xiàn)了更簡單的證明。,15,A，B，C，D四人中要派兩個人出差，按下述三個條件有幾種派法？如何派？若A去則C和D中要去一個人；B和C不能都去；C去則D要留下．,2.出差派遣問題,典型實例,3.船夫過河問題,船夫要把一匹狼、一只羊和一棵白菜運過河。只要船夫不在場,羊就會吃白菜、狼就會吃羊。船夫的船每次只能運送一種東西。怎樣才能把三者都運過河?,16,4、工作調度和安排問題,如在生產原子彈的曼哈頓計劃中，涉及到很多工序、很多人員安排、很多元件生產。怎樣合理調度各種人員的工作？怎樣科學安排各種工序間的銜接？怎樣計劃使整個工期的時間盡可能短？,5、航空調度和航班設定問題,怎樣周密設定各個航班，以滿足不同旅客轉機的需求？怎樣同時也使得每個機場的各個航班的起降分布合理？在一些航班有延誤的特殊情況下，怎樣作出科學的調整？,典型實例,17,6、交通規(guī)劃與管理問題,哪些地方可能是阻塞要地？哪些地方應設單行道？立交橋建在哪里最合適？紅綠燈怎樣設置最合理？,7、中國郵路問題,一個郵遞員送信，要走完他負責投遞的全部街道，完成任務后回到郵局，應按怎樣的路線走，他所走的路程才會最短？由我國數(shù)學家管梅谷在1962年首先提出的，因此，在國際上稱為中國郵路問題。,典型實例,18,8、工程工序管理問題,世界著名的假日飯店在其科學管理中嚴格規(guī)定了有關工序：清潔工第一步是換什么，洗什么？第二步又做什么？同時需要確保他進出房間的次數(shù)最少？一個如此簡單的工作都要講究工程工序管理，那么更復雜的的工作就更不用說了。,9、地面鋪磚問題,用形狀相同的方形磚塊，無疑可將地面鋪滿（不考慮邊緣的特殊情況）而如用不同形狀，又非方形的磚塊來鋪地面時，能否鋪滿？這一常見的實際的簡單問題，也涉及到很深的數(shù)學原理。,典型實例,19,10、網絡布局問題,一個通信網絡怎樣布局最節(jié)?。棵绹呢悹枌嶒炇液虸BM公司都有世界一流的組合數(shù)學家在研究這個問題。該問題關系到巨大的經濟效益。,11、金融分析問題,投資方案的確定怎樣找出好的投資組合以降低投資風險。南開大學組合數(shù)學研究中心開發(fā)出“金沙股市風險分析系統(tǒng)”，已投放市場，為短線投資者提供有效的風險防范工具。,典型實例,20,12、一筆畫問題,所謂一筆畫，就是從圖形上的某點出發(fā)，筆不離開紙，而且每條線都只畫一次不準重復。什么樣的圖形能一筆畫成呢？,,21,13、螞蟻比賽問題,甲乙兩只螞蟻進行比賽：從他們所在的結點出發(fā)，在圖中走過所有的點，最后到達C處，如果他們的速度相同，問誰先到達目的地？,22,14、哥尼斯堡七橋問題,18世紀時，歐洲有一個風景秀麗的小城哥尼斯堡，那里有七座橋。如圖所示。當時哥尼斯堡的居民中流傳著一道難題：一個人怎樣才能一次走遍七座橋，每座橋只走過一次，最后回到出發(fā)點？,23,15、環(huán)游世界問題,從正十二面體的一個頂點出發(fā)，沿著正十二面體的棱前進，要把二十個頂點無一遺漏地全部通過，而且每個頂點恰好只通過一次，最后回到出發(fā)點，這樣，便是哈密爾頓周游世界問題。,24,教學要求：通過該課程的學習，學生應當了解并掌握計算機科學中普遍采用的離散數(shù)學中的一些基本概念、基本思想、基本方法。自學要求：通過反復看書及做課后習題，來加深對該課程中的一些基本概念的理解，逐步提高自己的抽象思維和邏輯推理能力。,學習要求,25,離散數(shù)學課程的學習方法:強調：邏輯性、抽象性；注重：概念、方法與應用離散數(shù)學的學習要領：概念（正確）必須掌握好離散數(shù)學中大量的概念判斷（準確）根據概念對事物的屬性進行判斷推理（可靠）根據多個判斷推出一個新的判斷,學習方法,26,第一部分數(shù)理邏輯,數(shù)理邏輯,27,歷史使人聰明，詩歌使人機智，數(shù)學使人精細，哲學使人深邃，道德使人嚴肅，邏輯與修辭使人善辯。,數(shù)理邏輯,28,------一套符號體系+一組規(guī)則,邏輯學：舊稱“名學”、“論理學”，是研究推理的一門學科；數(shù)理邏輯：用數(shù)學方法研究推理的形式結構和規(guī)律的一門數(shù)學學科,數(shù)學方法：建立一套符號來描述和討論問題，避免歧義性；推理：就是研究前提和結論之間的關系和思維規(guī)律，亦即符號之間的關系,數(shù)理邏輯,29,數(shù)理邏輯的創(chuàng)始人是Leibniz，為了實現(xiàn)把推理變?yōu)檠菟愕南敕?，他把?shù)學引入了形式邏輯。其后，又經多人努力，逐漸使得數(shù)理邏輯成為一門專門的學科。上個世紀30年代以后，數(shù)理邏輯進入一個嶄新的發(fā)展階段，邏輯學不僅與數(shù)學結合，還與計算機科學等密切關聯(lián)。1931年Godel不完全性定理的提出，以及遞歸函數(shù)可計算性的引入，促使了1936年Turing機的產生，十年后，第一臺電子計算機問世。,數(shù)理邏輯,30,數(shù)理邏輯在計算機科學中的作用,硬件開發(fā)----硬件電路的表示、分析和設計軟件設計----程序＝算法＋數(shù)據---算法＝邏輯＋控制,為什么要研究數(shù)理邏輯？“邏輯是不可戰(zhàn)勝的，因為要反對邏輯還得使用邏輯?！薄狿.Boutroux計算機可處理大量信息，要利用計算機就要學會編制“程序”：,31,著名計算機軟件設計大師E.W.Dijkstra曾經這樣說：“我現(xiàn)在年紀大了，搞了這么多年軟件，錯誤不知犯了多少，現(xiàn)在覺悟了。我想，假如我早年在數(shù)理邏輯上好好下點功夫的話，我就不會犯這么多的錯誤。不少東西邏輯學家早就說了，可我不知道。要是我能年輕20歲的話，就要回去學邏輯?！蔽覈麛?shù)理邏輯學家甚至說得更加直截了當：“事實上，程序設計或者就是數(shù)理邏輯，或者是用計算機語言書寫的數(shù)理邏輯，或者是數(shù)理邏輯在計算機上的應用。”可以說計算機的本質結構就是邏輯結構。,數(shù)理邏輯在計算機科學中的作用,32,數(shù)理邏輯與計算機學、控制論、人工智能的相互滲透推動了其自身的發(fā)展，模糊邏輯、概率邏輯、歸納邏輯、時態(tài)邏輯等都是目前比較熱門的研究領域。本章和下一章我們只從語義出發(fā)，對數(shù)理邏輯中的命題邏輯與謂詞邏輯等作一簡單的、直接的、非形式化的介紹，將不涉及任何公理系統(tǒng)。,數(shù)理邏輯,33,任何基于命題分析的邏輯稱為命題邏輯。命題是研究思維規(guī)律的科學中的一項基本要素，它是一個判斷的語言表達。,第一章命題邏輯的基本概念,（一）命題的概念（二）命題表示方法（三）聯(lián)結詞（四）命題合式公式（五）命題公式的翻譯,34,命題與真值命題：判斷結果是否惟一的陳述句命題的真值：判斷的結果真值的取值：真與假真命題與假命題注意：感嘆句、祈使句、疑問句都不是命題;悖論，判斷結果不惟一確定的不是命題.,一、命題的概念,35,例1下列句子中那些是命題？(1)是有理數(shù).(2)2+5=7.(3)x+5>3.(4)你去教室嗎？(5)這個蘋果真大呀！(6)請不要講話！(7)2050年元旦下大雪.(8)我正在說謊。,假命題,真命題,不是命題,不是命題,不是命題,不是命題,命題，但真值現(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：這菜辣了（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）三角形是等邊三角形，當且僅當三內角相等。,由命題和聯(lián)結詞構成的命題稱為復合命題。構成復合命題的可以是原子命題，也可以是另一個復合命題。一個復合命題的真值不僅與構成復合命題的命題的真值有關，而且也與所用聯(lián)結詞有關。,命題分類：簡單命題和復合命題,40,三、聯(lián)結詞（邏輯運算符）,定義1.3設p,q為兩個命題，復合命題“p或q”稱作p與q的析取式，記作p∨q，∨稱作析取聯(lián)結詞.規(guī)定p∨q為假當且僅當p與q同時為假.,定義1.1設p為命題，復合命題“非p”(或“p的否定”)稱為p的否定式，記作?p，符號?稱作否定聯(lián)結詞.規(guī)定?p為真當且僅當p為假.,定義1.2設p,q為兩個命題，復合命題“p并且q”(或“p與q”)稱為p與q的合取式，記作p∧q，∧稱作合取聯(lián)結詞.規(guī)定p∧q為真當且僅當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)吳穎雖然聰明，但不用功.(4)張輝與王麗都是三好生.(5)張輝與王麗是同學.,合取聯(lián)結詞的實例,43,解令p:吳穎用功,q:吳穎聰明(1)p?q(2)p?q(3)?p?q(4)設p:張輝是三好生,q:王麗是三好生p?q(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年.,析取聯(lián)結詞的實例,45,解(1)令p:2是素數(shù),q:4是素數(shù),p?q(2)令p:2是素數(shù),q:3是素數(shù),p?q(3)令p:4是素數(shù),q:6是素數(shù),p?q(4)令p:小元元拿一個蘋果,q:小元元拿一個梨(p??q)?(?p?q)(5)p:王小紅生于1975年,q:王小紅生于1976年,(p??q)?(?p?q)或p?q(1)—(3)為相容或(4)—(5)為排斥或,符號化時(5)可有兩種形式，而(4)則不能,析取聯(lián)結詞的實例,46,定義1.4設p,q為兩個命題，復合命題“如果p,則q”稱作p與q的蘊涵式，記作p?q，并稱p是蘊涵式的前件，q為蘊涵式的后件，?稱作蘊涵聯(lián)結詞.規(guī)定：p?q為假當且僅當p為真q為假.,蘊涵聯(lián)結詞,(1)p?q的邏輯關系：q為p的必要條件(2)“如果p,則q”有很多不同的表述方法：若p，就q只要p，就qp僅當q只有q才p除非q,才p或除非q，否則非p，…．(3)當p為假時，p?q恒為真，稱為空證明(4)常出現(xiàn)的錯誤：不分充分與必要條件,47,例4設p：天冷，q：小王穿羽絨服，將下列命題符號化(1)只要天冷，小王就穿羽絨服.(2)因為天冷，所以小王穿羽絨服.(3)若小王不穿羽絨服，則天不冷.(4)只有天冷，小王才穿羽絨服.(5)除非天冷，小王才穿羽絨服.(6)除非小王穿羽絨服，否則天不冷.(7)如果天不冷，則小王不穿羽絨服.(8)小王穿羽絨服僅當天冷的時候.,蘊涵聯(lián)結詞的實例,p?q,注意：p?q與?q??p等值（真值相同）,p?q,p?q,q?p,q?p,p?q,q?p,q?p,48,說明：數(shù)理邏輯中的聯(lián)結詞是對日常語言中的聯(lián)結詞的一種邏輯抽象，日常語言中聯(lián)結詞所聯(lián)結的句子之間是有一定內在聯(lián)系的，但在數(shù)理邏輯中，聯(lián)結詞所聯(lián)結的命題可以毫無關系。如與自然語言的不同：前件與后件可以沒有任何內在聯(lián)系！p：天下雨了；r：三七二十一。則p→r：如果天下雨，則三七二十一。,49,定義1.5設p,q為兩個命題，復合命題“p當且僅當q”稱作p與q的等價式，記作p?q，?稱作等價聯(lián)結詞.規(guī)定p?q為真當且僅當p與q同時為真或同時為假.p?q的邏輯關系：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,補充：,小明和小亮既是兄弟又是同學。,,,P∧Q,如果你和他不都是白癡，則你倆都不會去干此傻事。,無論你和他去不去，我去。,53,四、命題合式公式,為了用數(shù)學的方法研究命題，就必須像數(shù)學處理問題那樣將命題公式化，并討論對于這些公式的演算（推理）規(guī)則，以期由給定的公式推導出新的命題公式來。,54,定義1簡單命題/命題常項/命題常元：真值唯一確定的陳述句。定義2命題變項/變元：真值可以變化的陳述句。命題常項與命題變項都可以用p,q,r…等表示，具體情況由上下文確定。定義3合式公式/命題公式：將命題變項用聯(lián)結詞和圓括號按一定的邏輯關系聯(lián)結起來的符號串。當使用聯(lián)結詞集{?，∧，∨，?，?}時，合式公式定義如下：,55,定義4合式公式（簡稱公式）的遞歸定義：,(1)單個命題變項和命題常項是合式公式,稱作原子命題公式；,(2)若A是合式公式，則(?A)也是合式公式；,(3)若A,B是合式公式，則(A?B),(A?B),(A?B),(A?B)也是合式公式；,(4)只有有限次地應用(1)—(3)形成的符號串才是合式公式。,,56,五、命題公式的翻譯,命題的翻譯把自然語言中的有些語句，轉變成數(shù)理邏輯中的符號形式，稱為命題的翻譯。命題翻譯關鍵在于公式的邏輯含義與語句的邏輯含義保持一致。,例：假如上午不下雨，我去看電影，否則就在家里讀書或看報。,解：設P：上午下雨；Q：我去看電影；R：我在家里讀書；S：我在家里看報。本例可表示為：（?P?Q）∧（P?（R∨S））。,57,解釋：指定命題變元代表某個具體的命題【例】公式：A=（p∧q）→r。解釋I1：假設p：現(xiàn)在是白天，q：現(xiàn)在是晴天，r：我們能看見太陽。則A：如果現(xiàn)在是白天且是晴天，則我們能看見太陽。其真值為1。解釋I2：假設p、q如上，r：我們能看見星星。則A：如果現(xiàn)在是白天且是晴天，則我們能看見星星。其真值為0。,,命題公式的解釋,58,定義1.8設p1,p2,…,pn是出現(xiàn)在公式A中的全部命題變項,給p1,p2,…,pn各指定一個真值,稱為對A的一個賦值或解釋.若使A為1,則稱這組值為A的成真賦值;若使A為0,則稱這組值為A的成假賦值.幾點說明：A中僅出現(xiàn)p1,p2,…,pn，給A賦值?=?1?2…?n指p1=?1,p2=?2,…,pn=?n,?i=0或1,?i間不加標點符號含n個命題變項的公式有2n個賦值.如000,010,101,110是?(p?q)?r的成真賦值001,011,100,111是成假賦值.,公式賦值,