第2章數理邏輯《離散數學基礎》——1數理邏輯部分邏輯學(1ogic)是研究人類推理規則（過程）的科學。邏輯學分為兩大流派：傳統邏輯（亞式邏輯）數理邏輯（符號邏輯）2傳統邏輯由亞里士多德創立（故稱亞式邏輯），它是從日常生活的經驗出發，訓練我們在生活中如何使用概念，以及如何判斷和推理。其推理的主要規則是定言三段論。數理邏輯(mathematicallogic)則是近代由歐美人創立的，使用的都是抽象的數學符號和數學公式，也就是用數學的方法來研究邏輯，所以數理邏輯又叫符號邏輯（symbolicLogic）。3邏輯研究的內容：

——著重于推理過程是否正確；

——著重于語句之間的關系，而不是一個具體語句的內容。例:語句1:所有的數學家都穿涼鞋。語句2:任何一個穿涼鞋的人都是代數學家。語句3:所有數學家都是代數學家。從技術上來說，邏輯并不幫助確定這些語句是否為真;然而，如果前兩個語句為真，邏輯可以保證語句3也為真。4傳統邏輯適用于日常生活中的推理；數理邏輯則偏重演算，適用于計算機實現推理。數理邏輯是計算機軟件理論技術和硬件邏輯設計、人工智能等學科的重要理論基礎。

程序＝算法＋數據

算法＝邏輯＋控制本課程包含了數理邏輯的兩個基礎演算(命題演算和謂詞演算)，叫作邏輯代數。5本章主要內容1、命題邏輯及聯接詞2、命題公式和分類3、等值演算與范式4、命題邏輯的推理理論6第一節命題及連接詞7§1命題的定義與運算一、命題的概念推理的構成:

前提(一個或多個判斷句)

結論(一個或多個判斷句)

判斷句----表達判斷的陳述句----是推理的基本單位。

表達判斷----有真假意義,要么為真,要么為假,但不能兼而有之。

【定義】能判斷出真假的陳述句，稱為命題（proposition或statement）。8

命題的真值：作為命題的陳述句所表達的判斷結果。真值只有兩種取值：真(true)或假(false)。任何命題的真值都是唯一的。

真命題：假命題：判斷給定句子是否為命題，一般分為兩步：

首先判斷它是否為陳述句，然后判斷它是否有唯一真值。9【例1】

判斷下列句子是不是命題:4是素數。π是無理數。x

大于y。充分大的偶數等于兩個素數之和。火星上有生物。你能幫助我嗎？請不要吸煙！這朵花真美麗啊！我正在說假話。10）如果x>y，則x-y>0。（命題）（命題）（命題）（命題）（真值不唯一）（疑問句）（祈使句）（感嘆句）（悖論）（命題）10

解：1)、2)、4)、5)、10）這5句是命題，其中第１)句是假命題；第２)句是真命題；第4)句和第5)句雖然目前暫時無法判斷其真假,但它們的真值是客觀存在的，而且是唯一的，將來總會找到它們的真值。

6)是疑問句，7)是祈使句，8)是感嘆句，不是命題

3)x,y表示變元，它們不是確定的對象（從而導致真值不惟一），所以不是命題。

9)是一個自相矛盾的病態語句----稱為悖論，不是命題。11

二、原子命題和復合命題

【定義】不能再分解為更簡單句子的命題叫原子命題（簡單命題），否則稱為復合命題。例：今天是星期一。例：今天是星期一并且今天天晴。

原子命題中的“原子”取原子的“不可再分”之意,它是最基本的命題,相當于自然語言的簡單陳述句。12

【例】

下面的命題由哪些原子命題組成:

1)王斌貧窮但快樂。

2)只要明天天氣好,我就去春游。

3)如果10是一個大于１的整數,則10的大于１的最小因數一定是素數。13

解

1)有兩個原子命題P和Q,其中

P:王斌貧窮。Q:王斌快樂。

2)有兩個原子命題R和s,其中

R:明天天氣好。s:我去春游。

3)有兩個原子命題a和b,其中

a:10是一個大于１的整數。

b:10的大于１的最小因數是素數。

14三、命題及真值的符號化1、用小寫字母p,q,r,…或加下標的小寫字母pi,qi,ri,…表示命題。

【示例】

p:4是素數。（句中的“：”讀作“表示”）

q:1+1=2

r:火星上有生物。2、用

T或1表示真，用

F或0表示假。示例中p

的真值為0，q

的真值為1，r的真值暫時還不知道。15

由簡單命題通過“非”、“并且”、“或者”、“如果…那么…”等聯結詞組合可產生新命題。但在自然語言中出現的聯結詞有時有二義性。因而在數理邏輯中，必須給出聯結詞的嚴格定義，并且將它們形式化。§2邏輯聯結詞16定義設p是一個命題,復合命題“非p”稱為p的否定式,記作┐p。┐稱作否定聯結詞。

“┐”的讀法：not（英）非、…的否定（中）1.非┐P的真值定義為：┐P為真

iff

P為假。（iff表示“當且僅當”）17┐p的真值定義為：┐p為真

iff

p為假。p┐p0110表2.1┐p的真值表18【例如】P：3是偶數。┐

P：3不是偶數。(不是3是偶數。×)Q：今天是星期天。┐Q：今天不是星期天。

