離散數(shù)學(xué)-命題邏輯2013下

離散數(shù)學(xué)中國石油大學(xué)（華東）計(jì)算機(jī)與通信工程學(xué)院計(jì)算機(jī)科學(xué)系06二月2023《離散數(shù)學(xué)》(DiscreteMathematics)課程學(xué)時(shí)：80裴振奎peizhk@126.com計(jì)算機(jī)與通信工程學(xué)院計(jì)算機(jī)科學(xué)系離散數(shù)學(xué)

DiscreteMathematics裴振奎peizhk@126.com離散數(shù)學(xué)研究離散數(shù)量關(guān)系和離散結(jié)構(gòu)數(shù)學(xué)模型的數(shù)學(xué)分支統(tǒng)稱為離散數(shù)學(xué)。離散數(shù)學(xué)是計(jì)算機(jī)科學(xué)中基礎(chǔ)理論的核心課程。以研究離散量的結(jié)構(gòu)和相互之間的關(guān)系為主要目標(biāo)，其研究對(duì)象一般地是有限個(gè)或可數(shù)個(gè)元素，它充分描述了計(jì)算機(jī)科學(xué)離散性的特點(diǎn)。計(jì)算機(jī)科學(xué)——離散數(shù)學(xué)數(shù)字電子計(jì)算機(jī)的飛速發(fā)展與廣泛應(yīng)用，極大地沖擊了現(xiàn)代數(shù)學(xué)。無論計(jì)算機(jī)科學(xué)本身，還是與計(jì)算機(jī)科學(xué)及其應(yīng)用密切相關(guān)的現(xiàn)代科學(xué)研究領(lǐng)域，都面臨這樣一些問題：

如何高速、有效地處理離散的對(duì)象和離散的數(shù)量關(guān)系，如何對(duì)離散結(jié)構(gòu)建立離散數(shù)學(xué)模型，又如何將已用連續(xù)數(shù)量關(guān)系建立起來的數(shù)學(xué)模型離散化，從而可由計(jì)算機(jī)加以處理。離散數(shù)學(xué)——未來計(jì)算機(jī)系統(tǒng)的創(chuàng)新離散數(shù)學(xué)課程所提供的訓(xùn)練，十分有益于學(xué)生概括抽象能力、邏輯思維能力、歸納構(gòu)造能力的提高，十分有益于學(xué)生嚴(yán)謹(jǐn)、完整、規(guī)范的科學(xué)態(tài)度的培養(yǎng)。這些能力與態(tài)度是一切軟、硬件計(jì)算機(jī)科學(xué)工作者所不可缺少的。就象20世紀(jì)30年代圖靈機(jī)的提出為現(xiàn)代計(jì)算機(jī)奠定基礎(chǔ)一樣，未來計(jì)算機(jī)系統(tǒng)的創(chuàng)新也取決于人類對(duì)離散結(jié)構(gòu)、計(jì)算（包括思維與推理）模型的研究取得新的突破。學(xué)習(xí)離散數(shù)學(xué)——學(xué)習(xí)微積分計(jì)算機(jī)求解基本模式:

實(shí)際問題數(shù)學(xué)建模算法設(shè)計(jì)編程實(shí)現(xiàn)離散數(shù)學(xué)的作用：◆為數(shù)學(xué)建模打下知識(shí)基礎(chǔ)

◆為算法設(shè)計(jì)提供具體指導(dǎo)有人預(yù)計(jì)，未來社會(huì)將有越來越多的人學(xué)習(xí)離散數(shù)學(xué),就象當(dāng)今人們學(xué)習(xí)微積分教程一樣。教材與教輔課程教材左孝凌,李為鑒,劉永才編著.離散數(shù)學(xué).上海科學(xué)技術(shù)文獻(xiàn)出版社，2006年12月第54次印刷．左孝凌,李為鑒,劉永才編著.離散數(shù)學(xué)理論.分析.題解.上海科學(xué)技術(shù)文獻(xiàn)出版社，2002年1月.其它參考書《離散數(shù)學(xué)教程》

耿素云屈婉玲等編著北京大學(xué)出版社

DISCRETEMATHEMATICSANDITSAPPLICATIONS(FIFTHEDITION)離散數(shù)學(xué)及其應(yīng)用，機(jī)械工業(yè)出版社(4小時(shí)出庫)

(4小時(shí)出庫)

目錄第一篇數(shù)理邏輯第二篇集合論第三篇代數(shù)系統(tǒng)第四篇圖論抽象代數(shù)結(jié)構(gòu)——圖靈機(jī)布爾代數(shù)——電子計(jì)算機(jī)硬件設(shè)計(jì)半群理論——自動(dòng)機(jī)和形式語言關(guān)系代數(shù)理論——數(shù)據(jù)庫的理論模型泛代數(shù)——程序設(shè)計(jì)方法學(xué)研究…………姚期智：圖靈獎(jiǎng)（TuringAward）1946年12月24日生，美籍華人，計(jì)算機(jī)科學(xué)家，2000年圖靈獎(jiǎng)得主，是目前唯一一位獲得此獎(jiǎng)項(xiàng)的華人及亞洲人。目前是清華大學(xué)理論計(jì)算機(jī)科學(xué)研究中心教授。圖靈獎(jiǎng)是世界計(jì)算機(jī)科學(xué)領(lǐng)域的最高獎(jiǎng)項(xiàng)，與物理、化學(xué)、醫(yī)學(xué)、經(jīng)濟(jì)學(xué)領(lǐng)域的諾貝爾獎(jiǎng)齊名。姚期智:開華裔獲圖靈之先河姚期智對(duì)計(jì)算機(jī)科學(xué)技術(shù)所作出的貢獻(xiàn)主要在計(jì)算理論方面。姚期智進(jìn)入計(jì)算機(jī)科學(xué)領(lǐng)域最早的論文之一《尋找最小生成樹的O(|E|log

log|V|)算法》一文就引起轟動(dòng)，因?yàn)閷W(xué)術(shù)界原先認(rèn)為，尋找最小生成樹算法的時(shí)間復(fù)雜度的下界是O(|E|log|V|)，而姚期智的論文證明這個(gè)極限是可以打破的。課程考核考勤：10%平時(shí)作業(yè):20%（作業(yè)每周周一下午交上周的作業(yè)，遲交作業(yè)的同學(xué)本次作業(yè)算沒有交作業(yè)）期末考試：70%課程內(nèi)容

本課程根據(jù)大綱的內(nèi)容和相關(guān)獨(dú)立性，可分為四大部分

第一部分?jǐn)?shù)理邏輯包括命題邏輯;謂詞邏輯

第二部分集合論包括集合與關(guān)系;函數(shù)第三部分代數(shù)系統(tǒng)包括代數(shù)結(jié)構(gòu);格與布爾代數(shù)第四部分圖論

