主析取范式解析及其應(yīng)用

[摘要]數(shù)理邏輯中的范式在課本中基本上都是直接定義，然后推演，導(dǎo)致學(xué)生不知道范式的重要性以及與生活中的聯(lián)系，無法深入理解。本文針對這一情況，深入分析了范式的定義，對比了各種范式求解方法，更為重要的是給出了范式中所包含的若干原理與方法，并且與顯示生活中的問題連接了起來，使其構(gòu)成了一個相對完整的知識體系。為解決離散數(shù)學(xué)課程中普遍存在的問題提供了一個方法。

[關(guān)鍵詞]范式 數(shù)理邏輯 離散數(shù)學(xué)

離散數(shù)學(xué)一方面充分地描述了計算機科學(xué)離散性的特點，而且給后繼課程數(shù)據(jù)庫原理、數(shù)據(jù)結(jié)構(gòu)、編譯原理等提供必要的數(shù)學(xué)基礎(chǔ)；另一方面，離散數(shù)學(xué)課程所涉及的概念、方法和理論、所傳授的思想和方法，廣泛地體現(xiàn)在計算機科學(xué)技術(shù)及相關(guān)專業(yè)的諸領(lǐng)域，計算機科學(xué)所需要的概括抽象能力、邏輯思維能力、歸納構(gòu)造能力都可以通過離散數(shù)學(xué)的學(xué)習(xí)得到加強和鍛煉，計算機技術(shù)所需要的嚴謹、完整、規(guī)范的科學(xué)態(tài)度也會通過離散數(shù)學(xué)中的概念、模型描述、證明得到充分體現(xiàn)。

范式在離散數(shù)學(xué)的教學(xué)過程中是一個重點內(nèi)容，同時也是一個難點內(nèi)容，以至于有的學(xué)校將其作為選講內(nèi)容，筆者認為這一部分知識很重要，應(yīng)該講，且應(yīng)該講透。這對學(xué)生有以下的幫助：可以深入理解數(shù)理邏輯，學(xué)會科學(xué)分析問題，找出與生活中問題的聯(lián)系，求出解決方法，全面領(lǐng)略范式的魅力，從而領(lǐng)略邏輯魅力，提高學(xué)生學(xué)習(xí)離散數(shù)學(xué)的動力和能力，為解決離散數(shù)學(xué)課程中普遍存在的問題提供了一個方法。

一、目前教學(xué)中存在的問題

范式在目前的教學(xué)中往往只注重方法的講解，例如真值表法，公式轉(zhuǎn)換法，以及其它間接的求法等，一般先定義文字、短語等概念，然后引出主析?。ê先。┓妒降?，然后就直接告訴學(xué)生用主析取范式解決一些問題。這樣的講解，往往使學(xué)生不能夠深入理解范式的本質(zhì)，概念難以理解，術(shù)語過多，往往在學(xué)過之后很快忘記。為了避免這種現(xiàn)象，我們討論以下的解決方法。

二、明確范式在整個命題邏輯中的主線作用

范式在數(shù)理邏輯教學(xué)中具有非常重要的地位，我們知道，數(shù)理邏輯是將數(shù)學(xué)延伸到了邏輯領(lǐng)域，在邏輯領(lǐng)域語言是一個重要的組成，如何對語言進行分析，推理是非常重要的。數(shù)理邏輯將其符號化，使得爭辯不再需要無謂的爭執(zhí)，只需要坐下來靜靜地拿一支筆將要討論的問題符號化，然后進行數(shù)學(xué)演算就可以得到一個正確的結(jié)果，為了使這個結(jié)果有一個統(tǒng)一的表示形式，避免許多等價公式引來等價判斷上的困難，我們引出了范式的概念，這樣就將語言與邏輯聯(lián)系起來，使得讀者很容易理解為什么用“短語”等來定義范式中的組成成分。通過對主析取范式進行不同的求解，我們將命題邏輯中的最基本的知識“真值表”與邏輯推演中的命題等價演算以及聯(lián)結(jié)詞的使用統(tǒng)一起來，而且我們可以通過實例使人們真切地體會主析取范式在生活中的應(yīng)用。這樣，整個知識點就不再離散，而是變得系統(tǒng)，并且生動有趣了。