R：所有的蘋果都是紅的。┐R：不是所有的蘋果都是紅的。（所有的蘋果都不是紅的。×）19常見錯誤：命題的表述不符合日常規范。例：

p：3是偶數，則┐p表示的命題是什么？常見的錯誤答案是：“不是3是偶數”。正確的答案是：“3不是偶數”。20常見錯誤：部分否定與全部否定。例：

p：所有的蘋果都是紅的，則┐p表示的命題是什么？常見的錯誤答案是：“所有的蘋果都不是紅的”。正確的答案是：“并非所有的蘋果都是紅的”。21定義設p,q是兩個命題,復合命題“p并且q”稱為p與q的合取式，記做p∧q，∧稱為合取聯結詞。“∧”的讀法：and

（英）合取、且（中）

p∧q的真值定義為：

p∧q為真

iff

p,q都為真。2.與（且）22pqp∧q000110110001表2.2p∧q真值表p∧q的真值定義為：p∧q為真

iff

p,q都為真。

23可以抽象成合取詞∧的自然語言的連接詞有:“并且”“和”“及”“既…又…”“不但…而且…”“雖然…但是…”

“一面…一面…”24【例】

將下列命題符號化。(1)吳穎既用功又聰明。(2)吳穎雖然聰明但不用功，這不是真的。(3)張輝與王麗都是三好學生。(4)張輝與王麗是同學。

解首先將原子命題符號化：

P:吳穎用功Q:吳穎聰明

R:張輝是三好學生s:王麗是三好學生

t:張輝與王麗是同學P∧Q┐(┐P∧Q)R∧st25則符號化的命題如下：(1)p∧q

(2)

┐(┐p∧q)(3)r∧s(4)t26關于命題符號化需要注意以下兩點：

（1）p、q、r等符號用來代表肯定形式的命題，而不是否定形式的命題。如下面的符號化不合適（不是原子命題）:

命題：今天不是星期二并且今天天晴。設p：今天不是星期二

q：今天天晴則命題符號化為：p∧q。

（2）p、q、r等符號不能用來代表復合命題（上例其實也是這種情況），因為這樣會掩蓋命題的結構，不利于推理。27定義設p,q是兩個命題,復合命題“p或q”稱為p與q的析取式，記做p∨q，∨稱為析取聯結詞。“∨”的讀法：or

（英）析取、或（中）p∨q的真值定義為：

p∨q為真

iff

p,q至少有一個為真3.或28表2.3p∨q真值表

pqp∨q000110110111p∨q的真值定義為：p∨q為真

iff

p,q至少有一個為真29

析取詞∨是自然語言中的連接詞“或者”等的邏輯抽象。但自然語言中的“或者”具有二義性：

(1)相容或(可兼或)：用它聯結的命題具有相容性：命題可以同時為真，如：張三會講英語或日語。

(2)排斥或(不可兼或)：用它聯結的命題具有排斥性：命題不能同時為真，如：(1)這張桌子是紅色或藍色。

(2)派小王或小李中的一人去開會。∨表示相容或。30注：

在使用析取聯結詞時，首先應分析表達的是可兼或還是不可兼或。若是可兼或，以及p,q不能同時為真的不可兼或①，均可直接符號化為p∨q的形式。如果是不可兼或②，并且p與q可同時為真，就應符號化為(p∧┐q)∨(┐p∧q)的形式。31【例】

將下列命題符號化。張三選修了英語課或者微積分課。今晚張三要么只看書要么只聽音樂。a>0或a=0。32

分析：

(1)是“可兼或”（為什么？），可用析取式表示：p∨q

其中p:張三選修了英語課，

q:張三選修了微積分課(2)是“不可兼或②”：(p∧┐q)∨(┐p∧q)

(3)是“不可兼或①”：p∨q33定義設p,q是兩個命題,復合命題“如果p，則q”稱為p與q的蘊涵式（條件式），記做p→q，→稱為蘊涵聯結詞，p稱為前件，q稱為后件。“→

”的讀法：implies,if…then…

（英）蘊涵、如果…則…

（中）p→q的真值定義為：

p→q為假

iff

p為真而q為假4.條件34表2.4p→q真值表pqp→q000110111101p→q的真值定義為：

p→q為假

iff

p為真而q為假35蘊涵詞→是自然語言中的連接詞“如果……,則……”“只要……,就……”“因為……,所以……”

“只有……,才……”“除非……,否則……”

等的邏輯抽象。

p→q表明的邏輯關系是：p是q的充分條件，q是p的必要條件。36日常生活中的“如果p,則q”是聯系兩個有邏輯關系的語句p和q。而在數理邏輯中，前件p和后件q可以沒有任何邏輯聯系，蘊涵式p→q的真值僅由p,q的真值惟一確定。例：如果1+1=2，那么雪是白的。

37在數學和其他自然科學中，“如果p,則q”往往表達前件p為真，后件也為真的推理關系；而在數理邏輯中，當前件p為假，不管后件是真是假，規定

p→q都是真(∵復合命題p→q應有真值)。例：校長宣布：如果氣溫超過38℃，則全校停課。38關于“只有……,才……”和“除非……,否則……”的符號化：(1)只有肚子餓了，我才去麥當勞。

其意思相當于：