學(xué)習(xí)方法定義、定理多。本課內(nèi)容＝定義＋定理＋例題為了學(xué)好這門課，要求：（１）弄懂定義、定理，弄懂例題，加深對(duì)定義、定理的理解；（２）在復(fù)習(xí)基礎(chǔ)上，做好課外作業(yè)。同學(xué)之間可以討論，但要弄懂弄通。（3）做好課堂筆記。LuChaojun,SJTU1717什么是邏輯?邏輯(logic)是關(guān)于推理的科學(xué).或:關(guān)于思維形式規(guī)律的科學(xué).源自希臘文logos(言詞,思想,理性等等)中文“邏輯”一詞由嚴(yán)復(fù)首先譯用過去又稱名理學(xué),名學(xué),論理學(xué),理則學(xué),辯學(xué)等.西方邏輯起源于古希臘主要貢獻(xiàn)來自亞里士多德和斯多葛學(xué)派古代東方邏輯中國的名辯之學(xué),散見于名墨儒道各家古印度的因明LuChaojun,SJTU18為什么要學(xué)邏輯?思維必須符合規(guī)律才不會(huì)導(dǎo)致謬妄.推理是獲得知識(shí)的一種途徑邏輯研究怎樣的推理是可靠的.邏輯還研究一組知識(shí)是否協(xié)調(diào)(一致,相容).各門科學(xué)都是在特殊領(lǐng)域的思維推理活動(dòng),故邏輯是一切科學(xué)的公共基礎(chǔ).Geology,biology,physiology,…邏輯思維能力是學(xué)習(xí)、工作乃至日常生活中的重要能力.18LuChaojun,SJTU19形式邏輯形式邏輯(formallogic)研究推理的形式,推理有效性由形式而非內(nèi)容決定.例:“所有A是B,所有B是C,故所有A是C”是正確的推理形式,把ABC換成任何具體對(duì)象都有效.但“我喜歡吃辣,也喜歡吃魚,故我喜歡吃辣子魚”恐怕就不能得出一般的形式.19LuChaojun,SJTU20數(shù)理邏輯符號(hào)邏輯(symboliclogic):對(duì)邏輯推理的形式特征進(jìn)行符號(hào)抽象.使用人工符號(hào)語言.分為命題邏輯和謂詞邏輯.數(shù)理邏輯(mathematicallogic):是符號(hào)邏輯及其在其他數(shù)學(xué)領(lǐng)域的擴(kuò)展.四論:集合論,模型論,遞歸論,證明論或說:符號(hào)邏輯=數(shù)理邏輯20LuChaojun,SJTU21數(shù)理邏輯發(fā)展簡(jiǎn)史邏輯發(fā)展史中的里程碑人物亞里士多德萊布尼茨布爾弗雷格希爾伯特羅素哥德爾21LuChaojun,SJTU22古典邏輯亞里士多德的三段論(syllogism)從兩個(gè)前提推出一個(gè)結(jié)論的邏輯論證形式:1.大前提(majorpremise)人都是兩足動(dòng)物2.小前提(minorpremise)希臘人都是人3.結(jié)論(conclusion)希臘人都是兩足動(dòng)物斯多葛學(xué)派(Stoics)的命題邏輯芝諾(ZenoofCitium)于301BC創(chuàng)立克呂希波(Chrysippus)大大發(fā)展了Stoiclogic22LuChaojun,SJTU23亞里士多德Aristotle(384BC-322BC)形式邏輯的奠基人第一個(gè)邏輯學(xué)家第一個(gè)形式演繹邏輯系統(tǒng):三段論三段論是傳統(tǒng)演繹推理的核心,在西方邏輯中一直處于統(tǒng)治地位,直至19世紀(jì)被數(shù)理邏輯(一階謂詞邏輯)所取代.附注:歐幾里德(Euclid,330BC-275BC)的《幾何原本》第一次以公理化方式演繹地處理數(shù)學(xué).23LuChaojun,SJTU24萊布尼茨GottfriedWilhelmLeibniz(1646-1716)數(shù)理邏輯的先驅(qū)首先使用“數(shù)理邏輯”這個(gè)術(shù)語Leibniz’sDream:推理歸結(jié)為(符號(hào))計(jì)算.兩大思想:“普遍語言”和“思維演算”這正是數(shù)理邏輯的主導(dǎo)思想.“發(fā)生爭(zhēng)論時(shí)我們可以簡(jiǎn)單地說:讓我們計(jì)算一下吧,看誰正確.”羅素評(píng)價(jià)說:Leibniz未發(fā)表手稿中發(fā)展的邏輯的水平只在200年后才重新達(dá)到.24LuChaojun,SJTU25布爾GeorgeBoole(1815-1864)數(shù)理邏輯創(chuàng)始人之一如1847年的論文:邏輯的數(shù)學(xué)分析:論演繹推理的演算法.應(yīng)用數(shù)學(xué)(代數(shù))方法研究邏輯,發(fā)明了布爾代數(shù)(邏輯代數(shù),命題代數(shù),布爾邏輯)初步實(shí)現(xiàn)了Leibniz夢(mèng)想.亦可解釋成集合代數(shù),開關(guān)代數(shù)是計(jì)算機(jī)數(shù)字邏輯的基礎(chǔ)附注:AugustusdeMorgan(1806-1871)幾乎同時(shí)獨(dú)立地做出重要貢獻(xiàn). CharlesSandersPeirce(1839-1914)發(fā)展了這兩人的工作. ErnstSchr?der(1841-1902)進(jìn)一步總結(jié)發(fā)展前三人的工作.25LuChaojun,SJTU26弗雷格FriedrichLudwigGottlob

Frege(1848-1925)數(shù)理邏輯主要?jiǎng)?chuàng)始人分析哲學(xué),語言哲學(xué)創(chuàng)始人重要著作:Begriffsschrift

(1879)《概念文字:一種模仿算術(shù)語言構(gòu)造的純思維的形式語言》.第一個(gè)公理化謂詞邏輯系統(tǒng)自Aristotle以來邏輯的最重要進(jìn)展基本實(shí)現(xiàn)了Leibniz夢(mèng)想26LuChaojun,SJTU27數(shù)學(xué)基礎(chǔ)危機(jī)(1)19世紀(jì)早期發(fā)現(xiàn)數(shù)學(xué)一直存在缺陷.如:非歐幾何(Lobachevsky,Riemann)分析(微積分及其擴(kuò)展)的基礎(chǔ)19世紀(jì)后期的公理化運(yùn)動(dòng):去除基于直覺或經(jīng)驗(yàn)的樸素概念的模糊之處,使數(shù)學(xué)嚴(yán)密化.如:算術(shù)公理化(Dedekind1888,Peano1889)幾何公理化(Hilbert1899)27LuChaojun,SJTU28數(shù)學(xué)基礎(chǔ)危機(jī)(2)1900年國際數(shù)學(xué)大會(huì)Poincare:“借助集合論…可以建造數(shù)學(xué)大廈…今天我們可以宣稱絕對(duì)的嚴(yán)密已經(jīng)實(shí)現(xiàn)了!”隨后發(fā)現(xiàn)了Cantor集合論中的一些悖論:如1901年的羅素悖論.弗雷格:當(dāng)大廈竣工時(shí)基礎(chǔ)卻動(dòng)搖了.28LuChaojun,SJTU29解決危機(jī)的四大派別邏輯主義:主張從邏輯推出數(shù)學(xué).代表人物Russell形式主義:對(duì)全部數(shù)學(xué)進(jìn)行形式化,并證明其協(xié)調(diào)性.代表人物Hilbert直覺主義:反對(duì)排中律,強(qiáng)調(diào)構(gòu)造性.代表人物Brouwer公理化集合論代表人物Zermelo29LuChaojun,SJTU30羅素BertrandArthurWilliamRussell(1872-1970)邏輯主義創(chuàng)始人之一主張從邏輯推出全部數(shù)學(xué).重要論著PrincipiaMathematica,1910與Whitehead合著PM系統(tǒng)是完備的命題演算和謂詞演算.邏輯演算的經(jīng)典系統(tǒng).30LuChaojun,SJTU31希爾伯特DavidHilbert(1862-1943)數(shù)理邏輯中形式主義學(xué)派證明論創(chuàng)始人之一Hilbert’sprogram:將理論至于邏輯演算中加以形式化,重點(diǎn)研究系統(tǒng)中證明的邏輯性質(zhì),希望得出系統(tǒng)的協(xié)調(diào)性.強(qiáng)調(diào)證明要使用有窮方法.31LuChaojun,SJTU32G?del不完備性定理G?del于1931年發(fā)表的不完備性定理是對(duì)Hilbert’sprogram的致命一擊.大意:任何足夠強(qiáng)的形式系統(tǒng)都有無法證明的真命題.且系統(tǒng)自己不能證明自己無矛盾.顯示了形式化方法的本質(zhì)局限.20世紀(jì)數(shù)理邏輯的頂峰.也有評(píng)論說是20世紀(jì)最重要的數(shù)學(xué)定理32LuChaojun,SJTU33哥德爾KurtG?del(1906-1978)證明了一階謂詞演算的完備性.實(shí)現(xiàn)了Leibniz夢(mèng)想.證明了更加重要的成果:不完備性定理.Einstein說:自己的工作不再要緊,來研究院只是為了享有和G?del一起步行回家的特權(quán).3334數(shù)理邏輯的分支基礎(chǔ)的邏輯演算（命題邏輯，謂詞邏輯）公理集合論模型論遞歸論證明論34LuChaojun,SJTU35公理集合論研究公理集合論,是整個(gè)數(shù)學(xué)的基礎(chǔ).Cantor的樸素集合論有缺陷Burali-Forti悖論,羅素悖論,Richard悖論,…ErnstZermelo:第一個(gè)公理化集合論(1908)經(jīng)Fraenkel(1922)改進(jìn)成為經(jīng)典的ZF集合論避免了羅素悖論G?del和PaulCohen(1963)在CH方面的工作CH在ZF系統(tǒng)中不可判定Cohen的新方法(力迫法)讓人們證明了許多不可判定的問題.數(shù)學(xué)絕不是“非真即假”那么單純!35LuChaojun,SJTU36模型論建立形式理論的模型,研究模型之間的關(guān)系等.模型是對(duì)形式理論進(jìn)行具體解釋的一種結(jié)構(gòu).語法與語義的關(guān)系A(chǔ)lfredTarski奠定了模型論的基礎(chǔ)36LuChaojun,SJTU37遞歸論亦稱(能行)可計(jì)算性理論,研究能行可計(jì)算的函數(shù).從遞歸函數(shù)和圖靈機(jī)的等價(jià)產(chǎn)生可計(jì)算函數(shù)的概念代表人物G?del:遞歸函數(shù)AlonzoChurch(丘奇):演算AlanTuring(圖靈):圖靈機(jī)現(xiàn)代計(jì)算機(jī)設(shè)計(jì)思想的創(chuàng)始人之一3738證明論研究數(shù)學(xué)理論系統(tǒng)的形式證明問題,即以證明為研究對(duì)象,用數(shù)學(xué)方法分析之.主要關(guān)注系統(tǒng)的協(xié)調(diào)性.代表人物Hilbert:首先提出GerhardGentzen:發(fā)展了證明論的重要成果.證明了算術(shù)形式系統(tǒng)的協(xié)調(diào)性.是在系統(tǒng)外證明,且不是有窮主義的.與G?del的結(jié)果不矛盾.3839數(shù)理邏輯與計(jì)算機(jī)科學(xué)計(jì)算機(jī)圖靈機(jī)計(jì)算機(jī)能做什么,算法是什么可計(jì)算性理論計(jì)算機(jī)不能做什么算法不可解問題邏輯程序設(shè)計(jì)(Prolog)謂詞邏輯程序設(shè)計(jì)語言的語義學(xué)模型論形式規(guī)格說明與程序驗(yàn)證模型論AI,知識(shí)表示,自動(dòng)定理證明邏輯演算從形式證明產(chǎn)生程序證明論(Gentzen)……39LuChaojun,SJTU40戴克斯特拉Edsger

