1.1.2 聯結詞

定義1.1.4 設p是一個命題，表示一個新命題“非p”。“”是否定聯結詞，命題稱為p的否定。當且僅當p為假時，為真。

真值表給出命題真值之間的關系。表1.1.1給出命題變元p及其否定的所有可能的真值，稱為否定聯結詞“”的真值表。

例如，p表示“今天是晴天”，則表示“今天不是晴天”。注意，不能理解為“今天是雨天”，因為“今天是晴天”的否定并不是“今天是雨天”，還可能是“今天是陰天”“今天是下雪天”等。

自然語言中表示否定的連詞“非”“不”“沒有”“無”“并非”等都可用來表示。

定義1.1.5 設p、q表示任意兩個命題，p∧q可表示復合命題“p并且q”。“∧”稱為合取聯結詞。命題p∧q稱為p和q的合取。當且僅當p和q同時為真時，p∧q為真。真值表見表1.1.2。

例如，p表示“今天是晴天”，q表示“今天去公園”。則p∧q表示“今天是晴天并且今天去公園”。

自然語言中的“和”“與”“也”“并且”“既……又……”“不僅……而且……”“雖然……但是……”等表示同時的連詞都可用∧來表示。假設p表示“小李聰明”；q表示“小李用功”，則“小李既聰明又用功”和“小李不僅聰明而且用功”均可符號化為p∧q。

定義1.1.6 設p、q是任意兩個命題，p∨q可表示復合命題“p或q”,“∨”稱為析取聯結詞。命題p∨q稱為p和q的析取。當且僅當p和q都為假時，p∨q為假。真值表見表1.1.3。

例如，p表示“電燈不亮是燈泡有問題所致”，q表示“電燈不亮是線路有問題所致”，則p∨q表示電燈不亮是燈泡或線路有問題所致。

析取聯結詞可表示自然語言中的“或”“可能……可能……”“或者……或者……”等。自然語言中的“或”具有二義性，有時表示兼容性或，有時表示不兼容性或。由定義可以看出，p∨q表示的是兼容性或，即容許p和q的真值中一個為真，或p與q的真值都為真。而對于命題“派小王或小李中的一人去開會”，其中的“或”表達的是不兼容性或（又稱排斥或）。假設p表示命題“派小王去開會”，q表示命題“派小李去開會”，該句不能符號化為p∨q的形式，而應符號化為。在命題邏輯中，將不兼容性或稱為異或。

定義1.1.7 設p、q為任意兩個命題，p→q可表示復合命題“如果p，則q”，“→”稱為蘊涵聯結詞。命題p→q稱為p與q的蘊涵式。當且僅當p為真、q為假時，p→q為假。真值表見表1.1.4。

例如，p表示“今天天氣晴朗”，q表示“我們去海灘”，則p→q表示“如果今天天氣晴朗，我們就去海灘”。

蘊涵式p→q表示的邏輯關系是：p是q的充分條件，q是p的必要條件。因此形如“如果p，則q”“如果p，那么q”“當p則q”“p僅當q”等復合命題都可以符號化為p→q的形式。形如p→q的蘊涵式中，稱p為蘊涵前件，q為蘊涵后件。

例1.1.2 將下列命題符號化。

1）如果天氣晴朗，我們去海灘。

2）僅當天氣晴朗，我們去海灘。

解 假設p表示“天氣晴朗”，q表示“我們去海灘”。

1）可符號化為p→q，因為“天氣晴朗”是“我們去海灘”的充分條件。

2）可符號化為q→p，這句的“天氣晴朗”是“我們去海灘”的必要條件。

?

注意，只有p的真值為真而q的真值為假時，p→q的真值才為假；當p和q的真值都為真或p的真值為假（無論q的真值為真還是假）時，p→q的真值都為真。蘊涵式的前件的真值為假、后件的真值為任何值時，蘊涵式的真值都為真，對此，可以理解為當規定的前提條件不成立時，得出任何結論都是有效的。例如，命題“如果2+3=6，則太陽從東方升起”和“如果2+3=6，則太陽從西方升起”的真值都為真。

這兩個命題的假設和結論之間沒有什么聯系，在自然語言中，我們不會使用這樣的條件句。在數學推理中，條件語句作為一個數學概念不依賴于假設和結論之間的語義關系。

定義1.1.8 設p、q為任意兩個命題，p?q可表示命題“p當且僅當q”。“?”稱為等價聯結詞，命題p?q稱為等值式。當且僅當p和q同時為真或同時為假時，p?q為真。真值表見表1.1.5。

等值式p?q表示p與q互為充分必要條件的邏輯關系，也就是表示形如“p當且僅當q”“如果p，那么q，反之亦然”等的命題。

