“離散數(shù)學(xué)”命題邏輯的教與學(xué)研究

王國(guó)卿

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 ? ?如何判斷推理有效的問(wèn)題

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

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

6 ? ?結(jié)語(yǔ)

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

[參考文獻(xiàn)]

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

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

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