1.1 命題邏輯

原文：Foundations of Computation

譯者：飛龍

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

自豪地采用谷歌翻譯

一個命題是一個或真或假的陳述。 在命題邏輯中峻厚，我們將命題看做基礎(chǔ)辅斟，看看我們能做什么货徙。 既然這是數(shù)學(xué)课竣，我們需要能夠談?wù)撁}朦促，而不是說我們在說什么特定的命題童太，所以我們用符號來代表它們米辐。 我們始終使用小寫字母胸完，如p，q和r來表示命題翘贮。 以這種方式使用的字母稱為命題變量赊窥。 記住，當我說“假設(shè)p是一個命題”的時候狸页，我的意思是“對于討論其余部分锨能，讓符號p代表一些特定的陳述，它是真的或假的（雖然我現(xiàn)在沒有做出 關(guān)于它的任何假設(shè)）芍耘。討論具有數(shù)學(xué)一般性址遇，因為p可以代表任何陳述，并且無論它代表什么語句斋竞，討論都是有效的倔约。

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

[1] 句子的真值可以根據(jù)其組成部分的真值確定，并不總是真的勾栗。 例如惨篱，如果p是一個命題，那么“莎拉·佩林認為p”也是一個命題围俘，所以“莎拉·佩林認為”是某種運算符砸讳。 然而，它不算作邏輯運算符界牡，因為知道p是否為真簿寂，我們根本就不知道“莎拉·佩林認為p”是否為真。

但自然語言對于數(shù)理邏輯來說有點太豐富了宿亡。 當你讀“我想離開并且我離開了”這個句子時常遂，你可能會看到一個因果關(guān)系的內(nèi)涵：我離開了，因為我想離開挽荠。 這個含義并不符合“我想離開”和“我離開了”這兩個命題的真值的邏輯組合克胳∑郊ǎ或者考慮“我想離開但我沒有離開”這個命題的邏輯組合，在這里漠另， “但”具有與“和”一詞相同的邏輯含義捏雌，但內(nèi)涵卻非常不符。 因此酗钞，在數(shù)理邏輯中腹忽，我們使用符號來表示邏輯運算符来累。 這些符號不具有超出其定義的邏輯意義的任何內(nèi)涵砚作。 對應(yīng)于中文詞語“和”，“或”和“非”的邏輯運算符是∧嘹锁，∨和?葫录。

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

• 當p和q都是真時，p∧q是真摔竿，否則是假面粮。
• 當p和q至少一個是真時，p∨q是真继低，否則是假熬苍。
• 當p時假時?p是真，反之亦然袁翁。

運算符∧柴底，∨和?分別被稱為合取，析取和否定粱胜。 （請注意柄驻，p∧q讀為“p和q”，p∨q讀為“p或q”焙压，?p讀為“非p”）鸿脓。

這些運算符可以用于更復(fù)雜的表達式，如p∧(?q)或(p∨q)∧(q∨r)涯曲。 由簡單的命題和邏輯運算符組成的命題被稱為復(fù)合命題答憔。 可以在復(fù)合表達式中使用括號來表示運算符的求值順序。 在沒有括號的情況下掀抹，求值順序由優(yōu)先規(guī)則確定虐拓。 對于上面定義的邏輯運算符，規(guī)則是?具有較高優(yōu)先級傲武，∧次之并優(yōu)先于∨（就像乘法優(yōu)先于加法）蓉驹。 這意味著在沒有括號的情況下城榛，首先對任何?運算符進行求值，其次是任何∧運算符态兴，最后是任何∨運算符狠持。

例如，表達式?p∨q∧r等價于表達式(?p)∨(q∧r)瞻润，而p∨q∧q∨r等效于p∨(q∧q)∨r喘垂。 實際上，當你構(gòu)造自己的表達式時绍撞，通常最好放在括號中正勒，使你的意思清楚。 記住傻铣，即使你省略括號章贞，你的表達也有明確的含義。 如果你的意思是?(p∧q)非洲，那么你說成?p∧q就錯了鸭限！

