離散數(shù)學(xué)基礎(chǔ)-第二章-數(shù)理邏輯

第2章數(shù)理邏輯《離散數(shù)學(xué)基礎(chǔ)》——1數(shù)理邏輯部分邏輯學(xué)(1ogic)是研究人類推理規(guī)則（過(guò)程）的科學(xué)。邏輯學(xué)分為兩大流派：傳統(tǒng)邏輯（亞式邏輯）數(shù)理邏輯（符號(hào)邏輯）2傳統(tǒng)邏輯由亞里士多德創(chuàng)立（故稱亞式邏輯），它是從日常生活的經(jīng)驗(yàn)出發(fā)，訓(xùn)練我們?cè)谏钪腥绾问褂酶拍?，以及如何判斷和推理。其推理的主要?guī)則是定言三段論。數(shù)理邏輯(mathematicallogic)則是近代由歐美人創(chuàng)立的，使用的都是抽象的數(shù)學(xué)符號(hào)和數(shù)學(xué)公式，也就是用數(shù)學(xué)的方法來(lái)研究邏輯，所以數(shù)理邏輯又叫符號(hào)邏輯（symbolicLogic）。3邏輯研究的內(nèi)容：

——著重于推理過(guò)程是否正確；

——著重于語(yǔ)句之間的關(guān)系，而不是一個(gè)具體語(yǔ)句的內(nèi)容。例:語(yǔ)句1:所有的數(shù)學(xué)家都穿涼鞋。語(yǔ)句2:任何一個(gè)穿涼鞋的人都是代數(shù)學(xué)家。語(yǔ)句3:所有數(shù)學(xué)家都是代數(shù)學(xué)家。從技術(shù)上來(lái)說(shuō)，邏輯并不幫助確定這些語(yǔ)句是否為真;然而，如果前兩個(gè)語(yǔ)句為真，邏輯可以保證語(yǔ)句3也為真。4傳統(tǒng)邏輯適用于日常生活中的推理；數(shù)理邏輯則偏重演算，適用于計(jì)算機(jī)實(shí)現(xiàn)推理。數(shù)理邏輯是計(jì)算機(jī)軟件理論技術(shù)和硬件邏輯設(shè)計(jì)、人工智能等學(xué)科的重要理論基礎(chǔ)。

程序＝算法＋數(shù)據(jù)

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

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

結(jié)論(一個(gè)或多個(gè)判斷句)

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

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

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

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

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

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

判斷下列句子是不是命題:4是素?cái)?shù)。π是無(wú)理數(shù)。x

大于y。充分大的偶數(shù)等于兩個(gè)素?cái)?shù)之和?；鹦巧嫌猩?。你能幫助我嗎？請(qǐng)不要吸煙！這朵花真美麗啊！我正在說(shuō)假話。10）如果x>y，則x-y>0。（命題）（命題）（命題）（命題）（真值不唯一）（疑問(wèn)句）（祈使句）（感嘆句）（悖論）（命題）10

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

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

3)x,y表示變?cè)鼈儾皇谴_定的對(duì)象（從而導(dǎo)致真值不惟一），所以不是命題。

9)是一個(gè)自相矛盾的病態(tài)語(yǔ)句----稱為悖論，不是命題。11

二、原子命題和復(fù)合命題

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

原子命題中的“原子”取原子的“不可再分”之意,它是最基本的命題,相當(dāng)于自然語(yǔ)言的簡(jiǎn)單陳述句。12

【例】

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

1)王斌貧窮但快樂(lè)。

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

3)如果10是一個(gè)大于１的整數(shù),則10的大于１的最小因數(shù)一定是素?cái)?shù)。13

解

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

P:王斌貧窮。Q:王斌快樂(lè)。

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

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

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

a:10是一個(gè)大于１的整數(shù)。

b:10的大于１的最小因數(shù)是素?cái)?shù)。

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

【示例】

p:4是素?cái)?shù)。（句中的“：”讀作“表示”）

q:1+1=2

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

T或1表示真，用

F或0表示假。示例中p

的真值為0，q

的真值為1，r的真值暫時(shí)還不知道。15

