1.1 命題邏輯

原文：Foundations of Computation

譯者：飛龍

協(xié)議：CC BY-NC-SA 4.0

自豪地采用谷歌翻譯

一個(gè)命題是一個(gè)或真或假的陳述。 在命題邏輯中，我們將命題看做基礎(chǔ)，看看我們能做什么。 既然這是數(shù)學(xué)，我們需要能夠談?wù)撁}，而不是說我們?cè)谡f什么特定的命題，所以我們用符號(hào)來(lái)代表它們。 我們始終使用小寫字母，如p，q和r來(lái)表示命題。 以這種方式使用的字母稱為命題變量。 記住，當(dāng)我說“假設(shè)p是一個(gè)命題”的時(shí)候，我的意思是“對(duì)于討論其余部分，讓符號(hào)p代表一些特定的陳述，它是真的或假的（雖然我現(xiàn)在沒有做出 關(guān)于它的任何假設(shè)）。討論具有數(shù)學(xué)一般性，因?yàn)?code>p可以代表任何陳述，并且無(wú)論它代表什么語(yǔ)句，討論都是有效的。

我們用命題做的事情是，將它們與邏輯運(yùn)算符組合起來(lái)。 邏輯運(yùn)算符可以應(yīng)用于一個(gè)或多個(gè)命題，來(lái)產(chǎn)生新的命題。 新命題的真值完全由運(yùn)算符和所應(yīng)用命題的真值確定 [1]。在中文中，邏輯運(yùn)算符用“和”，“或”和“非”表示，例如，“我想離開并且我離開了”，這個(gè)命題由兩個(gè)簡(jiǎn)單的命題通過“和”組合而成。在“我離開了”這個(gè)命題中加上“非”一詞表示“我沒有離開” （經(jīng)過一點(diǎn)必要的語(yǔ)法調(diào)整）。

[1] 句子的真值可以根據(jù)其組成部分的真值確定，并不總是真的。 例如，如果p是一個(gè)命題，那么“莎拉·佩林認(rèn)為p”也是一個(gè)命題，所以“莎拉·佩林認(rèn)為”是某種運(yùn)算符。 然而，它不算作邏輯運(yùn)算符，因?yàn)橹?code>p是否為真，我們根本就不知道“莎拉·佩林認(rèn)為p”是否為真。

但自然語(yǔ)言對(duì)于數(shù)理邏輯來(lái)說有點(diǎn)太豐富了。 當(dāng)你讀“我想離開并且我離開了”這個(gè)句子時(shí)，你可能會(huì)看到一個(gè)因果關(guān)系的內(nèi)涵：我離開了，因?yàn)槲蚁腚x開。 這個(gè)含義并不符合“我想離開”和“我離開了”這兩個(gè)命題的真值的邏輯組合?；蛘呖紤]“我想離開但我沒有離開”這個(gè)命題的邏輯組合，在這里， “但”具有與“和”一詞相同的邏輯含義，但內(nèi)涵卻非常不符。 因此，在數(shù)理邏輯中，我們使用符號(hào)來(lái)表示邏輯運(yùn)算符。 這些符號(hào)不具有超出其定義的邏輯意義的任何內(nèi)涵。 對(duì)應(yīng)于中文詞語(yǔ)“和”，“或”和“非”的邏輯運(yùn)算符是∧，∨和?。

定義 1.1：假設(shè)p和q都是命題，那么p∧q、p∨q和?p也都是命題，它們的真值由以下規(guī)則確定：

• 當(dāng)p和q都是真時(shí)，p∧q是真，否則是假。
• 當(dāng)p和q至少一個(gè)是真時(shí)，p∨q是真，否則是假。
• 當(dāng)p時(shí)假時(shí)?p是真，反之亦然。

運(yùn)算符∧，∨和?分別被稱為合取，析取和否定。 （請(qǐng)注意，p∧q讀為“p和q”，p∨q讀為“p或q”，?p讀為“非p”）。