這仍然沒有說明表達式∧q∧r中哪個∧運算符首先求值的問題。 這通過以下規(guī)則來解決：當沒有括號的情況下两踏，出現(xiàn)幾個相等優(yōu)先級的運算符時败京，它們從左到右求值。 因此梦染，表達式p∧q∧r等于(p∧q)∧r而不是p∧(q∧r)赡麦。 在這種特殊情況下，事實上弓坞，首先求解哪個運算符是不重要的隧甚，因為兩個復(fù)合命題(p∧q)∧r和p∧(q∧r)總是具有相同的值， 不管命題p渡冻，q和r有什么邏輯值戚扳。 我們說∧是一個結(jié)合性運算。 我們將在下一節(jié)中詳細介紹運算的結(jié)合性和其他屬性族吻。

假設(shè)我們要驗證帽借，(p∧q)∧r和p∧(q∧r)實際上總是具有相同的值。 為此超歌，我們必須考慮p砍艾，q和r的值的所有可能的組合，并檢查對于所有這些組合巍举，兩個復(fù)合表達式確實具有相同的值脆荷。 將此計算組織成一個真值表是很方便的。 真值表是一個表，其中顯示了所包含的命題變量值的每個可能組合的蜓谋，一個或多個復(fù)合命題的值梦皮。 圖1.1是一個真值表，將p∧(q∧r)的值與p桃焕，q和r的所有可能值進行比較剑肯。 表中有八行，因為分配給p观堂，q和r的真值正好有八種不同的組合方式 [2]让网。在這個表中，我們看到最后兩列师痕，表示(p∧q)∧r和p∧(q∧r)相同溃睹。

[2] 一般來說，如果有n個變量七兜，那么有2^n個不同的方法來為變量賦值真值丸凭。 如果你嘗試提出一個方案福扬，系統(tǒng)地列出所有可能的值集合腕铸，這可能會變得清楚。 如果沒有铛碑，你將在本章后面找到嚴格的事實證明狠裹。

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：一個真值表，證明了(p∧q)∧r和p∧(q∧r)的邏輯等價性汽烦。 該表的最后兩列相同的事實表明涛菠，這兩個表達式對于p，q和r的值的所有八種可能的組合具有相同的值撇吞。

更一般地說俗冻，我們說如果它們總是具有相同的值，則兩個復(fù)合命題在邏輯上是等價的牍颈，無論它們包含的命題變量是什么真值迄薄。 如果命題變量的數(shù)量很少，則很容易使用真值表煮岁，來檢查兩個命題是否在邏輯上等價讥蔽。

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

[3] 請注意芋类，本書中為邏輯運算符使用的符號不是通用的瀑焦。 ∧，∨和→是相當標準的梗肝，?通常由~代替榛瓮，?有時由≡或?表示。 異或甚至更不標準巫击，但是它通常不如運算符那么重要禀晓。

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

當這些運算符在表達式中使用時，如果沒有括號表示求值順序坝锰，則使用以下優(yōu)先規(guī)則：異或運算符⊕與∨具有相同的優(yōu)先級粹懒。 條件運算符→具有比∧，∨顷级，?和⊕更低的優(yōu)先級凫乖，因此在它們之后進行求值。 最后弓颈，雙向運算符?具有最低的優(yōu)先級帽芽，因此最后求值。 例如翔冀，表達式p→q∧r??p⊕s求值為(p→(q∧r))?((?p)⊕s)忘衍。

為了高效處理邏輯運算符蚁署，你需要更多了解它們的含義朝蜘，以及它們與自然語言表達式的關(guān)系睡蟋。