由簡(jiǎn)單命題通過(guò)“非”、“并且”、“或者”、“如果…那么…”等聯(lián)結(jié)詞組合可產(chǎn)生新命題。但在自然語(yǔ)言中出現(xiàn)的聯(lián)結(jié)詞有時(shí)有二義性。因而在數(shù)理邏輯中，必須給出聯(lián)結(jié)詞的嚴(yán)格定義，并且將它們形式化?！?邏輯聯(lián)結(jié)詞16定義設(shè)p是一個(gè)命題,復(fù)合命題“非p”稱為p的否定式,記作┐p。┐稱作否定聯(lián)結(jié)詞。

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

iff

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

iff

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

P：3不是偶數(shù)。(不是3是偶數(shù)?！?Q：今天是星期天。┐Q：今天不是星期天。

R：所有的蘋果都是紅的。┐R：不是所有的蘋果都是紅的。（所有的蘋果都不是紅的。×）19常見(jiàn)錯(cuò)誤：命題的表述不符合日常規(guī)范。例：

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

p：所有的蘋果都是紅的，則┐p表示的命題是什么？常見(jiàn)的錯(cuò)誤答案是：“所有的蘋果都不是紅的”。正確的答案是：“并非所有的蘋果都是紅的”。21定義設(shè)p,q是兩個(gè)命題,復(fù)合命題“p并且q”稱為p與q的合取式，記做p∧q，∧稱為合取聯(lián)結(jié)詞?！啊摹钡淖x法：and

（英）合取、且（中）

p∧q的真值定義為：

p∧q為真

iff

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

iff

p,q都為真。

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

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

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

解首先將原子命題符號(hào)化：

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

R:張輝是三好學(xué)生s:王麗是三好學(xué)生

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

(2)

┐(┐p∧q)(3)r∧s(4)t26關(guān)于命題符號(hào)化需要注意以下兩點(diǎn)：

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

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

q：今天天晴則命題符號(hào)化為：p∧q。

（2）p、q、r等符號(hào)不能用來(lái)代表復(fù)合命題（上例其實(shí)也是這種情況），因?yàn)檫@樣會(huì)掩蓋命題的結(jié)構(gòu)，不利于推理。27定義設(shè)p,q是兩個(gè)命題,復(fù)合命題“p或q”稱為p與q的析取式，記做p∨q，∨稱為析取聯(lián)結(jié)詞?！啊拧钡淖x法：or

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

p∨q為真

iff

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

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

iff

p,q至少有一個(gè)為真29

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

(1)相容或(可兼或)：用它聯(lián)結(jié)的命題具有相容性：命題可以同時(shí)為真，如：張三會(huì)講英語(yǔ)或日語(yǔ)。

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

(2)派小王或小李中的一人去開會(huì)?！疟硎鞠嗳莼?。30注：

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

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

分析：

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

其中p:張三選修了英語(yǔ)課，

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

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

”的讀法：implies,if…then…

（英）蘊(yùn)涵、如果…則…

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

p→q為假

iff

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

p→q為假

iff

p為真而q為假35蘊(yùn)涵詞→是自然語(yǔ)言中的連接詞“如果……,則……”“只要……,就……”“因?yàn)椤?所以……”

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

等的邏輯抽象。

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

37在數(shù)學(xué)和其他自然科學(xué)中，“如果p,則q”往往表達(dá)前件p為真，后件也為真的推理關(guān)系；而在數(shù)理邏輯中，當(dāng)前件p為假，不管后件是真是假，規(guī)定

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

其意思相當(dāng)于：

如果我去麥當(dāng)勞，則我肚子餓了。設(shè)p：我肚子餓了q：我去麥當(dāng)勞則原命題可符號(hào)化為：q→p

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

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

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

【定義】設(shè)P,Q是兩個(gè)命題,復(fù)合命題“P當(dāng)且僅當(dāng)Q”稱為P與Q的等價(jià)式，記做PQ，稱為等價(jià)聯(lián)結(jié)詞。

PQ的真值定義為：

PQ為真

iff

P,Q真值相同因此,P,Q一真一假時(shí),P

Q為假。

“”的讀法：ifandonlyif=

iff

（英）

當(dāng)且僅當(dāng)、等價(jià)

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

43表2-5P

Q真值表

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

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

Q00011011100144【例】

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

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

令

P:北京比天津人口多

