命題邏輯中范式教學(xué)的思考與總結(jié)

命題邏輯中范式教學(xué)的思考與總結(jié)摘要：范式是命題邏輯中的重要概念，范式是把命題公式化歸為一種標(biāo)準(zhǔn)的形式。范式最大的作用是可以進(jìn)行兩個(gè)命題的等價(jià)判定。本文通過剖析范式的定義和判定方法，幫助離散數(shù)學(xué)的初學(xué)者深入理解范式并能夠熟練書寫命題的范式。關(guān)鍵詞：范式;命題邏輯;等價(jià)判定;離散數(shù)學(xué)一、范式的引入在引入范式的定義之前，我們先來講解一下判定的含義：以有限次步驟來決定命題公式是否為永真式、永假式還是可滿足式，或者判定兩個(gè)命題公式是否定價(jià)等這一類問題統(tǒng)稱為判定問題。在命題邏輯中，講解了兩個(gè)命題A和B等價(jià)（A<=>B）的充要條件是A<->B為永真式。具體判斷的方法可以歸納為三種：第一種是真值表法，即對(duì)于等價(jià)號(hào)兩邊的命題變?cè)o予相同的真值指派，看結(jié)果是否相同，相同的話A<->B即為永真式，此時(shí)A<=>B。第二種是命題演算的方法，即化簡(jiǎn)命題A<->B至最簡(jiǎn)式，看是否為T，然后判斷。第三種就是我們要介紹的范式判定的方法，將命題公式A和B分別化成主析取范式（或主合取范式）。如果化成后的主范式相同，則可以判定兩個(gè)公式等價(jià)。把命題公式化歸為一種規(guī)范標(biāo)準(zhǔn)的形式，稱此標(biāo)準(zhǔn)形式為范式。二、析（合）取范式許多教材對(duì)析取和合取范式有著不同類型的定義。這里我們先引入兩個(gè)詞的定義：基本積和基本和。命題的析取式稱為“和”，命題的合取式稱為“積”?；痉e是指命題公式的變?cè)妥冊(cè)姆穸ㄖe。同理，基本和是指命題公式的變?cè)妥冊(cè)姆穸ㄖ?。若“基本積”和“基本和”中有子公式，則稱為基本積（和）的因子?；痉e和永假式有著密切的關(guān)系，一個(gè)基本積是永假式的充分必要條件是它至少包含一對(duì)因子，其中一個(gè)是另一個(gè)的否定。該判定很容易理解，因?yàn)橐坏┌@樣的因子，那么其中必然含有F，由于基本積是合取，那么整個(gè)命題的值為F，即為永假命題。同理，一個(gè)“基本和”必定為永真式的充分必要條件是該公式至少包含一對(duì)因子，其中一個(gè)是另一個(gè)的否定。析取范式的定義可以簡(jiǎn)稱為“積之和”，即與命題公式等價(jià)的一個(gè)公式，如果是由基本積之和組成，則稱它為命題的析取范式。并記為：PP1∨P2∨…∨Pn（n∈I+）。其中P1，P2…Pn均為基本積。合取范式和析取范式相反，可以簡(jiǎn)稱為“和之積”，具體定義在此就不再贅述。從上面的定義可以看出，一個(gè)命題公式的析（合）取范式并不是唯一的，但是同一命題公式的析（合）取范式之間一定是等價(jià)的?？梢哉f，一個(gè)命題公式的析（合）取范式有無數(shù)多個(gè)，因此單純討論析（合）取范式意義不大。我們更希望能夠找到一種標(biāo)準(zhǔn)的形式，使得一個(gè)命題公式僅僅對(duì)應(yīng)一個(gè)等價(jià)的析（合）取范式，這樣就引入了主析（合）取范式。三、主析（合）取范式限于篇幅，這里我們以主析取范式為例。講解之前，先要給出極小項(xiàng)的定義，而極小項(xiàng)又和前面講的基本積息息相關(guān)。在n個(gè)變?cè)幕痉e中，若每個(gè)變?cè)捌浞穸ú⒉煌瑫r(shí)存在，且二者之一出現(xiàn)一次且僅出現(xiàn)一次，則稱此基本積為極小項(xiàng)。對(duì)于兩個(gè)命題變?cè)獊碚f，極小項(xiàng)有2的2次方4個(gè)，即P∧Q、?P∧Q、P∧?Q、?P∧?Q。對(duì)于只有一個(gè)變?cè)拿}，極小項(xiàng)有2個(gè)，即P、?P。依次類推，對(duì)于三個(gè)命題變?cè)獊碚f，極小項(xiàng)有8個(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è)獦?gòu)成的不同極小項(xiàng)有2的n次方個(gè)。而使得每個(gè)極小項(xiàng)為真的賦值僅有一個(gè)。有了極小項(xiàng)的定義，就可以定義主析取范式了，對(duì)于給定的命題公式來講，僅含有極小項(xiàng)的析取的等價(jià)式稱為給定命題公式的主析取范式。在真值表中，一個(gè)公式真值為T的指派所對(duì)應(yīng)的極小項(xiàng)的析取，即為此公式的主析取范式。對(duì)于該定義，要注意一下幾點(diǎn)：第一，只要命題公式不是永假式，則一定可以根據(jù)該命題公式的真值表直接寫出其主析取范式，其方法是找出該公式為“T”的行，對(duì)應(yīng)寫出極小項(xiàng)的析取式，且該公式一定是唯一的。第二，若命題公式是含有n個(gè)變?cè)挠勒媸?，則它的主析取范式一定含有2的n次方個(gè)極小項(xiàng)。第三，若兩個(gè)命題公式對(duì)應(yīng)的主析取范式相同，則此兩個(gè)命題公式一定是定價(jià)的。第四，命題公式的主析取范式中極小項(xiàng)的個(gè)數(shù)一定等于對(duì)應(yīng)真值表中真值為“T”的個(gè)數(shù)。四、求主析取范式的方法求主析取范式的方法主要有兩種，第一種是真值表法，其含義就是將真值表中對(duì)應(yīng)結(jié)果為“T”的項(xiàng)列出來，然后將這些項(xiàng)用∨連接起來。這種方法較為簡(jiǎn)單，列出真值表，結(jié)果就一目了然了。但是當(dāng)命題變?cè)獮?個(gè)以上時(shí)，真值表的數(shù)目將指數(shù)級(jí)增長(zhǎng)，較為麻煩。下面介紹不用真值表，直接求命題公式主析取范式的方法，分為4步：第1步將命題公式化為與其等價(jià)的析取范式。第2步除去永假項(xiàng)，合并基本積中相同項(xiàng)，變?yōu)樽詈?jiǎn)單析取范式。第3步是利用添變?cè)姆椒?，將所有基本積變?yōu)闃O小項(xiàng)。第4步合并相同的極小項(xiàng)變?yōu)橐豁?xiàng)。五、總結(jié)主范式是將無數(shù)不同的命題公式轉(zhuǎn)化成標(biāo)準(zhǔn)形式，以此來判斷不同的命題公式之間是否等價(jià)。我們知道，含有1個(gè)命題變?cè)墓綄?duì)應(yīng)的真值表有兩行，每一行的結(jié)果有兩種，分別是T和F，那么可以產(chǎn)生2的2次方種（即4種）不同的真值表。同理，含有2個(gè)命題變?cè)墓娇梢援a(chǎn)生出2的4次方種（即16種）不同的真值表。含有變?cè)獋€(gè)數(shù)越多