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

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

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

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

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

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

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

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

(4小時出庫)

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

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

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

第一部分數(shù)理邏輯包括命題邏輯;謂詞邏輯

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

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

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

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

Wybe

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

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

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

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

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

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

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

(1)符號“Λ”

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

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

(a)P：王華是黨員。

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

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

Q：房間里有一臺電視機則ＰΛＱ：我們?nèi)シN樹且房間里有一臺電視機?！?.2命題聯(lián)結詞(c)P：今天下雪

Q：3+3=6

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

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

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

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

當Ｐ為“Ｔ”，Ｑ為“Ｆ”時，則（Ｐ→Ｑ）為“Ｆ”，否則（Ｐ→Ｑ）均為“Ｔ”。Ｐ：稱為前件、條件、前提、假設Ｑ：稱為后件、結論。（３）舉例：

P：我拿起一本書

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

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

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

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

?Q→?P

原命題逆反命題Ｑ→Ｐ

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

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

Λ∨→?

（由高到低）（３）聯(lián)結詞按從左到右的次序進行運算（４）最外層的括號一律均可省去（Ｐ→Ｑ∨Ｒ）可寫成Ｐ→Ｑ∨Ｒ§1.2命題聯(lián)結詞例?Ｐ∨（Ｑ∨Ｒ）可省去括號因為“Ｖ”運算是可結合的。而Ｐ→（Ｑ→Ｒ）中的括號不能省去，因“→”不滿足結合律。§1.2命題聯(lián)結詞

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

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

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

P：李明是計算機系的學生。

Q：李明住在312室。

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

P：交通堵塞。

Q：老王準時到達了車站。該命題符號化為：PQ（4）首先用字母表示簡單命題。

P：三角形的一個角是直角。

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

P：老王去上海出差。

Q：小李去上海出差。該命題符號化為：P▽Q

也可符號化為：（PQ）（PQ）或者（PQ）（PQ）§1.4真值表與等價公式一．命題公式的真值表:命題變元用特定的命題來取代，這一過程稱為對該命題變元進行真值指派。命題公式可以看成是一個以真假值為定義域和真假值為值域的一個函數(shù)。寫成ｙ＝ｆ(x)§1.4真值表與等價公式

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

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

1)找出給定命題公式中所有的命題變元，列出所有可能的賦值。

2)按照從低到高順序寫出命題公式的各層次。

3)對應每個賦值，計算命題公式各層次的值，直到最后計算出整個命題公式的值?！?.4真值表與等價公式FTTTTFTTFTTFTTFTFFFF?（（Ｐ∨Ｑ）ΛＰ）（Ｐ∨Ｑ）ΛＰP∨QQP例１．構造命題公式?（（Ｐ∨Ｑ）ΛＰ）的真值表：§1.4真值表與等價公式

例２．寫出命題公式Ｐ∨（ＱΛＲ）的真值表TTTTTFTTTTFTTFFTTTTFFFTFFTFFFFFFＰ∨（ＱΛＲ)RQP§1.4真值表與等價公式由上二例可見，２個命題變元有４組真值指派；３個命題變元有23＝８組真值指派，ｎ個則有個2n個真值指派?！?.4真值表與等價公式３．命題公式的永真式、永假式和可滿足式[定義]設公式Ａ中有n個不同的原子變元

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

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

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

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

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

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

是Ｂ中的原子命題變元，若（1）用某些命題公式代換Ｂ中的一些原子命題變元Pi

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

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

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

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

P

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

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

?Ｐ∨

?Ｑ∨Ｐ

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

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

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

Ｐ→Ｑ§1.5重言式與蘊含式I10ＱＰ→ＱI11?（Ｐ→Ｑ）ＰI12

?（Ｐ→Ｑ）

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

(a)真值表法

(b)命題演算法

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

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

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

、B1

B2．．．．．．Bm

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

ΛHm

）

Ｑ，則稱H1,H2….Hm,共同蘊含Ｑ，并記作：

H1,H2….Hm

Ｑ。

§1.5重言式與蘊含式

[定理]若（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)結詞１．其他命題聯(lián)結詞：(1)不可兼或（異或，異）(a)符號:(⊕),ＰＱ,讀作“Ｐ異或Ｑ”(b)定義:（由真值表）(c)異或的性質：ＰＱ（?ＰΛＱ）∨（?ＱΛＰ）（Ｐ∨Ｑ）Λ（?Ｐ∨?Ｑ）

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

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

?ＰＴ，ＦＰＰ，ＴＰ

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

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

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

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

:Ｆ、Ｔ

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

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

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

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

?(ＰＱ){?，}

?

?

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

{↓}

?

?

（?Ｐ∨Ｑ）?

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

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

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

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

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

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

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

?（ＰΛＱ）?Ｐ∨?Ｑ—（２）∴不難看出：一個命題公式的否定等價于它的對偶式，且把變元的否定代替每一個變元。 例：設Ａ（Ｐ，Ｑ，Ｒ）?ＰΛ?

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

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

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

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

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

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

?P1，?

?P2．．．?

?Pn）

Ｂ*（?

?P1，?

?P2．．．?

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

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

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

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

PQ(PQ)(P∧P)

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

其中A1,A2,…,An都是由命題變元或其否定所組成的析取式。例如：(PQ)∧(PQ)∧(PQ)是合取范式定義：一個命題公式稱為析取范式，當且僅當它具有形式：A1A2…An，(n≥1)

其中A1,A2,…,An都是由命題變元或其否定所組成的合取式。例如：(P∧Q∧R)(P∧Q∧R)(Q∧R)R是析取式。如何求析（合）取范式？將公式中的聯(lián)結詞化歸成，∧，；利用德.摩根律將否定符號直接移到各個命題變元之前。利用分配律、結合律將公式歸約為合取范式或析取范式。例：求公式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對偶與范式（１）利用等價公式：化去“→”、“”聯(lián)結詞，把命題公式變?yōu)榕c其等價的用{?，∧，∨}表達的公式。

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

（?Ｐ∨Ｑ）∧（Ｐ∨?Ｑ）（２）將“?”深入到原子命題變元之前，并使變元之前最多只有一個“?”詞。例：?（?Ｐ∨?Ｑ）?

?Ｐ∧?

?ＱＰ∧Ｑ§1.7對偶與范式