離散數(shù)學(xué)第一章-命題邏輯

1、,第一章 命題邏輯,離散數(shù)學(xué) 陳志奎主編人民郵電出版社,,,,,,,,,,,,,,,,,,,,,引言,,,,,,,,,,,,,,,,,,,,,學(xué)習(xí)方法,精確嚴(yán)格地掌握好概念和術(shù)語，正確理解它們的內(nèi)涵和外延；獨(dú)立完成作業(yè)，自覺歸納基本解題方法；閱讀和復(fù)習(xí)時，隨時備好紙筆，以便進(jìn)行詳細(xì)的推導(dǎo)和計(jì)算；學(xué)習(xí)和理解術(shù)語，給術(shù)語賦予特殊的含義，加深理解。多做習(xí)題，加深理解。,,,,,,,,,,,,,,,,,,,,,什么是數(shù)理邏輯？,數(shù)理

2、邏輯是用數(shù)學(xué)方法研究思維規(guī)律的一門學(xué)科。所謂數(shù)學(xué)方法是指:用一套數(shù)學(xué)的符號系統(tǒng)來描述和處理思維的形式與規(guī)律。因此，數(shù)理邏輯又稱為符號邏輯。,,,,,,,,,,,,,,,,,,,,,什么是數(shù)理邏輯？,,數(shù)理邏輯的創(chuàng)始人--萊布尼茨,萊布尼茨(Leibniz, Gottfried Wilhelm) 1646.7.1-1716.11.14德國數(shù)學(xué)家、物理學(xué)家、哲學(xué)家等，一個舉世罕見的科學(xué)天才。研究領(lǐng)域涉及到邏輯學(xué)、數(shù)學(xué)、力學(xué)、地質(zhì)學(xué)、法學(xué)

3、、歷史學(xué)、語言學(xué)、生物學(xué)以及外交、神學(xué)等諸多方面.出生于德國東部萊比錫的一個書香之家，父親是萊比錫大學(xué)的道德哲學(xué)教授，母親出生在一個教授家庭。萊布尼茲的父親在他年僅6歲時便去世了，給他留下了豐富的藏書。,,,,,,,,,,,,,,,,,,,,,什么是數(shù)理邏輯？,,數(shù)理邏輯的創(chuàng)始人--萊布尼茨,15歲時，進(jìn)了萊比錫大學(xué)學(xué)習(xí)法律，一進(jìn)校便跟上了大學(xué)二年級標(biāo)準(zhǔn)的人文學(xué)科的課程，還廣泛閱讀了培根、開普勒、伽利略等人的著作，并對他們的著述進(jìn)行深

4、入的思考和評價。在聽了教授講授歐幾里德的《幾何原本》的課程后，萊布尼茲對數(shù)學(xué)產(chǎn)生了濃厚的興趣。17歲時他在耶拿大學(xué)學(xué)習(xí)了短時期的數(shù)學(xué)，并獲得了哲學(xué)碩士學(xué)位 。19歲設(shè)計(jì)出世界第一臺乘法器，被認(rèn)為是現(xiàn)代機(jī)器數(shù)學(xué)的先驅(qū)者。 Leibniz(1646～1716年) 之夢：有一天所有的知識，包括精神和無形的真理，能夠通過通用的代數(shù)演算放入一個單一的演繹系統(tǒng)。1693年，發(fā)現(xiàn)了機(jī)械能的能量守恒定律。與牛頓并稱為微積分的創(chuàng)立者。系統(tǒng)闡述了

5、二進(jìn)制記數(shù)法，并把它和中國的八卦聯(lián)系起來。,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,命題和聯(lián)結(jié)詞,,主要內(nèi)容,合式公式與真值表,永真式和等價式,對偶式與蘊(yùn)涵式,范式和判定問題,命題演算的推理理論,,,,,,,,,,,,,,,,,,,,,1.1 命題和聯(lián)結(jié)詞,,8,現(xiàn)實(shí)語言,,,判定,,推理,翻譯,應(yīng)用：計(jì)算機(jī)電路設(shè)計(jì) 計(jì)算機(jī)程序構(gòu)造 程序正確性證明,,,,,,,,,,,,,,,,,,,,,1.

6、1 命題和聯(lián)結(jié)詞,定義1.1 命題是或者為真，或者為假而不是兩者同時成立的陳述句。 作為命題的陳述句所表達(dá)的判斷結(jié)果稱作命題的真值，真值只能取兩個值：真或假。真值為真的命題稱為真命題，真值為假的命題稱為假命題。注意：任何命題的真值都是唯一的。 如果一個命題的真值是真，則用1或T(Ture)來表示；如果一個命題的真值是假，則用0或F（False）來表示。 命題用大寫的英文字母，如P，Q，R……來表示。 判斷給定句子是否為命

7、題分為兩步：首先判斷該句子是否為陳述句，其次判斷它是否有唯一的一個真值。,9,命題的概念,,,,,,,,,,,,,,,,,,,,,1.1 命題和聯(lián)結(jié)詞,例1.1 判斷下面句子是否是命題。（1）2013年是閏年。（2）2×2=5。（3）小明晚上去看電影。（4）這朵花真漂亮?。。?）請不要在此處吸煙！（6）你下午會出去嗎？（7）2既是素?cái)?shù)又是偶數(shù)。（8）本句話是錯的。,10,命題的概念,（1）、（2）、（3）和（