如果我去麥當勞，則我肚子餓了。設p：我肚子餓了q：我去麥當勞則原命題可符號化為：q→p

。39(2)除非下雨，否則我就騎自行車上班。其意思相當于：

如果不下雨，我就騎自行車上班。設p：天下雨q：我騎自行車上班則原命題可符號化為：┐p→q

。40【例】下列命題是否是含有蘊涵的復合命題?若是,指出其前件和后件。a)只要你發給我一個電子郵件，我就會把地址寄給你。b)暖天持續一周蘋果樹就開花。c)活塞隊贏得冠軍就意味著他們打敗了湖人隊。d)必須走8英里才能到朗斯峰的頂峰。e)只有你購買的Mp4機不超過90天，你的保修單才有效。f)如果你駕車超過400英里，就需要買汽油了。41g)你獲得這一職位表明你有最好的信譽。h)要成為美國公民，只要你生在美國就行了。i)除非下大雨，否則我是一定要出門的。j)要在服務器登錄必須有一個有效的口令。42

【定義】設P,Q是兩個命題,復合命題“P當且僅當Q”稱為P與Q的等價式，記做PQ，稱為等價聯結詞。

PQ的真值定義為：

PQ為真

iff

P,Q真值相同因此,P,Q一真一假時,P

Q為假。

“”的讀法：ifandonlyif=

iff

（英）

當且僅當、等價

（中）復合命題PQ的取值如表2―5所示。

43表2-5P

Q真值表

等值詞是自然語言中的連接詞“當且僅當”等的邏輯抽象。不難看出(P→Q)∧(Q→P)與PQ

的邏輯關系完全一致，即都表示P與Q互為充要條件。PQP

Q00011011100144【例】

將下列命題符合化，并討論它們的真值。π

是無理數當且僅當加拿大位于亞洲。2+3=5的充要條件是是無理數。若兩圓O1，O2的面積相等，則它們的半徑相等，反之亦然。如果今天是星期三，則地球是圓的，反之，如果地球是圓的，今天是星期三。45【例】

令

P:北京比天津人口多

Q:2+2=4

R:烏鴉是白色的求下列符合命題的真值：

((┐P∧Q)∨(P∧┐Q))→R(Q∨R)→(P→┐R)(┐P∨R)(P∧┐R)46

翻譯時,為了減少圓括號,我們對5個命題聯結詞的強弱次序規定為

┐、∧、∨、→、聯結詞小結：聯結詞類似于代數中的＋、－、×、/，只不過＋、－、×、/作用的是數（實數，甚至復數），而聯結詞作用的是命題。也就是說，聯結詞提供了命題之間的一種運算。在本質上，聯結詞用于反映復合命題的內部邏輯結構。47練習一個人起初說：“占據空間的，有質量的而且不斷變化的叫物質。”后來他改口說：“占據空間的，有質量的叫物質，而物質是不斷變化的。”問他前后差異在什么地方，試以命題形式進行分析。48練習1、指出下列語句哪些是命題，哪些不是命題。如果是命題，指出它的真值；如果不是命題，說明理由。（1）離散數學是計算機系的一門必修課。（2）你有空嗎？（3）明天我去看電影。（4）請勿隨地吐痰！（5）不存在最大的質數。（6）如果我掌握了英語、法語，那么學習其它歐洲語言就容易的多。（7）9＋5≤12。（8）x＝3。（9）我們要努力學習！492、試把下列命題符號化。（1）或者你沒有給我寫信，或者它在途中丟失了。（2）假如上午不下雨，我去看電影，否則就在家里讀書或看報。（3）我今天進城，除非下雨。（4）僅當你走我將留下（5）如果你來了，那么她唱不唱歌將看你是否伴奏而定50邏輯聯結詞的應用----布爾檢索邏輯聯結詞廣泛用于在大量信息中檢索，例如，檢索網頁索引。由于這些檢索使用來自命題邏輯的技術，所以稱為布爾檢索。在布爾檢索中，聯結詞AND用于匹配包含兩個檢索項的記錄，聯結詞OR用于匹配兩個檢索項之一或兩項均匹配的記錄，而聯結詞NOT用于排除某個特定的檢索項。51例

網頁檢索的布爾檢索技術。大部分網上檢索引擎支持布爾檢索，因為它有助于找到有關特定主題的網頁。5253第二節命題公式和分類54若P、Q、R、S為命題，則判斷以下符號串，哪些構成復雜命題1）┐P→(Q∧┐R)2）(┐P∨┐Q)∧(R→┐s)3）→(┐P→Q)∨(┐∧R∧

┐s)§1命題變元和命題公式怎樣的組合方式才能稱之為命題公式？55一、命題常元與命題變元命題常項（命題常元）----表示一個確定的、具體的簡單命題的標識符。命題常項有確定的真值,其真值不是０就是１。命題變項（命題變元）----表示任意一個命題的標識符，以“真、假”或“1、0”為取值范圍,仍用小寫字母表示。一個命題變元若被某個確定的命題替代,就具有確定的真值。（參：常數與變量）

注：1）命題變元不是命題。（參：整數變量不是整數。）

2）

P表示命題常元還是命題變元可由上、下文來確定。56二、命題公式【定義】

一個命題公式是由下列規則所產生的符號串:1)單個命題常元或命題變元是命題公式，稱為原子命題公式。