例如，p表示“兩個三角形是全等的”，q表示“兩個三角形的三條對應邊相等”，則p?q表示“兩個三角形是全等的當且僅當它們的三條對應邊相等”。

也可以用一個英文字母來表示復合命題，但在推理問題的研究中有時是不適合的。對于一個復合命題，通常先分析出其中包含的簡單命題及它們之間的關系，分別用英文字母表示每一個簡單命題，選用合適的聯結詞表示命題間的關系，然后用聯結詞聯結表示簡單命題的字母，組成復合命題的表示式。

例1.1.3 將下列命題符號化。

1）雖然天氣很冷，老王還是來了。

2）小王和小李是好朋友。

3）小王和小李是好學生。

4）小王或小李中的一個人是游泳冠軍。

5）只有學過微積分或數學系的學生，才可以選修這門課。

6）如果明天早晨6點不下雨，我就去跑步。

7）今天下雨與3+3=6。

8）登錄服務器必須輸入一個有效的口令。

9）2+3=5的充要條件是加拿大位于亞洲。

解 1）設p表示“天氣很冷”，q表示“老王來了”，則1）可符號化為p∧q。

2）這句雖然有連詞“和”，但是一個簡單句，可用p表示“小王和小李是好朋友”。

3）這句中的連詞“和”連接兩個簡單句“小王是好學生”和“小李是好學生”，分別用p和q表示這兩個簡單命題，則可符號化為p∧q。

4）這句中的“或”是不兼容性或，因此應符號化為，其中p表示“小王是游泳冠軍”，q表示“小李是游泳冠軍”。

5）這句含有3個簡單命題，可分別用p、q、r來表示，設p表示“學過微積分的學生”，q表示“數學系的學生”，r表示“你可以選修這門課”。這句中含有的“或”是兼容性或，“只有……才……”的表達方式表示“你學過微積分或是數學系的學生”是“你可以選修這門課”的必要條件，所以，這個命題可以符號化為r→（p∨q）。

6）設p表示“明天早晨6點下雨”，q表示“我去跑步”，則6）可符號化為，或者也可以符號化為。

7）設p表示“今天下雨”，q表示“3+3=6”，則7）可符號化為p∧q。

8）設p表示“登錄服務器”，q表示“輸入一個有效的口令”，則8）可符號化為p→q。

9）設p表示“2+3=5”，q表示“加拿大位于亞洲”，則9）可符號化為p?q。

?

有些命題在自然語言中可能是沒有意義的，如上例中的命題7），其中包含的兩個簡單句語義上沒有聯系，邏輯上是合取關系。在數理邏輯中，p∧q、p∨q、p→q、p?q中的p和q可以沒有語義上的聯系。

這里定義了5個主要聯結詞：，∧，∨，→，?。其中是一元聯結詞，∧、∨、→、?是二元聯結詞。與普通運算符一樣，可以規定運算的優先級，優先順序為、∧、∨、→、?。例如，p∨q→r等同于（p∨q）→r。若有括號，先進行括號中內容的運算。括號有時被省略，如是和q的合取，這里是省略了的括號，即，而不是p和q的合取的否定，即。合取運算符的優先級高于析取運算符，但這個規則不好記，所以可使用括號來區別合取運算符和析取運算符的順序。對于條件運算符和雙條件運算符，也可使用括號區分它們的運算順序。

例1.1.4 將下列命題符號化，并指出它們的真值。

1）1+1=2和2+3=6。

2）1+1=2或猴子是飛禽。

3）若2+3=6，則猴子是飛禽。

4）若猴子不是飛禽，則1+1=2和2+3=6。

5）若2+3=6或猴子是飛禽，則1+1=2。

6）2+3=6當且僅當猴子不是飛禽。

解 設p表示“1+1=2”，q表示“2+3=6”，r表示“猴子是飛禽”，則p表示的命題真值為1，q表示的命題真值為0，r表示的命題真值也為0。因而命題符號化為：

1）p∧q，真值為0，因為p和q中有一個為0。

2）p∨q，真值為1，因為p和q中有一個為1。

3）q→r，真值為1，因為這個條件蘊涵式的前件為0，當條件蘊涵式的前件為0時，無論它的后件的真值為1還是0，這個條件蘊涵式的真值都為1。

4），真值為0，因為這個條件蘊涵式的前件為1，后件為0。

5）q∨r→p，真值為1，原因同3）。

6），真值為0，因為q為0，為1。

?

除了這5個聯結詞外，還定義了一些表示其他邏輯關系的聯結詞。常用的有與非聯結詞、或非聯結詞和異或聯結詞等。下面給出它們的定義。

定義1.1.9 設p和q是任意兩個命題，p↑q可表示復合命題“p和q的與非”,“↑”稱為與非聯結詞。命題p↑q稱為p和q的與非式。當且僅當p和q同時為真時，p↑q為假。真值表見表1.1.6。可以看出，與非式p↑q和等值。