8、7）都是命題,,,,,,,,,,,,,,,,,,,,,1.1 命題和聯(lián)結(jié)詞,聯(lián)結(jié)詞是邏輯聯(lián)結(jié)詞或者命題聯(lián)結(jié)詞的簡稱，它是自然語言中連詞的邏輯抽象。有了聯(lián)結(jié)詞，就可以通過它和原子命題構(gòu)成復(fù)合命題。常用的邏輯聯(lián)結(jié)詞主要包括以下6種。（1）聯(lián)結(jié)詞“非”，記為“┓P ”，表示“否定”的意思。（2）聯(lián)結(jié)詞“合取”，記為“∧”，表示“且”的意思。（3）聯(lián)結(jié)詞“析取”，記為“∨”，表示“或”的意思。（4）聯(lián)結(jié)詞“蘊(yùn)涵”，記為“→”，表示“如果

9、…，則…”的意思。（5）聯(lián)結(jié)詞“等價”，記為“?”，表示“當(dāng)且僅當(dāng)”的意思。（6）聯(lián)結(jié)詞“抑或”，記為“?”，表示“要么…，要么…”的意思。,11,聯(lián)結(jié)詞,,,,,,,,,,,,,,,,,,,,,1.1 命題和聯(lián)結(jié)詞,設(shè)P是一個命題，則聯(lián)結(jié)詞┓和命題P構(gòu)成┓P，┓P為命題P的否定式復(fù)合命題，讀作“非P”。聯(lián)結(jié)詞┓是自然語言中的“非”、“不”和“沒有”等的邏輯抽象。 其真值是這樣定義的，若P的真值是T，那么┓P的真值是F；若P的真

10、值是F，則┓P的真值是T。命題P與其否定┓P的如表1.1所示。,12,邏輯聯(lián)結(jié)詞否定—“┓”,表1.1邏輯聯(lián)結(jié)詞“┐”的定義,,,,,,,,,,,,,,,,,,,,,1.1 命題和聯(lián)結(jié)詞,例1.2 給出下列命題的否定。（1）令P表示：大連是北方香港。 于是┓P表示：大連不是北方香港。 注意：邏輯聯(lián)結(jié)詞否定是個一元運(yùn)算符。（2）令Q表示：所有的素?cái)?shù)都是奇數(shù)。 于是┓Q表示

11、：并非所有的素?cái)?shù)都是奇數(shù)。 注意：翻譯成“所有的素?cái)?shù)都不是奇數(shù)”是錯誤的。因?yàn)榉穸ㄊ菍φ麄€命題進(jìn)行的。,13,邏輯聯(lián)結(jié)詞否定—“┓”,,,,,,,,,,,,,,,,,,,,,1.1 命題和聯(lián)結(jié)詞,設(shè)P是一個命題，Q是一個命題，由聯(lián)結(jié)詞∧把P和Q連接成P∧Q，稱P∧Q為P和Q的合取式復(fù)合命題，P∧Q讀作“P與Q”或者“P合取Q”。聯(lián)結(jié)詞∧是“并且”的邏輯抽象。 它的真值是這樣定義的：當(dāng)且僅當(dāng)P和Q的真值都為T時，P∧

12、Q的真值才為T，否則P∧Q的真值為F。邏輯聯(lián)結(jié)詞“∧”的定義如表1.2所示。,14,邏輯聯(lián)結(jié)詞合取——“∧”,,表1.2邏輯聯(lián)結(jié)詞“∧”的定義,,,,,,,,,,,,,,,,,,,,,1.1 命題和聯(lián)結(jié)詞,例1.3 令P表示：外面正在下雪。 令Q表示：3小于5。 于是P∧Q表示 ：外面正在下雪并且3小于5。 從自然語言看，上述命題是不合理的、沒有意義的，因?yàn)镻和Q毫不相關(guān)。但是，在數(shù)理邏輯中是被允

13、許的，也是正確的。P和Q再合取P∧Q仍可成為一個新的命題。只要P和Q的真值給定，P∧Q的真值即可確定。 邏輯聯(lián)結(jié)詞“∧”是個二元運(yùn)算符，且具有對稱性，即P∧Q和Q∧P具有相同真值。,15,邏輯聯(lián)結(jié)詞合取——“∧”,,,,,,,,,,,,,,,,,,,,,,1.1 命題和聯(lián)結(jié)詞,設(shè)P是一個命題，Q是一個命題，由聯(lián)結(jié)詞∨把P、Q連接成P∨Q，稱P∨Q為P、Q的析取式復(fù)合命題，讀作“P或Q”，或“P析取Q”。 其真值是這樣的定義的：當(dāng)且

14、僅當(dāng)P和Q的真值均為F時，P∨Q的真值為F，其余情況均為T。邏輯聯(lián)結(jié)詞“∨”的定義如表1.3所示。,16,邏輯聯(lián)結(jié)詞析取——“∨”,,表1.3邏輯聯(lián)結(jié)詞“∨”的定義,,,,,,,,,,,,,,,,,,,,,1.1 命題和聯(lián)結(jié)詞,聯(lián)結(jié)詞∨是自然語言中“或”、“或者”的邏輯抽象。而在自然語言中，“或”是多義的。從析取的定義不難看出，邏輯聯(lián)結(jié)詞“∨”和自然漢語中的“或”的意義并不完全相同。因?yàn)闈h語中的“或”可表示“排斥或”，亦可表示“可兼或

15、”，而邏輯聯(lián)結(jié)詞“析取”指的僅僅是“可兼或”，并不表示其他意義的“或”。 例1.4 令P表示：小明現(xiàn)在正在睡覺。 令Q表示：小明現(xiàn)在正在打球。于是命題，小明現(xiàn)在正在睡覺或者正在打球不能用P∨Q來表示。因?yàn)檫@里自然語言陳述的或是排斥或，這種意義的或我們用另一個邏輯聯(lián)結(jié)詞“異或”“?”來表示，后面我們將給出它的定義。,17,邏輯聯(lián)結(jié)詞析取——“∨”,,,,,,,,,,,,,,,,,,,,,,1.1 命

