命題邏輯基本概念.ppt

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

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