命題公式的范式

1、第一章 命題與邏輯 11.5命題公式的范式在命題邏輯中，判斷兩個(gè)命題公式是否等價(jià)是非常重要的事。以前我們多次提到，每一個(gè)命題公式都有無(wú)窮多個(gè)命題公式與之等價(jià)，它們的形式也可能是大相徑庭的。本節(jié)我們引進(jìn)命題公式的標(biāo)準(zhǔn)化，即使之等價(jià)于標(biāo)準(zhǔn)形式的命題公式，以致兩個(gè)命題公式等價(jià)當(dāng)且僅當(dāng)它們的標(biāo)準(zhǔn)形式一樣。這樣根據(jù)命題公式的形式，就可以判斷兩個(gè)命題公式是否等價(jià)。這和線性代數(shù)中二次型的合同標(biāo)準(zhǔn)形是類似的。2一、合取范式和析取范式定義 1.5.1 命題變?cè)捌浞穸ǚQ為文字。定義1.5.2 有限個(gè)文字的合取式稱為簡(jiǎn)單合取式，其中每個(gè)文字稱為合取項(xiàng)。有限個(gè)文字的析取式稱為簡(jiǎn)單析取式，其中每個(gè)文字稱為析取項(xiàng)。由定

2、義，文字既是簡(jiǎn)單合取式，又是簡(jiǎn)單析取式。 3 例1.5.1 , 都是簡(jiǎn)單合取式 , 都是簡(jiǎn)單析取式。 4定理1.5.1 (1)簡(jiǎn)單合取式是矛盾式的充要條件是它包含兩個(gè)分別為某個(gè)命題變?cè)捌浞穸ǖ暮先№?xiàng)。(2)簡(jiǎn)單析取式是重言式的充要條件是它包含兩個(gè)分別為某個(gè)命題變?cè)捌浞穸ǖ奈鋈№?xiàng)。 5證明 我們只證(2), (1)的證明是類似的。充分性 對(duì)命題變?cè)狿, PP為重言式。所以如果簡(jiǎn)單析取式中含有PP, 那么此簡(jiǎn)單析取式必是重言式。必要性 假設(shè)某簡(jiǎn)單析取式是重言式，并設(shè)其所含的命題變?cè)獮镻1,P2, ,Pn。如果此簡(jiǎn)單析取式中不存在兩個(gè)析取項(xiàng)分別為某個(gè)命題變?cè)捌浞穸?，那么它等價(jià)于P1*P2*Pn

3、*, 其中每個(gè)Pi*都為文字 Pi或Pi。顯然, 有個(gè)真值指派使每個(gè)Pi*取值都為0, 那么在此真值指派下, 此簡(jiǎn)單析取式取值為0, 矛盾于它是重言式。 6定義1.5.3 有限個(gè)簡(jiǎn)單合取式的析取式稱為析取范式。由定義，命題公式A為析取范式當(dāng)且僅當(dāng)A=A1A2An, (n1)，其中每個(gè)Ai都為簡(jiǎn)單合取式。定義1.5.4 有限個(gè)簡(jiǎn)單析取式的合取式稱為合取范式。由定義，命題公式A為合取范式當(dāng)且僅當(dāng)A=A1A2An, (n1), 其中每個(gè)Ai都為簡(jiǎn)單析取式。7由定義，下面的結(jié)論是顯然的:(1) 簡(jiǎn)單析取式和簡(jiǎn)單合取式都既是析取范式，又是合取范式。(2) 析取范式與合取范式都僅含聯(lián)結(jié)詞 , 和。析取范式

4、的對(duì)偶式是合取范式，合取范式的對(duì)偶式是析取范式。8例1.5.2 為析取范式, 為合取范式。 定理1.5.2 (范式存在定理) 對(duì)任一命題公式，都存在與之等價(jià)的析取范式和合取范式。9證明 (構(gòu)造性證明)下面給出求解等價(jià)于給定命題公式的范式的步驟：(1) 消除給定命題公式中的聯(lián)結(jié)詞和, 使之等價(jià)于僅含聯(lián)結(jié)詞, , 和的命題公式。利用等價(jià)關(guān)系和置換規(guī)則： 將子公式AB置換成AB 。 將子公式AB置換成(AB)(AB) 或 (AB)(AB) 。(2)將聯(lián)結(jié)詞向內(nèi)深入到命題變?cè)懊?。利用等價(jià)關(guān)系和置換規(guī)則： 將子公式 (AB)和(AB) 分別置換成AB 和 AB。 將子公式A置換成A。(3）利用結(jié)合律和

5、分配律將命題公式變成所要的范式。 10習(xí)慣上，我們稱與命題公式A等價(jià)的析取范式(或合取范式)為A的析取范式(或合取范式)。顯然，A的析取范式(或合取范式)不是唯一的。例如P, P(PP)和P(QQ) 都是A的析取范式。 11例1.5.3 求命題公式 的析取范式和合取范式。解 （合取范式） （析取范式） （析取范式） 12定理1.5.3 (1)命題公式A為矛盾式的充要條件是A的析取范式中每個(gè)簡(jiǎn)單合取式包含兩個(gè)分別為某個(gè)命題變?cè)捌浞穸ǖ暮先№?xiàng)。(2)命題公式A為重言式的充要條件是A的合取范式中每個(gè)簡(jiǎn)單析取式包含兩個(gè)分別為某個(gè)命題變?cè)捌浞穸ǖ奈鋈№?xiàng)。 13證明 我們只證(1)，(2)的證明是類似