這些運(yùn)算符可以用于更復(fù)雜的表達(dá)式，如p∧(?q)或(p∨q)∧(q∨r)。 由簡(jiǎn)單的命題和邏輯運(yùn)算符組成的命題被稱為復(fù)合命題。 可以在復(fù)合表達(dá)式中使用括號(hào)來(lái)表示運(yùn)算符的求值順序。 在沒有括號(hào)的情況下，求值順序由優(yōu)先規(guī)則確定。 對(duì)于上面定義的邏輯運(yùn)算符，規(guī)則是?具有較高優(yōu)先級(jí)，∧次之并優(yōu)先于∨（就像乘法優(yōu)先于加法）。 這意味著在沒有括號(hào)的情況下，首先對(duì)任何?運(yùn)算符進(jìn)行求值，其次是任何∧運(yùn)算符，最后是任何∨運(yùn)算符。

例如，表達(dá)式?p∨q∧r等價(jià)于表達(dá)式(?p)∨(q∧r)，而p∨q∧q∨r等效于p∨(q∧q)∨r。 實(shí)際上，當(dāng)你構(gòu)造自己的表達(dá)式時(shí)，通常最好放在括號(hào)中，使你的意思清楚。 記住，即使你省略括號(hào)，你的表達(dá)也有明確的含義。 如果你的意思是?(p∧q)，那么你說成?p∧q就錯(cuò)了！

這仍然沒有說明表達(dá)式∧q∧r中哪個(gè)∧運(yùn)算符首先求值的問題。 這通過以下規(guī)則來(lái)解決：當(dāng)沒有括號(hào)的情況下，出現(xiàn)幾個(gè)相等優(yōu)先級(jí)的運(yùn)算符時(shí)，它們從左到右求值。 因此，表達(dá)式p∧q∧r等于(p∧q)∧r而不是p∧(q∧r)。 在這種特殊情況下，事實(shí)上，首先求解哪個(gè)運(yùn)算符是不重要的，因?yàn)閮蓚€(gè)復(fù)合命題(p∧q)∧r和p∧(q∧r)總是具有相同的值， 不管命題p，q和r有什么邏輯值。 我們說∧是一個(gè)結(jié)合性運(yùn)算。 我們將在下一節(jié)中詳細(xì)介紹運(yùn)算的結(jié)合性和其他屬性。

假設(shè)我們要驗(yàn)證，(p∧q)∧r和p∧(q∧r)實(shí)際上總是具有相同的值。 為此，我們必須考慮p，q和r的值的所有可能的組合，并檢查對(duì)于所有這些組合，兩個(gè)復(fù)合表達(dá)式確實(shí)具有相同的值。 將此計(jì)算組織成一個(gè)真值表是很方便的。 真值表是一個(gè)表，其中顯示了所包含的命題變量值的每個(gè)可能組合的，一個(gè)或多個(gè)復(fù)合命題的值。 圖1.1是一個(gè)真值表，將p∧(q∧r)的值與p，q和r的所有可能值進(jìn)行比較。 表中有八行，因?yàn)榉峙浣op，q和r的真值正好有八種不同的組合方式 [2]。在這個(gè)表中，我們看到最后兩列，表示(p∧q)∧r和p∧(q∧r)相同。

[2] 一般來(lái)說，如果有n個(gè)變量，那么有2^n個(gè)不同的方法來(lái)為變量賦值真值。 如果你嘗試提出一個(gè)方案，系統(tǒng)地列出所有可能的值集合，這可能會(huì)變得清楚。 如果沒有，你將在本章后面找到嚴(yán)格的事實(shí)證明。

p     q     r     p∧q   q∧r   (p∧q)∧r p∧(q∧r) 
false false false false false false   false 
false false true  false false false   false 
false true  false false false false   false 
false true  true  false true  false   false 
true  false false false false false   false 
true  false true  false false false   false 
true  true  false true  false false   false 
true  true  true  true  true  true    true

圖1.1：一個(gè)真值表，證明了(p∧q)∧r和p∧(q∧r)的邏輯等價(jià)性。 該表的最后兩列相同的事實(shí)表明，這兩個(gè)表達(dá)式對(duì)于p，q和r的值的所有八種可能的組合具有相同的值。

更一般地說，我們說如果它們總是具有相同的值，則兩個(gè)復(fù)合命題在邏輯上是等價(jià)的，無(wú)論它們包含的命題變量是什么真值。 如果命題變量的數(shù)量很少，則很容易使用真值表，來(lái)檢查兩個(gè)命題是否在邏輯上等價(jià)。