Q:2+2=4

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

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

翻譯時(shí),為了減少圓括號(hào),我們對(duì)5個(gè)命題聯(lián)結(jié)詞的強(qiáng)弱次序規(guī)定為

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

網(wǎng)頁(yè)檢索的布爾檢索技術(shù)。大部分網(wǎng)上檢索引擎支持布爾檢索，因?yàn)樗兄谡业接嘘P(guān)特定主題的網(wǎng)頁(yè)。5253第二節(jié)命題公式和分類54若P、Q、R、S為命題，則判斷以下符號(hào)串，哪些構(gòu)成復(fù)雜命題1）┐P→(Q∧┐R)2）(┐P∨┐Q)∧(R→┐s)3）→(┐P→Q)∨(┐∧R∧

┐s)§1命題變?cè)兔}公式怎樣的組合方式才能稱之為命題公式？55一、命題常元與命題變?cè)}常項(xiàng)（命題常元）----表示一個(gè)確定的、具體的簡(jiǎn)單命題的標(biāo)識(shí)符。命題常項(xiàng)有確定的真值,其真值不是０就是１。命題變項(xiàng)（命題變?cè)?---表示任意一個(gè)命題的標(biāo)識(shí)符，以“真、假”或“1、0”為取值范圍,仍用小寫字母表示。一個(gè)命題變?cè)舯荒硞€(gè)確定的命題替代,就具有確定的真值。（參：常數(shù)與變量）

注：1）命題變?cè)皇敲}。（參：整數(shù)變量不是整數(shù)。）

2）

P表示命題常元還是命題變?cè)捎缮稀⑾挛膩?lái)確定。56二、命題公式【定義】

一個(gè)命題公式是由下列規(guī)則所產(chǎn)生的符號(hào)串:1)單個(gè)命題常元或命題變?cè)敲}公式，稱為原子命題公式。

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

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

B)也是命題公式。

4)只有有限次地運(yùn)用1),2),3)所產(chǎn)生的符號(hào)串才是命題公式。57

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

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

(P→Q)→R,(┐PQ)∨(R∧s)58一、命題公式的賦值命題公式的真值情況取決于其所含命題變?cè)恼嬷怠?/p>

【定義】

設(shè)p1,p2,…,pn是出現(xiàn)在公式A中的所有命題變?cè)?，給p1,p2,…,pn各指定一個(gè)真值，稱為對(duì)公式A的一個(gè)真值指派（也稱解釋）。§2

命題公式的賦值和真值表N個(gè)命題變?cè)卸嗌僦胁煌恼嬷抵概桑?9pqp∧q000110110001

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

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

解：分以下4步求得:1)寫出個(gè)命題變?cè)恼嬷抵概桑?/p>

2)寫出公式p∧q的真值表;3)寫出公式┐p的真值表;4)根據(jù)2)和3),寫出公式(p∧q)∧┐p的真值表。為清楚起見(jiàn),我們將這4步列在一個(gè)表內(nèi),見(jiàn)下表。61pqp∧q┐p(p∧q)∧┐p00011011000111000000(p∧q)∧┐p的真值表62構(gòu)造真值表注意事項(xiàng)：命題變?cè)聪聵?biāo)進(jìn)行排列，若無(wú)下標(biāo)，則按字典順序進(jìn)行排列；命題變?cè)娜≈蛋炊M(jìn)制編碼從小到大（或從大到?。┡帕校@樣容易做到“不重不漏”；根據(jù)經(jīng)驗(yàn)，最好是逐列求值，而不是逐行求值，這樣不容易出錯(cuò)；對(duì)于一個(gè)具體的命題公式，其真值表究竟分成幾列，要根據(jù)自己的熟練程度來(lái)定。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【定義】

設(shè)A為一個(gè)命題公式,

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

;

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

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

。§3命題公式的分類67

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

與

。

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

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

【例】證明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練習(xí)用真值表判斷下面兩組公式是否等值：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.結(jié)合律(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.等價(jià)等值式(AB)(A→B)∧(B→A)

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

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

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

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

代入規(guī)則:

在等值式中,將某一命題變?cè)加猛幻}公式代入后,得到的公式仍是等值式（反之不成立）（其正確性請(qǐng)讀者思考，舉反例）。例如,在A→(B→C)(A∧B)→C中,若用公式(S∨R)代替A,則得

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