2)若A是命題公式,則┐A也是命題公式。

3)若A,B是命題公式,則(A∧B),(A∨B),(A→B),(A

B)也是命題公式。

4)只有有限次地運用1),2),3)所產生的符號串才是命題公式。57

命題公式也簡稱為公式。上述命題公式的定義采用了遞歸定義方式。由定義可知,下面的符號串∧P,(PQ∨)，PQ→R都不是公式。而符號串

((P→Q)→R),((┐PQ)∨(R∧s))都是公式。為了簡便起見,我們常常省去公式最外層的圓括號。所以上面兩個公式又可以分別寫成

(P→Q)→R,(┐PQ)∨(R∧s)58一、命題公式的賦值命題公式的真值情況取決于其所含命題變元的真值。

【定義】

設p1,p2,…,pn是出現在公式A中的所有命題變元，給p1,p2,…,pn各指定一個真值，稱為對公式A的一個真值指派（也稱解釋）。§2

命題公式的賦值和真值表N個命題變元有多少中不同的真值指派？59pqp∧q000110110001

p∧q真值表例：成真賦值成假賦值60二、真值表的構造【示例】

求公式(p∧q)∧┐p的真值表。

解：分以下4步求得:1)寫出個命題變元的真值指派；

2)寫出公式p∧q的真值表;3)寫出公式┐p的真值表;4)根據2)和3),寫出公式(p∧q)∧┐p的真值表。為清楚起見,我們將這4步列在一個表內,見下表。61pqp∧q┐p(p∧q)∧┐p00011011000111000000(p∧q)∧┐p的真值表62構造真值表注意事項：命題變元按下標進行排列，若無下標，則按字典順序進行排列；命題變元的取值按二進制編碼從小到大（或從大到小）排列，這樣容易做到“不重不漏”；根據經驗，最好是逐列求值，而不是逐行求值，這樣不容易出錯；對于一個具體的命題公式，其真值表究竟分成幾列，要根據自己的熟練程度來定。63

pqr┐p┐p∧q┐r(┐p∧q)→┐r【示例】

求(┐p∧q)→┐r的真值表。1111000000110000101010101110111100000101001110010111011164PQ┐P┐QP∧┐PQ∧┐Q(P∧┐P)(Q∧┐Q)0001101111001010【例】

求公式(P∧┐P)

(Q∧┐Q)的真值表00000000111165

PQRP→Q┐(P→Q)┐(P→Q)∧Q┐(P→Q)∧Q∧R000001010011100101110111【示例】求┐(P→Q)∧Q∧R的真值表1111001100001100000000000000000066【定義】

設A為一個命題公式,

(1)若A在它的各種賦值下，其真值恒為１,則稱為A重言式或永真式

;

(2)若A在它的各種賦值下，其真值恒為0，則稱為A矛盾式或永假式；

(3)若A不是矛盾式（至少存在一種賦值，使A的真值為1），則稱其為可滿足式

。§3命題公式的分類67

從一個命題公式的真值表可以判斷公式的類型：若真值表最后一列全為1，則公式為重言式；若真值表最后一列全為0，則公式為矛盾式；若真值表最后一列至少有一個1，則公式為可滿足式。68第3節等值演算與范式69定義設A,B是命題公式,如果在其任意的解釋I下，其真值相同，記為AB。§1等價和基本等價式注：1）區別

與

。

2）等值具有①自反性；②對稱性；③傳遞性。

一、等價定理設A,B是命題公式,AB的充要條件是命題公式AB是永真式。70證明AB的方法：（1）列舉A與B的各種真值指派，證明其各種賦值之下，A與B的真值相同。（2）證明AB是永真式。（3）通過等值演算把A轉化為B71我們常常利用真值表來判斷兩個命題公式是否邏輯等價。

【例】證明p→q

┐p∨qpqp→q┐p∨q0001101111011101從真值表可以看出：p→q

┐p∨q72

【例】

判斷下面兩組公式是否等值：

(1)p→(q→r)與(p∧q)→r

(2)(p→

q)→r

與(p∧q)→r

解：從真值表可以看出：p→(q→r)(p∧q)→r

但：(p→

q)→r

(p∧q)→r

pqrp→(q→r)(p→

q)→r(p∧q)→r

000001010011100101110111

11111101010111011111110173練習用真值表判斷下面兩組公式是否等值：1）（(p→q)∧(p→r))，(p→(q∧r))2）┐((p∧q)∨(┐p∧┐q))，((p∨q)∧┐(p∧q))74§2等值演算

1.雙重否定律┐┐AA2.冪等律A∨AA，A∧AA4.結合律(A∨B)∨CA∨(B∨C)(A∧B)∧CA∧(B∧C)3.交換率A∨BB∨A，A∧BB∧A一、基本等值式759.同一律A∨0A，A∧1A7.吸收律A∨(A∧B)A，A∧(A∨B)A5.分配律A∨(B∧C)

(A∨B)∧(A∨C)A∧(B∨C)(A∧B)∨(A∧C)6.德摩根律┐(A∨B)┐A∧┐B┐(A∧B)┐A∨┐B8.零律A∨11，A∧007613.等價等值式(AB)(A→B)∧(B→A)