6、的。設(shè)A的任一析取范式為A1A2An, 其中每個(gè)Ai為簡(jiǎn)單合取式。充分性 因?yàn)槊總€(gè)Ai都包含兩個(gè)分別為某個(gè)命題變?cè)捌浞穸ǖ暮先№?xiàng)，所以由定理1.5.1, 每個(gè)Ai 都為矛盾式，因而A為矛盾式。必要性假設(shè)A為矛盾式，因?yàn)槊總€(gè)Ai蘊(yùn)涵 A， 所以由定理1.3.9每個(gè)Ai都為矛盾式。再由定理1.5.1得證。14例1.5.3 判斷下面兩個(gè)命題公式的類型。 (1)(2)15解 (1) 上面的合取范式中第一個(gè)簡(jiǎn)單析取式含P與P，第二個(gè)簡(jiǎn)單析取式含R與R。所以(1)為重言式。16(2) （析取范式） （合取范式）上面的析取范式和合取范式都不滿足定理1.5.3的條件，因而既不是重言式，又不是矛盾式，它是可滿

7、足式。17 二 、主范式雖然命題公式的范式為判別其類型帶來(lái)了一定的方便，但因?yàn)槠湫问降牟晃ㄒ恍?，所以我們往往還不能僅從比較兩個(gè)命題公式A和B的范式的形式(而不是看或的范式的形式)來(lái)判別A和B的等價(jià)或蘊(yùn)涵關(guān)系。為此我們需要引進(jìn)主范式的概念。 18定義 1.5.5 設(shè)P1,P2, ,Pn為n個(gè)命題變?cè)? 稱簡(jiǎn)單合取式 P1*P2*Pn* 為由命題變?cè)?P1,P2, ,Pn 所產(chǎn)生的小項(xiàng), 稱簡(jiǎn)單析取式。P1*P2*Pn* 為由命題變?cè)狿1,P2, ,Pn 所產(chǎn)生的大項(xiàng), 其中每個(gè) Pi*為文字Pi或 Pi 。記小項(xiàng)P1*P2*Pn* 為 , 其中, 如果 Pi*為文字Pi , 那么 ; 如果 Pi

8、*為文字Pi, 那么 。記大項(xiàng)P1*P2* Pn* 為 , 其中,如果 Pi*為文字Pi , 那么 ; 如果 Pi*為文字Pi, 那么 。 19 有時(shí)為了方便起見(jiàn)，我們也記 和 分別為mk和Mk, 其中k為由二進(jìn)制數(shù) 轉(zhuǎn)化的十進(jìn)制數(shù)。表1.5.1和表1.5.2列出了n=2時(shí)所有小項(xiàng)和大項(xiàng)的真值表。20表1.5.1 21表1.5.2 22由表1.5.1可以得到小項(xiàng)有如下的性質(zhì)：（1）n個(gè)命題變?cè)蓸?gòu)成2n個(gè)小項(xiàng)。（2）任意兩個(gè)小項(xiàng)的合取式為矛盾式，所有小項(xiàng)的析取式為重言式。（3）小項(xiàng) 在給每個(gè)Pi 以真值 的這一組真值指派下取值為1，在其余2n-1組真值指派下取值為0。 23由表1.5.2可以得

9、到大項(xiàng)有如下的性質(zhì)：（1）n個(gè)命題變?cè)蓸?gòu)成2n個(gè)大項(xiàng)。（2）任意兩個(gè)大項(xiàng)的合取式為矛盾式，所有大項(xiàng)的析取式為重言式。（3）大項(xiàng) 在給每個(gè)Pi 以真值 的這一組真值指派下取值為0，在其余2n-1組真值指派下取值為1。 24定義1.5.6 設(shè)P1,P2, ,Pn為n個(gè)命題變?cè)纱薾個(gè)命題變?cè)a(chǎn)生的互不相同的小項(xiàng)所構(gòu)成的析取范式稱為由P1,P2, ,Pn所產(chǎn)生的主析取范式。由此n個(gè)命題變?cè)a(chǎn)生的互不相同的大項(xiàng)所構(gòu)成的合取范式稱為由P1,P2, ,Pn所產(chǎn)生的主合取范式。顯然主析取范式不為矛盾式，主合取范式不為重言式。 25定理1.5.4 (主范式存在定理) 設(shè)A為命題變?cè)荚诩螾1,P2,