置換規(guī)則：

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

B,則Φ(A)

Φ(B)

。置換規(guī)則的正確性是由于:A

B,所以對(duì)任一組命題變?cè)恼嬷抵概?A和B的真值都相同,而Φ(A),Φ(B)除A和B以外的部分都相同,因此Φ(A)和Φ(B)的真值都相同,即有Φ(A)

Φ(B)

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

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

1）驗(yàn)證兩個(gè)公式等值

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

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

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

(結(jié)合律)

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

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

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

【示例】

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

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

證：(p→q)→(p→r)┐(┐p∨q)∨(┐p∨r)(蘊(yùn)含等值式)(┐(┐p∨q)∨┐p)∨r(結(jié)合律)

(p∧q)→r(蘊(yùn)含等值式)┐(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(蘊(yùn)含等值式)

((┐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)是一個(gè)重言式。重言式永假式可滿足式85等值演算練習(xí)一、證明下列等價(jià)式。(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：解決實(shí)際問(wèn)題A,B,C,D4人做百米競(jìng)賽，觀眾甲、乙、丙預(yù)報(bào)比賽的名次為：甲：C第一，B第二；乙：C第二，D第三；丙：A第二，D第四比賽結(jié)束后發(fā)現(xiàn)甲、乙、丙每人報(bào)告的情況都是各對(duì)一半，試問(wèn)實(shí)際名次如何（無(wú)并列者）？解：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不能同時(shí)第二，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（補(bǔ)）邏輯等價(jià)的應(yīng)用【例】利用基本的邏輯等價(jià)關(guān)系，化簡(jiǎn)電路圖rpsqpspqrp解：上述電路圖可描述為：((p∧q∧r)∨(p∧q∧s))∧((p∧r)∨(p∧s))90利用基本邏輯等價(jià)式，化簡(jiǎn)公式可得：

((p∧q∧r)∨(p∧q∧s))∧((p∧r)∨(p∧s))=((p∧q∧(r∨s))∧(p∧(r∨s))=p∧q∧(r∨s)；srqp91【例】將下面程序語(yǔ)言進(jìn)行化簡(jiǎn)。ifAthen

ifBthenXelseYelseifBthenXelseYTFFTFTStartAXYEndBB

解：執(zhí)行X的條件為：

(Ａ∧Ｂ)∨(Ａ∧Ｂ)

執(zhí)行Y的條件為：

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

執(zhí)行X的條件可化簡(jiǎn)為：

(Ａ∧Ｂ)∨(Ａ∧Ｂ)＝(Ａ∨Ａ)∧Ｂ＝Ｂ執(zhí)行Y的條件可化簡(jiǎn)為：

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

那個(gè)大？（2）兩個(gè)形式不同的命題公式是否等值？（3）為什么要有范式？為命題公式制定一種標(biāo)準(zhǔn)表達(dá)形式，使得命題公式的成真或成假賦值一目了然?！?范式94要了解什么是范式,先得介紹組成范式的基本成分——簡(jiǎn)單合取式和簡(jiǎn)單析取式。

【定義】

僅由命題變?cè)蛎}變?cè)姆穸ㄋM成的析取式稱為簡(jiǎn)單析取式，僅由命題變?cè)蛎}變?cè)姆穸ㄋM成的合取式稱為簡(jiǎn)單合取式。一、范式95

若p,q,r是命題變?cè)?則

p,q,r,┐p,┐q∧r,r∧┐r,p∧q∧r,p∧┐q∧┐p等都是簡(jiǎn)單合取式;p,q,r,┐p,┐p∨r,p∨┐r,p∨q∨r,p∨┐q∨┐p等都是簡(jiǎn)單析取式。96

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

注意：一個(gè)簡(jiǎn)單合取式為即為析取范式，又為合取范式。97公式A的析取范式常用來(lái)判定A是否是矛盾式;

公式A的合取范式常用來(lái)判定A是否是重言式。

【定理】(1)一個(gè)析取范式為矛盾式當(dāng)且僅當(dāng)它的每個(gè)簡(jiǎn)單合取式都是矛盾式。