12.蘊含等值式A→B┐A∨B11.矛盾律A∧┐A010.排中律A∨┐A116.歸謬論(A→B)∧(A→┐B)┐A15.等價否定等值式AB┐A┐B14.假言異位A→B┐B→┐A77

在上面的基本等值式中，很多是成對出現的，如果在僅含有連接詞┐、∧,∨的命題公式,將∧,∨,０,１分別換為∨,∧,１,０,就得到另外一個等值式。這些等值式都可用列真值表的方法證明。由于聯結詞∨、∧滿足可結合性，因此可將(P∨Q)∨R和P∨(Q∨R)簡記為P∨Q∨R；

(P∧Q)∧R和(P∧Q)∧R簡記為P∧Q∧R。78二、代入規則和置換規則

由已知的等值式，可以推演出更多的等值式，我們稱由已知的等值式推演出另外的等值式的過程稱為等值演算。在等值演算中常使用下面兩個重要的規則——代入規則和置換規則。

代入規則:

在等值式中,將某一命題變元都用同一命題公式代入后,得到的公式仍是等值式（反之不成立）（其正確性請讀者思考，舉反例）。例如,在A→(B→C)(A∧B)→C中,若用公式(S∨R)代替A,則得

(S∨R)→(B→C)((S∨R)∧B)→C79

置換規則：

設Φ(A)是含公式A的命題公式，Φ(B)是用公式B置換了Φ(A)中所有的A后得到的命題公式，若A

B,則Φ(A)

Φ(B)

。置換規則的正確性是由于:A

B,所以對任一組命題變元的真值指派,A和B的真值都相同,而Φ(A),Φ(B)除A和B以外的部分都相同,因此Φ(A)和Φ(B)的真值都相同,即有Φ(A)

Φ(B)

。例如：┐Q∧（P→Q）

┐Q∧（┐P∨Q）80三、等值演算的用途

1）驗證兩個公式等值

2）判別命題公式的類型★3）解決實際問題81用途1：驗證兩個公式等值【示例】證明等值式:p→(q→r)(p∧q)→r。證明p→(q→r)

p→(┐q∨r)(蘊含等值式)┐p∨(┐q∨r)

(蘊含等值式)(┐p∨┐q)∨r

(結合律)

┐(p∧q)∨r(德摩根律)(p∧q)→r(蘊含等值式)這種證明方法我們稱之為等值演算推導法。82

【例】用等值演算驗證等值式：┐(p∨q)∨r(德摩根律)(┐p∧┐q)∨r(冪等律、吸收律)

證(p→r)∧(q→r)(┐p∨r)∧(┐q∨r)(蘊含等值式)(p∨q)→r(p→r)∧(q→r)(p∨q)→r(蘊含等值式)(┐p∧┐q)∨(┐p∧r)∨(r∧┐q)∨(r∧r)(分配律)83

【示例】

證明等值式:(p∧q)→r

(p→q)→(p→r)。

證：(p→q)→(p→r)┐(┐p∨q)∨(┐p∨r)(蘊含等值式)(┐(┐p∨q)∨┐p)∨r(結合律)

(p∧q)→r(蘊含等值式)┐(p∧q)∨r

(德摩根)(┐q∨┐p)∨r(同一律)(1∧(┐q∨┐p))∨r(排中律)

((p∨┐p)∧(┐q∨┐p))∨r(分配律)((p∧┐q)∨┐p)∨r

(德摩根、雙重否定律)84用途2：判別命題公式的類型【例1.12】

用等值演算法判斷下列公式的類型：(p→q)∧p→q

┐(p→(p∨q))∧rp∧(((p∨q)∧p)→q)解：(p→q)∧p→q

(┐p∨q)∧p→q(蘊含等值式)

((┐p∧p)∨(q∧p))→q(分配律)

(0∨(q∧p))→q(矛盾律)

(q∧p)→q

┐(q∧p)∨q

(┐q∨┐p)∨q┐q∨┐p∨q

┐q∨q∨┐p

1

∨┐p

1

所以，公式(1)是一個重言式。重言式永假式可滿足式85等值演算練習一、證明下列等價式。(1)A→(B→A)┐A→(A→┐B)(2)┐(P∨┐Q)→(Q→R)Q→(P∨R)二、用等值演算法判斷下列公式的類型（1）┐((P∧Q)→P)（2）(┐P→Q)→(Q→┐P)86用途3：解決實際問題A,B,C,D4人做百米競賽，觀眾甲、乙、丙預報比賽的名次為：甲：C第一，B第二；乙：C第二，D第三；丙：A第二，D第四比賽結束后發現甲、乙、丙每人報告的情況都是各對一半，試問實際名次如何（無并列者）？解：ai,bi,ci,di表示A,B,C,D第i名，i=1,2,3,4①(c1∧┐b2)∨(┐c1∧b2)

1②(c2∧┐d3)∨(┐c2∧d3)1③(a2∧┐d4)∨(┐a2∧d4)

187①∧②1，C不能既第一又第二，B和C不能都第二，所以((c1∧┐b2)∨(┐c1∧b2))∧((c2∧┐d3)∨(┐c2∧d3))(c1∧┐b2)∧((┐c2∧d3)∨(c2∧┐d3))∨(┐c1∧b2)∧((┐c2∧d3)∨(c2∧┐d3))(c1∧┐b2∧┐c2∧d3)∨(c1∧┐b2∧c2∧┐d3)