命題p→q稱為蘊含或條件。它通常讀作“p蘊含q”控硼。在自然語言中泽论，p→q通常表示為“若p則q”。例如卡乾，如果p表示命題“比爾·蓋茨是窮人”翼悴，q表示“月亮是綠色奶酪制成的”，然后p→q可以表示為“如果比爾·蓋茨是窮人说订，那么月亮是綠色奶酪制成的”抄瓦。在這個例子中，p是假的陶冷，q也是假的钙姊。檢查p→q的定義，我們看到p→q是一個真實的陳述埂伦。大多數(shù)人會同意這一點煞额。類似的例子值得一看。假設(shè)我斷言“如果 Mets 是一個偉大的團隊，那么我就是法國的國王”膊毁，這個說法就是m→k胀莹，其中m是“Mets 是一個偉大的團隊”，k是命題“我是法國的國王”婚温，現(xiàn)在我顯然不是法國的國王描焰，所以k是假的。因為k是假的栅螟，所以m→k為真的唯一方法是荆秦，m也是假的。 （檢查表中的→的定義Ａν肌）所以步绸，通過斷言m→k，我確實認為 Mets 不是一個偉大的團隊吃媒。

或者考慮這個陳述瓤介，“如果聚會在星期二，那么我會參加”赘那。如果我主張這個陳述刑桑，我該怎么說？我認為p→q是真的漓概，其中p代表“聚會在星期二”漾月，q表示“我將參加聚會”病梢。假設(shè)p是真實的胃珍，那就是聚會實際上在星期二。檢查→的定義蜓陌，我們看到觅彰，在p為真且p→q為真的唯一情況下，q也為真钮热。所以從“如果聚會在星期二填抬，我將參加聚會”和“派對實際上在星期二”的事實，你可以推斷隧期，“我將參加聚會”也是正確的飒责。但是，另一方面仆潮，假設(shè)聚會實際上在星期三宏蛉。那么p是假的。當p為假并且p→q為真時性置，p→q的定義允許q為真或假拾并。所以，在這種情況下，你不能對我是否參加聚會做任何推導(dǎo)嗅义。陳述“如果聚會在星期二屏歹，那么我會參加”不會宣布，如果聚會在星期二之外的其他日子會發(fā)生什么之碗。

蘊含(?q)→(?p)被稱為p→q的逆否蝙眶。 一個蘊含在邏輯上等同于它的逆否。 “如果今天是星期二褪那，那么我們在比利時”的逆否是“如果我們不在比利時械馆，那么今天不是星期二”。這兩個句子斷言了完全一樣的東西武通。

注意霹崎，p→q在邏輯上不等同于q→p。 蘊含q→p稱為p→q的逆冶忱。 “如果今天是星期二尾菇，那么我們在比利時”的逆是“如果我們在比利時，那么今天是星期二”囚枪。請注意派诬，這些陳述中的任何一個是可以的，而另一個是假的链沼。 在自然語言中默赂，我可以表達這樣的一個事實，即“如果今天是星期二括勺，那么我們在比利時缆八，反之亦然”。在邏輯上疾捍，這可以使用(p→q)∧(q→p)來表示奈辰。

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

最后载绿，我們轉(zhuǎn)向異或運算符。 中文的“或”其實有些含糊不清油航。 兩個運算符⊕和∨表示這個單詞的兩個可能的含義崭庸。 命題p∨q可以明確地表示為“p或q或都有”，而p⊕q表示“p或q谊囚，但不能同時存在”怕享。如果菜單說可以選擇湯或沙拉， 這意味著你不能同時擁有這兩個镰踏。 在這種情況下函筋，“或”是異或。 另一方面奠伪，“如果你吸煙或喝酒跌帐，那么你有心臟病的風(fēng)險”，或是包容性的绊率，因為如果你吸煙并且喝酒谨敛，你肯定會陷入困境。 在數(shù)學(xué)中滤否，“或”這個詞總是表達為p∨q的包容性含義脸狸。