三、分析主析取范式中的原理以及其求解方法

1．分析真值表技術(shù)

在此，要首先將方法與生活相聯(lián)系，使學(xué)生與具體問題的解決聯(lián)系起來，學(xué)習(xí)致用。

例如求出G=（P∧Q）∨R的主析取范式。真值表如表1。

將公式中G的真值中1對應(yīng)的極小項取出來，例如第二行1所對應(yīng)的命題變元P，Q，R取值分別為0，0，1，所對應(yīng)的極小項為，可標記為M0.01=M1根據(jù)真值表技術(shù)，我們?nèi)菀椎鹊狡渲魑鋈》妒綖椋?/p>

其中我們可以將極小項看成要完成一件事情必須具備的各種條件的一種情況，主析取范式就可以各種情況下命題變元可能的組合方式的一個集合。利用主析取范式，我們可以全面的考慮問題中出現(xiàn)的各種情況，避免了邏輯思維中遺漏對某些條件討論的弊端，使問題的解決痕全面。

2．等價推演

如果命題變元較多，利用真值表會使工作量以級數(shù)2n的速度增加，而當將公式初步化為析取范式以后，各短語中包含的原子較少時，已經(jīng)較接近主析取范式，通過增加合取缺少的變元P的 (P∨P)，然后利用各種運算定律就可以輕松地解決問題。上例可以如下推導(dǎo)：

推導(dǎo)過程并不難，但為何如此推導(dǎo)，很少有人深究，這是不對的。我們增加短語中未出現(xiàn)命題變元的(P∨P)的形式，是與真值表法相同的，都是為了考慮到解決問題時的各種因素（即范式中的變元），這樣一講，事理很顯然。

3．其他方法中的原理

我們可以使用真值表法求出公式G的否定G的主析取范式G′，然后將G′中未出現(xiàn)的極小項進行全析取G″就是公式G的主析取范式。課本上對此一般是通過證明公式來完成的。

嚴格的證明是必須的，但也要找出其中的通俗道理，當這些條件使G′為假時，則G必為真，因此真值表中為0的那些真值指派必然使G為真，是G中的極小項，同理，當這些條件使G′為真時，則G必為假，因此真值表中為1的那些真值指派必然使G為假，不可能是G中的極小項。

四、范式的應(yīng)用

1．在電路的邏輯設(shè)計方面有廣泛的應(yīng)用

加法器的設(shè)計，有兩個n 位二進制數(shù)a，b 相加和為s(s=a+b) ，a，b 分別寫成：

2. 在生活中的應(yīng)用

安排課表，教語言課的教師希望將課程安排在第一或第三節(jié)；教數(shù)學(xué)課的教師希望將課程安排在第二或第三節(jié)；教原理課的教師希望將課程安排在第一或第二節(jié)。如何安排課表，使得三位教師都滿意。

五、總結(jié)

通過分析討論各種方法的適用情況，求解方法，通俗的道理，使這些形式化的數(shù)理邏輯不再枯燥，與生活生動的聯(lián)系在一起，極大地增強了學(xué)生學(xué)習(xí)的興趣和動力，將難點分而化之。

參考文獻：

[1]耿素云.離散數(shù)學(xué)[M].北京：清華大學(xué)出版社，1999.

[2]傅彥.離散數(shù)學(xué)[M].北京：機械工業(yè)出版社，2005.

[3]郁國瑞.主析取范式求法解析[J].河北能源職業(yè)技術(shù)學(xué)院學(xué)報，2004，（3）.

（作者單位：山東青島農(nóng)業(yè)大學(xué)信息學(xué)院）