關(guān)于范式求法解析

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

關(guān)鍵詞：主范式 推演 方法

中圖分類號：G64文獻(xiàn)標(biāo)識碼：A 文章編號：1674-098X（2012）12（c）-0-01

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

定義1：簡單合取式是僅由有限個(gè)命題變項(xiàng)或否定構(gòu)成的合取式。

例如：

定義2：僅由有限個(gè)簡單析取式構(gòu)成的合取式稱為合取范式。

設(shè)，為簡單析取式，則是合取范式。

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

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

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

方法：1：

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

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

（2）真值表最后一列的左側(cè)二進(jìn)制數(shù)對應(yīng)的極大項(xiàng)寫出來。

證明：按照上面得出的極大項(xiàng)的合取范式為，下證就行。設(shè)中包含了個(gè)命題變元，而且由上面方法可得出個(gè)極大項(xiàng)。依照的順序取公式中任一個(gè)解釋，對應(yīng)的二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)后記作M。

那么。

如果，則對應(yīng)的極大項(xiàng)必為中的一個(gè)。此時(shí)由極大項(xiàng)性質(zhì)。

如果，那么對應(yīng)極大項(xiàng)肯定不在中，這時(shí)由極大項(xiàng)性質(zhì)。

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

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

方法2：

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

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

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

以上推演中，反復(fù)使用分配律、交換律、結(jié)合律、等冪律、互補(bǔ)律、零一律、同一律等算律，最終將簡單析取式轉(zhuǎn)化成若干個(gè)極大項(xiàng)的合取形式。對于中其他不是極大項(xiàng)的簡單析取式，反復(fù)使用上述方法，化為若干個(gè)極大項(xiàng)的析取式，最后將公式運(yùn)用一些運(yùn)算律，整理為規(guī)范的主合取范式。

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

例求公式的主合取范式

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

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

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

方法3：

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

證明：下證，已知。設(shè)為公式的個(gè)極大項(xiàng)，而是關(guān)于命題變項(xiàng)的另個(gè)極大項(xiàng)。設(shè)為公式的任一個(gè)解釋，則為公式的任一解釋。

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

如果，則解釋不滿足中任一個(gè)；于是有，由極大項(xiàng)性質(zhì)，一定滿足中某些極大項(xiàng)，因此，所以。綜上。

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

方法4：

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

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

參考文獻(xiàn)

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

[2]伲士健，蔡經(jīng)球.離散數(shù)學(xué)[M].北京：科學(xué)出版社，2001.

[3]嚴(yán)士健，王長沛.離散數(shù)學(xué)初步[M].北京：科學(xué)出版社，1996.

[4]盛驟，謝式千，潘承毅.概率論與數(shù)理統(tǒng)計(jì)[M].2版.北京：高等教育出版社，2000.

[5]尹寶林，何自強(qiáng)，許光漢.離散數(shù)學(xué)（修訂版）[M].北京：高等教育出版社，2004.

[6]杜忠復(fù)，陳兆均.離散數(shù)學(xué)[M].北京：高等教育出版社，2004.

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

[8]馬振華.離散數(shù)學(xué)導(dǎo)引[M].北京：清華大學(xué)出版社，1993.