數(shù)理邏輯中范式教學(xué)探討

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

摘要：命題公式范式是命題邏輯中的一個(gè)重要內(nèi)容，也是計(jì)算機(jī)學(xué)科中人工智能、軟件工程等多門核心課程的重要數(shù)學(xué)基礎(chǔ)。本文作者對(duì)此內(nèi)容進(jìn)行了深入的研究，在結(jié)合教學(xué)實(shí)踐的基礎(chǔ)上，提出了一個(gè)完整的教學(xué)案例。

關(guān)鍵詞：離散數(shù)學(xué)；命題邏輯；主合取范式；主析取范式

中圖分類號(hào)：G642

文獻(xiàn)標(biāo)識(shí)碼：A

1引言

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

2范式的有關(guān)概念回顧

范式的有關(guān)概念：積，和，基本積，基本和，析取范式，合取范式，極小項(xiàng)，極大項(xiàng)，主析取范式，主合取范式定義參見文獻(xiàn)[1]。

3教學(xué)案例

任一含有n個(gè)命題變?cè)墓剑加形ㄒ坏囊粋€(gè)與之等值的恰僅含n個(gè)命題變?cè)闹鞣妒?，即主析取范式或主合取范式?/p>

2.1主范式的求法

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

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

2.2主范式的重要作用

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

2.2.1利用主范式證明命題公式等價(jià)

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

例1證明 和

邏輯等價(jià)。

證明：

所以，兩式邏輯等價(jià)。

2.2.2利用主范式將命題公式簡(jiǎn)化

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

例2將命題公式進(jìn)行化簡(jiǎn)。

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

(其主析取范式)

(根據(jù)上式) 即將原公式簡(jiǎn)化了。

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

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

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

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

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

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

解

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

2.2.5利用主范式推導(dǎo)命題公式的真值表

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

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

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

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

① 如果今天是星期二，那么我有一次計(jì)算方法測(cè)驗(yàn)或物理測(cè)驗(yàn)。如果物理老師生病，那么沒有物理測(cè)驗(yàn)，今天是星期二并且物理老師生病，所以我有一次計(jì)算方法測(cè)驗(yàn)。

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

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

① 設(shè)P：今天是星期二；Q：我有一計(jì)

算方法測(cè)驗(yàn)；R：我有一次物理測(cè)驗(yàn)；S：物理老師生病；即前提是 、 、 ，結(jié)論是 。推理規(guī)則是

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

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

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

4范式內(nèi)容擴(kuò)展

3.1范式與集合的關(guān)系

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

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

證明：由真值表可得。

定理2設(shè) ， ， 是命題公式，其包含的變?cè)?中，則

證明略。

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

3.2謂詞公式的判別問題

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

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

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

5結(jié)論

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

參考文獻(xiàn)

[1] 方世昌. 離散數(shù)學(xué)[M].西安電子科技大學(xué).1985.

[2] 儲(chǔ)昭輝. 主范式在數(shù)理邏輯中的重要作用[J]. 滁州學(xué)院學(xué)報(bào)，2006，8(4).

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

[4] 楊彥. 淺析離散數(shù)學(xué)中關(guān)系圖的教學(xué)研究[J]. 中國(guó)水運(yùn)(理論版)，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.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”