除了∧，∨和?之外，還有其他的邏輯運(yùn)算符。 我們將考慮條件運(yùn)算符→，雙向運(yùn)算符?，和異或運(yùn)算符⊕ [3]，這些運(yùn)算符可以由真值表完全定義，它顯示了p和q的真值的四種可能組合的值。

[3] 請(qǐng)注意，本書中為邏輯運(yùn)算符使用的符號(hào)不是通用的。 ∧，∨和→是相當(dāng)標(biāo)準(zhǔn)的，?通常由~代替，?有時(shí)由≡或?表示。 異或甚至更不標(biāo)準(zhǔn)，但是它通常不如運(yùn)算符那么重要。

p     q     p → q p ? q p⊕q 
false false true  true  false 
false true  true  false true 
true  false false false true 
true  true  true  true  false

當(dāng)這些運(yùn)算符在表達(dá)式中使用時(shí)，如果沒有括號(hào)表示求值順序，則使用以下優(yōu)先規(guī)則：異或運(yùn)算符⊕與∨具有相同的優(yōu)先級(jí)。 條件運(yùn)算符→具有比∧，∨，?和⊕更低的優(yōu)先級(jí)，因此在它們之后進(jìn)行求值。 最后，雙向運(yùn)算符?具有最低的優(yōu)先級(jí)，因此最后求值。 例如，表達(dá)式p→q∧r??p⊕s求值為(p→(q∧r))?((?p)⊕s)。

為了高效處理邏輯運(yùn)算符，你需要更多了解它們的含義，以及它們與自然語(yǔ)言表達(dá)式的關(guān)系。

命題p→q稱為蘊(yùn)含或條件。它通常讀作“p蘊(yùn)含q”。在自然語(yǔ)言中，p→q通常表示為“若p則q”。例如，如果p表示命題“比爾·蓋茨是窮人”，q表示“月亮是綠色奶酪制成的”，然后p→q可以表示為“如果比爾·蓋茨是窮人，那么月亮是綠色奶酪制成的”。在這個(gè)例子中，p是假的，q也是假的。檢查p→q的定義，我們看到p→q是一個(gè)真實(shí)的陳述。大多數(shù)人會(huì)同意這一點(diǎn)。類似的例子值得一看。假設(shè)我斷言“如果 Mets 是一個(gè)偉大的團(tuán)隊(duì)，那么我就是法國(guó)的國(guó)王”，這個(gè)說法就是m→k，其中m是“Mets 是一個(gè)偉大的團(tuán)隊(duì)”，k是命題“我是法國(guó)的國(guó)王”，現(xiàn)在我顯然不是法國(guó)的國(guó)王，所以k是假的。因?yàn)?code>k是假的，所以m→k為真的唯一方法是，m也是假的。 （檢查表中的→的定義！）所以，通過斷言m→k，我確實(shí)認(rèn)為 Mets 不是一個(gè)偉大的團(tuán)隊(duì)。

或者考慮這個(gè)陳述，“如果聚會(huì)在星期二，那么我會(huì)參加”。如果我主張這個(gè)陳述，我該怎么說？我認(rèn)為p→q是真的，其中p代表“聚會(huì)在星期二”，q表示“我將參加聚會(huì)”。假設(shè)p是真實(shí)的，那就是聚會(huì)實(shí)際上在星期二。檢查→的定義，我們看到，在p為真且p→q為真的唯一情況下，q也為真。所以從“如果聚會(huì)在星期二，我將參加聚會(huì)”和“派對(duì)實(shí)際上在星期二”的事實(shí)，你可以推斷，“我將參加聚會(huì)”也是正確的。但是，另一方面，假設(shè)聚會(huì)實(shí)際上在星期三。那么p是假的。當(dāng)p為假并且p→q為真時(shí)，p→q的定義允許q為真或假。所以，在這種情況下，你不能對(duì)我是否參加聚會(huì)做任何推導(dǎo)。陳述“如果聚會(huì)在星期二，那么我會(huì)參加”不會(huì)宣布，如果聚會(huì)在星期二之外的其他日子會(huì)發(fā)生什么。