(2)一個(gè)合取范式為重言式當(dāng)且僅當(dāng)它的每個(gè)簡(jiǎn)單析取式都是重言式。

98

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

從定義可知,一個(gè)范式有以下特征:1)不含蘊(yùn)含聯(lián)結(jié)詞→和等價(jià)聯(lián)結(jié)詞

;2)不含雙重否定┐┐;3)否定詞┐僅出現(xiàn)在命題變?cè)?4)析取范式是簡(jiǎn)單合取式的析取,而合取范式是簡(jiǎn)單析取式的合取。

所以,求一個(gè)公式的范式就是求滿足以上四點(diǎn)的公式。其具體步驟是:

991)消去聯(lián)結(jié)詞→和:

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)使┐出現(xiàn)在命題變?cè)?┐(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二、主范式為使范式惟一,我們引入了一種特殊的范式——主范式。主范式的基本成分是特殊的簡(jiǎn)單合取式和簡(jiǎn)單析取式,它們分別稱為極小項(xiàng)和極大項(xiàng)。

1、極小項(xiàng)和極大項(xiàng)【定義】

設(shè)有n個(gè)命題變?cè)猵1,p2,…,pn,則簡(jiǎn)單合取式p1′∧p2′∧…pn′稱為由n個(gè)命題變?cè)a(chǎn)生的極小項(xiàng)，簡(jiǎn)單析取式p1′∨p2′∨…pn′

稱為由n個(gè)命題變?cè)猵1,p2,…,pn所產(chǎn)生的極大項(xiàng)。其中pi′或?yàn)閜i或?yàn)椹磒i（i=1,2,…,n）。105極大、極小項(xiàng)的特征：極小項(xiàng)————n個(gè)變?cè)恢夭宦┑暮?jiǎn)單合取式極大項(xiàng)————n個(gè)變?cè)恢夭宦┑暮?jiǎn)單析取式示例：若有三個(gè)命題變?cè)猵,q,r,則p∧q∧r,p∧┐q∧r,┐p∧q∧┐r等是由p,q,r所產(chǎn)生的極小項(xiàng);p∨q∨r,

p∨┐q∨r,┐p∨q∨┐r等是由p,q,r所產(chǎn)生的極大項(xiàng)。一般地,由ｎ個(gè)命題變?cè)a(chǎn)生的全部不同的極小項(xiàng)和極大項(xiàng)都是2n個(gè)。106

每個(gè)極小項(xiàng)p1′∧p2′∧…pn′都有且僅有一個(gè)成真賦值，不妨假設(shè)其對(duì)應(yīng)的二進(jìn)制數(shù)為δ1δ2……δn

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

每個(gè)極大項(xiàng)p1′∨p2′∨

…pn′

都有且僅有一個(gè)成假賦值，不妨假設(shè)其對(duì)應(yīng)的二進(jìn)制數(shù)為δ1δ2……δn

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

的取值規(guī)則極小項(xiàng)與極小項(xiàng)時(shí)正好相反107

如果一個(gè)極小項(xiàng)對(duì)應(yīng)的二進(jìn)制數(shù)為δ1δ2…δn，則將對(duì)應(yīng)的十進(jìn)制數(shù)r作為該極小項(xiàng)的序號(hào)，并將該極小項(xiàng)簡(jiǎn)記為mr。顯然r從０取到2n－1。以３個(gè)命題變?cè)猵1,p2,p3為例,極小項(xiàng)┐p1∧┐p2∧┐p3對(duì)應(yīng)的二進(jìn)制數(shù)為000,其序號(hào)為０，用m0表示;極小項(xiàng)┐p1∧p2∧p3對(duì)應(yīng)的二進(jìn)制數(shù)為011,其序號(hào)為3，用m3表示。反之,如果要求m5對(duì)應(yīng)的極小項(xiàng)，因?yàn)樾蛱?hào)5對(duì)應(yīng)的二進(jìn)制數(shù)為101，所以該極小項(xiàng)是p1∧┐p2∧p3。由此可見(jiàn),極小項(xiàng)與其序號(hào)一一對(duì)應(yīng)。1088個(gè)極小項(xiàng)對(duì)應(yīng)情況如下：極小項(xiàng)成真賦值記號(hào)┐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極小項(xiàng)的性質(zhì)：(1)對(duì)一個(gè)含有n個(gè)變項(xiàng)的公式來(lái)說(shuō),所有可能的極小項(xiàng)個(gè)數(shù)和該公式的解釋個(gè)數(shù)一樣多,都是2n

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

