“離散數學”命題邏輯的教與學研究

王國卿

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

關鍵詞：命邏輯;邏輯聯結詞;主范式;重言式

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

1 ? ?命題邏輯的知識結構是一個從具體到抽象的過程

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

2 ? ?堅持真值表唯一定義聯結詞的授課理念

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

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

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

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

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

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

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

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

首先，等值演算法基于16組基本等值式與置換規則，求得公式的析取（或合取）范式。其次，查看范式中的簡單合取（或析取）式是不是極小項（或極大項），對于不是極小項的，合取1補入缺少的文字（命題變項及其否定），再用分配率展開得到極小項（或極大項）。最后，整理極小項（或極大項）的順序并將重復出現的極小項（或極大項）合并。

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

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

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

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

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

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

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

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

6 ? ?結語

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

[參考文獻]

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

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

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