主范式的求解及其應(yīng)用

黃忠銑，周　榕

（武夷學(xué)院數(shù)學(xué)與計(jì)算機(jī)系，福建武夷山354300）

?

主范式的求解及其應(yīng)用

黃忠銑，周榕

（武夷學(xué)院數(shù)學(xué)與計(jì)算機(jī)系，福建武夷山354300）

摘要：數(shù)理邏輯作為數(shù)學(xué)及思維科學(xué)的一個(gè)分支，在各學(xué)科領(lǐng)域的發(fā)展中，有著廣泛的應(yīng)用。討論數(shù)理邏輯中的重要概念主范式的求解方法：真值表法、等值演算法、等值替換結(jié)合二進(jìn)制數(shù)法及構(gòu)造樹法等；并且論述主范式在命題公式中的若干作用。

關(guān)鍵詞：主析取范式；主合取范式；極小項(xiàng)；極大項(xiàng)

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

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

1 主范式的求法

1.1 真值表法

利用真值表法求解命題公式A的主范式具有一定的普遍性。求主析取范式的一般步驟為：①寫出A的真值表；②找出A的全部成真賦值；③求出每個(gè)成真賦值對應(yīng)的用名稱表示的極小項(xiàng)，按角標(biāo)從小到大進(jìn)行析?。?］。

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

對偶地求主合取范式一般步驟如下：①寫出A的真值表；②找出A的全部成假賦值；③求出每個(gè)成假賦值對應(yīng)的極大項(xiàng)（用名稱表示），按角標(biāo)從大到小進(jìn)行合?。?］。如例1，可得出所求主合取范式：

真值表法普遍運(yùn)用于求解主范式當(dāng)中，任何形式的命題公式均適用。運(yùn)用此法比較易于我們理解與計(jì)算，但先求出公式的真值表時(shí)，若命題變項(xiàng)較多，則會(huì)加大工作量，并且容易出錯(cuò).

1.2 等值演算法

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

設(shè)所給公式A為含n個(gè)命題變項(xiàng)，

①求A的析取范式A'；

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

繼續(xù)這一過程，直到B1，B2，…，Bs都被展成長度為n的極小項(xiàng)為止；

③將重復(fù)的命題變項(xiàng)“消去”，可以通過p代替p∨p，0代替p∨┑p，mi代替mi∨mi；

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

例2已知公式A含3個(gè)命題變項(xiàng)p，q，r，且析取范式為：

求A的主析取范式。

解用快速法求解∶

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

①求A的合取范式A'；

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

繼續(xù)這一過程，直到B1，B2，…，Bs都被展成長度為n的極大項(xiàng)為止；

③將重復(fù)出現(xiàn)的命題變項(xiàng)“消去”。

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

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

解用快速法求解∶

當(dāng)命題公式化為析取或合取范式，各合取式或析取式仍缺少一兩個(gè)命題變項(xiàng)時(shí)，用此法會(huì)較快求解.但同真值表法一樣，當(dāng)命題變項(xiàng)較多時(shí)，工作難度加大，容易出錯(cuò)，所以比較不適用。

1.3 邏輯等值替換結(jié)合二進(jìn)制數(shù)求解法

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

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

②求析取范式中每一個(gè)合取子式所含的所有極小項(xiàng)，利用二進(jìn)制數(shù)可求解出；

③去除重復(fù)出現(xiàn)的極小項(xiàng)，并作出這些極小項(xiàng)的析取，即得出主析取范式；

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

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

解

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

再由0到7中未出現(xiàn)的整數(shù)是6，得對應(yīng)的二進(jìn)制數(shù)110，對應(yīng)的極大項(xiàng)為P∨Q∨┑R。

1.4 構(gòu)造樹法

當(dāng)所給的公式較多且易化成合取范式時(shí)，運(yùn)用此方法會(huì)簡化很多，該法的核心思想就是利用析取對合取的分配律［5］。

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

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

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

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

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

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

用構(gòu)造樹法分析如何對他們進(jìn)行選派。

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

圖3 -1例5構(gòu)造樹

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

小結(jié)：所給的命題比較容易化成合取范式，此法利用析取對合取的分配律，會(huì)很大程度地簡化計(jì)算過程，不容易出現(xiàn)命題公式較多就出錯(cuò)的問題，比較實(shí)用。

2 在數(shù)理邏輯中，主范式的作用

2.1 判斷命題公式是否等價(jià)

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

2.2 判別命題公式類型

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

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

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

2.4 判斷推理過程是否正確

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

3 結(jié)論

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

參考文獻(xiàn)：

［1］王青海.數(shù)理邏輯中范式教學(xué)探討［J］.計(jì)算機(jī)教育，2008 （12）∶60-62.

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

［3］耿素云，屈婉玲.離散數(shù)學(xué)學(xué)習(xí)指導(dǎo)與習(xí)題解析［M］.北京∶清華大學(xué)出版社，2005：22-25.

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

［5］儲(chǔ)昭輝.主范式在數(shù)理邏輯中的重要作用［J］.滁州學(xué)院學(xué)報(bào)，2006（4）∶44-46.

（責(zé)任編輯：葉麗娜）

Solution and Its Applications of Principal Normal Form

HUANG Zhongxian，ZHOU Rong

（SchooL of Mathematics and Computer Science，Wuyi University，Wuyishan，F(xiàn)ujian 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文獻(xiàn)標(biāo)識瑪：A

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

收稿日期：2015-10-10

基金項(xiàng)目：福建省精品課程項(xiàng)目（Sj2010003）。

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