∨(┐c1∧b2∧┐c2∧d3)∨(┐c1∧b2∧c2∧┐d3)

(c1∧┐b2∧┐c2∧d3)∨(┐c1∧b2∧┐c2∧d3)1④(c1∧┐b2∧┐c2∧d3)∨(┐c1∧b2∧┐c2∧d3)188③∧④1且A，B不能同時第二，D不能第三又第四，所以((a2∧┐d4)∨(┐a2∧d4))∧((c1∧┐b2∧┐c2∧d3)∨(┐c1∧b2∧┐c2∧d3))(a2∧┐d4)∧((c1∧┐b2∧┐c2∧d3)∨(┐c1∧b2∧┐c2∧d3))

∨(┐a2∧d4)∧((c1∧┐b2∧┐c2∧d3)∨(┐c1∧b2∧┐c2∧d3))(a2∧┐d4∧c1∧┐b2∧┐c2∧d3)∨(a2∧┐d4∧┐c1∧b2∧┐c2∧d3)∨(┐a2∧d4∧c1∧┐b2∧┐c2∧d3)∨(┐a2∧d4∧┐c1∧b2∧┐c2∧d3)(a2∧┐d4∧c1∧┐b2∧┐c2∧d3)1所以C第一，A第二，D第三，B第四89（補）邏輯等價的應用【例】利用基本的邏輯等價關系，化簡電路圖rpsqpspqrp解：上述電路圖可描述為：((p∧q∧r)∨(p∧q∧s))∧((p∧r)∨(p∧s))90利用基本邏輯等價式，化簡公式可得：

((p∧q∧r)∨(p∧q∧s))∧((p∧r)∨(p∧s))=((p∧q∧(r∨s))∧(p∧(r∨s))=p∧q∧(r∨s)；srqp91【例】將下面程序語言進行化簡。ifAthen

ifBthenXelseYelseifBthenXelseYTFFTFTStartAXYEndBB

解：執行X的條件為：

(Ａ∧Ｂ)∨(Ａ∧Ｂ)

執行Y的條件為：

(Ａ∧Ｂ)∨(Ａ∧Ｂ)92

執行X的條件可化簡為：

(Ａ∧Ｂ)∨(Ａ∧Ｂ)＝(Ａ∨Ａ)∧Ｂ＝Ｂ執行Y的條件可化簡為：

(Ａ∧Ｂ)∨(Ａ∧Ｂ)＝(Ａ∨Ａ)∧Ｂ＝ＢTXYEndStartBF程序可簡化為：IfBthenXelseY93思考以下問題：（1）(0001010)2與(10)10

那個大？（2）兩個形式不同的命題公式是否等值？（3）為什么要有范式？為命題公式制定一種標準表達形式，使得命題公式的成真或成假賦值一目了然。§3范式94要了解什么是范式,先得介紹組成范式的基本成分——簡單合取式和簡單析取式。

【定義】

僅由命題變元或命題變元的否定所組成的析取式稱為簡單析取式，僅由命題變元或命題變元的否定所組成的合取式稱為簡單合取式。一、范式95

若p,q,r是命題變元,則

p,q,r,┐p,┐q∧r,r∧┐r,p∧q∧r,p∧┐q∧┐p等都是簡單合取式;p,q,r,┐p,┐p∨r,p∨┐r,p∨q∨r,p∨┐q∨┐p等都是簡單析取式。96

【定義】由有限個簡單合取式的析取構成的析取式稱為析取范式。由有限個簡單析取式的合取構成的合取式稱為合取范式。析取范式和合取范式統稱為范式。設Ai(i=1,2,…,n)為簡單合取式，則A=A1∨A2∨…∨An為A析取范式。設Bi(i=1,2,…,n)為簡單析取式，則B=B1∧B2∧…∧Bn為B合取范式。

注意：一個簡單合取式為即為析取范式，又為合取范式。97公式A的析取范式常用來判定A是否是矛盾式;

公式A的合取范式常用來判定A是否是重言式。

【定理】(1)一個析取范式為矛盾式當且僅當它的每個簡單合取式都是矛盾式。

(2)一個合取范式為重言式當且僅當它的每個簡單析取式都是重言式。

98

【定理】(范式存在定理)任一命題公式都存在與之等值得析取范式與合取范式。

從定義可知,一個范式有以下特征:1)不含蘊含聯結詞→和等價聯結詞

;2)不含雙重否定┐┐;3)否定詞┐僅出現在命題變元之前;4)析取范式是簡單合取式的析取,而合取范式是簡單析取式的合取。

所以,求一個公式的范式就是求滿足以上四點的公式。其具體步驟是:

991)消去聯結詞→和:

p→q

┐p∨q

p

q

(p→q)∧(q→p)

(┐p∨q)∧(┐q∨p)(1)

(p∧q)∨(┐p∧┐q)(2)

把pq化為(1)還是(2)依所求的是析取范式還是合取范式而定。

2)消去┐┐:┐┐pp3)使┐出現在命題變元之前:┐(p∨q)┐p∧┐q┐(p∧q)┐p∨

┐q4)利用分配律將公式化為所求范式:

p∧(q∨r)(p∧q)∨(p∧r)

