主析取范式的求法課件

第一章命題邏輯第七講定義對(duì)于給定的命題公式，如果有一個(gè)等價(jià)公式僅由小項(xiàng)的析取所組成，則該等價(jià)式稱為原式的主析取范式。內(nèi)容回顧小項(xiàng)定義n個(gè)命題變?cè)暮先∈?，稱為布爾合取或小項(xiàng)，其中每個(gè)變?cè)c它的否定不能同時(shí)存在，但兩者必須出現(xiàn)且僅出現(xiàn)一次。

每個(gè)小項(xiàng)可用n位二進(jìn)制編碼表示。以變?cè)陨沓霈F(xiàn)的用1表示，以其否定出現(xiàn)的用0表示：小項(xiàng)的性質(zhì)如下：（1）每一個(gè)小項(xiàng)當(dāng)其真值指派與編碼相同時(shí)，其真值為1，其余的2n－1種均為0;（2）任意兩個(gè)不同小項(xiàng)的合取式永假：（3）全體小項(xiàng)的析取式永為真，記為：趣味推理題A、B、C三人去餐館吃飯，他們每人要的不是火腿就是豬排。

（1）如果A要的是火腿，那么B要的就是豬排。

（2）A或C要的是火腿，但是不會(huì)兩人都要火腿。

（3）B和C不會(huì)兩人都要豬排。

誰(shuí)昨天要的是火腿，今天要的是豬排？只有B才能昨天要火腿，今天要豬排。

1．5．4主合取范式定義1-n個(gè)命題變?cè)奈鋈∈剑Q為布爾析取或極大項(xiàng)，其中每個(gè)變?cè)c它的否定不能同時(shí)存在，但兩者必須出現(xiàn)且僅出現(xiàn)一次。例如，2個(gè)命題變?cè)猵和Q的大項(xiàng)為：3個(gè)命題變?cè)猵、Q、R的大項(xiàng)為：

n個(gè)命題變?cè)灿?n個(gè)大項(xiàng)，每個(gè)大項(xiàng)可表示為n位二進(jìn)制編碼，以變?cè)陨沓霈F(xiàn)的用0表示，以變?cè)姆穸ǔ霈F(xiàn)的用1表示；且對(duì)應(yīng)十進(jìn)制編碼。這一點(diǎn)與小項(xiàng)的表示剛好相反。若n=2，則有定義1-對(duì)于給定的命題公式，如果有一個(gè)等價(jià)公式僅由極大項(xiàng)的合取所組成，則該等價(jià)式稱為原式的主合取范式。定理1-（主合取范式存在惟一定理）任何命題公式的主合取范式一定存在，并且惟一。

由真值表方法可知：一個(gè)公式的真值為0的真值指派所對(duì)應(yīng)的大項(xiàng)的合取，即為此公式的主合取范式。例1-用真值表方法求的主合取范式解:公式的真值表如下PQRP→Q

?R(p→Q)→?R000001010011100101110111111100111010101010101110所以公式的主合取范式為:用等值演算方法構(gòu)成主合取范式的主要步驟如下：（1）將原命題公式化歸為合取范式；（2）除去合取范式中所有永真的合取項(xiàng)；（3）合并相同的析取項(xiàng)和相同的變?cè)唬?）對(duì)合取項(xiàng)補(bǔ)入沒有出現(xiàn)的命題變?cè)?，即添加?p∧┐p)的式子，再按分配律進(jìn)行演算；（5）將大項(xiàng)按下標(biāo)由小到大的順序排列。例1-用等值演算方法求的主合取范式。解：極小項(xiàng)與極大項(xiàng)由p,q兩個(gè)命題變項(xiàng)形成的極小項(xiàng)與極大項(xiàng)

公式

成真賦值名稱

公式

成假賦值名稱

p

qp

qp

qp

q00011011m0m1m2m3

p

q

p

q

p

q

p

q

00011011

M0M1M2M3

極小項(xiàng)

極大項(xiàng)

由p,q,r三個(gè)命題變項(xiàng)形成的極小項(xiàng)與極大項(xiàng)

極小項(xiàng)

極大項(xiàng)

公式

成真賦值名稱

公式

成假賦值名稱

pq

rpq

rpq

rpq

rpq

rpq

rpq

rpq

r000001010011100101110111m0m1m2m3m4m5m6m7p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

000001010011100101110111M0M1M2M3M4M5M6M7

證明：所以P∧(p→Q)?Q下面介紹幾種證明A永真蘊(yùn)含B的方法。方法一：用真值表法或等價(jià)變換(推導(dǎo))法證明A→B?1。例1-24證明。PQP→QP∧(P→Q)(P∧(P→Q))→Q00011011110100011111方法二：通過分析的方法來(lái)證明一個(gè)條件命題是蘊(yùn)含式。由于原命題等于其逆反命題，即A→B?┐B→┐A，所以用分析法證明A?B，有如下兩種方法:(1)假設(shè)前件A為真時(shí),推出后件B也為真,則A?B;