蘊(yùn)含(?q)→(?p)被稱為p→q的逆否。 一個(gè)蘊(yùn)含在邏輯上等同于它的逆否。 “如果今天是星期二，那么我們?cè)诒壤麜r(shí)”的逆否是“如果我們不在比利時(shí)，那么今天不是星期二”。這兩個(gè)句子斷言了完全一樣的東西。

注意，p→q在邏輯上不等同于q→p。 蘊(yùn)含q→p稱為p→q的逆。 “如果今天是星期二，那么我們?cè)诒壤麜r(shí)”的逆是“如果我們?cè)诒壤麜r(shí)，那么今天是星期二”。請(qǐng)注意，這些陳述中的任何一個(gè)是可以的，而另一個(gè)是假的。 在自然語(yǔ)言中，我可以表達(dá)這樣的一個(gè)事實(shí)，即“如果今天是星期二，那么我們?cè)诒壤麜r(shí)，反之亦然”。在邏輯上，這可以使用(p→q)∧(q→p)來(lái)表示。

雙向條件運(yùn)算符與條件運(yùn)算符密切相關(guān)。事實(shí)上，p?q在邏輯上等同于(p→q)∧(q→p)。 命題p?q通常讀取為“p當(dāng)且僅當(dāng)q”（“p當(dāng)q”部分表示q→p，而“p僅當(dāng)q”是另一種斷言p→q的方式）。 也可以表示為“若p則q，反之亦然”。有時(shí)候在中文中，“如果...那么”的真實(shí)含義是“當(dāng)且僅當(dāng)”，例如，如果一個(gè)父母告訴一個(gè)孩子 “如果你聽話，圣誕老人會(huì)帶給你玩具”，父母可能真的意味著說“圣誕老人會(huì)帶給你玩具，當(dāng)且僅當(dāng)你聽話”（父母可能不會(huì)回應(yīng)孩子的完全合乎邏輯的辯解：“但是你從來(lái)沒有說過，如果我不聽話就會(huì)發(fā)生什么事情”）。

最后，我們轉(zhuǎn)向異或運(yùn)算符。 中文的“或”其實(shí)有些含糊不清。 兩個(gè)運(yùn)算符⊕和∨表示這個(gè)單詞的兩個(gè)可能的含義。 命題p∨q可以明確地表示為“p或q或都有”，而p⊕q表示“p或q，但不能同時(shí)存在”。如果菜單說可以選擇湯或沙拉， 這意味著你不能同時(shí)擁有這兩個(gè)。 在這種情況下，“或”是異或。 另一方面，“如果你吸煙或喝酒，那么你有心臟病的風(fēng)險(xiǎn)”，或是包容性的，因?yàn)槿绻阄鼰煵⑶液染?，你肯定?huì)陷入困境。 在數(shù)學(xué)中，“或”這個(gè)詞總是表達(dá)為p∨q的包容性含義。

現(xiàn)在，使用任何→，?和⊕運(yùn)算的任何復(fù)合命題，都可以重寫為僅使用∧，∨和?的邏輯等效命題。 很容易檢查p→q在邏輯上等同于(?p)∨q。 （只需檢查(?p)∨q的真值表）。同樣，p?q可以表示為((?p) ∨q) ∧((?q) ∨p)，所以在嚴(yán)格的邏輯意義上，→，?和⊕是不必要的。 （不過，它們是實(shí)用和重要的，我們不會(huì)放棄它們。）

更是如此：在嚴(yán)格的邏輯意義上，我們可以沒有合取運(yùn)算符∧。 很容易檢查p∧q在邏輯上等同于?p∨?q，所以使用∧的任何表達(dá)式都可以重寫為僅使用?和∨的表達(dá)式。 或者，我們可以沒有∨，并以?和∧來(lái)編寫一切。

某些類型的命題，將在我們進(jìn)一步的邏輯使用中發(fā)揮特殊的作用。 特別是，我們定義的重言式和矛盾如下：

定義1.3。 一個(gè)復(fù)合命題是重言式，當(dāng)且僅當(dāng)對(duì)于它包含的命題變量的真值的所有可能組合，它都是真的。 一個(gè)復(fù)合命題是矛盾，當(dāng)且僅當(dāng)對(duì)于它包含的命題變量的真值的所有可能組合，它都是假的。

