文章編號：1672-5913(2008)12-0060-03

摘要：命題公式范式是命題邏輯中的一個重要內容，也是計算機學科中人工智能、軟件工程等多門核心課程的重要數學基礎。本文作者對此內容進行了深入的研究，在結合教學實踐的基礎上，提出了一個完整的教學案例。

關鍵詞：離散數學；命題邏輯；主合取范式；主析取范式

中圖分類號：G642

文獻標識碼：A

1引言

命題公式的范式理論是數理邏輯的重要內容，它在計算機科學與技術專業(yè)后續(xù)課程數據結構、編譯原理、軟件工程、計算機網絡、人工智能等領域中有廣泛的應用。本文通過對范式教學的研究，提出了一個完整的教學案例，并在此基礎上對于范式與集合論的聯(lián)系、范式在人工智能中的應用給出了知識的擴展，使學生在學習的同時既能獲取數學知識同時又能對知識的應用、延伸取得了較好的效果。

2范式的有關概念回顧

范式的有關概念：積，和，基本積，基本和，析取范式，合取范式，極小項，極大項，主析取范式，主合取范式定義參見文獻[1]。

3教學案例

任一含有n個命題變元的公式，都有唯一的一個與之等值的恰僅含n個命題變元的主范式，即主析取范式或主合取范式。

2.1主范式的求法

通常求主范式的方法有兩種，一是將已知命題公式等值變換為所要求的主范

式;二是列出真值表后，根據真值表寫出相應的極大項和極小項，最后寫出主合取范式與主析取范式。由于后面要多用到主范式求法故在此略。

2.2主范式的重要作用

主范式在數理邏輯中具有重要作用，歸納起來如下。

2.2.1利用主范式證明命題公式等價

由命題公式的主范式的唯一性可知，若兩個命題公式A、B具有同一主范式，則必有 ，反之依然。

例1證明 和

邏輯等價。

證明：

所以，兩式邏輯等價。

2.2.2利用主范式將命題公式簡化

先求出命題公式的主范式，再由分配律可得 則可用A替換二式。

例2將命題公式進行化簡。

解先求出該公式的主析取范式：

(其主析取范式)

(根據上式) 即將原公式簡化了。

2.2.3利用主范式判斷命題公式類型

真值表法和等值演算法都能解決命題公式的判定問題，但當命題變項的數目較多時，上述兩種方法都顯得不方便，而主范式提供了最理想的判別方法[2]。若命題公式的主析取范式中含所有的極小項或其主合取范式中不含任何極大項，則為重言式；若公式的主析取范式中不含任何極小項或其主合取范式中含所有的極大項，則為矛盾式；若公式的主析取范式中至少含有一個極小項或其主合取范式中至少有一個極大項不含有，則為可滿足式。

例3判斷下列命題公式的類型。

2.2.4利用主范式研究命題公式的賦值

命題公式的主析取范式中所含極小項角碼的二進制表示為公式的成真賦值，沒有出現(xiàn)的極小項角碼(即公式主合取范式中所含極大項角碼)的二進制表示為公式的成假賦值。

例4研究命題公式的賦值情況。

解

所以，公式成真賦值為000，010，100；成假賦值為001，011，101，110，111。

2.2.5利用主范式推導命題公式的真值表

由命題公式的主范式可直接寫出真值表，如例6真值表見表1

2.2.6利用主范式判斷推理的正確性

推理的理論基礎是邏輯等價式與永真蘊涵式，通過主范式可以方便的驗證作為推理規(guī)則的等值式和蘊涵式是否為永真式，從而說明推理過程是否正確。

例5判斷下列推理是否正確。

① 如果今天是星期二，那么我有一次計算方法測驗或物理測驗。如果物理老師生病，那么沒有物理測驗，今天是星期二并且物理老師生病，所以我有一次計算方法測驗。

② 如果張小三的手沾滿鮮血，那么他殺了人，張小三手很清潔，所以張小三沒有殺人。