定義1.1.10 設p和q是任意兩個命題，p↓q可表示復合命題“p和q的或非”,“↓”稱為或非聯結詞。命題p↓q稱為p和q的或非式。當且僅當p和q同時為假時，p↓q為真。真值表見表1.1.7。可以看出，或非式p↓q和等值。

定義1.1.11 設p和q是任意兩個命題，p⊕q可表示復合命題“p、q之中恰有一個成立”，“⊕”稱為異或（不兼容性或）聯結詞。命題p⊕q稱為p和q的異或式。當且僅當p和q恰有一個為真時，p⊕q為真。真值表見表1.1.8。可以看出，異或式p⊕q和等值。

在計算機中，這些聯結詞表示的邏輯關系可以用數字電路中的門電路實現，例如，表示“非”邏輯關系的否定聯結詞用數字電路中的“非門”實現，∧聯結詞用“與門”實現，∨聯結詞用“或門”實現，→和?實際上可以用、∧和∨三個聯結詞來表示，所以可以用非門、與門和或門組合的電路來實現。圖1.1.1是非門、與門和或門的電路符號。

非門有一個輸入端和一個輸出端，與門和或門有兩個或兩個以上的輸入端和一個輸出端。與非、或非和異或邏輯關系可用與非門、或非門和異或門實現。在計算機電路中經常用到這些門電路。

例1.1.5 用邏輯電路實現命題公式。

解 可以用圖1.1.2所示的邏輯電路實現命題公式。

?

邏輯聯結詞廣泛應用于信息檢索中，例如，大部分網絡搜索引擎支持布爾檢索技術。在布爾檢索中，聯結詞AND用于匹配同時包含兩個檢索項的記錄，聯結詞OR用于匹配至少包含一個檢索項的記錄，而聯結詞NOT用于排除某個特定的檢索項。采用布爾檢索時，細心安排邏輯聯結詞的使用有助于有效找到特定主題的網頁和信息。

使用邏輯運算符可以把自然語言表示的命題翻譯成由命題變元和邏輯聯結詞組成的表達式，例如，在說明計算機硬件系統和軟件系統時，將自然語言翻譯成邏輯表達式是很重要的部分。對于一些邏輯難題，可以用邏輯表達式表示，然后推理求解。

例1.1.6 將下面的系統規范說明翻譯成邏輯表達式，并確定這些系統規范說明是否一致。

“當且僅當系統正常操作時，系統處于多用戶狀態。”

“如果系統正常操作，則它的核心程序正在運行。”

“核心程序沒有正常運行，或者系統處于中斷模式。”

“系統不處于中斷模式。”

解 令p表示“系統正常操作”，q表示“系統處于多用戶狀態”，r表示“核心程序正在運行”，s表示“系統處于中斷模式”，則上述規范說明可以表示為

系統和軟件工程師從自然語言中提取需求，生成精確、無歧義性的規范說明，這些規范說明可作為軟件開發的基礎。系統規范說明應該是一致的，不應該包含有沖突的需求。當規范說明不一致時，無法開發出滿足所有規范說明的系統。

若為真，則s需為假。當s為假時，為真則r必須為假，這時p必須為假，才能使p→r為真。當p為假時，q必須為假，才有p?q為真。因此，當s、r、p、q都為假時，上述規范說明的邏輯表達式的真值都為真，這4個規范說明是一致的。

如果在上述規范說明中增加“如果系統不處于多用戶狀態，它就處于中斷狀態”，表示為邏輯表達式。當q和s都為假時，為假。因此，這5個規范說明就是不一致的。

例1.1.7 三個客人坐在餐館，服務生問：“每個人都要咖啡嗎？”第一位客人回答：“我不知道。”接著第二位客人也回答：“我不知道。”最后，第三位客人回答：“不是每個人都要咖啡。”一會兒，服務生回來，將咖啡遞給需要的客人。請問服務生是如何判斷哪位客人需要咖啡的？

解 根據三位客人的回答，服務生給第一位客人和第二位客人送來咖啡。

設p、q、r分別表示第一、二、三位客人要咖啡。如果每個人都要咖啡，則p∧q∧r為真。如果第一位客人不要咖啡，則p為假，這時p∧q∧r為假，可以說“不是每個人都要咖啡”。第一個客人的回答是“我不知道”，服務生可以判斷p不為假。根據第二個人的回答可以判斷q為真，因為q為假時，第二個客人就知道“不是每個人都要咖啡”。第三位客人的回答說明r為假，因為這時已知p和q都為真，只有r為假，p∧q∧r才為假，也就是“不是每個人都要咖啡”。因此，服務員可以斷定第一位和第二位客人要咖啡，第三位客人不要咖啡。

?