16、題和聯(lián)結(jié)詞,例1.5 將句子“他昨晚做了20或者30道作業(yè)題”表示為復(fù)合命題。在此例中，該句子不能被表示成復(fù)合命題，因?yàn)檫@里的“或”表示的是近似或者猜測的意思。 例1.6 令P表示：張亮是跳高運(yùn)動員。 令Q表示：張亮是跳遠(yuǎn)運(yùn)動員。于是命題，張亮可能是跳高或跳遠(yuǎn)運(yùn)動員就可以用P∨Q來表示，因?yàn)檫@里的或是可兼或。邏輯聯(lián)結(jié)詞析取也是個二元運(yùn)算符。,18,邏輯聯(lián)結(jié)詞析取——“∨”,,,,,,,,,,,,

17、,,,,,,,,,,1.1 命題和聯(lián)結(jié)詞,設(shè)P是一個命題，Q是一個命題，由聯(lián)結(jié)詞→把P、Q連接成P→Q，稱P→Q為P、Q的條件式復(fù)合命題，把P和Q分別稱為P→Q的前件和后件，或者前提和結(jié)論。P→Q讀作“如果P則Q”或“如果P那么Q”。其中P被稱為前件，Q被稱為為后件。很多時候聯(lián)結(jié)詞→也被稱為蘊(yùn)涵。 P→Q的真值是這樣定義的，當(dāng)且僅當(dāng)P→Q的前件P的真值為T，后件Q的真值為F時，P→Q的真值為F，否則，P→Q的真值為T。單條件邏輯聯(lián)結(jié)詞

18、“→”的定義如表1.4所示。,19,邏輯聯(lián)結(jié)詞單條件—“→”,,表1.4邏輯聯(lián)結(jié)詞“→”的定義,,,,,,,,,,,,,,,,,,,,,1.1 命題和聯(lián)結(jié)詞,例1.7：（1）令P表示：天不下雨 令Q表示：植物枯萎 于是P→Q表示：如果天不下雨，則植物枯萎。（2）令R表示：我有時間。 令S表示：我一定去學(xué)畫畫。 于是，R→S表示：如果我有時間，那我一定去學(xué)畫畫。

19、（3）令U表示：大海的顏色是藍(lán)色的。 令V表示：雪的顏色是白色的。 于是，U→V表示：如果大海的顏色是藍(lán)色的，那么雪的顏色是白色的。,20,邏輯聯(lián)結(jié)詞單條件—“→”,,,,,,,,,,,,,,,,,,,,,,1.1 命題和聯(lián)結(jié)詞,設(shè)P是一個命題，Q是一個命題，于是聯(lián)結(jié)詞?把P、Q連接成P?Q，稱P?Q為P和Q的雙條件式復(fù)合命題，讀作“P當(dāng)且僅當(dāng)Q”或“P等值于Q”。 P?Q的真值是這樣定義的，當(dāng)且

20、僅當(dāng)P和Q有相同的真值時，P?Q的真值為T，否則，P?Q的真值為F。P?Q的運(yùn)算表如表1.5所示。,21,邏輯聯(lián)結(jié)詞雙條件—“?”,,表1.5邏輯聯(lián)結(jié)詞“?”的定義,,,,,,,,,,,,,,,,,,,,,1.1 命題和聯(lián)結(jié)詞,例1.8 使用聯(lián)結(jié)詞翻譯一下命題：（1）三角形是等邊的，當(dāng)且僅當(dāng)它的3個內(nèi)角相等。（2）電燈不亮，當(dāng)且僅當(dāng)燈泡發(fā)生故障或開關(guān)發(fā)生故障。（3）2 + 2 = 4，當(dāng)且僅當(dāng)今天天晴。,22,邏輯聯(lián)結(jié)詞雙條件

21、—“?”,,解：令P：三角形是等邊的。 Q：三角形3個內(nèi)角相等。于是（1）可表示為：P?Q令R：電燈不亮。 S：燈泡發(fā)生故障。 T：開關(guān)發(fā)生故障。于是（2）可表示成：R?(S∨T)。令A(yù)：2 + 2 = 4。 B：今天天晴。于是（3）可表示為：A?B,,,,,,,,,,,,,,,,,,,,,1.1 命題和聯(lián)結(jié)詞,設(shè)P是一個命題，Q是一個命題，于是“P異或Q”是一個新的命題，記作“P?Q”，讀

22、作“P異或Q”。其真值是這樣定義的，當(dāng)且僅當(dāng)P和Q有不同的真值時，P?Q的真值為T，否則P?Q的真值為F。 P?Q的運(yùn)算表如表1.6所示。,23,邏輯聯(lián)結(jié)詞異或—“?”,,表1.6邏輯聯(lián)結(jié)詞“?”的定義,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,命題和聯(lián)結(jié)詞,,主要內(nèi)容,合式公式與真值表,永真式和等價式,對偶式與蘊(yùn)涵式,范式和判定問題,命題演算的推理理論,,,,,,,,,,,,,,,,,,,,,1.2 合式公

23、式與真值表,定義1.2 合式公式：（1）真值T和F是合式公式。（2）原子命題公式是一個合式公式。（3）如果A是合式的公式，那么┓A是合式的公式。（4）如果A和B均是合式的公式，那么(A∧B)，(A∨B),(A→B)和(A?B)都是合式的公式。（5）當(dāng)且僅當(dāng)有限次地應(yīng)用（1）至（4）條規(guī)則由邏輯聯(lián)結(jié)詞、圓括號所組成的有意義的符號串是合式的公式。 以上定義方法稱為遞歸定義法。其中（1）稱為遞歸定義的基礎(chǔ)，（2）