10、 ,Pn 中的命題公式。(1)如果A不為矛盾式,那么A等價(jià)于一個(gè)由P1,P2, ,Pn 所產(chǎn)生的主析取范式, 稱之為A關(guān)于P1,P2, ,Pn 的主析取范式, 進(jìn)一步如果A=A(P1,P2, ,Pn), 簡(jiǎn)稱為A的主析取范式。(2)如果A不為重言式,那么A等價(jià)于一個(gè)由P1,P2, ,Pn 所產(chǎn)生的主合取范式, 稱之為A關(guān)于P1,P2, ,Pn 的主合取范式，進(jìn)一步如果A=A(P1,P2, ,Pn ), 簡(jiǎn)稱為A的主合取范式。26證明 (構(gòu)造性證明) 首先由定理1.5.2，可以得到A的析取范式和合取范式。繼續(xù)進(jìn)行構(gòu)造，便可得到A關(guān)于P1,P2, ,Pn的主析取范式和主合取范式。我們?cè)诖藘H就(1)

11、進(jìn)行構(gòu)造證明，(2)的證明是類似的。設(shè)A*是A的析取范式。(1) 擴(kuò)展: 如果A*的某個(gè)簡(jiǎn)單合取式B不含命題變?cè)?及其否定Pi, 那么利用置換規(guī)則, 用BPi(BPi)置換B。(2) 削去: 將重復(fù)出現(xiàn)的命題變?cè)苁胶椭貜?fù)出現(xiàn)的小項(xiàng)都削去。(3) 排序: 將小項(xiàng)按下標(biāo)從小到大的順序排列。 27由小項(xiàng)和大項(xiàng)的性質(zhì)，容易得到下面用A=A(P1,P2, ,Pn )的真值表來(lái)求A的主范式的方法:(1) A的主析取范式為所有與A在同一組關(guān)于P1,P2, ,Pn 的真值指派下都取值為1的由P1,P2, ,Pn 所產(chǎn)生的小項(xiàng)所構(gòu)成的析取范式。(2) A的主合取范式為所有與A在同一組關(guān)于P1,P2, ,P

12、n 的真值指派下都取值為0的由P1,P2, ,Pn 所產(chǎn)生的大項(xiàng)所構(gòu)成的合取范式。 28例1.5.3 求命題公式(PQ) P的主析取范式和主合取范式解一 （主析取范式） （主合取范式）29表1.5.3 解二 30因?yàn)榕c(PQ) P 在同一組真值指派下都取值為1的小項(xiàng)只有m11, 與(PQ) P在同一組真值指派下都取值為0的所有大項(xiàng)是M00, M01, M10, 所以31小項(xiàng)和大項(xiàng)之間有如下的關(guān)系，有興趣的讀者可以自己給出其證明：(1) 設(shè)A=A(P1,P2, ,Pn)為命題公式， 和 為集合0,1,2, . , 2n-1的兩個(gè)子集。如果 那么 0,1,2, . , 2n-1。 32 定理1.5

13、.4 (范式唯一性定理) 設(shè)A為命題變?cè)荚诩螾1,P2, ,Pn中的命題公式，如果不計(jì)其中小項(xiàng)（或大項(xiàng)）的排列次序，那么A關(guān)于P1,P2, ,Pn的主析取范式（或主合取范式）是唯一的。33證明 (反證法) 我們只證主析取范式情形。假設(shè)A有兩個(gè)不同的關(guān)于P1,P2, ,Pn的主析取范式A1和A2, 那么至少有一個(gè)小項(xiàng), 如mi, 只出現(xiàn)在A1和A2之一中, 不妨設(shè)在A1中。那么在使mi成真的真值指派下A1為真，而A2為假。矛盾于A1等價(jià)于A2。34下面兩個(gè)定理是主范式在證明等價(jià)關(guān)系與蘊(yùn)涵關(guān)系和判別命題公式類型上的應(yīng)用，留給讀者給出其證明。 35定理1.5.5 設(shè)A和B為兩個(gè)命題變?cè)荚诩螾1,P2, ,Pn中的命題公式，那么AB的充要條件是A和B有相同的關(guān)于P1,P2, ,Pn的主析取范式或主合取范式。特別地，A為重言式的充要條件是A關(guān)于P1,P2, ,Pn的主析取范式含有所有的2n個(gè)小項(xiàng)；A為矛盾式的充要條件是A關(guān)