王國卿

摘 ? 要：高校“離散數(shù)學(xué)”命題邏輯與高中數(shù)學(xué)銜接，是高中數(shù)學(xué)的延續(xù)與深化。針對命題邏輯總體知識結(jié)構(gòu)以及內(nèi)容細(xì)節(jié)中的幾個關(guān)鍵難點，文章分別從教師和學(xué)生的視角出發(fā)，詳細(xì)講解了如何講授及理解這些問題的方法。

關(guān)鍵詞：命邏輯;邏輯聯(lián)結(jié)詞;主范式;重言式

“離散數(shù)學(xué)”主要研究離散量及離散量之間的關(guān)系，是現(xiàn)代數(shù)學(xué)的重要分支，也是計算機(jī)相關(guān)專業(yè)的基礎(chǔ)核心課程。目前，關(guān)于在“離散數(shù)學(xué)”課程中加入實驗與實踐教學(xué)的理念受到了大量教改項目的關(guān)注[1-2]。但是，實踐與應(yīng)用是建立在理論知識基礎(chǔ)之上的，而命題邏輯是大部分“離散數(shù)學(xué)”相關(guān)教材的第一部分。命題邏輯部分以其概念多、抽象、運算多等特點，讓部分學(xué)生感覺學(xué)起來比較困難。文章通過多年的教學(xué)實踐，總結(jié)出學(xué)生在該部分遇到的常見問題，試圖從總體知識結(jié)構(gòu)到某些關(guān)鍵難點解答學(xué)生的困惑，給相關(guān)教師提供一定的參考。

1 ? ?命題邏輯的知識結(jié)構(gòu)是一個從具體到抽象的過程

以高等教育出版社出版的屈婉玲等[3]編著的《離散數(shù)學(xué)》為例說明：第一小節(jié)學(xué)習(xí)命題的定義、邏輯連聯(lián)結(jié)詞及命題符號化，涉及的命題全是具體的命題，有具體內(nèi)容，可以判斷真假。類似小學(xué)初級階段數(shù)學(xué)的學(xué)習(xí)，學(xué)習(xí)具體數(shù)字的加減乘除運算。第二小節(jié)講命題常項與變項、命題公式、公式的真值表。命題常項就是第一小節(jié)涉及的具體的命題，命題變項其實就是命題常項的抽象，或者說是一個映射，定義域是所有具體的命題，值域為0和1。n元命題公式是將0和1構(gòu)成的長度為n的符號串映射到0或1的映射。在這一小節(jié)，命題的具體內(nèi)容已經(jīng)不再被關(guān)心，關(guān)心的重點轉(zhuǎn)移到哪些符號串通過命題公式映射到0（將命題公式映射到0的符號串稱作該命題公式的成假賦值），哪些符號串通過命題公式映射到1（將命題公式映射到1的符號串稱作該命題公式的成真賦值）。n元的命題公式雖然是千變?nèi)f化的，有無數(shù)多個，但是，它的映射關(guān)系只可能有22n種（定義域中有2n次方個元素，值域中有2個元素）。據(jù)此，定義n元真值函數(shù)，將所有的n元命題公式按等值關(guān)系（同真同假的公式為一類，其實就是映射關(guān)系相同的為一類）分類，分為22n個等價類，第i個等價類命名為F（n）i-1，等值關(guān)系是一個等價關(guān)系，因此，這是命題公式的一個劃分，n元真值函數(shù)集是n元命題公式關(guān)于等值關(guān)系的商集。這將可以作為后續(xù)第二部分理解等價關(guān)系與劃分的一個重要實例。

2 ? ?堅持真值表唯一定義聯(lián)結(jié)詞的授課理念

引入邏輯聯(lián)結(jié)詞時，為了便于理解與接受，往往用自然語言來描述邏輯聯(lián)結(jié)詞的意義。但是，聯(lián)結(jié)詞與其相關(guān)的自然語義并不是完全相同的，僅抓住這些自然語言，顯然學(xué)不到邏輯聯(lián)結(jié)詞的本質(zhì)。邏輯聯(lián)結(jié)詞本質(zhì)上是命題邏輯中的運算符號，其運算規(guī)則是由真值表唯一確定的。反過來，如果一個命題的真值表與某個邏輯聯(lián)結(jié)詞的真值表完全相同，則命題符號化時選用該邏輯聯(lián)結(jié)詞。這有助于理解一些較難的邏輯關(guān)系。下面舉例說明。

例1：（1）王燕學(xué)過英語或法語。p：王燕學(xué)過英語，q：王燕學(xué)過法語。（2）王燕在宿舍或在圖書館。p：王燕在宿舍，q：王燕在圖書館。（3）王燕和小明最多去一人。p：王燕去，q：小明去。問：上述哪個復(fù)合命題在符號化時，兩個原子命題之間僅用一個析取符號即可。

解：可列真值如表1所示。

這樣，依據(jù)真值表，就可以判斷只有（1）可以符號化為;（2）和（3）都不能符號化為。

例2：將下列命題符號化：（1）如果天下雨，我就在家。（2）只有天下雨，我才在家。（3）除非天下雨，否則我不在家。

