【正文】 范式： ?方法 1：真值表法 ?真值表中使公式 A為假的指派所對(duì)應(yīng)的大項(xiàng)組成的合取式即為 A的主合取范式。 ?有了對(duì)大項(xiàng)的充分討論，下面我們研究主合取范式的概念、性質(zhì)與求法。即其它任何指派都使此大項(xiàng)為真。如 ┐P∨ Q的編碼為 M10，P∨ ┐Q∨ R的編碼為 M010，因此大項(xiàng)與編碼是一一對(duì)應(yīng)的，編碼為 M101的小項(xiàng)為┐P∨ Q∨ ┐R。這樣每個(gè)大項(xiàng)就對(duì)應(yīng)一個(gè) n位二進(jìn)制數(shù)。 ? 由于含有 n個(gè)變?cè)拿總€(gè)大項(xiàng)都是 n項(xiàng)的析取，而每一項(xiàng)或者是變?cè)霈F(xiàn)或者是變?cè)穸ǔ霈F(xiàn)。那么什么是大項(xiàng)，大項(xiàng)又有什么性質(zhì)呢？ ? 定義 在含 n個(gè)變?cè)奈鋈∈街?，若每個(gè)變?cè)c其否定二者必出現(xiàn)且僅出現(xiàn)一個(gè)，則稱此析取式為含n個(gè)變?cè)?大項(xiàng) 。 ?下面我們對(duì)應(yīng)地介紹主合取范式。 ?方法 2：等價(jià)變形法 ?例 用等價(jià)變形法求 P → Q 的主析取范式 ?解： P → Q ? ?P∨ Q（這是析取范式。其道理不難從小項(xiàng)的性質(zhì)得出這樣的主析取范式與 A等價(jià)，因而可作為 A的主析取范式。 ?定義 對(duì)一析取范式，若其每一個(gè)合取式均為小項(xiàng)時(shí)，即是 主析取范式（ majordisjunctive normal form）。如小項(xiàng) m101只在指派101時(shí)為真，其它指派都是假。 ? 再來看看小項(xiàng)的性質(zhì)，我們從它們的真值表去分析：（表 8 .12 和表 8 .13分別是兩個(gè)變?cè)男№?xiàng)與三個(gè)變?cè)男№?xiàng)真值表） ?由上兩個(gè)小項(xiàng)真值表不難看出，小項(xiàng)具有如下性質(zhì)： ?任兩小項(xiàng)均不等價(jià)； ?每個(gè)小項(xiàng)有且僅有一組指派使其真值為真，且恰當(dāng)指派與小項(xiàng)編碼一致時(shí)。那么這個(gè)小項(xiàng)的編碼就用 m帶上這個(gè) n位二進(jìn)制數(shù)為右下標(biāo)組成。 ? 我們約定：當(dāng)變?cè)霈F(xiàn)時(shí)相應(yīng)位置記為“ 1”；當(dāng)變?cè)穸ǔ霈F(xiàn)時(shí)相應(yīng)位置記為“ 0”。 ? 如：兩個(gè)變?cè)?P， Q能夠組成的小項(xiàng)有： 4 = 22 個(gè) ? P∧ Q， P∧ ┐Q， ┐P∧ Q， ┐P∧ ┐Q ? 三個(gè)變?cè)?P， Q， R能夠組成的小項(xiàng)有： 8 = 23 個(gè) ? P∧ Q∧ R， ┐P∧ Q∧ R， P∧ ┐Q∧ R， P∧ Q∧ ┐R，┐P∧ ┐Q∧ R， ┐P∧ Q∧ ┐R， P∧ ┐Q∧ ┐R，┐P∧ ┐Q∧ ┐R ? 因此， n個(gè)變?cè)軌蚪M成的小項(xiàng)有 2N個(gè) . ? 我們知道 2N隨 n的增長(zhǎng)速率很快，下面討論一下對(duì)小項(xiàng)編碼問題。 主析取范式與主合取范式 主析取范式 ?主析取范式與析取范式的區(qū)別就在于對(duì)析取范式中的合取式有更嚴(yán)格的要求，即要達(dá)到都是小項(xiàng)。又如 ┐P∨ Q既可稱為 P→Q 的析取范式，又可稱為它的合取范式。 ?我們已經(jīng)發(fā)現(xiàn)，一公式的析取范式和合取范式可能不是唯一的，例如 ?另一方面，一公式的合取范式與析取范式又可能是同一的。 ? 解： ┐(P∨ Q) ? (P∧ Q) ? ?（ ┐(P∨ Q) ∧ (P∧ Q)） ∨ ( (P∨ Q)∧ ┐(P∧ Q)) ? ?（ ┐P∧ ┐Q) ∧ (P） ∨ ( (P∨ Q)∧ （ ┐P∨ ┐Q)) ? ?(P∨ Q)∧ （ ┐P∨ ┐Q) 合取范式 ? ?(P∧ ┐P)∨ （ ┐P∧ Q） ∨ （ P∧ ┐Q) ∨ （ Q∧ ┐Q) ? ?（ ┐P∧ Q） ∨ （ P∧ ┐Q) 析取范式 ? 我們看到：任一命題公式都可化為與其等價(jià)的析取范式和合取范式。 ?例 ┐P→┐(P→Q) 的析取范式及合取范式。 ?如 ┐P∧ Q， P∧ （ P∨ Q） ∧ （ P∨ Q∨ Q）都是合取范式。 ?如 ┐P∨ Q， ┐P∨ (Q∧ ┐P)∨ ┐Q都是析取范式。那我們想，是否可以在各類公式中分別選出一個(gè)公式作為各類的“代表”，而且使它們具有統(tǒng)一的規(guī)范形式呢？這就是我們現(xiàn)在要講的公式的范式或標(biāo)準(zhǔn)形式。如布爾代數(shù)系統(tǒng)以及下面要介紹的范式，就只用 ┐， ∧ ， ∨ 三個(gè)聯(lián)接詞。 ?注意， {┐， ∧ ， ∨ }， {∧ ， ∨ }， {┐， ?}等都不是最小聯(lián)接詞集。 {┐， → }在研究邏輯系統(tǒng)的演繹和推理時(shí)很重要，在程序系統(tǒng)的研究中也經(jīng)常用，如 {if…then…else}。我們?nèi)菀渍f明 ┐與 ∧ ， ┐與 ∨ 是相互獨(dú)立的，我們稱既具有完備性又具有獨(dú)立性的聯(lián)接詞集為 最小聯(lián)接詞集。 ? “蘊(yùn)涵否定詞” ，用記號(hào) ? 表示，其含義可由下列等價(jià)式?jīng)Q定： ? P?Q?┐(P→Q) ?那么到現(xiàn)在為止，我們共介紹了九個(gè)聯(lián)接詞，可以證明這九個(gè)聯(lián)接詞就夠用了，即滿足完備性。 ?“ 與非（ NAND）詞 ”，用記號(hào) ?表示，也稱為 悉非爾 （ Sheffer）豎，其含義可由下列等價(jià)式?jīng)Q定： P?Q?┐(P∧ Q) ?這說明當(dāng) P， Q都為真時(shí) P?Q為假。當(dāng)然我們只作最少的介紹。再來區(qū)分一下：“明天上午我或者在教室或者在圖書館”，“明天上午十點(diǎn)我或者在教室或者在圖書館”，前一語句中的“或”是可兼的，可用“ ∨ ”來表示，而后一語句中的“或”是不可兼的，不能用“ ∨ ”來表示。 8． 3． 1 聯(lián)結(jié)詞的擴(kuò)充與最小聯(lián)接詞集 ? 首先我們回過頭來分析一下五個(gè)基本聯(lián)接詞，我們發(fā)現(xiàn)其中的析取“ ∨ ”所表示的“或者”允許兩個(gè)都為真，即是可兼的，且當(dāng) A， B都為真時(shí)， A∨ B為真。 8． 3 命題公式的范式 ?在第一節(jié)我們介紹了五個(gè)聯(lián)接詞，強(qiáng)調(diào)它們是基本的重要的，因?yàn)樗鼈兪亲匀徽Z言中最常用的。 ?很明顯：邏輯等價(jià)式與邏輯蘊(yùn)涵式有如下關(guān)系： ?定理 A?B當(dāng)且僅當(dāng) A? B且 B ? A ?即說明等價(jià)是雙向的，蘊(yùn)涵是單向的。 ? 法二：依據(jù)等價(jià)式和置換規(guī)則作等價(jià)變形（以后簡(jiǎn)稱等價(jià)變形法） ? 因?yàn)?A∧ B→┐A→(C→B) ? ┐（ A∧ B）∨ A∨ (┐C∨ B) ? ?┐A∨ ┐B∨ A∨ ┐C∨ B?T ? 故 A∧ B?┐A→(C→B) 。 ?例 ： (A→B) ∧ ┐B? ┐A ? 證：（用前真推后真法） ?假設(shè)前件 (A→B) ∧ ┐B為真，則 A→B 為真，┐B也為真，于是 B為假，又 A→B 為真，從而A為假，故 ┐A為真，所以 (A→B) ∧ ┐B? ┐A。 ?B）后假推前假法： ?即由后件 B為假若能推得前件 A也為假，則A? B。但對(duì)蘊(yùn)涵我們還有兩個(gè)特殊的方法： ? A）前真推后真法： ?即由前件 A為真若能推得后件也為 B真，則A? B。 ?與符號(hào)“ ?”與“ ?”的區(qū)別類似，同樣要注意符號(hào) “ ?” 與“ → ”的區(qū)別。如果現(xiàn)在只要求 A→B 一個(gè)是重言式，則就是我們下邊要研究的另一種公式間的關(guān)系 蘊(yùn)涵。 8． 2． 3 蘊(yùn)涵式