(2)假設(shè)后件B為假時(shí),推出前件A也為假,則A?B

。例1-26如果我認(rèn)真學(xué)習(xí)，我的“離散數(shù)學(xué)”不會(huì)不及格，如果我不熱衷于玩電子游戲，我將認(rèn)真學(xué)習(xí)，但我的“離散數(shù)學(xué)”不及格。結(jié)論：我熱衷于玩電子游戲。證明：設(shè)P：我認(rèn)真學(xué)習(xí)。Q：我的“離散數(shù)學(xué)”及格。R：我熱衷于玩電子游戲。常見的蘊(yùn)含重言式析取三段論假言推論拒取式假言三段論二難推論化簡(jiǎn)式一附加式化簡(jiǎn)式二例1-27分析證明。證明：假設(shè)后件為0，則P為1，R為0。(a)若Q為1，則為0，所以為0；(b)若Q為0，則為0，所以為0。故此：成立。1.8推理理論邏輯學(xué)的主要任務(wù)是提出一套推理規(guī)則，按照公認(rèn)的推理規(guī)則從前提集合中推導(dǎo)出一個(gè)結(jié)論來(lái)，這個(gè)推理過程稱為演繹或形式證明。在一般的論證中，主要是根據(jù)實(shí)踐經(jīng)驗(yàn)。如果確認(rèn)前提為真，并遵守恰當(dāng)?shù)耐评硪?guī)則，則可期望所得的結(jié)論也是真的。倘若認(rèn)定前提是真的，從前提推導(dǎo)出結(jié)論的論證是遵守邏輯推理規(guī)則，且公認(rèn)此結(jié)論是真實(shí)的，則這個(gè)論證稱為合法論證。一般論證中必須特別注意論證的合法性。所謂合法是指前提和結(jié)論都符合客觀實(shí)際情況，大家公認(rèn)是真實(shí)的。即合情、合理、合法，令人信服。

在數(shù)理邏輯中情況稍有不同，它把注意力集中在推理規(guī)則的研究上，如果依據(jù)這些推理規(guī)則，從前提推導(dǎo)出來(lái)的任何結(jié)論都稱為有效結(jié)論，這種論證稱為有效論證。在確認(rèn)論證有效性時(shí)，前提與結(jié)論的真實(shí)性不起任何作用，也就是說(shuō)，在數(shù)理邏輯中，只關(guān)心論證的有效性，而不大關(guān)心論證的合法性。

前提：如果馬會(huì)飛或羊吃草，則母雞就會(huì)是飛鳥；如果母雞是飛鳥，那么烤熟的鴨子還會(huì)跑；烤熟的鴨子不會(huì)跑。結(jié)論：羊不吃草。

利用真值表判別一個(gè)有效論證的方法：方法一：在真值表上，若前提H1,H2,H3,…Hn均為真的所有行，結(jié)論C也為真，則論證有效。方法二：在真值表上，若結(jié)論C為假的每一行，其前提

H1,H2,H3,…Hn中至少有一個(gè)為假，則論證有效。例1-28如果我認(rèn)真學(xué)習(xí)，我的“離散數(shù)學(xué)”不會(huì)不及格，如果我不熱衷于玩電子游戲，我將認(rèn)真學(xué)習(xí)，但我的“離散數(shù)學(xué)”不及格。結(jié)論：我熱衷于玩電子游戲。P:我認(rèn)真學(xué)習(xí)，Q:我的“離散數(shù)學(xué)”及格，R:我熱衷于玩電子游戲。符號(hào)化為：其真值表如下：解：判斷法一：真值表中，只有第2行的前提都為1，其結(jié)論也為1，所以論證有效。判斷法二：真值表中，第1、3、5、7行為0，每行的前提至少有一個(gè)為0，所以論證有效。PQR?Rp→Q?R→p?QR000001010011100101110111101010101

111

0011

0

1

0111111

1

0011

00

0

1

01

01

01pqp→q﹁p﹁q00111011101000111100（二）構(gòu)造證明法

(1)推理規(guī)則常用的推理規(guī)則有：P規(guī)則：在推導(dǎo)的任意一步都可以引入一個(gè)前提。T規(guī)則：如果公式S等價(jià)于或被重言蘊(yùn)含在一個(gè)或多個(gè)前提或中間結(jié)果命題中，則推導(dǎo)中可以引入S。CP規(guī)則：如果能從R及一組前提推導(dǎo)出C，則可從這組前提推導(dǎo)出R→C。設(shè)前提若則

(2)推理定律

在推導(dǎo)過程除推理規(guī)則外,還需要推理定律,這些推理定律就是前面所講的常用的蘊(yùn)含式（用I表示）和命題定律（用E表示）?，F(xiàn)在將蘊(yùn)含式和命題定律再次顯示如下?；?jiǎn)1