關于范式求法解析

摘 要：離散數學中，主合取范式的目的在于討論公式的主合取范式。該文中對主合取范式求解方法進一步推廣，共給出4種求解方法。真值表法、推演法、用真值表法求的主合取范式、用推演法求的主析取范式等4種方法。

關鍵詞：主范式 推演 方法

中圖分類號：G64文獻標識碼：A 文章編號：1674-098X（2012）12（c）-0-01

分析主合取范式求解方法需要先說明簡單合取式，合取范式以及極大項定義。

定義1：簡單合取式是僅由有限個命題變項或否定構成的合取式。

例如：

定義2：僅由有限個簡單析取式構成的合取式稱為合取范式。

設，為簡單析取式，則是合取范式。

定義3：設命題公式中含個命題變項，如果的合取范式中的簡單析取式全是極大項，則稱該合取范式為主合取范式。

定義4：極大項是這樣的簡單析取式，在含個命題變項的簡單析取式中，若每個命題變項與其否定不同時存在，而二者之一必出現且僅出現一次，且第個命題變項或其否定出現在左起的第位上。

求一個公式的主合取范式有直接求法和間接求法，直接求法與間接求法各有兩種，4種方法并進行理論解析。

方法：1：

定理1.對于任意的公式，可按下面的方法求出其主合取范式：

（1）列出公式的真值表。

（2）真值表最后一列的左側二進制數對應的極大項寫出來。

證明：按照上面得出的極大項的合取范式為，下證就行。設中包含了個命題變元，而且由上面方法可得出個極大項。依照的順序取公式中任一個解釋，對應的二進制數轉化為十進制數后記作M。

那么。

如果，則對應的極大項必為中的一個。此時由極大項性質。

如果，那么對應極大項肯定不在中，這時由極大項性質。

于是，且必為唯一主合取范式。

如果已知公式層次非常多時，列真值表帶來麻煩，計算量加大。

方法2：

定理2.對于任意命題公式，其主合取范式可以由下面的推演法求得。設為命題公式的個命題變元。

（1）將命題公式化為任一合取范式。

（2）檢查中每個簡單析取式是否為極大項。如果是，就保留；如果不是關于的極大項，則中必然缺少某些命題變項，則

以上推演中，反復使用分配律、交換律、結合律、等冪律、互補律、零一律、同一律等算律，最終將簡單析取式轉化成若干個極大項的合取形式。對于中其他不是極大項的簡單析取式，反復使用上述方法，化為若干個極大項的析取式，最后將公式運用一些運算律，整理為規范的主合取范式。

如果公式中命題變項較多，所有原子命題變項關系復雜而且包含不易化為合取范式的符號；或化為析取范式后，所缺命題變項較多，這種方法就會很麻煩，很容易出現錯誤，不建議運用。將公式化為合取范式后，所缺命題變項相比之下就會少很多，在比較接近主合取范式時，用此法可解決問題。

例求公式的主合取范式

解將記為A，先將其化為合取范式：

此范式不是主合取范式，出現的簡單析取式不是極大項，例如在中沒有出現 。因此用等值式湊上。

最后得到的主合取范式為的主范式，其中出現5個極大項，使得為T的真值賦值是這5個極大項對應真值賦值，而使為F，即：為真的真值賦值是其余3個極大項所對應真值賦值.因此主合取范式是剩下3個極大項的合取式。

方法3：

定理3.設公式含有個命題變元，公式是按定理2的方法得到的的主合取范式；則將公式中沒有出現的關于極大項全合取出來為公式，即為的主合取范式。

證明：下證，已知。設為公式的個極大項，而是關于命題變項的另個極大項。設為公式的任一個解釋，則為公式的任一解釋。

如果，則解釋必使的某些極大項真值為假；此時有。那么由極大項的性質（2），此解釋一定使其他所有極大項為0，因此。所以。

如果，則解釋不滿足中任一個；于是有，由極大項性質，一定滿足中某些極大項，因此，所以。綜上。

特點：如果公式比公式形式更為簡單，那么先求出，然后列出的真值表，最右列公式真值表中1對應的極大項寫出來，可得到的主合取范式。如果已知的主合取范式，那么由此定理直接寫出的主合取范式。

方法4：

定理4.對于命題公式，可按下面方法求出其主合取范式：a）用推演法求出命題公式的主合取范式；b）由，求出的主合取范式；c）把的主合取范式成求出來 ；

特點：（1）如果命題公式的主析取范式，使用推演法很容易求得，則使用此定理可非常方便地求出命題公式的主合取范式。（2） 由此定理可認為對于任一命題公式的主合取范式和主析取范式可相互轉換，我們可根據實際情況自行選擇。

參考文獻

[1]耿東云，屈婉玲，張立昂.離散數學[M].北京：清華大學出版社，1998：22—52

[2]伲士健，蔡經球.離散數學[M].北京：科學出版社，2001.

[3]嚴士健，王長沛.離散數學初步[M].北京：科學出版社，1996.

[4]盛驟，謝式千，潘承毅.概率論與數理統計[M].2版.北京：高等教育出版社，2000.

[5]尹寶林，何自強，許光漢.離散數學（修訂版）[M].北京：高等教育出版社，2004.

[6]杜忠復，陳兆均.離散數學[M].北京：高等教育出版社，2004.

[7]王樹禾.離散數學引論（面向21世紀高等學校系列教材）[M].安徽：中國科學技術大學出版社，2001.

[8]馬振華.離散數學導引[M].北京：清華大學出版社，1993.