Wybe

Dijkstra(1930-2002)最偉大的計(jì)算機(jī)科學(xué)家(之一?)“搞了這么多年軟件,錯(cuò)誤不知犯了多少,現(xiàn)在覺悟了.我想,假如我早年在數(shù)理邏輯上好好下點(diǎn)功夫的話,我就不會(huì)犯這么多的錯(cuò)誤,不少東西邏輯學(xué)家早就說了,可我不知道.要是我能年輕二十歲的話,就要回去學(xué)邏輯.”成就很多,如Dijkstra最短路徑算法(見教材11.5)EWD手稿:/users/EWD/40第一篇數(shù)理邏輯

邏輯學(xué):研究思維形式及思維規(guī)律的科學(xué)。邏輯學(xué)分為二類：辯證邏輯:是研究事物發(fā)展的客觀規(guī)律。形式邏輯:對(duì)思維的形式結(jié)構(gòu)和規(guī)律進(jìn)行研究。數(shù)理邏輯：是用數(shù)學(xué)的方法研究概念、判斷和推理的科學(xué)，屬于形式邏輯。

研究推理的方法很多，用數(shù)學(xué)方法來研究推理的規(guī)律就稱為數(shù)理邏輯第一篇數(shù)理邏輯在數(shù)理邏輯中，用數(shù)學(xué)的方法是指引進(jìn)一套符號(hào)體系的方法來研究概念、判斷和推理。即對(duì)符號(hào)進(jìn)行判斷和推理。數(shù)理邏輯分為四大分支：證明論、模型論、遞歸論和公理集合論。我們這里介紹的是屬于四大分支的共同基礎(chǔ)—古典數(shù)理邏輯(命題邏輯和謂詞邏輯)。第一章命題邏輯§1.1命題§1.2命題聯(lián)結(jié)詞§1.3命題公式與翻譯§1.4真值表與等價(jià)式§1.5重言式與蘊(yùn)含式§1.6其他命題聯(lián)結(jié)詞§1.7對(duì)偶與范式§1.8推論理論第一章命題邏輯教學(xué)目的及要求：深刻理解和掌握命題邏輯中基本概念和基本方法。教學(xué)內(nèi)容：命題及表示、聯(lián)結(jié)詞、命題公式與翻譯、真值表與等價(jià)公式、重言式與蘊(yùn)涵式、對(duì)偶與范式、推理理論。教學(xué)重點(diǎn)：命題邏輯中的基本概念和基本推理方法。教學(xué)難點(diǎn)：推理理論?！?.1命題定義：客觀上具有確定真假值的陳述句叫命題。討論定義：（1）命題可以是真的，或者是假的，但不能同時(shí)為真又為假。（2）命題分類：

ⅰ)原子命題（基本命題、本原命題）：不能分解成為更簡(jiǎn)單的命題。例：5是自然數(shù)?！?.1命題ⅱ)分子命題（復(fù)合命題）：若干個(gè)原子命題使用適當(dāng)?shù)穆?lián)結(jié)詞所組成的新命題例：2是偶數(shù)并且2也是素?cái)?shù)。（3）命題標(biāo)識(shí)符：用來表示命題的符號(hào)。

常用大寫２６個(gè)英文字母(可以帶下標(biāo))表示命題。（4）命題中所有的“真”用“Ｔ”(或1)表示，命題中所有的“假”用“Ｆ”(或0)表示?！?.1命題例：判斷下列語句是否為命題。（1）十是整數(shù)。（Ｔ）（2）上海是一個(gè)村莊。（Ｆ）（3）火星上有生命存在。（4）加拿大是一個(gè)國家。（Ｔ）（5）２是偶數(shù)而３是奇數(shù)。（T）（6）2016年巴西奧運(yùn)會(huì)上中國的金牌數(shù)超過美國。（7）在十進(jìn)制中１＋１０１＝１１０（Ｆ）（8）今天是星期天。（Ｆ）§1.1命題命令句，感嘆句，疑問句均不是命題。（1）把門關(guān)上?。?）你到哪里去？語句既為真，同時(shí)又為假的陳述句不是命題，這樣的句子稱為“悖論”。（3）日本首相安倍正在說謊。（在命題邏輯中不討論這類問題）下列陳述句是否為命題？（1）趙本山很帥。（2）劉翔是高個(gè)子。（3）章子怡很漂亮。（4）姚明很富有?！?.2命題聯(lián)結(jié)詞在命題演算中也有類似的日常生活中的聯(lián)結(jié)詞稱做：“命題聯(lián)結(jié)詞”,下面先介紹五個(gè)常用的命題聯(lián)結(jié)詞。１．否定詞：（否定運(yùn)算、非運(yùn)算）（１）符號(hào)

,讀作“非”，“否定”設(shè)命題為Ｐ，則在Ｐ的前面加否定詞，變成Ｐ，Ｐ讀做“Ｐ的否定”或“非Ｐ”§1.2命題聯(lián)結(jié)詞（２）定義P的真值表：（３）舉例：Ｑ：每一種生物均是動(dòng)物。FＱ：有一些生物不是動(dòng)物。T

這里Ｑ不能講成“每一種生物都不是動(dòng)物”。對(duì)量化命題的否定，除對(duì)動(dòng)詞進(jìn)行否定外，同時(shí)對(duì)量化詞也要加以否定。TFFTPP§1.2命題聯(lián)結(jié)詞２．合取詞（“合取”、“積”、“與”運(yùn)算）

(1)符號(hào)“Λ”

設(shè)Ｐ，Ｑ為兩個(gè)命題，則ＰΛＱ稱Ｐ與Ｑ的合取，讀作：“Ｐ與Ｑ”、“Ｐ與Ｑ的合取”、“Ｐ并且Ｑ”等。

(2)定義（由真值表給出）：§1.2命題聯(lián)結(jié)詞TTTTFFFTFFTFFFFFQΛPPΛQQPＰΛＱ的真值表：§1.2命題聯(lián)結(jié)詞當(dāng)且僅當(dāng)Ｐ和Ｑ的真值均為“Ｔ”，則（ＰΛＱ）的真值為“Ｔ”。否則，其真值為“Ｆ”。注意：Ｐ和Ｑ是互為獨(dú)立的；地位是平等的，Ｐ和Ｑ的位置可以交換而不會(huì)影響ＰΛＱ的結(jié)果?！?.2命題聯(lián)結(jié)詞(3)舉例：

(a)P：王華是黨員。

Q：王華是三好學(xué)生。則ＰΛＱ：王華是黨員并且也是三好學(xué)生。

(b)P：我們?nèi)シN樹

Q：房間里有一臺(tái)電視機(jī)則ＰΛＱ：我們?nèi)シN樹且房間里有一臺(tái)電視機(jī)。§1.2命題聯(lián)結(jié)詞(c)P：今天下雪

Q：3+3=6

則ＰΛＱ：今天下雪和3+3=6由例(b)(c)可見，在日常生活中，合取詞應(yīng)用在二個(gè)有關(guān)系的命題之間。而在邏輯學(xué)中，合取詞可以用在二個(gè)毫不相干的命題之間。§1.2命題聯(lián)結(jié)詞(d)P:王大和王二是親兄弟。

Q:他打開箱子然后拿出一件衣服來。該語句不是合取聯(lián)結(jié)詞組成的命題。

§1.2命題聯(lián)結(jié)詞３．析取詞（或運(yùn)算）（１）符號(hào)“∨”設(shè)Ｐ、Ｑ為二個(gè)命題，則（Ｐ∨Ｑ）稱作Ｐ與Ｑ的“析取”，讀作：“Ｐ或Ｑ”。（２）定義（由真值表給出）：§1.2命題聯(lián)結(jié)詞當(dāng)且僅當(dāng)Ｐ、Ｑ均為“Ｆ”時(shí)，（Ｐ∨Ｑ）為“Ｆ”。否則，其真值為“Ｔ”．TTTTFTTTFFFFP∨QQPＰ∨Ｑ的真值表：§1.2命題聯(lián)結(jié)詞區(qū)分“可兼或”與“不可兼或（異或，排斥或）”“可兼或”即P或Q為“T”時(shí)（P∨Q）為“T”，是析取。例如：燈泡有故障或開關(guān)有故障。今晚寫字或看書。今天下雨或打雷。以上例句均為“可兼或”?！?.2命題聯(lián)結(jié)詞“不可兼或”即P和Q的真值不同時(shí)，P▽Q為T。（異或用“▽”表示）不是析取。FTTTFTTTFFFFP▽QQPP▽Q的真值表：§1.2命題聯(lián)結(jié)詞例：他通過電視看雜技或到劇場(chǎng)看雜技。他乘火車去北京或乘飛機(jī)去北京。以上兩句均為“不可兼或”?！?.2命題聯(lián)結(jié)詞４．單條件聯(lián)結(jié)詞：（１）符號(hào)“→”，讀作：“如果…則…”

