主范式的求解及其應用

黃忠銑，周　榕

（武夷學院數學與計算機系，福建武夷山354300）

?

主范式的求解及其應用

黃忠銑，周榕

（武夷學院數學與計算機系，福建武夷山354300）

摘要：數理邏輯作為數學及思維科學的一個分支，在各學科領域的發展中，有著廣泛的應用。討論數理邏輯中的重要概念主范式的求解方法：真值表法、等值演算法、等值替換結合二進制數法及構造樹法等；并且論述主范式在命題公式中的若干作用。

關鍵詞：主析取范式；主合取范式；極小項；極大項

作為信息科學和計算機科學的數學基礎離散數學，是一門核心課程。它能夠培養學生思維形式和邏輯表達的能力，從而應用于實際解決問題，而且對于學術的研究也是非常重要的［1］。數理邏輯是離散數學的重要組成部分，而主范式是數理邏輯的重要概念，在理論及應用中都有重要的地位，它在計算機科學與技術專業和信息與計算科學的后續課程，比如數據結構、編譯原理、軟件工程等有廣泛的實質性應用［1］。

本文主要以邏輯推理的思想為起點，討論幾種求解主范式的方法，比如：真值表法、等值演算法、邏輯等值替換結合二進制數加以求解法及構造樹法［2］。通過對范式的研究，能夠清楚地了解其在數理邏輯中的一些作用。

1 主范式的求法

1.1 真值表法

利用真值表法求解命題公式A的主范式具有一定的普遍性。求主析取范式的一般步驟為：①寫出A的真值表；②找出A的全部成真賦值；③求出每個成真賦值對應的用名稱表示的極小項，按角標從小到大進行析取［3］。

例1根據真值表法求出命題公式（P∨Q）→（P∧R）的主析取范式為：

對偶地求主合取范式一般步驟如下：①寫出A的真值表；②找出A的全部成假賦值；③求出每個成假賦值對應的極大項（用名稱表示），按角標從大到小進行合取［3］。如例1，可得出所求主合取范式：

真值表法普遍運用于求解主范式當中，任何形式的命題公式均適用。運用此法比較易于我們理解與計算，但先求出公式的真值表時，若命題變項較多，則會加大工作量，并且容易出錯.

1.2 等值演算法

利用命題公式有無窮多個等值式的特性，我們可以采用等值演算法進行求解。求主析取范式的步驟［4］：

設所給公式A為含n個命題變項，

①求A的析取范式A'；

②若A'中的某個簡單合取式Bj中既不含命題變項pi，又不含┑pi，則將Bj如下展開：

繼續這一過程，直到B1，B2，…，Bs都被展成長度為n的極小項為止；

③將重復的命題變項“消去”，可以通過p代替p∨p，0代替p∨┑p，mi代替mi∨mi；

④將極小項排序，并用Σ表示，如m3∨m4∨m6記為Σ（3，4，6），也可不用Σ表示。

例2已知公式A含3個命題變項p，q，r，且析取范式為：

求A的主析取范式。

解用快速法求解∶

求A的主合取范式的步驟與求主析取范式的類似，具體如下：

①求A的合取范式A'；

②若A'中的某個簡單析取式Bj中既不含命題變項pj，也不含┑pi，則可將Bj如下展開：

繼續這一過程，直到B1，B2，…，Bs都被展成長度為n的極大項為止；

③將重復出現的命題變項“消去”。

④將極大項排序，并用∏表示，如m3∧m4∧m6記為∏（3，4，6），也可不用∏表示。

例3已知公式B中含有3個命題變項p，q，r，且合取范式為（p∨q∨┑r）∧┑p，求B的主合取范式。

解用快速法求解∶

當命題公式化為析取或合取范式，各合取式或析取式仍缺少一兩個命題變項時，用此法會較快求解.但同真值表法一樣，當命題變項較多時，工作難度加大，容易出錯，所以比較不適用。

1.3 邏輯等值替換結合二進制數求解法

當命題變項較多出現時，前兩種方法的求解過程有些繁瑣且工作量較大，所以可以采取邏輯等值替換結合二進制數求解法，簡化求解的過程。此法與真值表法及等值演算法性比較，較為簡潔實用。

①將命題公式等值替換成僅由┑、∧和∨表示的形式，化簡得到由合取子式析取的析取范式；

②求析取范式中每一個合取子式所含的所有極小項，利用二進制數可求解出；

③去除重復出現的極小項，并作出這些極小項的析取，即得出主析取范式；

④求出主析取范式所有極小項的對應二進制數，同時得出十進制數，將0到（2n-1）中未出現的數寫出，由這些數的二進制數作出相應的極大項，再由極大項的合取得出主合取范式［2］。

例4求P→（Q→R）的主范式.

解

