主范式及其應用

白昊月

本文介紹了命題公式主范式的基本定義及相關定理，并對其作出了相應解釋，探討了命題公式主范式的求法：等值演算法，以及它的用途，最后給出了主范式的應用，并聯(lián)系實際對這些應用加以闡述.

1 主范式可分為主析取范式與主合取范式。

主析取范式是所有簡單合取式都是極小項的析取范式，主合取范式是所有簡單析取式都是極大項的合取范式.其中，命題變項及其否定統(tǒng)稱為文字，僅由有限個文字構(gòu)成的析取式稱作簡單析取式，僅由有限個文字構(gòu)成的合取式稱作簡單合取式.由有限個簡單合取式的析取構(gòu)成的命題公式稱作析取范式;由有限個簡單析取式的合取構(gòu)成的命題公式稱作合取范式，析取范式與合取范式統(tǒng)稱作范式.

求給定公式的范式在題目中十分常見，任一命題公式都存在與之等值的析取范式與合取范式，其求解步驟為：

1）消去聯(lián)結(jié)詞： →， ?

2）用雙重否定律消去雙重否定符，用德摩根律內(nèi)移否定符。

3）使用分配律：求析取范式時使用∧對∨的分配律，求合取范式時使用∨對∧的分配律.

在含有n個命題變項的簡單合取式或簡單析取式中，若每個命題變項和它的否定式恰好出現(xiàn)一個且僅出現(xiàn)一次，而且命題變項或它的否定式按照下標從小到大或按照字典順序排列，稱這樣的簡單合取式或簡單析取式為極小項或極大項.

在學習中，通常把主范式分為主合取范式與主析取范式進行研究.最常見的一類問題是給出指定公式，求出與其等值的主析取范式和主合取范式.首先要清楚任何命題公式都存在與之等值的主析取范式和主合取范式，并且是唯一的;還要熟練掌握等值式的運用.

2 根據(jù)主析取范式與主合取范式的特殊關系，若某命題公式的主合取范式以得出，則可直接得出主析取范式。

以主析取范式為例，討論其用途。主.析取范式像真值表一樣，可以表達出公式以及公式之間關系的一切信息.

2.1 求公式的成真賦值與成假賦值.

2.2 判斷公式的類型

設公式A中含n個命題變項，則易得出：

（1）A為重言式當且僅當A的主析取范式含全部2?個極小項.

（2）A為矛盾式當且僅當A的主析取范式不含任何極小項.此時，記A的主析取范式為0.

（3）A為可滿足式當且僅當A的主析取范式中至少含一個極小項.

2.3 判斷兩個命題公式是否等值.

若兩個公式A，B的主析取范式相等，則A與B等值.為使主析取范式的用途更直接地表現(xiàn)出來，可舉例說明，

3 在實際生活中我們隨時都會應用主范式分析和解決問題，如在學校中的課程安排問題：某班下學期有A，B，C，D，E五門課，特定要求是：

1）A，B不能安排在同一天上課

2）C是B的實驗課，如果有課程B，當天便有課程C

3）D，E是同一任課教師，該教師要求兩門課不能排在同一天

命題公式主范式作為數(shù)理邏輯的重要概念，在理論和應用中十分重要.本文簡單介紹了主范式的基本定理與相關應用，力圖增加讀者對主范式的認識和了解。

（作者單位：吉林師范大學）