Ｐ、Ｑ為二個(gè)命題，（Ｐ→Ｑ）為新的命題，讀作：“如果Ｐ則Ｑ”。（２）定義（由真值表給出）§1.2命題聯(lián)結(jié)詞Ｐ→Ｑ的真值表：TTTFFTTTFTFFP→QQP§1.2命題聯(lián)結(jié)詞

當(dāng)Ｐ為“Ｔ”，Ｑ為“Ｆ”時(shí)，則（Ｐ→Ｑ）為“Ｆ”，否則（Ｐ→Ｑ）均為“Ｔ”。Ｐ：稱為前件、條件、前提、假設(shè)Ｑ：稱為后件、結(jié)論。（３）舉例：

P：我拿起一本書

Q：我一口氣讀完了這本書§1.2命題聯(lián)結(jié)詞P→Q：如果我拿起一本書，則我一口氣讀完了這本書。(b)P：月亮出來了

Q：3×3=9P→Q：如果月亮出來了，則3×3=9。通常稱：

(a)為形式條件命題——前提和結(jié)果有某種形式和內(nèi)容上的聯(lián)系。§1.2命題聯(lián)結(jié)詞(b)為實(shí)質(zhì)條件命題——前提和結(jié)果可以有聯(lián)系，也可以沒有聯(lián)系，只要滿足單條件命題的定義。所以,是形式條件命題一定是實(shí)質(zhì)條件命題,反之不一定?！啊笔菍?shí)質(zhì)條件命題。例：Ｐ：我買到了魚；Ｑ:我吃魚。Ｐ→Ｑ：如果我買到了魚，則我吃魚。但“如果我沒買到魚，則我吃魚”，在日常生活中不可能，但在單條件命題的定義中是允許的。

§1.2命題聯(lián)結(jié)詞可以證明：Ｐ→Ｑ

?Q→?P

原命題逆反命題Ｑ→Ｐ

?Ｐ→?Ｑ逆命題反命題§1.2命題聯(lián)結(jié)詞列出真值表,由真值表得：原命題逆反命題；逆命題反命題。TTTTTTTTFFFTFFTTTFTTTTFF?Ｐ→?ＱＱ→P?Q→?P

P→QQP5．雙條件聯(lián)結(jié)詞（等價(jià)聯(lián)結(jié)詞）：（１）符號(hào)“?”，讀作：“當(dāng)且僅當(dāng)”Ｐ、Ｑ為二個(gè)命題，（Ｐ?Ｑ）為新的命題，讀作：“Ｐ當(dāng)且僅當(dāng)Ｑ”。（２）定義（由真值表給出）§1.2命題聯(lián)結(jié)詞P?Q的真值表:每當(dāng)Ｐ和Ｑ的真值相同時(shí)，則（Ｐ?Ｑ）的真值為“Ｔ”，否則（Ｐ?Ｑ）的真值為“Ｆ”。TTTFFTFTFTFFP?QQP§1.2命題聯(lián)結(jié)詞（３）舉例：（a）設(shè)Ｐ：△ABC是等腰三角形Ｑ：△ABC有兩只角相等Ｐ?Ｑ：△ABC是等腰三角形當(dāng)且僅當(dāng)有兩只角相等。§1.2命題聯(lián)結(jié)詞（b）下面均為等價(jià)聯(lián)結(jié)詞：春天來了當(dāng)且僅當(dāng)燕子飛回來了。平面上二直線平行，當(dāng)且僅當(dāng)二直線不相交。２＋２＝４當(dāng)且僅當(dāng)雪是白色的。§1.2命題聯(lián)結(jié)詞（４）Ｐ,Ｑ中，Ｐ、Ｑ的地位是平等的，Ｐ、Ｑ交換位置不會(huì)改變真值表中的值。（５）Ｐ當(dāng)且僅當(dāng)ＱＰ?ＱＰ僅當(dāng)ＱＰ→ＱＰ當(dāng)且ＱＱ→Ｐ§1.2命題聯(lián)結(jié)詞６．命題聯(lián)結(jié)詞在使用中的優(yōu)先級(jí)（１）先括號(hào)內(nèi)，后括號(hào)外（２）運(yùn)算時(shí)聯(lián)結(jié)詞的優(yōu)先次序?yàn)椋?

Λ∨→?

（由高到低）（３）聯(lián)結(jié)詞按從左到右的次序進(jìn)行運(yùn)算（４）最外層的括號(hào)一律均可省去（Ｐ→Ｑ∨Ｒ）可寫成Ｐ→Ｑ∨Ｒ§1.2命題聯(lián)結(jié)詞例?Ｐ∨（Ｑ∨Ｒ）可省去括號(hào)因?yàn)椤埃帧边\(yùn)算是可結(jié)合的。而Ｐ→（Ｑ→Ｒ）中的括號(hào)不能省去，因“→”不滿足結(jié)合律?！?.2命題聯(lián)結(jié)詞

７．命題聯(lián)結(jié)詞小結(jié)：

（1）五個(gè)聯(lián)結(jié)詞的含義與日常生活中的聯(lián)結(jié)詞的含義大致相同。

（2）“或”可分為可兼或（∨）和異或（▽）（不可兼或）（3）“?”為一元運(yùn)算，其余四個(gè)均為二元運(yùn)算?！?.2命題聯(lián)結(jié)詞(4)“→”分為形式條件和實(shí)質(zhì)條件命題，當(dāng)前件為“Ｆ”時(shí)，不論后件怎樣，則單條件命題的真值均為“Ｔ”。(5)命題聯(lián)結(jié)詞是命題或命題之間的聯(lián)結(jié)詞，而不是名詞之間、數(shù)字之間和動(dòng)詞之間的聯(lián)結(jié)詞。§1.3命題公式與翻譯約定：（１）我們只注意命題的真假值，而不再去注意命題的漢語意義。（２）對(duì)命題聯(lián)結(jié)詞，我們只注意真值表的定義，而不注意它日常生活中的含義?！?.3命題公式與翻譯１．命題公式命題常元：表示確定的命題｛T，F(xiàn)｝。命題變?cè)阂哉婕贋槠渥冇蛑冊(cè)?，或沒有指定真值的命題。常用大寫英文字母Ａ…Ｚ表示。命題公式：由命題變?cè)?、常元、?lián)結(jié)詞、括號(hào)，以規(guī)定的格式聯(lián)結(jié)起來的字符串?！?.3命題公式與翻譯[定義]命題公式(wff)可按下述法則來生成：１）單個(gè)的命題變?cè)且粋€(gè)命題公式。２）若Ａ是命題公式，?Ａ也為命題公式。３）若Ａ、Ｂ是命題公式，則（ＡΛＢ）、（Ａ∨Ｂ）、（Ａ→Ｂ）、（Ａ?Ｂ）均為命題公式。４）當(dāng)且僅當(dāng)有限次使用（１）（２）（３）所得到的包含有命題變?cè)兔}常元，聯(lián)結(jié)詞，括號(hào)的符號(hào)串才是命題公式。§1.3命題公式與翻譯例如：(?(P∨Q))，(P→(Q→R))，((PΛQ)?R)，P都是命題公式。而(P→)，(P∨?)都不是命題公式§1.3命題公式與翻譯以上介紹了五種常用的聯(lián)結(jié)詞及其相應(yīng)的復(fù)合命題形式。數(shù)理邏輯的特點(diǎn)是把邏輯推理變成類似數(shù)學(xué)演算的完全形式化了的邏輯演算，為此，首先要把推理所涉及到的各命題符號(hào)化。步驟如下：①找出各簡(jiǎn)單命題，分別符號(hào)化。②找出各聯(lián)結(jié)詞，把簡(jiǎn)單命題逐個(gè)聯(lián)結(jié)起來?！?.3命題公式與翻譯例.將下列命題符號(hào)化：（1）李明是計(jì)算機(jī)系的學(xué)生，他住在312室或313室。（2）張三和李四是朋友。（3）雖然交通堵塞，但是老王還是準(zhǔn)時(shí)到達(dá)了車站。（4）只有一個(gè)角是直角的三角形才是直角三角形。（5）老王或小李中有一個(gè)去上海出差。§1.3命題公式與翻譯解：（1）首先用字母表示簡(jiǎn)單命題。

P：李明是計(jì)算機(jī)系的學(xué)生。

Q：李明住在312室。

R：李明住在313室。該命題符號(hào)化為：P（Q▽R）（2）張三和李四是朋友。是一個(gè)簡(jiǎn)單句該命題符號(hào)化為：P§1.3命題公式與翻譯（3）首先用字母表示簡(jiǎn)單命題。

