第一章 命題邏輯.doc

第一章 命題邏輯 邏輯學(xué)是研究推理過(guò)程規(guī)律一門(mén)科學(xué)。數(shù)理邏輯則是用數(shù)學(xué)的方法研究思維規(guī)律的一門(mén)學(xué)科。由于它使用了一套符號(hào)，簡(jiǎn)潔地表達(dá)出各種推理的邏輯關(guān)系，因此數(shù)理邏輯又稱為符號(hào)邏輯或理論邏輯。數(shù)理邏輯和計(jì)算機(jī)的發(fā)展有著密切的聯(lián)系，它為機(jī)器證明、自動(dòng)程序設(shè)計(jì)、計(jì)算機(jī)輔助設(shè)計(jì)等計(jì)算機(jī)應(yīng)用和理論研究提供必要的理論基礎(chǔ)。數(shù)理邏輯的主要分支包括公理化集合論、證明論、遞歸函數(shù)論、模型論等。從本章開(kāi)始，我們用三章的篇幅介紹數(shù)理邏輯的基本內(nèi)容：命題邏輯、謂詞邏輯和非經(jīng)典邏輯簡(jiǎn)介。命題邏輯研究的是以原子命題為基本單位的推理演算，其特征在于，研究和考查邏輯形式時(shí)，我們把一個(gè)命題只分析到其中所含的原子命題成分為止。通過(guò)這樣的分析可以顯示出一些重要的邏輯形式，這種形式和有關(guān)的邏輯規(guī)律就是命題邏輯。1.1 命題與聯(lián)結(jié)詞1.1.1 命題與命題變?cè)Z(yǔ)言的單位是句子。句子可以分為疑問(wèn)句、祈使句、感嘆句與陳述句等，其中只有陳述句能分辨真假，其他類型的句子無(wú)所謂真假。定義1.1 能夠分辨真假的陳述句叫做命題（Proposition）。從這個(gè)定義可以看出命題有兩層含義：(1)命題是陳述句。其他的語(yǔ)句，如疑問(wèn)句、祈使句、感嘆句均不是命題；(2)這個(gè)陳述句表示的內(nèi)容可以分辨真假，而且不是真就是假，不能不真也不假，也不能既真又假。作為命題的陳述句所表示的判斷結(jié)果稱為命題的真值，真值只取兩個(gè)值：真或假。凡是與事實(shí)相符的陳述句是真命題，而與事實(shí)不符合的陳述句是假命題。通常用1（或大寫(xiě)字母T）表示真，用0（或大寫(xiě)字母F）表示假。例1.1 判斷下列語(yǔ)句是否為命題，并指出其真值。(1) 北京是中國(guó)的首都。（2）5可以被2整除。（3）2+2=5。（4）請(qǐng)勿吸煙。（5）烏鴉是黑色的嗎？（6）這個(gè)小男孩多勇敢?。。?）地球外的星球上存在生物。（8）我正在說(shuō)謊。 解 （1）（3）是命題，其中（1）是真命題，（2），（3）是假命題。值得注意的是，像2+2=5這樣的數(shù)學(xué)公式也是一個(gè)命題，事實(shí)上，一個(gè)完整的數(shù)學(xué)公式與一個(gè)完整的陳述句并沒(méi)有什么本質(zhì)的差異。（4）是祈使句，（5）是疑問(wèn)句，（6）是感嘆句，因而這3個(gè)句子都不是命題。（7）是命題，雖然目前我們無(wú)法確定其真值，但它們的真值客觀存在，而且是惟一的，隨著科技的發(fā)展，不久的將來(lái)就會(huì)知道其真值。因此一個(gè)語(yǔ)句本身是否能分辨真假與我們是否知道它的真假是兩回事。也就是說(shuō)，對(duì)于一個(gè)句子，有時(shí)我們可能無(wú)法判定它的真假，但它本身卻是有真假的，那么這個(gè)語(yǔ)句是命題，否則就不是命題。（8）不是命題，若（8）的真值為真，即“我正在說(shuō)謊”為真，則（8）的真值應(yīng)為假；反之，若（8）的真值為假，即“我正在說(shuō)謊”為假，也就是“我正在說(shuō)真話”為真，則又推出（8）的真值應(yīng)為真；可見(jiàn)（8）的真值無(wú)法確定，它顯然不是命題，像（8）這樣由真推出假，又由假推出真的語(yǔ)句叫悖論，因此凡是悖論都不是命題。涉及命題的邏輯領(lǐng)域稱為命題邏輯(Propositional Logic)或命題演算(Propositional Calculus)。它最初是2300年前由古希臘哲學(xué)家亞里士多德（Aristotle）系統(tǒng)地創(chuàng)建的。亞里士多德曾師從柏拉圖，但他的哲學(xué)思想與柏拉圖有很大的不同。與柏拉圖相比，其更注重實(shí)際，研究問(wèn)題更注重提出疑難，注重多方面收集材料、嘗試和探索。他的著作可分為兩大類，一是他生前公開(kāi)發(fā)表供一般人閱讀的，用的是對(duì)話體，這類著作大部分已經(jīng)散失，只有一些片段流傳到今天。另一類作品樸素?zé)o華，推論嚴(yán)謹(jǐn)，大概是亞里士多德的講授提綱、研究札記或?qū)W生的聽(tīng)講筆記，此類保存下了一部分。命題可以分為兩類，一類是原子命題，一類是復(fù)合命題。所謂原子命題（Atomic Proposition），是指不能再分解為更簡(jiǎn)單命題的命題；所謂復(fù)合命題（Compound Proposition）是指由若干命題用聯(lián)結(jié)詞組成的新命題。例如“雪是白的”是原子命題；“昨天下雨，而且打雷”，“如果明天天晴我就去打球或者游泳”都是復(fù)合命題。為了對(duì)命題進(jìn)行邏輯演算，需要將論述或推理中的各種要素都符號(hào)化，即構(gòu)造各種符號(hào)語(yǔ)言來(lái)代替自然語(yǔ)言，我們稱完全由符號(hào)所構(gòu)成的語(yǔ)言為形式語(yǔ)言（Formal Language），并約定用大寫(xiě)字母P，Q，R，S，T等表示命題，也可以帶下標(biāo)。例如，用P表示“北京是中國(guó)的首都”，Q表示“5可以被2整除”等。當(dāng)P表示任一命題時(shí)，P就稱為命題變?cè)?，有如下的定義。定義1.2 真值確定的原子命題稱為命題常元（Propositional Constant），真值不確定的原子命題稱為命題變?cè)≒ropositional Variable）。如果命題符號(hào)P代表命題常元?jiǎng)t意味它是某個(gè)具體命題的符號(hào)化，如果P代表命題變?cè)獎(jiǎng)t意味著它可指代任何具體命題。本書(shū)中如果沒(méi)有特別指明，通常來(lái)說(shuō)命題符號(hào)P等是命題變?cè)?，即可指代任何命題。1.1.2 命題聯(lián)結(jié)詞及真值表在數(shù)理邏輯中，最重要最常用的命題聯(lián)結(jié)詞（Propositions Conjunction）有五個(gè)，下面分別予以介紹。表1.1 否定詞的真值表否定詞（Negation）是一元聯(lián)結(jié)詞。設(shè)P表示一個(gè)命題，那么P表示命題P的否定。P讀作“非P”。若P為真時(shí)，則P為假；若P為假時(shí)，則P為真。P與P間的真值關(guān)系，用表1.1來(lái)表示，這個(gè)表稱為真值表。日常用語(yǔ)中的“非”，“不”，“無(wú)”，“沒(méi)有”等均可用否定詞表示。但要注意，否定詞是否定命題的全部，而不是部分。例如，設(shè)P表示命題“雪是白的”，則“并非雪是白的”、“雪不是白的”應(yīng)表示為P，此時(shí)P為假，因?yàn)镻為真。2. 合取詞“”表1.2 合取詞的真值表P QPQ0 00 11 01 10001合取詞（Conjunction）是二元聯(lián)結(jié)詞。設(shè)P，Q表示兩命題，那么PQ表示合取P和Q所得的命題，即P和Q同時(shí)為真時(shí)PQ為真，否則PQ為假。PQ讀作“P合取Q”或“P并且Q”。合取詞的意義和命題PQ的真值狀況由表1.2給出。日常用語(yǔ)中的“與”，“和”，“也”,“并且”，“而且”，“既，又”，“一面，一面”等可用合取詞表示。例如，設(shè)P表示命題“你去了學(xué)?！?，Q表示命題“我去了工廠”，則PQ表示命題“你去了學(xué)校并且我去了工廠”。PQ為真，當(dāng)且僅當(dāng)你、我分別去了學(xué)校和工廠。 需要注意的是，并非命題中所有出現(xiàn)的“與”或“和”就一定使用合取詞，而是要看它在命題中的含義。例如，“張三和李四是同學(xué)”就不是一個(gè)復(fù)合命題，雖然命題中也使用了聯(lián)結(jié)詞“和”，但這個(gè)聯(lián)結(jié)詞“和”是聯(lián)結(jié)該句主語(yǔ)的，而整個(gè)句子仍是簡(jiǎn)單命題，因此只能用一個(gè)命題變?cè)狿表示。3.析取詞“”表1.3 析取詞的真值表P QPQ0 00 11 01 10111析取詞（Disjunction）是二元聯(lián)結(jié)詞。設(shè)P，Q表示兩命題，那么PQ表示P和Q的析取，即當(dāng)P和Q有一個(gè)為真時(shí)，PQ為真，只有當(dāng)P和Q均為假時(shí)PQ為假。PQ讀作“P析取Q”或“P或者Q”。析取詞的意義及復(fù)合命題PQ的真值狀況由表1.3給出。日常用語(yǔ)中的“或”，“要么要么”等可用析取詞表示。例如，設(shè)P，Q分別表示“今晚我看書(shū)”和“今晚我去看電影”，則PQ表示“今晚我看書(shū)或者去看電影”。當(dāng)我于當(dāng)晚看了書(shū)，或者看了電影，或者既看了書(shū)又看了電影時(shí)，PQ為真，只是在我既沒(méi)看書(shū)也沒(méi)看電影時(shí)PQ為假。需要注意的是，析取詞“”與日常語(yǔ)言中的“或”并不完全相同。后者既可表示“排斥或”，又可表示“可兼或”，而數(shù)理邏輯中的析取詞“”僅指“可兼或”。例如，“選修過(guò)微積分或計(jì)算機(jī)科學(xué)的學(xué)生可以選修本課。”這句話中的“或”表達(dá)的即是“可兼或”。若餐館的菜單上寫(xiě)著“米飯或面條，加一道小菜。”一般這都表示顧客可以選擇米飯，也可以選擇面條，但不是既選米飯又選面條時(shí)，才加一道小菜。因此，這里“或”是“排斥或”而不是“可兼或”。4.蘊(yùn)含詞“-”表1.4 蘊(yùn)含詞的真值表P QP-Q0 00 11 01 11101蘊(yùn)含詞（Implication）是二元聯(lián)結(jié)詞。設(shè)P，Q表示兩命題，那么PQ表示命題“如果P，那么Q”。當(dāng)P真而Q假時(shí)，命題PQ為假，否則均認(rèn)為P-Q為真。P-Q中的P稱為蘊(yùn)含前件，Q稱為蘊(yùn)含后件。P-Q的讀法較多，可讀作“P蘊(yùn)含Q”，“若P則Q”， “如果P，那么Q”，“P是Q的充分條件”，“Q是P的必要條件”等等。數(shù)學(xué)中還常把Q-P，P-Q，Q-P分別叫做P-Q的逆命題，否命題，逆否命題。蘊(yùn)含詞的意義及復(fù)合命題P-Q的真值狀況由表1.4給出。日常用語(yǔ)中的“若則”，“如果那么”，“只有才”等可用蘊(yùn)含詞表示。例如，設(shè)P表示“我有車(chē)”，Q表示“我去接你”，則P-Q表示命題“如果我有車(chē)，那么我去接你”。當(dāng)我有車(chē)時(shí)，若我去接了你，這時(shí)P-Q為真；若我沒(méi)去接你，則P-Q為假。當(dāng)我沒(méi)有車(chē)時(shí)，我無(wú)論去或不去接你均未食言，此時(shí)認(rèn)定P-Q為真是適當(dāng)?shù)?。需要注意的是，P-Q中的P，Q可以沒(méi)有任何關(guān)系，只要P，Q為命題，P-Q就有意義。例如“如果2+2=5，那么雪是黑的”，就是一個(gè)有意義的命題，且據(jù)定義其值為“真”。蘊(yùn)含詞的這種規(guī)定形式，在討論數(shù)學(xué)問(wèn)題和邏輯問(wèn)題時(shí)是正確的、充分的、方便的，這在日常用語(yǔ)中不大使用。5. 等價(jià)詞“”表1.5 等價(jià)詞的真值表P QPQ0 00 11 01 11001等價(jià)詞（Equivalence）或稱雙向蘊(yùn)含詞是二元聯(lián)結(jié)詞。設(shè)P，Q為兩命題，那么PQ表示命題“P與Q等價(jià)”,“P當(dāng)且僅當(dāng)Q”，即當(dāng)P與Q同真值時(shí)PQ為真，否則為假。PQ讀作“P等價(jià)于Q”，“P當(dāng)且僅當(dāng)Q”，“P雙向蘊(yùn)含Q”。等價(jià)詞的意義及PQ的真值狀況由表1.5給出。日常用語(yǔ)中的“等價(jià)”，“當(dāng)且僅當(dāng)”，“充要條件” 等可用等價(jià)詞表示。例如，設(shè)P表示命題“ABC是直角三角形”，Q表示命題“ABC有一個(gè)角是直角”，則PQ表示“ABC是直角三角形當(dāng)且僅當(dāng)ABC有一個(gè)角是直角”。為使下一節(jié)講到的命題公式的形式更為清晰、簡(jiǎn)潔，我們給聯(lián)結(jié)詞規(guī)定優(yōu)先級(jí)順序：的優(yōu)先級(jí)最高，接著依次是，-和，的優(yōu)先級(jí)最低。1.2 命題公式1.2.1 命題公式與命題符號(hào)化定義1.3 命題公式（Propositional Formula）歸納定義如下：（1）命題變?cè)敲}公式；（2）如果a是命題公式，則a也是命題公式；（3）如果a和b是命題公式，則ab，ab，ab，ab均是命題公式；（4）只有有限次地利用（1）（3）形成的符號(hào)串才是命題公式。 按照上述定義可知，(PQ)，P(PQ)等都是命題公式，而CPQ，RP等不是命題公式。由定義可看出，命題公式歸根結(jié)底是由命題變?cè)兔}聯(lián)結(jié)詞組成的公式，其基本元素是命題變?cè)吐?lián)結(jié)詞。 顯然，如果把公式中的命題變?cè)栽用}或復(fù)合命題，則該公式便是一個(gè)復(fù)合命題。因此，對(duì)復(fù)合命題的研究可化為對(duì)公式的研究，今后我們將以公式為主要研究對(duì)象。 命題公式不是命題，只有當(dāng)公式中的每一個(gè)命題變?cè)急毁x以確定的真值時(shí)，公式的真值才被確定，從而成為一個(gè)命題。 命題邏輯里討論的對(duì)象是命題公式，而日常生活中的推理問(wèn)題是用自然語(yǔ)言描述的，因此要進(jìn)行推理演算必須先把自然語(yǔ)言符號(hào)化（或形式化）成邏輯語(yǔ)言，即命題公式。然后再根據(jù)邏輯演算規(guī)律進(jìn)行推理演算。例1.2 將下列用自然語(yǔ)言描述的命題符號(hào)化。推理演示（1）我和他既是弟兄又是同學(xué)。 解 令P：我和他是弟兄；Q：我和他是同學(xué)，則該語(yǔ)句可符號(hào)化為PQ。（2）我和你之間至少有一個(gè)要去海南島。解 令P：我去海南島；Q：你去海南島，則該語(yǔ)句可符號(hào)化為PQ。 （3）如果他沒(méi)來(lái)見(jiàn)你，那么他或者是生病了，或者是不在本地。 解 令P：他來(lái)見(jiàn)你；Q：他生??；R：他在本地，則該語(yǔ)句可符號(hào)化為（4）n是偶數(shù)當(dāng)且僅當(dāng)它能被2整除。解 令P：n是偶數(shù)；Q：n能被2整除，則該語(yǔ)句可符號(hào)化為P-Q。從以上例子中可以看出，所謂命題符號(hào)化是指把一個(gè)用自然語(yǔ)言敘述的命題相應(yīng)地寫(xiě)成由命題變?cè)⒙?lián)結(jié)詞和圓括號(hào)表示的命題公式。符號(hào)化應(yīng)該注意下列事項(xiàng)： 確定給定句子是否為命題。 句子中連詞是否為命題聯(lián)結(jié)詞。 要正確地表示原子命題和適當(dāng)選擇命題聯(lián)結(jié)詞。1.2 命題公式1.2.1 命題公式與命題符號(hào)化定義1.3 命題公式（Propositional Formula）歸納定義如下：（1）命題變?cè)敲}公式；（2）如果a是命題公式，則a也是命題公式；（3）如果a和b是命題公式，則ab，ab，ab，ab均是命題公式；（4）只有有限次地利用（1）（3）形成的符號(hào)串才是命題公式。 按照上述定義可知，(PQ)，P(PQ)等都是命題公式，而CPQ，RP等不是命題公式。由定義可看出，命題公式歸根結(jié)底是由命題變?cè)兔}聯(lián)結(jié)詞組成的公式，其基本元素是命題變?cè)吐?lián)結(jié)詞。 顯然，如果把公式中的命題變?cè)栽用}或復(fù)合命題，則該公式便是一個(gè)復(fù)合命題。因此，對(duì)復(fù)合命題的研究可化為對(duì)公式的研究，今后我們將以公式為主要研究對(duì)象。 命題公式不是命題，只有當(dāng)公式中的每一個(gè)命題變?cè)急毁x以確定的真值時(shí)，公式的真值才被確定，從而成為一個(gè)命題。 命題邏輯里討論的對(duì)象是命題公式，而日常生活中的推理問(wèn)題是用自然語(yǔ)言描述的，因此要進(jìn)行推理演算必須先把自然語(yǔ)言符號(hào)化（或形式化）成邏輯語(yǔ)言，即命題公式。然后再根據(jù)邏輯演算規(guī)律進(jìn)行推理演算。例1.2 將下列用自然語(yǔ)言描述的命題符號(hào)化。推理演示（1）我和他既是弟兄又是同學(xué)。 解 令P：我和他是弟兄；Q：我和他是同學(xué)，則該語(yǔ)句可符號(hào)化為PQ。（2）我和你之間至少有一個(gè)要去海南島。解 令P：我去海南島；Q：你去海南島，則該語(yǔ)句可符號(hào)化為PQ。 （3）如果他沒(méi)來(lái)見(jiàn)你，那么他或者是生病了，或者是不在本地。 解 令P：他來(lái)見(jiàn)你；Q：他生??；R：他在本地，則該語(yǔ)句可符號(hào)化為（4）n是偶數(shù)當(dāng)且僅當(dāng)它能被2整除。解 令P：n是偶數(shù)；Q：n能被2整除，則該語(yǔ)句可符號(hào)化為P-Q。從以上例子中可以看出，所謂命題符號(hào)化是指把一個(gè)用自然語(yǔ)言敘述的命題相應(yīng)地寫(xiě)成由命題變?cè)⒙?lián)結(jié)詞和圓括號(hào)表示的命題公式。符號(hào)化應(yīng)該注意下列事項(xiàng)： 確定給定句子是否為命題。 句子中連詞是否為命題聯(lián)結(jié)詞。 要正確地表示原子命題和適當(dāng)選擇命題聯(lián)結(jié)詞。1.2.2 命題公式的分類設(shè)n元公式a中所含有的不同命題元為P1,P2,Pn，我們把這些命題元組成的變?cè)M(P1,P2,Pn)稱為a的變?cè)M，a的變?cè)M(P1,P2,Pn)的任意一組確定的值都稱為該公式a關(guān)于該變?cè)M(P1,P2,Pn)的完全指派。如果僅對(duì)變?cè)M中部分變?cè)x以確定的值，其余變?cè)獩](méi)有賦以確定的值，則這樣的一組值稱為該公式a關(guān)于該變?cè)M(P1,P2,Pn)的部分指派。例1.3 設(shè)a=(P(QR)S，其變?cè)M為(P,Q,R,S)。(P,Q,R,S)=(1,0,1,1)為a的完全指派，(P,Q,R,S)=(0,0,1,S)為a的部分指派.定義1.4 對(duì)于任一公式a，凡使得a為真的指派，不管是完全指派還是部分指派，都稱為a的成真指派，凡使得a為假的指派，也不管是完全指派還是部分指派，都稱為a的成假指派。例1.4 設(shè)，則完全指派(P,Q,R,S)=(0,1,0,1)和部分指派(P,Q,R,S)=(0,1,0,S)都是a的成真指派，而指派(P,Q,R,S)=(1,0,1,0)為a的成假指派。定義1.5 對(duì)于命題公式中命題變?cè)拿恳环N可能的完全指派，以及由它們確定出的公式真值所列成的表，稱為該命題公式的真值表（Truth Table）。定義1.6 設(shè)a為命題公式，b為a中的一個(gè)連續(xù)的符號(hào)串，且b為命題公式，則稱b為a的子公式（Sub Formula）。例如，設(shè)公式等都是a的子公式，而等都不是a的子公式，因?yàn)樗鼈儽旧聿皇枪健Ｓ脷w納法不難證明，對(duì)于含有n個(gè)命題變?cè)墓剑?n個(gè)完全指派，即在該公式的真值表中有2n行。為方便構(gòu)造真值表，特約定如下： 命題變?cè)醋值湫蚺帕小?對(duì)每個(gè)指派，以二進(jìn)制數(shù)從小到大或從大到小順序列出。 若公式較復(fù)雜，可先列出各子公式的真值(若有括號(hào)，則應(yīng)從里層向外層展開(kāi))，最后列出所求公式的真值。例1.5 利用真值表求命題公式(P(QR)的成真指派和成假指派。推理演示解 命題公式(P(QR)的真值表如表1.6所示。表1.6 命題公式(P(QR)的真值表P Q RQRP(QR)(P(QR)0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1011101111111011100001000從表1.6可看出，指派(1,0,0)為成真指派，而指派(0