主析取范式解析及其應用

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

[關鍵詞]范式 數理邏輯 離散數學

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

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

一、目前教學中存在的問題

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

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

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

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

1．分析真值表技術

在此，要首先將方法與生活相聯系，使學生與具體問題的解決聯系起來，學習致用。

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

將公式中G的真值中1對應的極小項取出來，例如第二行1所對應的命題變元P，Q，R取值分別為0，0，1，所對應的極小項為，可標記為M0.01=M1根據真值表技術，我們容易等到其主析取范式為：

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

2．等價推演

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

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

3．其他方法中的原理

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

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

四、范式的應用

1．在電路的邏輯設計方面有廣泛的應用

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

2. 在生活中的應用

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

五、總結

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

參考文獻：

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

[2]傅彥.離散數學[M].北京：機械工業出版社，2005.

[3]郁國瑞.主析取范式求法解析[J].河北能源職業技術學院學報，2004，（3）.

（作者單位：山東青島農業大學信息學院）