例如，命題((p∨q)∧-q)→p是一個(gè)重言式。 這可以用真值表檢查：

p     q     p∨q   ?q    (p∨q)∧?q ((p∨q)∧?q) → p 
false false false true  false    true 
false true  true  false false    true 
true  false true  true  true     true 
true  true  true  false false    true

最后一列中的所有條目都為真的事實(shí)告訴我們，這個(gè)表達(dá)式是一種重言式。 注意，對(duì)于任何復(fù)合命題P，P是重言式，當(dāng)且僅當(dāng)?P是矛盾時(shí)。 （這里和以后我用大寫字母代表復(fù)合命題，P代表由簡(jiǎn)單命題，命題變量和邏輯運(yùn)算符組成的任何公式。）邏輯等價(jià)可以根據(jù)重言式定義：

定義1.4。 當(dāng)且僅當(dāng)命題P?Q是重言式時(shí)，兩個(gè)復(fù)合命題P和Q被認(rèn)為是邏輯等價(jià)的。

在邏輯上等同于Q的斷言，象征性地表示為P≡Q。例如，(p→q)≡(?p∨q)和p⊕q≡(p∨q)∧?(p∧q)。

練習(xí)

一、給出三個(gè)真值表，定義邏輯運(yùn)算符∧，∨和?。

二、將括號(hào)插入以下復(fù)合命題中，來(lái)展示運(yùn)算符求值順序：

a) ?p∨q b) p∧q∨?p c) p∨q∧r d) p∧?q∨r

三、列出四個(gè)命題變量s，p，q，r的真值的16種可能的組合。 嘗試找出一個(gè)系統(tǒng)的方式來(lái)列出值。 （提示：就像圖1.1中的真值表那樣，從p，q和r的八個(gè)值的組合開始，現(xiàn)在，解釋為什么五個(gè)變量可能組合的值有32個(gè)，并描述如何系統(tǒng)地列出它們）。

四、以下復(fù)合命題中，一些是重言式，一些是矛盾，一些都不是。 對(duì)于每個(gè)情況，使用真值表來(lái)判斷命題屬于哪一類：

a) (p∧(p → q)) → q b) ((p → q)∧(q → r)) → (p → r)
c) p∧(?p) d) (p∨q) → (p∧q)
e) p∨(?p) f) (p∧q) → (p∨q)

五、使用真值表來(lái)證明，以下每個(gè)命題在邏輯上等同于p?q。

a) (p → q)∧(q → p) b) (?p) ? (?q)
c) (p → q)∧((?p) → (?q)) d) ?(p⊕q)

六、→是結(jié)合運(yùn)算嘛？ 也就是(p→q)→r在邏輯上等同于p→(q→r)嘛？ ?是結(jié)合運(yùn)算嘛？

七、讓p代表“你離開”的命題，讓q代表“我離開”的命題。使用p和q將以下句子表示為復(fù)合命題，并表明它們?cè)谶壿嬌系葍r(jià)：

a) 要么你離開，要么我離開（或者都是）。
b) 如果你不離開，我就離開。

八、假設(shè)m代表“地球移動(dòng)”的命題，c代表“地球是宇宙的中心”，而g代表“伽利略被抓了”。將以下復(fù)合命題翻譯成中文：

a) ?g ∧c b) m →?c c) m ??c d) (m → g)∧(c →?g)

九、給出以下每個(gè)中文句子的逆和逆否：

a) 如果你聽話，圣誕老人會(huì)給你玩具。
b) 如果包裹重量大于一盎司，你需要付額外的郵費(fèi)。
c) 如果我有選擇，我就不吃茄子。

十、在普通的 52 張撲克牌組中，有多少?gòu)埧M足條件：

a) 這張卡是紅桃 10。
b) 這張卡是紅桃，或者 10。
c) 如果這種卡是 10，那么它是紅桃。
d) 這張卡是 10，當(dāng)且僅當(dāng)它是紅桃。

十一、定義邏輯運(yùn)算符↓，使得p↓q在邏輯上等同于?(p∨q)。 （這個(gè)操作符通常被稱為“或非”）。 證明每個(gè)命題?p，p∧q，p∨q，p→q，p?q和p⊕q可以重寫為邏輯等價(jià)命題，使用↓作為其唯一運(yùn)算符。