現(xiàn)在，使用任何→藐俺，?和⊕運算的任何復(fù)合命題炊甲，都可以重寫為僅使用∧，∨和?的邏輯等效命題紊搪。 很容易檢查p→q在邏輯上等同于(?p)∨q蜜葱。 （只需檢查(?p)∨q的真值表）。同樣耀石，p?q可以表示為((?p) ∨q) ∧((?q) ∨p)，所以在嚴格的邏輯意義上爸黄，→滞伟，?和⊕是不必要的。 （不過炕贵，它們是實用和重要的梆奈，我們不會放棄它們。）

更是如此：在嚴格的邏輯意義上称开，我們可以沒有合取運算符∧亩钟。 很容易檢查p∧q在邏輯上等同于?p∨?q乓梨，所以使用∧的任何表達式都可以重寫為僅使用?和∨的表達式。 或者清酥，我們可以沒有∨扶镀，并以?和∧來編寫一切。

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

定義1.3辱志。 一個復(fù)合命題是重言式蝠筑，當且僅當對于它包含的命題變量的真值的所有可能組合，它都是真的揩懒。 一個復(fù)合命題是矛盾什乙，當且僅當對于它包含的命題變量的真值的所有可能組合，它都是假的已球。

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

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

最后一列中的所有條目都為真的事實告訴我們和悦，這個表達式是一種重言式退疫。 注意，對于任何復(fù)合命題P鸽素，P是重言式褒繁，當且僅當?P是矛盾時。 （這里和以后我用大寫字母代表復(fù)合命題馍忽，P代表由簡單命題棒坏，命題變量和邏輯運算符組成的任何公式。）邏輯等價可以根據(jù)重言式定義：

定義1.4遭笋。 當且僅當命題P?Q是重言式時坝冕，兩個復(fù)合命題P和Q被認為是邏輯等價的。

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

練習(xí)

一磨澡、給出三個真值表，定義邏輯運算符∧质和，∨和?稳摄。

二、將括號插入以下復(fù)合命題中饲宿，來展示運算符求值順序：

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

三厦酬、列出四個命題變量s胆描，p，q仗阅，r的真值的16種可能的組合昌讲。 嘗試找出一個系統(tǒng)的方式來列出值。 （提示：就像圖1.1中的真值表那樣霹菊，從p剧蚣，q和r的八個值的組合開始，現(xiàn)在旋廷，解釋為什么五個變量可能組合的值有32個鸠按，并描述如何系統(tǒng)地列出它們）。

四饶碘、以下復(fù)合命題中目尖，一些是重言式，一些是矛盾扎运，一些都不是瑟曲。 對于每個情況，使用真值表來判斷命題屬于哪一類：

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)

五豪治、使用真值表來證明洞拨，以下每個命題在邏輯上等同于p?q。

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

六负拟、→是結(jié)合運算嘛烦衣？ 也就是(p→q)→r在邏輯上等同于p→(q→r)嘛？ ?是結(jié)合運算嘛掩浙？

七花吟、讓p代表“你離開”的命題，讓q代表“我離開”的命題厨姚。使用p和q將以下句子表示為復(fù)合命題衅澈，并表明它們在邏輯上等價：

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

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

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

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

a) 如果你聽話蘑志，圣誕老人會給你玩具累奈。
b) 如果包裹重量大于一盎司贬派，你需要付額外的郵費。
c) 如果我有選擇澎媒，我就不吃茄子搞乏。

十、在普通的 52 張撲克牌組中戒努，有多少張卡滿足條件：

a) 這張卡是紅桃 10请敦。
b) 這張卡是紅桃，或者 10储玫。
c) 如果這種卡是 10侍筛，那么它是紅桃。
d) 這張卡是 10撒穷，當且僅當它是紅桃匣椰。

十一、定義邏輯運算符↓端礼，使得p↓q在邏輯上等同于?(p∨q)禽笑。 （這個操作符通常被稱為“或非”）。 證明每個命題?p蛤奥，p∧q佳镜，p∨q，p→q凡桥，p?q和p⊕q可以重寫為邏輯等價命題蟀伸，使用↓作為其唯一運算符。