p∨(q∧r)(p∨q)∧(p∨r)100【例】

求下面公式的析取范式（1）(P∨Q)→((QR)∧S)（2）(P→┐Q)→((Q∨R)→┐S)(1)(P∨Q)→((QR)∧S)┐(P∨Q)∨((┐Q∨R)∧

(┐R

∨Q)∧S)(

┐P∧

┐Q)∨((┐Q∨R)∧

(┐R

∨Q)∧S)(

┐P∧

┐Q)∨((┐Q∧

┐R)∨(R

∧Q)∧S)(

┐P∧

┐Q)∨(┐Q∧

┐R∧S)∨(R

∧Q∧S)

101（2）(P→┐Q)→((Q∨R)→┐S)┐(┐P∨┐Q)∨

(┐(Q∨R)∨┐S)(P∧Q)∨

(

(┐Q∧┐

R)∨┐S)(P∧Q)∨

(┐Q∧┐

R)∨┐S102【例】

求下面公式的合取范式:（1）(P→Q)→R（2）P→(Q

R)（3）(┐P→Q)→(Q∧(R→S)）(P→Q)→R┐(┐

P∨Q)∨R

(P∧

┐Q)∨R

(P∨R）∧（

┐

Q∨R)103(2)P→(Q

R)┐P∨((┐Q∨R)∧(

┐R∨Q))(┐P∨┐Q∨R)∧(┐P∨┐R∨Q)(3)(┐P→Q)→(Q∧(R→S))┐(P∨

Q)∨

(Q∧(┐

R∨

S))(┐P∧

┐Q)∨

(Q∧(┐

R∨

S))((┐P∧

┐Q)∨Q)∧((┐P∧

┐Q)∨(┐R∨S))((┐P∨Q)∧(

┐Q∨Q))∧((┐P∧

┐Q)∨(┐R∨S))(┐P∨Q)∧((┐P∨┐R∨S)∧(┐Q∨┐R∨S))(┐P∨Q)∧(┐P∨┐R∨S)∧(┐Q∨┐R∨S)104二、主范式為使范式惟一,我們引入了一種特殊的范式——主范式。主范式的基本成分是特殊的簡單合取式和簡單析取式,它們分別稱為極小項和極大項。

1、極小項和極大項【定義】

設有n個命題變元p1,p2,…,pn,則簡單合取式p1′∧p2′∧…pn′稱為由n個命題變元所產生的極小項，簡單析取式p1′∨p2′∨…pn′

稱為由n個命題變元p1,p2,…,pn所產生的極大項。其中pi′或為pi或為┐pi（i=1,2,…,n）。105極大、極小項的特征：極小項————n個變元不重不漏的簡單合取式極大項————n個變元不重不漏的簡單析取式示例：若有三個命題變元p,q,r,則p∧q∧r,p∧┐q∧r,┐p∧q∧┐r等是由p,q,r所產生的極小項;p∨q∨r,

p∨┐q∨r,┐p∨q∨┐r等是由p,q,r所產生的極大項。一般地,由ｎ個命題變元所產生的全部不同的極小項和極大項都是2n個。106

每個極小項p1′∧p2′∧…pn′都有且僅有一個成真賦值，不妨假設其對應的二進制數為δ1δ2……δn

,其中：(i=1,2,…,n）

每個極大項p1′∨p2′∨

…pn′

都有且僅有一個成假賦值，不妨假設其對應的二進制數為δ1δ2……δn

,其中：(i=1,2,…,n）注意：δi

的取值規則極小項與極小項時正好相反107

如果一個極小項對應的二進制數為δ1δ2…δn，則將對應的十進制數r作為該極小項的序號，并將該極小項簡記為mr。顯然r從０取到2n－1。以３個命題變元p1,p2,p3為例,極小項┐p1∧┐p2∧┐p3對應的二進制數為000,其序號為０，用m0表示;極小項┐p1∧p2∧p3對應的二進制數為011,其序號為3，用m3表示。反之,如果要求m5對應的極小項，因為序號5對應的二進制數為101，所以該極小項是p1∧┐p2∧p3。由此可見,極小項與其序號一一對應。1088個極小項對應情況如下：極小項成真賦值記號┐p∧┐q∧┐r－－000－－0記作m0┐p∧┐q∧r－－001－－1記作m1┐p∧q∧┐r－－010－－2記作m2┐p∧q∧r－－011－－3記作m3p∧┐q∧┐r－－100－－4記作m4p∧┐q∧r－－101－－5記作m5p∧q∧┐r－－110－－6記作m6p∧q∧r－－111－－7記作m7109極小項的性質：(1)對一個含有n個變項的公式來說,所有可能的極小項個數和該公式的解釋個數一樣多,都是2n

。(2)每個極小項只在一個賦值下為真，且與它所對應的二進值編號相同。(3)極小項兩兩不等值,而且mi∧mj=F(i,j)。(4)任一含有n個變項的公式,都可由k個(k≤2n)極小項的析取來表示。110

類似地，如果一個極大項對應的二進制數為δ1δ2…δn，就將對應的十進制數r作為該極大項序號，并將該極大項簡記為Mr。顯然r從０到2n－1。以３個命題變元P1,P2,P3為例,

極大項p1∨p2∨p3對應的二進制數為000,其序號為０，用M0表示；極大項┐p1∨p2∨p3對應的二進制數為100,其序號為4，用M4表示。反之,如果要求M5對應的極大項，因為序號5對應的二進制數為101，所以該極大項是┐p1∨p2∨┐p3。由此可見,極大項與其序號一一對應。1118個極大項對應情況如下：極大項成假賦值記號p∨q∨r－－000－－0記作M0p∨q∨┐r－－001－－1記作M1p∨┐q∨r－－010－－2記作M2p∨┐q∨┐r－－011－－3記作M3┐p∨q∨r－－100－－4記作M4┐p∨q∨┐r－－101－－5記作M5┐p∨┐q∨r－－110－－6記作M6┐p∨┐q∨┐r－－111－－7記作M7112極大項的性質：對一個含有n個變項的公式來說,所有可能的極大項個數和該公式的解釋個數一樣多,都是2n

。每個極大項只在一個解釋下為假，且與它所對應的二進值編號相同。極大項兩兩不等值,而且Mi∨Mj=T(i≠j)。任一含有n個變項的公式,都可由k個(k≤2n)極大項的合取來表示。

1132、極小項與極大項的關系

【定理】設mi與Mi是有命題變元p1,p2,…pn形成的極小項和極大項，則┐mi

Mi，

┐

Mi

mi3、主析取范式與主合取范式

【定義】由若干不同的極小項所組成的析取式叫做主析取范式。由若干不同的極大項所組成的合取式叫做主合取范式。

【定義】與公式A等值的主析取范式（主合取范式）稱為公式A的主析取范式（主合取范式）。

【定理】（存在唯一性）

任何命題公式都存在與之等值的主析取范式和主合取范式，并且是唯一的。1144、主范式的求法一般有兩種方法：

(1)真值表方法

(2)公式化歸法-----等值推演方法下面先通過例子來說明真值表方法。

【例】

求命題公式p→q的主析取范式和主合取范式。所有p→qm0∨

m1∨

m3

M2pqp→q極小項極大項000110111101m0m1m3M2115pqp→qm0┐p∧┐qm1┐p∧qm3p∧qm0∨m1∨m3M2p∧┐q00011011110110000100000111011101116由前面的例子可以歸納出真值表法的步驟：1)

寫出命題公式的真值表。2)

找出所有的成真賦值，其對應的極小項即為該公式的主析取范式中所含的所有極小項3)