類似地，如果一個(gè)極大項(xiàng)對(duì)應(yīng)的二進(jìn)制數(shù)為δ1δ2…δn，就將對(duì)應(yīng)的十進(jìn)制數(shù)r作為該極大項(xiàng)序號(hào)，并將該極大項(xiàng)簡(jiǎn)記為Mr。顯然r從０到2n－1。以３個(gè)命題變?cè)狿1,P2,P3為例,

極大項(xiàng)p1∨p2∨p3對(duì)應(yīng)的二進(jìn)制數(shù)為000,其序號(hào)為０，用M0表示；極大項(xiàng)┐p1∨p2∨p3對(duì)應(yīng)的二進(jìn)制數(shù)為100,其序號(hào)為4，用M4表示。反之,如果要求M5對(duì)應(yīng)的極大項(xiàng)，因?yàn)樾蛱?hào)5對(duì)應(yīng)的二進(jìn)制數(shù)為101，所以該極大項(xiàng)是┐p1∨p2∨┐p3。由此可見(jiàn),極大項(xiàng)與其序號(hào)一一對(duì)應(yīng)。1118個(gè)極大項(xiàng)對(duì)應(yīng)情況如下：極大項(xiàng)成假賦值記號(hào)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極大項(xiàng)的性質(zhì)：對(duì)一個(gè)含有n個(gè)變項(xiàng)的公式來(lái)說(shuō),所有可能的極大項(xiàng)個(gè)數(shù)和該公式的解釋個(gè)數(shù)一樣多,都是2n

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

1132、極小項(xiàng)與極大項(xiàng)的關(guān)系

【定理】設(shè)mi與Mi是有命題變?cè)猵1,p2,…pn形成的極小項(xiàng)和極大項(xiàng)，則┐mi

Mi，

┐

Mi

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

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

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

【定理】（存在唯一性）

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

(1)真值表方法

(2)公式化歸法-----等值推演方法下面先通過(guò)例子來(lái)說(shuō)明真值表方法。

【例】

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

m1∨

m3

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

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

找出所有的成真賦值，其對(duì)應(yīng)的極小項(xiàng)即為該公式的主析取范式中所含的所有極小項(xiàng)3)

找出所有的成假賦值，其對(duì)應(yīng)的極大項(xiàng)即為該公式的主合取范式中所含的所有極大項(xiàng)；4)

從而可立即寫出兩個(gè)主范式。117

【例】

求命題公式(p→q)

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

pqrp→q(p→

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

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

→r2）p

(q∧r)

120

用真值表方法我們能求出一個(gè)公式惟一的主范式,然而這個(gè)方法僅對(duì)命題變?cè)獋€(gè)數(shù)較少時(shí)可行。因?yàn)橹鞣妒绞且环N范式,但又具有特殊性,所以我們對(duì)主范式介紹一種類似于求范式的方法－－公式化歸法：先求范式，再求主范式。用公式化歸法求一個(gè)公式A的主范式的過(guò)程如下:1)～4)步同于求范式的四步,求出A的析取范式或合取范式;5)利用同一律、排中律將析取范式中所有矛盾的簡(jiǎn)單合取式消去，將所有重言的簡(jiǎn)單析取式消去。1216)利用冪等律合并析取范式中相同的簡(jiǎn)單合取式以及合取范式中相同的簡(jiǎn)單析取式,同時(shí)合并簡(jiǎn)單合取式和簡(jiǎn)單析取式中相同的命題變?cè)?/p>

7)由PP∧(Q∨┐Q)可以將簡(jiǎn)單合取式中沒(méi)有出現(xiàn)的命題變?cè)猀補(bǔ)充進(jìn)去;由PP∨(Q∧┐Q)可以將簡(jiǎn)單析取式中沒(méi)有出現(xiàn)的命題變?cè)猀補(bǔ)充進(jìn)去。

8)利用分配律展開公式,并除去相同的小項(xiàng)和大項(xiàng),由此求得公式的主范式。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∨