24、、（3）和（4）稱為遞歸定義的歸納，（5）稱為遞歸定義的界限。,25,合式公式,,,,,,,,,,,,,,,,,,,,,,1.2 合式公式與真值表,按照上面的定義，下面的字符串都是合式的公式。（1）┓(P∧Q)（2）┓(P→Q)（3）(P→(P∧┓Q))（4）(((P→Q)∧(Q→R))?(S ?T)) 下面的字符串則不是合式的公式。（1）(P→Q)→(∧Q)（2）(P→Q)（3）(P∧Q)→Q),26,合式公式,,,

25、,,,,,,,,,,,,,,,,,,,1.2 合式公式與真值表,今后，我們把合式的公式簡稱為命題公式。一般一個命題公式的真值是不確定的，只有用確定的命題去取代命題公式中的命題變元，或?qū)ζ渲械拿}變元進(jìn)行真值指派時，命題公式才成為具有確定真值的命題。給定兩個命題公式，若對其中變元的所有可能的真值指派兩個命題公式具有相同的真值，則稱它們是相互等價的?？梢岳谜嬷当砑夹g(shù)來判定兩個命題公式的等價性。,27,合式公式,,,,,,,,,,,,,,

26、,,,,,,,,1.2 合式公式與真值表,定義1.3 設(shè)A為一命題公式，對其中出現(xiàn)的命題變元做所有可能的每一組真值指派S，連同公式A相應(yīng)S(A)的取值匯列成表，稱為A的真值表。一個真值表由兩部分構(gòu)成。（1）表的左半部分列出公式的每一種解釋。（2）表的右半部分給出相應(yīng)每種解釋公式得到的真值。為構(gòu)造的真值表方便和一致，有如下約定。（1）命題變元按字典序排列。（2）對公式的每種解釋，以二進(jìn)制數(shù)從小到大或者從大到小順序排列。（3）

27、若公式復(fù)雜，可先列出各子公式的真值（若有括號從里層向外展開），最后列出所給公式的真值。,28,真值表,,,,,,,,,,,,,,,,,,,,,,1.2 合式公式與真值表,例1.10：（1）給出命題公式┓(P∨Q)∧P)的真值表。（2）使用真值表技術(shù)證明命題公式P?Q與P∧Q∨┓P∧┓Q是相互等價的。,29,真值表,,解：構(gòu)造（1）的真值表如下,對于（2）構(gòu)造真值表如下,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

28、,命題和聯(lián)結(jié)詞,,主要內(nèi)容,合式公式與真值表,永真式和等價式,對偶式與蘊(yùn)涵式,范式和判定問題,命題演算的推理理論,,,,,,,,,,,,,,,,,,,,,1.3 永真式和等價式,定義1.4 永真式、永假式與可滿足式。（1）不依賴于命題變元的真值指派，而總是取值為T（即1）的命題公式，稱為永真式或稱作重言式。（2）不依賴于命題變元的真值指派，而總是取值為F（即0）的命題公式，稱為永假式或矛盾式。（3）至少存在一組真值指派使命題公式

29、取值為T的命題公式，稱為可滿足的。,31,永真式,,,,,,,,,,,,,,,,,,,,,,1.3 永真式和等價式,定義1.5 設(shè)A和B是兩個命題公式，如果A、B在其任意解釋下，其真值都是相同的，即A?B是重言式，則稱A和B是等價的，或邏輯相等，記作A?B，讀作A恒等于B，或A等價于B。 注意符號“?”與符號“?”的意義是有區(qū)別的。符號“?”是邏輯聯(lián)結(jié)詞，是個運(yùn)算符；而符號“?”是關(guān)系符，A?B表示A和B有邏輯等價關(guān)系。,32,等

30、價式,,,,,,,,,,,,,,,,,,,,,,1.3 永真式和等價式,常用的邏輯恒等式如表1.7所示。 表中符號P、Q、R代表任意命題，符號T代表真命題，符號F代表假命題。表中所有公式是進(jìn)行等價變換和邏輯推理的重要依據(jù)。,33,等價式,,,,,,,,,,,,,,,,,,,,,,1.3 永真式和等價式,在一個重言式中，某個命題變元出現(xiàn)的每一處均代以同一個公式后，所得到的新的公式仍是重言式，這條規(guī)則稱之為代入規(guī)則。這條規(guī)則之所以正確

31、，是因?yàn)橛勒媸綄θ魏谓忉?，其值都是真，與所給的某個變元指派的真值是真還是假無關(guān)，因此，用一個命題公式代入到原子命題變元R出現(xiàn)的每一處后，所得命題公式的真值還是真。例如：P∧┓P?F令以R∧Q代P得，（R∧Q）∧┓(R∧Q) ? F仍是重言式。,34,代入規(guī)則,,,,,,,,,,,,,,,,,,,,,,1.3 永真式和等價式,設(shè)有恒等式A?B若在公式C中出現(xiàn)A的地方替換以B（不一定是每一處都進(jìn)行）而得到公式D,則C?D，這條規(guī)則稱之為

32、替換規(guī)則。如果A是公式C中完整的部分，且A是合式的公式，則稱A是C的子公式。規(guī)則中“公式C中出現(xiàn)A”意即“A是C的子公式”。這條規(guī)則之所以正確，是因?yàn)樵诠紺和D中替換部分以外均相同，所以C和D的真值也相同，故C?D。,35,替換規(guī)則,,,,,,,,,,,,,,,,,,,,,,1.3 永真式和等價式,設(shè)應(yīng)用代入規(guī)則和替換規(guī)則及已有的重言式可以證明新的重言式。例如對公式E12：┓（P∧Q）? ┓P∨┓Q，我們以A∧B代E12中