找出所有的成假賦值，其對應的極大項即為該公式的主合取范式中所含的所有極大項；4)

從而可立即寫出兩個主范式。117

【例】

求命題公式(p→q)

r的主析取范式和主合取范式。解列出命題公式的真值表如下：

pqrp→q(p→

q)r極小項極大項0000010100111001011101111111001101011001m1m3m4m7M0M2M5M6所以(p→q)

rm1∨m3∨m4∨m7M0∧M2∧M5∧M6118由前面兩個例子還可以看出：含有n個命題變元的公式,它的主析取范式所含小項的個數與其主合取范式所含大項的個數之和為2n個。可以由公式的主析取范式求出主合取范式，或者由主合取范式求出主析取范式。（想想兩者之間關系？）若公式A是一個重言式,則A的主析取范式含有全部可能的極小項,而其主合取范式不能包含任一極大項。我們定義重言式A的主合取范式為1;若公式A是一個矛盾式,則A的主合取范式含有全部可能的極大項,而其主析取范式不能包含任一極小項。我們定義矛盾式A的主析取范式為０。119練習：用真值表法求下列公式的主析取范式和主合取范式。1）(pq)

→r2）p

(q∧r)

120

用真值表方法我們能求出一個公式惟一的主范式,然而這個方法僅對命題變元個數較少時可行。因為主范式是一種范式,但又具有特殊性,所以我們對主范式介紹一種類似于求范式的方法－－公式化歸法：先求范式，再求主范式。用公式化歸法求一個公式A的主范式的過程如下:1)～4)步同于求范式的四步,求出A的析取范式或合取范式;5)利用同一律、排中律將析取范式中所有矛盾的簡單合取式消去，將所有重言的簡單析取式消去。1216)利用冪等律合并析取范式中相同的簡單合取式以及合取范式中相同的簡單析取式,同時合并簡單合取式和簡單析取式中相同的命題變元。

7)由PP∧(Q∨┐Q)可以將簡單合取式中沒有出現的命題變元Q補充進去;由PP∨(Q∧┐Q)可以將簡單析取式中沒有出現的命題變元Q補充進去。

8)利用分配律展開公式,并除去相同的小項和大項,由此求得公式的主范式。122【例】求命題公式p→q的主析取范式和主合取范式。解(1)p→q

┐p∨q(主合取范式）

M2

(2)p→q

┐p∨q

(┐p∧(q∨┐q))∨((p∨┐p)∧q)

(┐p∧q)∨(┐p∧┐q)∨(p∧q)∨(┐p∧q)

(┐p∧┐q)∨(┐p∧q)∨(p∧q)(主析取范式）

m0∨m1∨m3123【例】求命題公式(p→q)

r的主析取范式和主合取范式。解在例1.13中已求出該命題公式的析取范式：

(p→q)

r

(p∧┐q∧┐r)∨(┐p∧r)∨(q∧r)想想主合取范式如何求？(p→q)

rm1∨m3∨