解：p：天下雨，q：我在家。則可列真值如表2所示。

這樣，依據(jù)真值表，就可以將上述命題分別符號化為：（1）;（2）;（3）。

3 ? ?等值演算法求主范式的技巧

首先，等值演算法基于16組基本等值式與置換規(guī)則，求得公式的析?。ɑ蚝先。┓妒?。其次，查看范式中的簡單合?。ɑ蛭鋈。┦绞遣皇菢O小項（或極大項），對于不是極小項的，合取1補(bǔ)入缺少的文字（命題變項及其否定），再用分配率展開得到極小項（或極大項）。最后，整理極小項（或極大項）的順序并將重復(fù)出現(xiàn)的極小項（或極大項）合并。

部分同學(xué)在補(bǔ)入文字并的計算過程中容易出錯，特別是缺少的文字比較多時。據(jù)此，通過演算過程帶領(lǐng)同學(xué)們觀察和總結(jié)，得到一個小技巧，可以快速由析取范式（合取范式）寫出主析取范式（主合取范式）。

觀察此題，在簡單合取式轉(zhuǎn)化為的兩個極小項中，都含有，一個合取r，一個合取，對應(yīng)的極小項的唯一一組成真賦值剛好是100（對應(yīng)十進(jìn)制數(shù)4）和101（對應(yīng)十進(jìn)制數(shù)5）。在r轉(zhuǎn)化的4個極小項中，都含有r，對應(yīng)的極小項的唯一成真賦值第3個位置固定為1，前兩位是0和1的構(gòu)成的所有排列組合，即001，011，101，111（對應(yīng)十進(jìn)制數(shù)分別為1，3，5，7）。

綜上，對于析取范式中的任何一個簡單合取式，將命題變項看成1，將其否定看成0，沒有出現(xiàn)的文字可以是0或1，這樣組成的所有賦值就是該簡單合取式的所有成真賦值，從而可以直接寫出與其等值的主析取范式。同理，可以由合取范式直接寫出與其等值的主合取范式。對于合取范式中的任何一個簡單析取式，將命題變項看成0，將其否定看成1，沒有出現(xiàn)的文字可以是0或1，這樣組成的所有賦值就是該簡單析取式的所有成假賦值，從而可以直接寫出與其等值的主合取范式。

4 ? ?重言式和矛盾式的主范式的理解

主范式的一個重要應(yīng)用之一就是可以判斷公式的類型。其中的難點是學(xué)生對重言式的主合取范式為1、矛盾式的主析取范式為0的理解稍有困難。原因是他們認(rèn)為重言式的主合取范式?jīng)]有極大項，按照小學(xué)的知識，沒有應(yīng)該就是0。的確，在數(shù)論中，0代表什么都沒有。但是，這是在命題邏輯中，0和1只是符號，0表示命題為假，1表示命題為真，同樣地，F(xiàn)也可以表示假，T也可以表示真。重言式是永真式，所有賦值都是成真賦值，其主合取范式中沒有極大項，用1表示。其主析取范式包含了所有極小項，將所有極小項列出。矛盾式是永假式，所有賦值都是成假賦值，其主合取范式包含了所有極大項，將所有極大項列出。其主析取范式中沒有極小項，用0表示。

5 ? ?如何判斷推理有效的問題

推理有效是指由前提合取與結(jié)論構(gòu)成的蘊含式是重言式。這個邏輯思維與我們平時的自然語言“太陽從西邊出來了”一致——當(dāng)前件為假時，說什么都是對的;或者也可以用來表達(dá)驚訝、不可能的情感。

由于蘊含式當(dāng)且僅當(dāng)前件為真后件為假時才為假，因此，在判定推理是否有效時僅需考慮前件為真的情況。這個思路可以幫助理解推理定律，以及后續(xù)一階邏輯推理和一些由蘊含式定義的概念的理解。推理定律就可以理解為“若前提成立，則結(jié)論”;后續(xù)二元關(guān)系中關(guān)系的性質(zhì)、偏序集中的特殊元素等概念的理解。

6 ? ?結(jié)語

本文將“離散數(shù)學(xué)”命題邏輯中的幾個難點進(jìn)行了闡述，希望相關(guān)課程教師和學(xué)生通過閱讀此文能突破命題邏輯中的難點，感受數(shù)學(xué)嚴(yán)謹(jǐn)之美。后續(xù)作者將進(jìn)一步研究“離散數(shù)學(xué)”各個部分的重難點，期望能提高學(xué)生的學(xué)習(xí)興趣，給教師同行們拋磚引玉。

[參考文獻(xiàn)]

[1]王海英，蒲新成，陳虹璇，等.基于實驗教學(xué)的《離散數(shù)學(xué)》課程改革分析[J].科學(xué)咨詢（科技·管理），2018（45）：72-73.

[2]王濤，肖巍，徐中宇.基于新工科理念的離散數(shù)學(xué)課程建設(shè)[J].計算機(jī)教育，2019（1）：29-30.

[3]屈婉玲，耿素云，張立昂.離散數(shù)學(xué)[M].2版.北京：高等教育出版社，2004.