命題邏輯中范式教學的思考與總結摘要：范式是命題邏輯中的重要概念，范式是把命題公式化歸為一種標準的形式。范式最大的作用是可以進行兩個命題的等價判定。本文通過剖析范式的定義和判定方法，幫助離散數學的初學者深入理解范式并能夠熟練書寫命題的范式。關鍵詞：范式;命題邏輯;等價判定;離散數學一、范式的引入在引入范式的定義之前，我們先來講解一下判定的含義：以有限次步驟來決定命題公式是否為永真式、永假式還是可滿足式，或者判定兩個命題公式是否定價等這一類問題統稱為判定問題。在命題邏輯中，講解了兩個命題A和B等價（A<=>B）的充要條件是A<->B為永真式。具體判斷的方法可以歸納為三種：第一種是真值表法，即對于等價號兩邊的命題變元給予相同的真值指派，看結果是否相同，相同的話A<->B即為永真式，此時A<=>B。第二種是命題演算的方法，即化簡命題A<->B至最簡式，看是否為T，然后判斷。第三種就是我們要介紹的范式判定的方法，將命題公式A和B分別化成主析取范式（或主合取范式）。如果化成后的主范式相同，則可以判定兩個公式等價。把命題公式化歸為一種規(guī)范標準的形式，稱此標準形式為范式。二、析（合）取范式許多教材對析取和合取范式有著不同類型的定義。這里我們先引入兩個詞的定義：基本積和基本和。命題的析取式稱為“和”，命題的合取式稱為“積”。基本積是指命題公式的變元和變元的否定之積。同理，基本和是指命題公式的變元和變元的否定之和。若“基本積”和“基本和”中有子公式，則稱為基本積（和）的因子。基本積和永假式有著密切的關系，一個基本積是永假式的充分必要條件是它至少包含一對因子，其中一個是另一個的否定。該判定很容易理解，因為一旦包含這樣的因子，那么其中必然含有F，由于基本積是合取，那么整個命題的值為F，即為永假命題。同理，一個“基本和”必定為永真式的充分必要條件是該公式至少包含一對因子，其中一個是另一個的否定。析取范式的定義可以簡稱為“積之和”，即與命題公式等價的一個公式，如果是由基本積之和組成，則稱它為命題的析取范式。并記為：PP1∨P2∨…∨Pn（n∈I+）。其中P1，P2…Pn均為基本積。合取范式和析取范式相反，可以簡稱為“和之積”，具體定義在此就不再贅述。從上面的定義可以看出，一個命題公式的析（合）取范式并不是唯一的，但是同一命題公式的析（合）取范式之間一定是等價的。可以說，一個命題公式的析（合）取范式有無數多個，因此單純討論析（合）取范式意義不大。我們更希望能夠找到一種標準的形式，使得一個命題公式僅僅對應一個等價的析（合）取范式，這樣就引入了主析（合）取范式。三、主析（合）取范式限于篇幅，這里我們以主析取范式為例。講解之前，先要給出極小項的定義，而極小項又和前面講的基本積息息相關。在n個變元的基本積中，若每個變元及其否定并不同時存在，且二者之一出現一次且僅出現一次，則稱此基本積為極小項。對于兩個命題變元來說，極小項有2的2次方4個，即P∧Q、?P∧Q、P∧?Q、?P∧?Q。對于只有一個變元的命題，極小項有2個，即P、?P。依次類推，對于三個命題變元來說，極小項有8個，即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個命題變元構成的不同極小項有2的n次方個。而使得每個極小項為真的賦值僅有一個。有了極小項的定義，就可以定義主析取范式了，對于給定的命題公式來講，僅含有極小項的析取的等價式稱為給定命題公式的主析取范式。在真值表中，一個公式真值為T的指派所對應的極小項的析取，即為此公式的主析取范式。對于該定義，要注意一下幾點：第一，只要命題公式不是永假式，則一定可以根據該命題公式的真值表直接寫出其主析取范式，其方法是找出該公式為“T”的行，對應寫出極小項的析取式，且該公式一定是唯一的。第二，若命題公式是含有n個變元的永真式，則它的主析取范式一定含有2的n次方個極小項。第三，若兩個命題公式對應的主析取范式相同，則此兩個命題公式一定是定價的。第四，命題公式的主析取范式中極小項的個數一定等于對應真值表中真值為“T”的個數。四、求主析取范式的方法求主析取范式的方法主要有兩種，第一種是真值表法，其含義就是將真值表中對應結果為“T”的項列出來，然后將這些項用∨連接起來。這種方法較為簡單，列出真值表，結果就一目了然了。但是當命題變元為3個以上時，真值表的數目將指數級增長，較為麻煩。下面介紹不用真值表，直接求命題公式主析取范式的方法，分為4步：第1步將命題公式化為與其等價的析取范式。第2步除去永假項，合并基本積中相同項，變?yōu)樽詈唵挝鋈》妒健５?步是利用添變元的方法，將所有基本積變?yōu)闃O小項。第4步合并相同的極小項變?yōu)橐豁棥Ｎ濉⒖偨Y主范式是將無數不同的命題公式轉化成標準形式，以此來判斷不同的命題公式之間是否等價。我們知道，含有1個命題變元的公式對應的真值表有兩行，每一行的結果有兩種，分別是T和F，那么可以產生2的2次方種（即4種）不同的真值表。同理，含有2個命題變元的公式可以產生出2的4次方種（即16種）不同的真值表。含有變元個數越多