解先將命題符號化，再寫出前提、結論及推理規(guī)則，然后通過主范式判斷。

① 設P：今天是星期二；Q：我有一計

算方法測驗；R：我有一次物理測驗；S：物理老師生??；即前提是 、 、 ，結論是 。推理規(guī)則是

。推理是否正確取決于此規(guī)則是否為永真式。易得其主析取范式為 為永真式(過程略)，顯然此推理是正確的。

② 設P：張小三的手沾滿鮮血；Q：他殺了人。

即前提是 、 ，結論是 。推理規(guī)則是 。易得其主析取范式是 不為永真式(過程略)，顯然此推理是錯誤的。

4范式內容擴展

3.1范式與集合的關系

集合在計算機中易于存儲和表示，但命題邏輯中的等價式、蘊含式和推理在計算機中存儲和表示比較困難。本文給出了命題邏輯中的集合表示，使得求一個命題公式的主范式，證明命題公式的等價，以及邏輯推理都可用集合的運算得到，因而命題邏輯中的一些問題也可以非常方便地用計算機進行求解。對于命題公式A，A的主析取范式用其對應的小項的下標組成的集合表示，記為(A)；A的主合取范式用其對應的大項的下標組成的集合表示，記為[A]。令 ，則U為n個命題變元所組成的所有小項(或大項)對應的下標組成的集合，這樣可將命題邏輯的主范式知識與集合運算有機的結合[3]。

定理1設 ， ，對于任意 ，則(Pi)={x︱x∈U∧x的n位二進制表示中第i位元素為1}，[P]={x︱x∈U∧x的n位二進制表示中第i位元素為0}。約定，x的n位二進制表示中從左到右依次為第1位、第2位、#8943; 、第n位。

證明：由真值表可得。

定理2設 ， ， 是命題公式，其包含的變元均在 中，則

證明略。

定理2給出了主范式運算可由集合運算的結果可得，進一步描述了命題公式范式與集合論之間的聯(lián)系，限于篇幅在此不再贅述。

3.2謂詞公式的判別問題

謂詞邏輯是命題邏輯的發(fā)展與延續(xù)，在謂詞公式類型的判別中主范式運算仍然起著重要的作用。謂詞公式若在任何解釋下都為真則此公式是永真式，若在任何解釋下都為假則此公式是永假式，否則即為可滿足式。

例6判斷謂詞公式 的類型。

解： 可看作是 代 、 代 即命題公式 的代入實例，而 (過程略)是永真式，則 為永真式。

5結論

本文通過對命題公式范式教學案例的分析，在學生掌握基本概念的基礎上，以主范式在數理邏輯的重要作用為重點，對知識之間的各種聯(lián)系進行了深入的研究，得到了一些重要的結論。并能夠拓展與整合不同章節(jié)的知識，對于激發(fā)學生的學習興趣與提高學生的自學能力，從而更好的提高教學質量，無疑是非常有益的探索【4】。

參考文獻

[1] 方世昌. 離散數學[M].西安電子科技大學.1985.

[2] 儲昭輝. 主范式在數理邏輯中的重要作用[J]. 滁州學院學報，2006，8(4).

[3] 徐鳳生. 命題邏輯的集合表示[J]. 計算機與現(xiàn)代化，2005，(5).

[4] 楊彥. 淺析離散數學中關系圖的教學研究[J]. 中國水運(理論版)，2006，4(5).

Studies on the Normal Form Teaching in Mathematics Logic

WANG Qing-hai

(Computer department of QingHai Normal University，Xining city ， QingHai province810008)

Abstract: Normal form of propositional function is an important part in propositional logic， and it is also the important mathematics foundation of several core courses such as artificial intelligence and software engineering etc. in computer subject. In this paper， the author had a thorough research to this contents， and put forward a full teaching case in combination with teaching practices.

Key word: Discrete Mathematics; Propositional logic; Special Conjunctive Normal Form; Special Disjunctive Normal Form.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”