P：交通堵塞。

Q：老王準(zhǔn)時(shí)到達(dá)了車站。該命題符號(hào)化為：PQ（4）首先用字母表示簡(jiǎn)單命題。

P：三角形的一個(gè)角是直角。

Q：三角形是直角三角形。該命題符號(hào)化為：PQ§1.3命題公式與翻譯（5）首先用字母表示簡(jiǎn)單命題。

P：老王去上海出差。

Q：小李去上海出差。該命題符號(hào)化為：P▽Q

也可符號(hào)化為：（PQ）（PQ）或者（PQ）（PQ）§1.4真值表與等價(jià)公式一．命題公式的真值表:命題變?cè)锰囟ǖ拿}來取代，這一過程稱為對(duì)該命題變?cè)M(jìn)行真值指派。命題公式可以看成是一個(gè)以真假值為定義域和真假值為值域的一個(gè)函數(shù)。寫成ｙ＝ｆ(x)§1.4真值表與等價(jià)公式

例如：公式P(QR)定義三元函數(shù)

Y(P，Q，R)＝P(QR)[定義]命題公式A在其所有可能的賦值下取得的值列成的表稱為A的真值表?！?.4真值表與等價(jià)公式構(gòu)造真值表的步驟如下：

1)找出給定命題公式中所有的命題變?cè)谐鏊锌赡艿馁x值。

2)按照從低到高順序?qū)懗雒}公式的各層次。

3)對(duì)應(yīng)每個(gè)賦值，計(jì)算命題公式各層次的值，直到最后計(jì)算出整個(gè)命題公式的值。§1.4真值表與等價(jià)公式FTTTTFTTFTTFTTFTFFFF?（（Ｐ∨Ｑ）ΛＰ）（Ｐ∨Ｑ）ΛＰP∨QQP例１．構(gòu)造命題公式?（（Ｐ∨Ｑ）ΛＰ）的真值表：§1.4真值表與等價(jià)公式

例２．寫出命題公式Ｐ∨（ＱΛＲ）的真值表TTTTTFTTTTFTTFFTTTTFFFTFFTFFFFFFＰ∨（ＱΛＲ)RQP§1.4真值表與等價(jià)公式由上二例可見，２個(gè)命題變?cè)校唇M真值指派；３個(gè)命題變?cè)?3＝８組真值指派，ｎ個(gè)則有個(gè)2n個(gè)真值指派?！?.4真值表與等價(jià)公式３．命題公式的永真式、永假式和可滿足式[定義]設(shè)公式Ａ中有n個(gè)不同的原子變?cè)?/p>

p1,…pn,(n為正整數(shù))。該變?cè)M的任意一組確定的值（u1,…un）稱為Ａ關(guān)于p1,…pn的一個(gè)完全指派，其中ui或?yàn)椋?，或?yàn)椋?。如果?duì)于Ａ中部分變?cè)x以確定值，其余變?cè)獩]有賦以確定的值，則這樣的一組值稱為公式Ａ的關(guān)于該變?cè)M的部分指派。[定義]使公式取真的指派稱為成真指派?！?.4真值表與等價(jià)公式[定義]如果一個(gè)命題公式的所有完全指派均為成真指派，則該公式稱為永真式。如果一個(gè)命題公式的所有完全指派均為成假指派，則該公式稱為永假式。既不是永真式，又不是永假式，則稱此命題公式是可滿足式。討論：（１）永真式的否定為永假式（?Ｔ＝Ｆ）；永假式的否定為永真式（?Ｆ＝Ｔ）。（２）二個(gè)永真式的析取、合取、蘊(yùn)含、等價(jià)均為永真式?！?.4真值表與等價(jià)公式二．等價(jià)式[定義]如果對(duì)兩個(gè)公式Ａ，Ｂ不論作何種指派，它們真值均相同，則稱Ａ，Ｂ是邏輯等價(jià)的，亦說Ａ（Ｂ）等價(jià)于Ｂ（Ａ）,并記作：ＡＢ§1.4真值表與等價(jià)公式例：Ｐ∨?ＰＱ∨?ＱTTTTTTTFTTFTTTFFQ∨?QP∨?PPQ§1.4真值表與等價(jià)公式例：判斷公式A：(PQ)(PQ)與

B：(PR)(PR)是否等價(jià)。解：列該公式的真值表：§1.4真值表與等價(jià)公式FFFTTFTTFFFFFTFFFTTTFFFFFTTTFFFTFFFTFFTFFTTFTTTTTTTTFFTTTTTFTTTTFTTTTTTTTFFTTTTTTFTTFTTTBAPRPRRPQPQQRQP§1.4真值表與等價(jià)公式[定理]

命題公式ＡＢ的充要條件是Ａ?Ｂ為永真式。說明：“”為等價(jià)關(guān)系符，ＡＢ表示Ａ和Ｂ有等價(jià)關(guān)系。ＡＢ不為命題公式“?”為等價(jià)聯(lián)結(jié)詞（運(yùn)算符），Ａ、Ｂ為命題公式，則（Ａ?Ｂ）也為一命題公式。

§1.4真值表與等價(jià)公式證明：（１）充分性：Ａ?Ｂ為永真式，即Ａ、Ｂ有相同的真值，所以ＡＢ。（２）必要性：ＡＢ，即Ａ、Ｂ有相同的真值表，所以Ａ?Ｂ為永真式。例：證明??ＰＰ；Ｐ→Ｑ?Ｐ∨Ｑ§1.4真值表與等價(jià)公式TTTTTTTTFTFTTTFTTTTFTFTFTTTFTFFFP→Q?P∨Q??PPQP由定理可知：ＡＡ若ＡＢ，則ＢＡ若ＡＢ，ＢC，則ＡＣ§1.4真值表與等價(jià)公式下面列出１５組等價(jià)公式（1）雙重否定律??ＰＰ（2）同等律Ｐ∨ＰＰ；ＰΛＰＰ（3）交換律Ｐ∨ＱＱ∨Ｐ；ＰΛＱＱΛＰ；ＰＱＱＰ（4）結(jié)合律（Ｐ∨Ｑ）∨ＲＰ∨（Ｑ∨Ｒ）；（ＰΛＱ）ΛＲＰΛ（ＱΛＲ）；（ＰＱ）ＲＰ（ＱＲ）§1.4真值表與等價(jià)公式（5）分配律ＰΛ（Ｑ∨Ｒ）（ＰΛＱ）∨（ＰΛＲ）；Ｐ∨（ＱΛＲ）（Ｐ∨Ｑ）Λ（Ｐ∨Ｒ）（6）摩根律

?（Ｐ∨Ｑ）?ＰΛ?Ｑ；

?（ＰΛＱ）?Ｐ∨?Ｑ（7）吸收律Ｐ∨（ＰΛＱ）Ｐ；ＰΛ（Ｐ∨Ｑ）Ｐ§1.4真值表與等價(jià)公式（8）蘊(yùn)含律Ｐ→Ｑ?Ｐ∨Ｑ（9）等價(jià)律ＰＱ（Ｐ→Ｑ）Λ（Ｑ→Ｐ）（10）零律Ｐ∨ＴＴ；ＰΛＦＦ（11）同一律Ｐ∨ＦＰ；ＰΛＴＰ（12）互補(bǔ)律Ｐ∨?ＰＴ；ＰΛ?ＰＦ（13）輸出律ＰΛＱ→ＲＰ→（Ｑ→Ｒ）§1.4真值表與等價(jià)公式（14）歸繆律（Ｐ→Ｑ）Λ（Ｐ→?Ｑ）?Ｐ（15）逆反律Ｐ→Ｑ?Ｑ→?Ｐ說明：（１）證明上述１５組等價(jià)公式的方法可用真值表法，把改為所得的命題公式為永真式，則成立。§1.4真值表與等價(jià)公式（2）Λ、∨、均滿足結(jié)合律，則在單一用Λ、∨、聯(lián)結(jié)詞組成的命題公式中，括號(hào)可以省去。（3）每個(gè)等價(jià)模式實(shí)際給出了無窮多個(gè)同類型的具體的命題公式。例如：(PQ)(PQ)，((PQ)(RS))((PQ)(RS)，((PQ)R)((PQ)R)§1.4真值表與等價(jià)公式２．置換規(guī)則[定義]給定一命題公式Ｂ，其中P1、P2．．．Pn

是Ｂ中的原子命題變?cè)簦?）用某些命題公式代換Ｂ中的一些原子命題變?cè)狿i

