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

2、義，文字既是簡單合取式，又是簡單析取式。 3 例1.5.1 , 都是簡單合取式 , 都是簡單析取式。 4定理1.5.1 (1)簡單合取式是矛盾式的充要條件是它包含兩個分別為某個命題變元及其否定的合取項。(2)簡單析取式是重言式的充要條件是它包含兩個分別為某個命題變元及其否定的析取項。 5證明 我們只證(2), (1)的證明是類似的。充分性 對命題變元P, PP為重言式。所以如果簡單析取式中含有PP, 那么此簡單析取式必是重言式。必要性 假設某簡單析取式是重言式，并設其所含的命題變元為P1,P2, ,Pn。如果此簡單析取式中不存在兩個析取項分別為某個命題變元及其否定，那么它等價于P1*P2*Pn

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

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

5、分配律將命題公式變成所要的范式。 10習慣上，我們稱與命題公式A等價的析取范式(或合取范式)為A的析取范式(或合取范式)。顯然，A的析取范式(或合取范式)不是唯一的。例如P, P(PP)和P(QQ) 都是A的析取范式。 11例1.5.3 求命題公式 的析取范式和合取范式。解 （合取范式） （析取范式） （析取范式） 12定理1.5.3 (1)命題公式A為矛盾式的充要條件是A的析取范式中每個簡單合取式包含兩個分別為某個命題變元及其否定的合取項。(2)命題公式A為重言式的充要條件是A的合取范式中每個簡單析取式包含兩個分別為某個命題變元及其否定的析取項。 13證明 我們只證(1)，(2)的證明是類似

6、的。設A的任一析取范式為A1A2An, 其中每個Ai為簡單合取式。充分性 因為每個Ai都包含兩個分別為某個命題變元及其否定的合取項，所以由定理1.5.1, 每個Ai 都為矛盾式，因而A為矛盾式。必要性假設A為矛盾式，因為每個Ai蘊涵 A， 所以由定理1.3.9每個Ai都為矛盾式。再由定理1.5.1得證。14例1.5.3 判斷下面兩個命題公式的類型。 (1)(2)15解 (1) 上面的合取范式中第一個簡單析取式含P與P，第二個簡單析取式含R與R。所以(1)為重言式。16(2) （析取范式） （合取范式）上面的析取范式和合取范式都不滿足定理1.5.3的條件，因而既不是重言式，又不是矛盾式，它是可滿

7、足式。17 二 、主范式雖然命題公式的范式為判別其類型帶來了一定的方便，但因為其形式的不唯一性，所以我們往往還不能僅從比較兩個命題公式A和B的范式的形式(而不是看或的范式的形式)來判別A和B的等價或蘊涵關系。為此我們需要引進主范式的概念。 18定義 1.5.5 設P1,P2, ,Pn為n個命題變元, 稱簡單合取式 P1*P2*Pn* 為由命題變元 P1,P2, ,Pn 所產生的小項, 稱簡單析取式。P1*P2*Pn* 為由命題變元P1,P2, ,Pn 所產生的大項, 其中每個 Pi*為文字Pi或 Pi 。記小項P1*P2*Pn* 為 , 其中, 如果 Pi*為文字Pi , 那么 ; 如果 Pi

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

9、到大項有如下的性質：（1）n個命題變元可構成2n個大項。（2）任意兩個大項的合取式為矛盾式，所有大項的析取式為重言式。（3）大項 在給每個Pi 以真值 的這一組真值指派下取值為0，在其余2n-1組真值指派下取值為1。 24定義1.5.6 設P1,P2, ,Pn為n個命題變元，由此n個命題變元所產生的互不相同的小項所構成的析取范式稱為由P1,P2, ,Pn所產生的主析取范式。由此n個命題變元所產生的互不相同的大項所構成的合取范式稱為由P1,P2, ,Pn所產生的主合取范式。顯然主析取范式不為矛盾式，主合取范式不為重言式。 25定理1.5.4 (主范式存在定理) 設A為命題變元都在集合P1,P2,

10、 ,Pn 中的命題公式。(1)如果A不為矛盾式,那么A等價于一個由P1,P2, ,Pn 所產生的主析取范式, 稱之為A關于P1,P2, ,Pn 的主析取范式, 進一步如果A=A(P1,P2, ,Pn), 簡稱為A的主析取范式。(2)如果A不為重言式,那么A等價于一個由P1,P2, ,Pn 所產生的主合取范式, 稱之為A關于P1,P2, ,Pn 的主合取范式，進一步如果A=A(P1,P2, ,Pn ), 簡稱為A的主合取范式。26證明 (構造性證明) 首先由定理1.5.2，可以得到A的析取范式和合取范式。繼續(xù)進行構造，便可得到A關于P1,P2, ,Pn的主析取范式和主合取范式。我們在此僅就(1)

11、進行構造證明，(2)的證明是類似的。設A*是A的析取范式。(1) 擴展: 如果A*的某個簡單合取式B不含命題變元 及其否定Pi, 那么利用置換規(guī)則, 用BPi(BPi)置換B。(2) 削去: 將重復出現(xiàn)的命題變元，矛盾式和重復出現(xiàn)的小項都削去。(3) 排序: 將小項按下標從小到大的順序排列。 27由小項和大項的性質，容易得到下面用A=A(P1,P2, ,Pn )的真值表來求A的主范式的方法:(1) A的主析取范式為所有與A在同一組關于P1,P2, ,Pn 的真值指派下都取值為1的由P1,P2, ,Pn 所產生的小項所構成的析取范式。(2) A的主合取范式為所有與A在同一組關于P1,P2, ,P

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

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