于是析取范式┑P∨┑Q∨R中有三個基本積┑P、┑Q和R。由合取子式┑P可得出四個極小項┑P∧Q∧R、┑P∧┑Q∧R、┑P∧Q∧┑R、┑P∧┑Q∧┑R，他們相對應的二進制數為011，001，010，000，十進制數就是0，1，2，3；由合取子式┑Q得四個極小項┑P∧┑Q∧R、P∧┑Q∧R、┑P∧┑Q∧┑R、P∧┑Q∧┑R，他們對應的二進制數為001，010，000，100，十進制數為0，1，2，4；由合取子式R可得四個極小項┑P∧┑Q∧R、┑P∧Q∧R、P∧Q∧R、P∧┑Q∧R，他們相對應的二進制數為001，011，111，101，十進制數就是1，3，5，7；消去重復項得主析取范式：

再由0到7中未出現的整數是6，得對應的二進制數110，對應的極大項為P∨Q∨┑R。

1.4 構造樹法

當所給的公式較多且易化成合取范式時，運用此方法會簡化很多，該法的核心思想就是利用析取對合取的分配律［5］。

例5某社團從張大、李二、王三、趙四、劉五五名干事中選派部分人去外地實訓見習，由于他們及社團的需要，出現了以下幾個條件：

（1）張大和李二必有一人去；

（2）若是王三去，趙四也去；

（3）劉五和李二一起去或一起不去；

（4）王三和劉五中只有一人去；

（5）李二不去的話，趙四和劉五就不去。

用構造樹法分析如何對他們進行選派。

解將命題符號化：P：張大去，Q：李二去，R：王三去，S：趙四去，T：劉五去，相應的命題條件為：P∨Q，R→S，Q圮T，（R∧┑Q）∨（┑R∧Q），Q→S∧T。所求出的選派方案即為五個公式的主析取范式∶

圖3 -1例5構造樹

從構造樹中看出，黑色為終止葉子節點，從另外的非終止葉子節點到根節點1的路徑可以得出三條：┑T∧┑Q∧┑S∧┑R∧P、T∧Q∧S∧R∧P及T∧Q∧S∧R，即得出方案：張大一人去；五人同去；只有張大不去。

小結：所給的命題比較容易化成合取范式，此法利用析取對合取的分配律，會很大程度地簡化計算過程，不容易出現命題公式較多就出錯的問題，比較實用。

2 在數理邏輯中，主范式的作用

2.1 判斷命題公式是否等價

通過本文定理2可得，主范式唯一，即若A等值于B，則A與B主范式同類型。逆命題：若A與B主范式同類型，則A等值于B［1-2，4］。

2.2 判別命題公式類型

根據主析取范式中含有極小項的個數，可以判斷出命題公式的類型。當含有全部2n個極小項時，為永真（重言）式；不含任何極小項時，為永假（矛盾）式；至少含有一個極小項時，為可滿足式［1-2，4］。

2.3 判斷命題公式的賦值情況并推出真值表

根據主析取范式極小項角碼的二進制數為成真賦值，主合取范式極大項角碼的二進制數成假賦值，從而可直接推出真值表［1-2，4］。

2.4 判斷推理過程是否正確

推理是由前提推出結論的過程，通過主范式可以驗證公式等值式與蘊含式是否永真，從而判斷推理過程正確與否［1-2，5］。

3 結論

數理邏輯作為一門基礎學科，它所發揮的作用已不言而喻了。不管是在生活中的簡單事例，還是在學術研究中，它都顯得至關重要。但在命題公式的求解中，難免會出現公式繁瑣的情況，所以，范式性質的運用能大大簡化求解過程。在所有范式概念中，主范式是使用最為廣泛的。因此，本文介紹了四種方法，對求法進行深入地研究，在計算過程中可根據實際問題靈活地選擇計算方法，從而提高計算的效率和正確性。

參考文獻：

［1］王青海.數理邏輯中范式教學探討［J］.計算機教育，2008 （12）∶60-62.

［2］呂誠，孫秀華，呂敏.主范式的計算方法及其在命題公式中的作用［J］.宜春學院學報，2011，33（4）∶39-40.

［3］耿素云，屈婉玲.離散數學學習指導與習題解析［M］.北京∶清華大學出版社，2005：22-25.

［4］楊菲.主析取范式的求法及其應用［J］.科教文匯（下旬刊），2013（6）∶53-54.

［5］儲昭輝.主范式在數理邏輯中的重要作用［J］.滁州學院學報，2006（4）∶44-46.

（責任編輯：葉麗娜）

Solution and Its Applications of Principal Normal Form

HUANG Zhongxian，ZHOU Rong

（SchooL of Mathematics and Computer Science，Wuyi University，Wuyishan，Fujian 354300）

Abstract：As a branch of mathematics and noetic science，MathematicaL Logic has a broad reaL appLication in the deveLopment of various discipLines. we sum up the four methods of soLving the principaL normaL form，such as∶truth tabLe method，equivaLent aLgorithm，repLacement combining binary number method and tree construction method，etc. And we sum up the main appLications of speciaL normaL forms in the proposition formuLa.

Key words:principaL disjunctive normaL form；principaL conjunctive normaL form；mintern form；maximum form

中圖分類號：O158文獻標識瑪：A

文章編號：1674-2109（2016）03-0051-04

收稿日期：2015-10-10

基金項目：福建省精品課程項目（Sj2010003）。

作者簡介：黃忠銑（1973-），女，漢族，副教授，主要從事代數方面的研究。