（2）用命題公式Ａi代換Pi，則必須用Ａi代換Ｂ中的所有Pi由此而得到的新的命題公式Ａ稱為命題公式Ｂ的代換實(shí)例§1.4真值表與等價(jià)公式討論定義：（１）用命題公式只能代換原子命題變?cè)?，而不能去代換分子命題公式。（２）要用命題公式同時(shí)代換同一個(gè)原子命題變?cè)＃ǎ常┯勒媸降拇鷵Q實(shí)例仍為永真式；反之代換實(shí)例為永真式時(shí)，則不能斷定原公式也一定是永真式?！?.4真值表與等價(jià)公式例：Ｐ∨?Ｐ為一永真式，若用任何命題公式代換Ｐ，則仍為永真式Ｐ→Ｑ為一個(gè)可滿足的命題公式，若用Ｐ代換Ｑ，則得（Ｐ→Ｐ）為永真式，但（Ｐ→Ｑ）并不是永真式。（４）一個(gè)命題公式的代換實(shí)例有許多個(gè)，但不一定都等價(jià)于原來的命題公式§1.4真值表與等價(jià)公式例１．設(shè)Ｂ：Ｐ→（?QΛＰ）若用（ＲＳ）代換Ｂ中的Ｐ，得Ａ：（Ｒ?Ｓ）→（?QΛ（ＲＳ））是Ｂ的代換實(shí)例，而Ａ’：（Ｒ?Ｓ）→（?QΛＰ）不是B的代換實(shí)例。例２．Ｐ→?Ｑ的代換實(shí)例有：（ＲΛ?Ｓ）→?Ｍ，（ＲΛ?Ｓ）→Ｐ，Ｑ→?（Ｐ→?Ｑ）等所以，一個(gè)命題公式的代換實(shí)例有無限個(gè)?！?.4真值表與等價(jià)公式下面討論取代過程（置換規(guī)則）：[定義]給定一命題公式Ａ，Ａ’是Ａ的任何部分，若Ａ’也是一命題公式，則稱Ａ’是Ａ的子命題公式。例：Ａ：（Ｐ∨Ｑ）→（Ｑ∨（ＲΛ?Ｓ））Ａ的子命題公式有：Ｐ、Ｑ、Ｒ、?Ｓ、（Ｐ∨Ｑ）、ＲΛ?Ｓ）、（Ｑ∨（ＲΛ?Ｓ））、（Ｐ∨Ｑ）→（Ｑ∨（ＲΛ?Ｓ））等。§1.4真值表與等價(jià)公式[定理]給定一命題公式Ａ，Ａ’是Ａ的子公式。設(shè)B’是一命題公式，若Ａ’

B’，并用B’取代Ａ中的Ａ’，從而生成一新的命題公式B，則ＡB。從定理可見：一個(gè)命題公式A，經(jīng)多次取代，所得到的新公式與原公式等價(jià)。例：證明：Ｐ→（Ｑ→Ｒ）Ｐ→（?Ｑ∨Ｒ）?Ｐ∨?Ｑ∨?Ｒ§1.4真值表與等價(jià)公式?（ＰΛＱ）∨Ｒ（ＰΛＱ）→Ｒ例：證明：（（Ｐ∨Ｑ）Λ?（?ＰΛ（?Ｑ∨?Ｒ）））∨（?ＰΛ?Ｑ）∨（?ＰΛ?Ｒ）為一永真式§1.4真值表與等價(jià)公式證明：原式：（（Ｐ∨Ｑ）Λ?（?ＰΛ（?Ｑ∨?Ｒ）））∨（?ＰΛ?Ｑ）∨（?ＰΛ?Ｒ）（（Ｐ∨Ｑ）Λ（Ｐ∨（ＱΛＲ）））∨?（Ｐ∨Ｑ）∨?（Ｐ∨Ｒ）

（（Ｐ∨Ｑ）Λ（Ｐ∨Ｑ）Λ（Ｐ∨Ｒ））∨?（（Ｐ∨Ｑ）Λ（Ｐ∨Ｒ））

（（Ｐ∨Ｑ）Λ（Ｐ∨Ｒ））∨?（（Ｐ∨Ｑ）Λ（Ｐ∨Ｒ））Ｔ∵它是ＰΛ?Ｐ（永真式）的代換實(shí)例，永真式的代換實(shí)例仍為永真式！§1.5重言式與蘊(yùn)含式[定義]命題公式Ａ稱為蘊(yùn)含命題公式Ｂ，當(dāng)且僅當(dāng)Ａ→Ｂ是一個(gè)永真式，記作：ＡＢ說明：“ＡＢ”讀作“Ａ永真蘊(yùn)含Ｂ”，“Ａ蘊(yùn)含Ｂ”，“Ａ能推得Ｂ”“”是關(guān)系符，ＡＢ不為命題公式。例：證明：ＰＰ∨Ｑ；ＰΛＱ

P

（１）列出真值表證明：Ｐ→（Ｐ∨Ｑ）和（ＰΛＱ）→Ｐ為永真式§1.5重言式與蘊(yùn)含式（２）可用等價(jià)公式證：Ｐ→（Ｐ∨Ｑ）?Ｐ∨（Ｐ∨Ｑ）

T（ＰΛＱ）→Ｐ?（ＰΛＱ）∨Ｐ

?Ｐ∨

?Ｑ∨Ｐ

TTTTTTTTTFTTTTTFTFTFFTTTFFTFFTFFF（ＰΛＱ）→ＰＰ→（Ｐ∨Ｑ）QP§1.5重言式與蘊(yùn)含式[定理]設(shè)Ａ、Ｂ是二個(gè)命題公式ＡＢ的充分必要條件是ＡＢ且ＢＡ。證明：若ＡＢ，則ＡＢ為一永真式由定律：（ＡＢ）（Ａ→Ｂ）Λ（Ｂ→Ａ）∴（Ａ→Ｂ）且（Ｂ→Ａ）也為一永真式即：ＡＢ且ＢＡ成立反之ＡＢ且ＢＡ則ＡＢ也成立此定理把“”和“”之間建立了相應(yīng)的關(guān)系。§1.5重言式與蘊(yùn)含式下面給出常用的永真蘊(yùn)含式I1ＰＰ∨Ｑ（ＱＰ∨Ｑ）I2

ＰΛＱＰ（ＰΛＱＱ）I3ＰΛ（Ｐ→Ｑ）ＱI4（Ｐ→Ｑ）Λ?Ｑ

?ＰI5?ＰΛ（Ｐ∨Ｑ）ＱI6（Ｐ→Ｑ）Λ（Ｑ→Ｒ）（Ｐ→Ｒ）I7（Ｐ→Ｑ）Λ（Ｒ→Ｓ）（ＰΛＲ→ＱΛＳ）I8（ＰＱ）Λ（ＱＲ）（ＰＲ）I9?P

Ｐ→Ｑ§1.5重言式與蘊(yùn)含式I10ＱＰ→ＱI11?（Ｐ→Ｑ）ＰI12

?（Ｐ→Ｑ）

?ＱI13（Ｐ∨Ｑ）Λ（Ｐ→Ｒ）Λ（Ｑ→Ｒ）Ｒ證明上述永真蘊(yùn)含式的方法有三種：（１）把“”關(guān)系符改為“→”聯(lián)結(jié)詞，證明它為永真式。

(a)真值表法

(b)命題演算法

§1.5重言式與蘊(yùn)含式（２）找出使單條件命題前件為“Ｔ”的所有真值指派，試看能否導(dǎo)致后件均為“Ｔ”，若為“Ｔ”，則永真蘊(yùn)含關(guān)系成立。TTTFFTTTFTFFP→QQP§1.5重言式與蘊(yùn)含式例：ＰΛ（Ｐ→Ｑ）Ｑ前件為“Ｔ”的所有指派為Ｐ、（Ｐ→Ｑ）均為“Ｔ”，Ｐ→Ｑ為“Ｔ”，∵Ｐ為“Ｔ”，∴Ｑ也應(yīng)為“Ｔ”，∴ＰΛ（Ｐ→Ｑ）Ｑ成立（３）＊找出使單條件命題的后件均為“Ｆ”的所有真值指派，試看前件的所有真值是否為“Ｆ”，若是，則蘊(yùn)含成立?！?.5重言式與蘊(yùn)含式例：?ＱΛ（Ｐ→Ｑ）

?Ｐ后件為“Ｆ”的所有條件是：Ｐ為“Ｔ”，代入前件得（?。┤簦褳椋裕瑒t?ＱΛ（Ｐ→Ｑ）為“Ｆ”；（ⅱ）若Ｑ為Ｆ，則?ＱΛ（Ｐ→Ｑ）為“Ｆ”；∴?ＱΛ（Ｐ→Ｑ）

?Ｐ成立若后件簡(jiǎn)單則可選用(3)；若前件簡(jiǎn)單則可選用(2)。二種方法是互為獨(dú)立的，只需使用一種證明就行?！?.5重言式與蘊(yùn)含式討論一下永真式可得出三個(gè)結(jié)論：（１）若一個(gè)命題公式等價(jià)于一個(gè)永真式，則該公式一定為永真式。（２）若一個(gè)永真的命題公式永真蘊(yùn)含一個(gè)命題公式，則此命題公式一定也為永真式。（３）若一個(gè)永假的命題公式永真蘊(yùn)含一個(gè)命題公式，則該公式可能是永真式、永假式或可滿足的?！?.5重言式與蘊(yùn)含式[定理]給定命題公式Ａ、Ｂ、Ｃ，若ＡＢ，且ＢＣ，則ＡＣ。證明：∵ＡＢ，且ＢＣ，∴（Ａ→Ｂ）Λ（Ｂ→Ｃ）為永真式，由I6：（Ａ→Ｂ）Λ（Ｂ→Ｃ）（Ａ→Ｃ），（Ａ→Ｃ）也為永真式；即，ＡＣ成立§1.5重言式與蘊(yùn)含式[推論]若ＡB1