33、的P，而以┓A∧┓B代E12中的Q就得出公式┓((A∧B)∧(┓A∧┓B)) ? ┓(A∧B) ∨┓(┓A∧┓B)對公式E20：P∧T?P，我們利用公式P∨┓P?T，對其中的T作替換（對命題常元不能做代換）得公式P∧(P∨┓P) ?P…因此，我們可以說表1.7和表1.9中的字符P、Q和R不僅代表命題變元，而且可以代表命題公式；T和F不僅代表真命題和假命題，而且可以代表重言式和永假式。用這樣的觀點(diǎn)看待表中的公式，應(yīng)用就顯得更方便。,

34、36,,,,,,,,,,,,,,,,,,,,,,1.3 永真式和等價式,例1.12（1）試證P→(Q→R)? Q→(P→R) ? ┓R→(Q→┓P)證：P→(Q→R) ?┓P∨(┓Q∨R)兩次替換 ?┓Q∨(┓P∨R) 結(jié)合、交換、結(jié)合 ? Q→(P→R) 兩次替換類似可證P→(Q→R)? ┓R→(Q→┓P)。（2）試證（P→Q）→(Q∨R) ? P∨Q∨R證：(P→Q)→(Q∨R) ?

35、 (┓(┓P∨Q) ∨(Q∨R)E27和替換規(guī)則 ? (P∧┓Q)∨(Q∨R) E12和替換規(guī)則 ? ((P∧┓Q)∨Q)∨RE4 ? ((P∨Q)∧(Q∨┓Q))∨R ? P∨Q∨R例1.12的（1）和替換規(guī)則,37,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,命題和聯(lián)結(jié)詞,,主要內(nèi)容,合式公式與真值表,永真式和等價式,對偶式與蘊(yùn)涵式,范式和判定問題,命題

36、演算的推理理論,,,,,,,,,,,,,,,,,,,,,1.4 對偶式與蘊(yùn)含式,定義1.6 設(shè)有公式A，其中僅含邏輯聯(lián)結(jié)詞┓，∧，∨和邏輯常值T和F。在A中將∧，∨，T，F(xiàn)分別換以∨，∧，F(xiàn)，T得公式A*，則稱A*為A的對偶式。同理，A也可稱為A*的對偶式，即對偶式是相互的。定理1.1 設(shè)A和A*互為對偶式，P1，P2，…，Pn是出現(xiàn)于A和A*中的所有命題變元，于是：┓A（P1，P2，…，Pn）?A*( P1，P2，…，Pn)

37、 A（┓P1，┓P2，…，┓Pn）?┓A*( P1，P2，…，Pn),39,對偶式,,,,,,,,,,,,,,,,,,,,,,1.4 對偶式與蘊(yùn)含式,定理1.2 若A?B，且A、B為命題變元P1，P2，…，Pn及聯(lián)結(jié)詞∧，∨，┓構(gòu)成的公式，則A*?B*。證明：A?B意味著：A(P1，P2，…，Pn）?B(P1，P2，…，Pn）為永真式，于是┓A(P1，P2，…，Pn）?┓B(P1，P2，…，Pn）為永真式，由定理

38、1.1得，A*(┓P1，┓P2，…，┓Pn）?B*(┓P1，┓P2，…，┓Pn）為永真式。因?yàn)樯鲜绞怯勒媸?，使用帶入?guī)則所得仍為永真式，今以┓Pi代P（i=1,2,…,n），得A*(P1，P2，…，Pn）?B*(P1，P2，…，Pn）為永真式，所以A*?B* 。本定理稱為對偶原理。,40,對偶式,,,,,,,,,,,,,,,,,,,,,,1.4 對偶式與蘊(yùn)含式,定理1.3 如果A? B且A，B為命題變元P1，P2，…，Pn及

39、聯(lián)結(jié)詞∧，∨，┓構(gòu)成的公式，則B* ? A*證明：A ? B意味著A(P1，P2，…，Pn）→B(P1，P2，…，Pn）為永真式。由逆反律得，┓B(P1，P2，…，Pn）→┓A(P1，P2，…，Pn）為永真式。由定理1.1得，B*(┓P1，┓P2，…，┓Pn）→A*(┓P1，┓P2，…，┓Pn）為永真式。因?yàn)樯鲜绞怯勒媸?，使用帶入?guī)則仍為永真式，今以┓Pi代 Pi (i=1，2，…， )得B* ? A* 。,41,對偶式,

40、,,,,,,,,,,,,,,,,,,,,,1.4 對偶式與蘊(yùn)含式,如果單條件聯(lián)結(jié)式A→B是一個永真式，則它被稱為永真蘊(yùn)涵式，記為“A?B”,讀作“A永真蘊(yùn)涵B”。其中A稱為B的有效前提，B稱為A的邏輯結(jié)果，可以說由A推出B，也可以說B是由A推出的。從A?B的定義不難看出，要證明A永真蘊(yùn)涵B，只要證明A→B是一個永真式即可。而從A→B的定義不難知道要說明A→B是永真式，只要說明下面兩點(diǎn)之一即可。假定前件A是真，若能推出后件B必為真，則A

41、→B永真，于是A?B。假定后件B是假，若能推出前件A必為假，則A→B永真，于是A?B。也可以用真值表法來證明永真蘊(yùn)涵式。即證明對于命題公式中命題變元的所有真值指派來說，若其中使邏輯前提取值為真的那些真值指派，也必然使邏輯結(jié)果取值為真，則說A?B。,42,蘊(yùn)含式,,,,,,,,,,,,,,,,,,,,,,1.4 對偶式與蘊(yùn)含式,常用的永真蘊(yùn)涵式如表1.9所示。,43,蘊(yùn)含式,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

42、,,,,,命題和聯(lián)結(jié)詞,,主要內(nèi)容,合式公式與真值表,永真式和等價式,對偶式與蘊(yùn)涵式,范式和判定問題,命題演算的推理理論,,,,,,,,,,,,,,,,,,,,,1.5 范式和判定問題,定義1.7 命題公式中的一些變元和一些變元的否定之積，稱為基本積；一些變元和變元的否定之和，稱為基本和。定理1.4 一個基本積是永假式，當(dāng)且僅當(dāng)它含有P，┓P形式的兩個因子。證明：（充分性）P∧┓P是永假式，而Q∧F兩個因子時，此基本是永假式

43、，所以含有P和┓P形式的兩個因子的基本積是永假式。（必要性）用反證法。設(shè)基本積永假但不含P和┓P形式的因子，于是給這個基本積中的命題變元指派真值T，給帶有否定的命題變元指派真值F，得基本積的真值是T，與假設(shè)矛盾。證畢。,45,析取范式,,,,,,,,,,,,,,,,,,,,,,1.5 范式和判定問題,定理1.5 一個基本和是永真式，當(dāng)且僅當(dāng)它含有P，┓P形式的兩個因子。定義1.8 一個由基本積的和組成的公式，如果與給定的公式A

44、等價，則稱它是A的析取范式，記為：A＝A1∨A2∨…∨An ，n≥1，其中Ai(i＝1，2，…，n)是基本積。對于任何命題公式，都可求得與其等價的析取范式，這是因?yàn)槊}公式中出現(xiàn)的→和?可用∧、∨和┓表達(dá)，括號可通過德·摩根定律和∧對∨的分配律消去。但是一個命題公式的析取范式不是唯一的。如果析取范式中每個基本積都是永假式，則該范式必定是永假式。,46,析取范式,,,,,,,,,,,,,,,,,,,,,,1.5 范式和判

45、定問題,例1.16（1）求(P∧(Q→R)) →S的析取范式。解：(P∧(Q→R)) →S ?┓(P∧(┓Q∨R)) ∨S ? (┓P∨(Q∧┓R)) ∨S ? ┓P∨(Q∧┓R) ∨S 析取范式（2）求┓(P∨Q) ? (P∧Q)的析取范式。解：┓(P∨Q) ? (P∧Q)?┓(P∨Q)∧(P∧Q)∨┓(┓(P∨Q))∧┓(P∧Q)? (┓P∧┓Q∧P∧Q)∨((P∨Q)∧(┓P∨

46、┓Q))?F∨(P∨Q)∧(┓P∨┓Q)? (P∨Q)∧(┓P∨┓Q)? ((P∨Q)∧┓P)∨((P∨Q)∧┓Q)?P∧┓P∨┓P∧Q∨P∧┓Q∨Q∧┓Q?F∨┓P∧Q∨P∧┓Q∨F?(┓P∧Q)∨(P∧┓Q)。,47,析取范式,,,,,,,,,,,,,,,,,,,,,,1.5 范式和判定問題,定義1.9 一個由基本和的積組成的公式，如果與給定的命題公式A等價，則稱它是A的合取范式，記為：A＝A1∧A2

47、∧…∧An ，n≥1，其中A1，A2，…，An，是基本和。對任何命題公式都可求得與其等價的合取范式，道理同析取范式。同樣，一個命題公式的合取范式也不唯一。如果一個命題公式的合取范式的每個基本和都是永真式，則該式也必定是永真式。,48,合取范式,,,,,,,,,,,,,,,,,,,,,,1.5 范式和判定問題,例1.17（1）試證Q∨P∧┓Q∨┓P∧┓Q是永真式。解：Q∨P∧┓Q∨┓P∧┓Q?Q∨(P∨┓P)∧┓Q

48、 ?Q∨T∧┓Q ?Q∨┓Q ?T（2）求┓(P∨Q) →(P∧Q)的合取范式。解：令A(yù)?┓(P∨Q) →(P∧Q)，則 ┓A?┓(┓(P∨Q) ∨(P∧Q)) ?┓((┓(P∨Q)∧(P∧Q))∨(┓(┓(P∨Q)∧┓(P∧Q))) ?┓((┓P∧┓Q∧P∧Q)∨((P∨Q)∧(┓P∨┓Q))) ? (┓P∧┓Q)∨(P∧Q)由于A?┓┓A＝┓(┓P∧┓Q∨P∧Q

49、)所以A? (P∨Q)∧(┓P∨┓Q),49,合取范式,,,,,,,,,,,,,,,,,,,,,,1.5 范式和判定問題,定義1.10 在含n個變元的基本積中，若每個變元與其否定不同時存在，而二者之一必出現(xiàn)且僅出現(xiàn)一次，則稱這種基本積為極小項(xiàng)。n個變元可構(gòu)成2n個不同的極小項(xiàng)。例如3個變元P、Q，R可構(gòu)成8個極小項(xiàng)。我們把命題變元看成1，命題變元的否定看成0，于是每個極小項(xiàng)對應(yīng)于一個二進(jìn)制數(shù)，也對應(yīng)一個十進(jìn)制數(shù)。對應(yīng)情況如下。,

50、50,極小項(xiàng),,┓P∧┓Q∧┓R——000——0┓P∧┓Q∧R——001——l┓P∧Q∧┓R——010——2┓P∧Q∧R——011——3P∧┓Q∧┓R——100——4P∧┓Q∧R——101——5P∧Q∧┓R——110——6P∧Q∧R——111——7,┓P∧┓Q∧┓R ＝m0┓P∧┓Q∧R＝m 1┓P∧Q∧┓R＝m 2┓P∧Q∧R＝m 3P∧┓Q∧┓R＝m 4P∧┓Q∧R ＝m 5P

51、∧Q∧┓R＝m 6P∧Q∧R＝m 7,把極小項(xiàng)對應(yīng)的十進(jìn)制數(shù)當(dāng)作足標(biāo)，并用mi(i=0，1，2，…，2n-1)表示這一項(xiàng),一般，n個變元的極小項(xiàng)是：┓P1∧┓P2∧…∧┓Pn＝m0┓P1∧┓P2∧…∧┓Pn-1∧Pn＝m1┓P1∧┓P2∧…∧Pn-1∧┓Pn＝m2…P1∧P2∧…∧Pn＝,,,,,,,,,,,,,,,,,,,,,,,1.5 范式和判定問題,定義1.11 一個由極小項(xiàng)的和組成的公式，如果與命題

52、公式A等價，則稱它是公式A的主析取范式。對任何命題公式(永假式除外)都可求得與其等價的主析取范式，而且主析取范式的形式唯一。它給范式判定問題帶來很大益處。例如：A?P∧Q∨R ?(P∧Q)∧(R∨┓R)∨(P∨┓P)∧R ?P∧Q∧R∨P∧Q∧┓R∨P∧R∨┓P∧R ?P∧Q∧R∨P∧Q∧┓R∨P∧R∧(Q∨┓Q)∨(┓P∧R)∧(Q∨┓Q) ?P∧Q∧R∨P∧Q∧┓R∨P∧Q∧R∨P∧┓Q∧R∨┓P∧Q∧R∨┓P

53、∧┓Q∧R ?P∧Q∧R∨P∧Q∧┓R∨P∧┓Q∧R∨┓P∧Q∧R∨┓P∧┓Q∧R ?m7∨m6∨m5∨m3∨m1 ?∑(1，3，5，6，7)其中，符號“∑”是借用數(shù)學(xué)中求和的符號，這里代表析取。,51,主析取范式,,,,,,,,,,,,,,,,,,,,,,,1.5 范式和判定問題,定義1.12 在含n個變元的基本和中，若每個變元與其否定不同時存在，而二者之一必出現(xiàn)且僅出現(xiàn)一次，則稱這種基本和為極大項(xiàng)。n個變元可以構(gòu)

54、成2n個不同的極大項(xiàng)。例如三個變元P，Q，R可構(gòu)成八個極大項(xiàng)。在極大項(xiàng)中，我們把命題變元看成0,而把命題變元的否定看成1，于是每一個極大項(xiàng)對應(yīng)于一個二進(jìn)制數(shù)，也對應(yīng)一個十進(jìn)制數(shù)。對應(yīng)情況如下,52,極大項(xiàng),,P∨Q∨R--000—0P∨Q∨┓R--001—1P∨┓Q∨R--010—2P∨┓Q∨┓R--011—3┓P∨Q∨R--100—4┓P∨Q∨┓R --101—5┓P∨┓Q∨R--110—6┓P∨┓Q∨┓R

55、 --111—7,P∨Q∨R＝M0P∨Q∨┓R ＝M1P∨┓Q∨R ＝M2P∨┓Q∨┓R ＝M3┓P∨Q∨R＝M4┓P∨Q∨┓R ＝M5┓P∨┓Q∨R ＝M6┓P∨┓Q∨┓R ＝M7,把極大項(xiàng)對應(yīng)的十進(jìn)制數(shù)當(dāng)作足標(biāo)，并用mi(i=0，1，2，…，2n-1)表示這一項(xiàng),一般，n個變元的極大項(xiàng)是：P1 ∨P2 ∨ … ∨Pn＝M0P1 ∨P2 ∨…Pn-1 ∨ ┓ Pn＝ M

56、1P1 ∨P2 ∨ …∨┓Pn-1 ∨Pn＝M2…┓P1 ∨ ┓P2 ∨ … ∨ ┓ Pn＝,,,,,,,,,,,,,,,,,,,,,,,1.5 范式和判定問題,定義1.13 一個由極大項(xiàng)的積組成的公式，如果與命題公式A等價，則稱它是A的主合取范式。對任何命題公式(永真式除外)都可求得與其等價的主合取范式，且主合取范式的形式唯一。例如：A ＝P∧Q∨R ＝(P∨R)∧(Q∨R) ＝(P∨R)∨(Q∧┓Q)∧

57、(Q∨R)∨(P∧┓P) ＝(P∨Q∨R)∧(P∨┓Q∨R)∧(P∨Q∨R)∧(┓P∨Q∨R) ＝(P∨Q∨R)∧(P∨┓Q∨R)∧(┓P∨Q∨R) ＝M0∧M2∧M4 ＝∏(0，2，4)．其中，符號“∏”是借用數(shù)學(xué)中求積的符號，這里代表合取。從A的主合取范式，我們立刻可以判斷出A是可滿足的。,53,主合取范式,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,命題和聯(lián)結(jié)詞,,主要內(nèi)容,合式公式與真

58、值表,永真式和等價式,對偶式與蘊(yùn)涵式,范式和判定問題,命題演算的推理理論,,,,,,,,,,,,,,,,,,,,,1.6 命題演算的推理理論,邏輯學(xué)的主要任務(wù)是提供一套推論規(guī)則，按照公認(rèn)的推論規(guī)則，從前提集合中推導(dǎo)出一個結(jié)論來，這樣的推導(dǎo)過程稱為演繹或形式證明。在任何論證中，倘若認(rèn)定前提是真的，從前提推導(dǎo)出結(jié)論的論證是遵守了邏輯推論規(guī)則，則認(rèn)為此結(jié)論是真的，并且認(rèn)為這個論證過程是合法的。也就是說，對于任何論證來說，人們所注意的是論證

59、的合法性。數(shù)理邏輯則把注意力集中于推論規(guī)則的研究，依據(jù)這些推論規(guī)則推導(dǎo)出的任何結(jié)論，稱為有效結(jié)論，而這種論證規(guī)則被稱為有效論證。數(shù)理邏輯所關(guān)心的是論證的有效性而不是合法性，也就是說數(shù)理邏輯所注重的是推論過程中推論規(guī)則使用的有效，而并不關(guān)心前提的實(shí)際真值。推論理論對計(jì)算機(jī)科學(xué)中的程序驗(yàn)證、定理的機(jī)械證明和人工智能都十分重要。,55,,,,,,,,,,,,,,,,,,,,,,,1.6 命題演算的推理理論,定義1.14 設(shè)H1 ，H2

60、,…, Hm +, C是一些命題公式。當(dāng)且僅當(dāng)H1∧H2∧…∧Hm ? C，則說C是前提集合{H1，H2，…，Hm}的有效結(jié)論。顯然，給定一個前提集合和一個結(jié)論，用構(gòu)成真值表的方法，在有限步內(nèi)能夠確定該結(jié)論是否是該前提集合的有效結(jié)論。這種方法被稱為真值表技術(shù)。,56,,,,,,,,,,,,,,,,,,,,,,,1.6 命題演算的推理理論,規(guī)則P：引入一個前提稱為使用一次P規(guī)則。規(guī)則T：在推導(dǎo)中，如果前面有一個或多個公式永真蘊(yùn)涵

61、公式S，則可以把公式S引進(jìn)推導(dǎo)過程中。換句話說，引進(jìn)前面推導(dǎo)過程中的推論結(jié)果稱為使用T規(guī)則。 規(guī)則CP：如果能從R和前提集合中推導(dǎo)出S來，則就能夠從前提集合中推導(dǎo)出R→S。實(shí)際上恒等式E28就可以推出規(guī)則CP。(P∧Q→R)? ﹁(P∧Q) ∨R ? ﹁P∨﹁Q∨R ? ﹁P∨(﹁Q∨R) ? ﹁P∨(Q→R) ? P→(Q→R)設(shè)P表示前提的合取，Q是

62、任意公式，則上述恒等式可表述成：在前提集合中若包含有附加前提Q，并且從P∧Q中可以推導(dǎo)出R來，則可從前提P中推導(dǎo)出Q→R來。,57,,,,,,,,,,,,,,,,,,,,,,,1.6 命題演算的推理理論,例1.19 試證明﹁P是﹁(P∧﹁Q)，﹁Q∨R，﹁R的有效結(jié)論。解：{1} (1) ﹁(P∧﹁Q) P規(guī)則{1} (2) ﹁P∨Q T 規(guī)則 (1)和E11{1}

63、(3) P→Q T規(guī)則(2)和E27{4} (4) ﹁Q∨R P規(guī)則{4} (5) Q→R T規(guī)則 (4)和E27{1,4 } (6) P→R T, (3) , (5)和I12{7} (7) ﹁R P規(guī)則{1,4,7} (8) ﹁P T規(guī)則(6)

64、,(7)和I11…,58,,,,,,,,,,,,,,,,,,,,,,,1.6 命題演算的推理理論,例1.20 證明R→S是前提P→(Q→S)，Q和﹁R∨P的有效結(jié)論。解：把R作為附加前提，首先推導(dǎo)出S來，再由此推導(dǎo)出R→S來。{1} (1) R P規(guī)則（附加前提）{2} (2) ﹁R∨P P規(guī)則{1,2} (3) P

65、 T規(guī)則 (1) , (2) ,和I9{4} (4) P→(Q→S)P規(guī)則{1,2,4} (5) Q→S T規(guī)則(3) , (4)和I10{6} (6) Q P規(guī)則{1,2,4,6} (7) S T規(guī)則，(5), (6)和I10{1,2,4,6} (8) R→S

66、 CP規(guī)則 (1) , (7)…,59,,,,,,,,,,,,,,,,,,,,,,,1.6 命題演算的推理理論,規(guī)則F，也稱間接證明法(或反證法)。為了說明規(guī)則F，我們給出下面的定義和定理。 定義1.15 設(shè)公式H1 ，H2，…，Hm中的原子變元是P1，P2，…，Pn。如果給各原子變元P1，P2，…，Pn指派某一個真值集合，能使H1∧H2∧…∧Hm具有真值T，則命題公式集合{ H1 ，H2 ，…，Hm

67、 } 稱為一致的(或相容的)；對于各原子變元的每一個真值指派，如果命題公式H1 ，H2 ，…，Hm中至少有一個是假，從而使得H1∧H2∧…∧Hm是假，則稱命題公式集合{H1 ，H2 ，…，Hm }是不一致的(或不相容的)。設(shè){H1 ，H2 ，…，Hm }是一個命題公式集合，如果它們的合取蘊(yùn)涵著一個永假式，也就是說H1∧H2∧…∧Hm ? R∧﹁R這里R是任何一個公式，則公式集合{ H1 ，H2 ，…，Hm }必然是非一致的。因?yàn)?/p>

68、R∧﹁R是一個永假式，所以它充分而又必要地決定了H1∧H2∧…∧Hm是一個永假式。,60,,,,,,,,,,,,,,,,,,,,,,,1.6 命題演算的推理理論,定理1.6 設(shè)命題公式集合{ H1 ，H2 ，…，Hm，﹁C}是非一致的，亦即它蘊(yùn)涵著一個永假式，則可以從前提集合{ H1 ，H2 ,…, Hm}中推導(dǎo)出命題公式C來。證明：因?yàn)镠1∧H2∧…∧Hm∧﹁C ? R∧﹁R，所以H1∧H2∧…∧﹁C必定是永假式。因?yàn)榍疤峒?/p>