、B1

B2．．．．．．Bm

Ｂ，則ＡＢ。[定理]給定一個(gè)命題公式Ａ、Ｂ、Ｃ，若ＡＢ,ＡＣ，則Ａ（ＢΛＣ）證明：∵ＡＢΛＡＣ，∴（Ａ→Ｂ）Λ（Ａ→Ｃ）為永真式，由條件，若Ａ一定為“Ｔ”，則Ｂ、Ｃ均為“Ｔ”，∴Ａ→（ＢΛＣ）也為“Ｔ”，結(jié)論：Ａ（ＢΛＣ）為“Ｔ”?！?.5重言式與蘊(yùn)含式上述也可用等價(jià)公式證明它：（Ａ→Ｂ）Λ（Ａ→Ｃ）（?Ａ∨Ｂ）Λ（?Ａ∨Ｃ）?Ａ∨（ＢΛＣ）Ａ→（ＢΛＣ）也為永真式∴Ａ（ＢΛＣ）成立[定義]設(shè)H1,H2….Hm,Ｑ均為命題公式，若（H1ΛH2Λ…

ΛHm

）

Ｑ，則稱H1,H2….Hm,共同蘊(yùn)含Ｑ，并記作：

H1,H2….Hm

Ｑ。

§1.5重言式與蘊(yùn)含式

[定理]若（H1ΛH2Λ…Hm

）,P

Ｑ，則（H1ΛH2Λ…Hm

）

（Ｐ→Ｑ）。

證明：（H1ΛH2Λ…ΛHm

ΛP）→Ｑ?（H1ΛH2Λ…ΛHm

ΛP）∨Q（?

H1∨

?

H2∨

…

∨?

Hm

）

∨（?

P∨Q）?（H1ΛH2Λ…ΛHm

）

∨（

P→Q）

H1Λ

H2Λ

….Λ

Hm→（Ｐ→Ｑ）也為永真式∴（H1Λ,H2Λ

….Λ

Hm

）（Ｐ→Ｑ）成立

§1.6其他聯(lián)結(jié)詞１．其他命題聯(lián)結(jié)詞：(1)不可兼或（異或，異）(a)符號(hào):(⊕),ＰＱ,讀作“Ｐ異或Ｑ”(b)定義:（由真值表）(c)異或的性質(zhì)：ＰＱ（?ＰΛＱ）∨（?ＱΛＰ）（Ｐ∨Ｑ）Λ（?Ｐ∨?Ｑ）

?（ＰＱ）ＱＰ(ＰＱ)ＲＰ(ＱＲ)FTTTFTTTFFFFP

QQP§1.6其他聯(lián)結(jié)詞ＰΛ（ＱＲ）（ＰΛＱ）（ＰΛＲ）（Λ對(duì)可分配的）ＰＰＦ，Ｐ

?ＰＴ，ＦＰＰ，ＴＰ

?Ｐ若ＰＱＲ，則有：ＰＲＱＲＰＲＱＰＱＲＱＰＲ，ＰＱＲＦ§1.6其他聯(lián)結(jié)詞(２)“與非”聯(lián)結(jié)詞：(a)符號(hào)↑,Ｐ↑Ｑ讀作“Ｐ與Ｑ的否定”或“Ｐ與非Ｑ”(b)定義：（由真值表）（Ｐ↑Ｑ）?（Ｐ∧Ｑ）FTTTFTTTFTFFP↑QQP§1.6其他聯(lián)結(jié)詞(c)性質(zhì)：（Ｐ↑Ｑ）（Ｑ↑Ｐ）（Ｐ↑Ｐ）?Ｐ（Ｐ↑Ｑ）↑（Ｐ↑Ｑ）（Ｐ∧Ｑ）（Ｐ↑Ｐ）↑（Ｑ↑Ｑ）（Ｐ∨Ｑ）Ｐ↑（Ｑ↑Ｒ）?Ｐ∨（Ｑ∧Ｒ）不可結(jié)合（Ｐ↑Ｑ）↑Ｒ（Ｐ∧Ｑ）∨?Ｒ不可結(jié)合Ｐ↑Ｔ?Ｐ，Ｐ↑ＦＴ§1.6其他聯(lián)結(jié)詞(３)“或非”聯(lián)結(jié)詞：(a)符號(hào)：“↓”（Ｐ↓Ｑ）讀作：“Ｐ或Ｑ的否定”或“Ｐ或非Ｑ”(b)定義（由真值表給出）：（Ｐ↓Ｑ）

?（Ｐ∨Ｑ）FTTFFTFTFTFFＰ↓ＱQP§1.6其他聯(lián)結(jié)詞(c)性質(zhì)：Ｐ↓ＱＱ↓Ｐ（可交換的）Ｐ↓Ｐ?Ｐ（Ｐ↓Ｑ）↓（Ｐ↓Ｑ）Ｐ∨Ｑ（Ｐ↓Ｐ）↓（Ｑ↓Ｑ）Ｐ∧ＱＰ↓（Ｑ↓Ｒ）?Ｐ∧（Ｑ∨Ｒ）不可結(jié)合（Ｐ↓Ｑ）↓Ｒ（Ｐ∨Ｑ）∧?Ｒ不可結(jié)合Ｐ↓Ｆ?Ｐ；Ｐ↓ＴＦ(d)由（２）和（３）中的性質(zhì)可見，↑和↓是互為對(duì)偶的?！?.6其他聯(lián)結(jié)詞(4)“蘊(yùn)含否定”聯(lián)結(jié)詞：(a)符號(hào)：(b)定義(由真值表給出）：PQ(PQ)“”cFFFFTFTFTFTTPQQPcc§1.6其他聯(lián)結(jié)詞(１)不同真值表的命題公式：按命題公式的生成規(guī)則，用聯(lián)結(jié)詞可組成無限個(gè)命題公式。下面討論這些命題公式有多少種不同的真值表：(a)若命題變?cè)挥幸粋€(gè)Ｐ，則用聯(lián)結(jié)詞組成的命題公式由四種不同的真值表，即為：

TFTFTTTFFF3210P§1.6其他聯(lián)結(jié)詞所有依賴于Ｐ的命題公式均等價(jià)于這四個(gè)中的一個(gè)(b)若有二個(gè)命題變?cè)?、Ｑ，則命題公式的不同真值表有：222=24=16種。推廣到一般：若有ｎ個(gè)變?cè)拿}公式，則可構(gòu)成不同的真值表為22n（個(gè)）?！?.6其他聯(lián)結(jié)詞（２）二元運(yùn)算中的全部聯(lián)結(jié)詞總結(jié)：

?、∧、∨、→、是五個(gè)基本聯(lián)結(jié)詞。到此為止，一個(gè)符號(hào)系統(tǒng)已定義完畢，它們是：命題變?cè)?Ａ、Ｂ…Ｘ、Ｙ、Ｚ值

:Ｆ、Ｔ

運(yùn)算符:?、∧、∨、→、、、↑、↓、括號(hào):（）關(guān)系符:、。C§1.6其他聯(lián)結(jié)詞３．全功能聯(lián)結(jié)詞集合：[定義]一個(gè)聯(lián)結(jié)詞集合，用其中聯(lián)結(jié)詞構(gòu)成的式子足以把一切命題公式等價(jià)的表達(dá)出來，則稱此聯(lián)結(jié)詞集合為全功能聯(lián)結(jié)詞集合。[定義]設(shè)有一聯(lián)結(jié)詞集合Ａ，若（１）用Ａ中的聯(lián)結(jié)詞的等價(jià)式能表達(dá)任何的一個(gè)命題公式；（２）刪除Ａ中的任一聯(lián)結(jié)詞，從而形成一個(gè)新的聯(lián)結(jié)詞集合Ａ’，至少有一個(gè)命題公式Ｂ不能用Ａ’中的聯(lián)結(jié)詞的等價(jià)式來表示，則稱A為最小的全功能聯(lián)結(jié)詞集合?！?.6其他聯(lián)結(jié)詞我們可以證明：{?，∨}；{?，∧}；{?，→}；{↑}；{↓}均為全功能聯(lián)結(jié)詞集合，且均是最小的全功能聯(lián)結(jié)詞集合。例：用上述最小全功能聯(lián)結(jié)詞集合中的聯(lián)結(jié)詞單一表達(dá)下述命題公式：§1.6其他聯(lián)結(jié)詞（Ｐ→Ｑ）

?Ｐ∨Ｑ{?，∨}??（?Ｐ∨Ｑ）

?（Ｐ∧?Ｑ）{?，∧}

??（Ｐ→Ｑ）{?，→}

?(ＰＱ){?，}

?

?

（?Ｐ∨Ｑ）（（Ｐ↓Ｐ）↓Ｑ）↓（（Ｐ↓Ｐ）↓Ｑ）

{↓}

?

?

（?Ｐ∨Ｑ）?

（Ｐ∧?Ｑ）Ｐ↑（Ｑ↑Ｑ）

{↑}→c→c§1.7對(duì)偶與范式３．對(duì)偶原理（對(duì)偶定律）[定義]給定二個(gè)命題公式Ａ和A*

，若用Λ代換∨，用∨代換Λ，用Ｔ代換Ｆ，用Ｆ代換Ｔ，其中一個(gè)命題公式由另一個(gè)命題公式得來，則稱Ａ和A*是互為對(duì)偶的，而聯(lián)結(jié)詞Λ和∨也是互為對(duì)偶的例：寫出下列命題公式的對(duì)偶式：Ｐ∨（ＱΛＲ）ＰΛ（Ｑ∨Ｒ）Ｐ∨ＦＰ對(duì)偶式A*ＰΛＴＰＰ∨ＴＴＰΛＦＦ

§1.7對(duì)偶與范式討論定義：（１）若命題公式中有聯(lián)結(jié)詞，，則必須把化成由聯(lián)結(jié)詞Λ，∨，組成的等價(jià)的命題公式，然后求它的對(duì)偶式；例：求(PQ)(PR)的對(duì)偶式§1.7對(duì)偶與范式（２）在寫對(duì)偶式時(shí)，原命題公式中括號(hào)不能省去，必須按優(yōu)先級(jí)的次序畫上括號(hào)，并在求其對(duì)偶式時(shí)仍將保留括號(hào)。例：（ＰΛＱ）∨Ｒ對(duì)偶式寫成（Ｐ∨Ｑ）ΛＲ，而不能寫成Ｐ∨ＱΛＲ§1.7對(duì)偶與范式[定理]（摩根推廣定理）設(shè)Ａ和A*為對(duì)偶式P1,P2．．．Pn

是出現(xiàn)在Ａ和A*中的所有原子命題變?cè)?，，于是有?Ａ（P1，P2．．．Pn）A*

（?P1，?P2．．．?Pn）——（1）Ａ（?P1，?P2．．．?Pn）?A*（P1，P2．．．Pn）——（２）§1.7對(duì)偶與范式證明：由摩根定理

?（Ｐ∨Ｑ）?ＰΛ?Ｑ—（１）

?（ＰΛＱ）?Ｐ∨?Ｑ—（２）∴不難看出：一個(gè)命題公式的否定等價(jià)于它的對(duì)偶式，且把變?cè)姆穸ù婷恳粋€(gè)變?cè)?例：設(shè)Ａ（Ｐ，Ｑ，Ｒ）?ＰΛ?

（Ｑ∨Ｒ），驗(yàn)證上述定理：§1.7對(duì)偶與范式證明：(１)Ａ（Ｐ，Ｑ，Ｒ）?ＰΛ?ＱΛ?Ｒ∴?Ａ（Ｐ，Ｑ，Ｒ）Ｐ∨Ｑ∨ＲA*（Ｐ，Ｑ，Ｒ）?Ｐ∨?Ｑ∨?ＲA*（?Ｐ，?Ｑ，?Ｒ）Ｐ∨Ｑ∨Ｒ（２）Ａ（?Ｐ，?Ｑ，?Ｒ）ＰΛＱΛＲ?A*（Ｐ，Ｑ，Ｒ）?（?Ｐ∨Ｑ∨?Ｒ）

ＰΛＱΛＲ有Ａ（?Ｐ，?Ｑ，?Ｒ）

?A*（Ｐ，Ｑ，Ｒ）§1.7對(duì)偶與范式[定理]若二個(gè)命題公式互為等價(jià)，則它們的對(duì)偶式也互為等價(jià)，亦即若ＡＢ，則A*B*成立。證明：已知：Ａ、Ｂ為任一命題公式，且ＡＢ，要證明A*B*設(shè)：P1、P2．．．Pn

是出現(xiàn)在Ａ和Ｂ中的原子命題變?cè)?，?.7對(duì)偶與范式由ＡＢ，即Ａ（P1，P2．．．Pn）Ｂ（P1，P2．．．Pn）∴?Ａ（P1，P2．．．Pn）?Ｂ（P1，P2．．．Pn）由摩根推廣定理∴Ａ*（?P1，?P2．．．?Pn）Ｂ*（?P1，?P2．．．?Pn）§1.7對(duì)偶與范式∴Ａ*（?P1，?P2．．．?Pn）

Ｂ*（?P1，?P2．．．?Pn）為永真式＊前面講過永真式的代換實(shí)例仍為永真式，所以用?Pi代換A*和B*中的Pi

（1≤i≤n)則得：Ａ*（?

?P1，?

?P2．．．?

?Pn）

Ｂ*（?

?P1，?

?P2．．．?

?Pn）即為：Ａ*（P1，P2．．．Pn）

Ｂ*（P1，P2．．．Pn）§1.7對(duì)偶與范式例：證明：（１）?（ＰΛＱ）→（?Ｐ∨（?Ｐ∨Ｑ））（?Ｐ∨Ｑ）（２）（Ｐ∨Ｑ）Λ（?ＰΛ（?ＰΛＱ））（?ＰΛＱ）證明：（１）左邊??(ＰΛＱ）∨（?Ｐ∨（?Ｐ∨Ｑ））

（ＰΛＱ）∨（?Ｐ∨Ｑ）（Ｐ∨?Ｐ∨Ｑ）Λ（Ｑ∨?Ｐ∨Ｑ）（?Ｐ∨Ｑ）§1.7對(duì)偶與范式（２）左邊（Ｐ∨Ｑ）Λ（?ＰΛＱ）（ＰΛ?ＰΛＱ）∨（ＱΛ?ＰΛＱ）（?ＰΛＱ）結(jié)論：（１）和（２）是互為對(duì)偶的?！?.7對(duì)偶與范式如何判定命題公式為永真式、永假式和可滿足式或二個(gè)命題公式等價(jià)，歸納有三種方法：（1）真值表法：對(duì)于變?cè)乃姓嬷抵概桑磳?duì)應(yīng)命題公式的真值。（2）命題演算方法：化簡(jiǎn)命題公式至最簡(jiǎn)式，看是否存在和（Ｐ∨?Ｐ）、（Ｐ∧?Ｐ）等價(jià)，若不則為可滿足的。（3）范式方法：本節(jié)就介紹此法。§1.7對(duì)偶與范式什么叫范式把命題公式化歸為一種標(biāo)準(zhǔn)的形式，稱此標(biāo)準(zhǔn)形式為范式。什么叫判定以有限次步驟來決定命題公式是否為永真式、永假式，還是可滿足的，或者判定二個(gè)命題公式是否等價(jià)等這一類的問題，統(tǒng)稱為判定問題。討論范式和主范式的目的就是為了進(jìn)行判定。

下面討論如何求析取范式和合取范式同一命題公式可以有各種相互等價(jià)的表達(dá)形式。如：PQ

PQ(PQ)(P∧P)

(PQP)∧(PQP)。為了把命題公式規(guī)范化，下面討論命題公式的范式。定義：一個(gè)命題公式稱為合取范式，當(dāng)且僅當(dāng)具有形式：A1∧A2∧…∧An，(n≥1)

其中A1,A2,…,An都是由命題變?cè)蚱浞穸ㄋM成的析取式。例如：(PQ)∧(PQ)∧(PQ)是合取范式定義：一個(gè)命題公式稱為析取范式，當(dāng)且僅當(dāng)它具有形式：A1A2…An，(n≥1)

其中A1,A2,…,An都是由命題變?cè)蚱浞穸ㄋM成的合取式。例如：(P∧Q∧R)(P∧Q∧R)(Q∧R)R是析取式。如何求析（合）取范式？將公式中的聯(lián)結(jié)詞化歸成，∧，；利用德.摩根律將否定符號(hào)直接移到各個(gè)命題變?cè)啊＠梅峙渎?、結(jié)合律將公式歸約為合取范式或析取范式。例：求公式P(P∧Q)的析取范式與合取范式解：合取范式

原式(P(P∧Q))

∧((P∧Q)P)(P(P∧Q))∧((P∧Q)P)

(PP)∧(PQ)∧(PQP)析取范式：原式(P∧(P∧Q))(P∧(P∧Q))(P∧P∧Q)(P∧(PQ))(P∧Q)(P∧P)(P∧Q)(P∧Q)P(P∧Q)

§1.7對(duì)偶與范式（１）利用等價(jià)公式：化去“→”、“”聯(lián)結(jié)詞，把命題公式變?yōu)榕c其等價(jià)的用{?，∧，∨}表達(dá)的公式。

例:Ｐ→Ｑ?Ｐ∨Ｑ，Ｐ?Ｑ（Ｐ∧Ｑ）∨（?Ｐ∧?Ｑ）

（?Ｐ∨Ｑ）∧（Ｐ∨?Ｑ）（２）將“?”深入到原子命題變?cè)?，并使變?cè)白疃嘀挥幸粋€(gè)“?”詞。例：?（?Ｐ∨?Ｑ）?

?Ｐ∧?

?ＱＰ∧Ｑ§1.7對(duì)偶與范式