一個(gè)離散數(shù)學(xué)輔助教學(xué)軟件的設(shè)計(jì)與開發(fā)

周曉聰　趙清　謝揚(yáng)　周宇　喬海燕

摘? 要：離散數(shù)學(xué)是計(jì)算機(jī)專業(yè)的核心基礎(chǔ)課程，通常包括邏輯、證明、集合、關(guān)系、函數(shù)、組合計(jì)數(shù)、圖論和代數(shù)等多個(gè)模塊。一個(gè)能求解離散數(shù)學(xué)問題的計(jì)算機(jī)軟件對(duì)離散數(shù)學(xué)課程的教學(xué)和學(xué)習(xí)都有很好的輔助作用。本文使用面向?qū)ο蠓椒ㄔO(shè)計(jì)和開發(fā)了一個(gè)包含能求解邏輯、集合、組合計(jì)數(shù)、圖論與代數(shù)等離散數(shù)學(xué)課程模塊中問題的教學(xué)輔助軟件。該軟件不僅能展示離散數(shù)學(xué)問題求解的詳細(xì)過程，還能隨機(jī)生成問題供學(xué)生練習(xí)。對(duì)學(xué)生試用后的調(diào)查表明，該軟件對(duì)學(xué)生學(xué)習(xí)離散數(shù)學(xué)課程很有幫助，也有助于培養(yǎng)學(xué)生的計(jì)算思維。

關(guān)鍵詞：離散數(shù)學(xué);輔助教學(xué)軟件;面向?qū)ο笤O(shè)計(jì)

中圖分類號(hào)：TP31? ? ?文獻(xiàn)標(biāo)識(shí)碼：A

Design and Development of an Aided Instruction Software for Discrete Mathematics

ZHOU Xiaocong， ZHAO Qing， XIE Yang， ZHOU Yu， QIAO Haiyan

（School of Computer Science and Engineering， Sun Yat-Sen University， Guangzhou 510006， China）

isszxc@mail.sysu.edu.cn; zhaoq78@mail2.sysu.edu.cn; xiey233@mail2.sysu.edu.cn;

zhouy635@mail2.sysu.edu.cn; qiaohy@mail.sysu.edu.cn

Abstract： Discrete mathematics is a core basic course of computer majors， which usually includes multiple modules such as logic， proof， set， relation， function， combinatorial counting， graph theory and algebra. A computer software that can solve discrete mathematics problems motivates teaching and learning of discrete mathematics. By using object-oriented method， this paper proposes to design and develop an aided instruction software to solve problems in discrete mathematics course modules， such as logic， sets， combinatorial counting， graph theory and algebra. The proposed software can not only show the detailed process of solving problems， but also randomly generate instances of such problems for students to practice. Post-trial survey of students shows that the proposed software is helpful for students to learn discrete mathematics， and good for cultivating students' computational thinking as well.

Keywords： discrete mathematics; aided instruction software; object-oriented design

1? ?引言（Introduction）

離散數(shù)學(xué)是計(jì)算機(jī)專業(yè)的核心基礎(chǔ)課程，通常包括邏輯、證明、集合、關(guān)系、函數(shù)、組合計(jì)數(shù)、圖論和代數(shù)等多個(gè)模塊。離散數(shù)學(xué)課程的內(nèi)容抽象，概念眾多，教師希望能有很多可選的例子幫助講解相關(guān)內(nèi)容，學(xué)生也希望有更多的例子幫助理解和做更多的練習(xí)，但教材受篇幅所限通常不會(huì)提供太多的例題和習(xí)題，對(duì)于例題的求解過程有時(shí)也不會(huì)寫得非常詳細(xì)。教師自己想擬出更多例子時(shí)，卻由于思維的某種局限性，往往擬出的例子與已有例子非常相似，例子的復(fù)雜性和代表性都可能不夠。因此，一款能夠隨機(jī)生成例子并給出詳細(xì)求解過程的計(jì)算機(jī)軟件對(duì)離散數(shù)學(xué)課程的教學(xué)和學(xué)習(xí)都會(huì)非常有幫助[1]。

離散數(shù)學(xué)被認(rèn)為是計(jì)算機(jī)學(xué)科的基礎(chǔ)理論之一，其中很多問題都是可以使用計(jì)算機(jī)程序進(jìn)行求解的。很多問題的求解算法，例如關(guān)系閉包的計(jì)算算法（Warshall算法）通常也是離散數(shù)學(xué)課程的知識(shí)內(nèi)容之一，有些教材也會(huì)提供編程練習(xí)題[2-3]，因此利用計(jì)算機(jī)程序求解離散數(shù)學(xué)問題并展示問題求解過程是幫助學(xué)生學(xué)習(xí)這門課程的一種可行途徑。遺憾的是，目前還很缺乏這方面的軟件，只有一些零散的離散數(shù)學(xué)課程中有算法的實(shí)現(xiàn)代碼展示[4-8]，卻不能生成例子并展示詳細(xì)求解過程。有些通用的大型數(shù)學(xué)軟件或計(jì)算代數(shù)系統(tǒng)（Computer Algebra System， CAS），如Maple、Mathematica、Magma等雖然也能用于求解離散數(shù)學(xué)問題，但不會(huì)展示求解過程，或者求解過程需要用戶自己使用軟件提供的語言編程實(shí)現(xiàn)，很難用于離散數(shù)學(xué)課程例子的自動(dòng)生成。

我們?cè)诰帉懡滩腫3]時(shí)為構(gòu)造特有的例子和驗(yàn)證解答的正確性，在前期一些零散演示工具[9]的基礎(chǔ)上，使用面向?qū)ο蠓椒ㄔO(shè)計(jì)和開發(fā)了一個(gè)離散數(shù)學(xué)輔助教學(xué)軟件——離散數(shù)學(xué)基礎(chǔ)例題演示軟件Deedm（Demonstrator for Examples in Elementary Discrete Mathematics），實(shí)現(xiàn)了命題邏輯、集合、關(guān)系、函數(shù)、組合計(jì)數(shù)、圖論和代數(shù)中多個(gè)離散數(shù)學(xué)問題的例子生成和求解過程的展示。學(xué)生使用這個(gè)軟件可更好地理解教材例子并得到教材許多習(xí)題的詳細(xì)解答范本;教師使用這個(gè)軟件可生成更多例子用于考試或課堂講解，減輕了教師備課和出卷的工作量。

2? 軟件功能分析與總體架構(gòu)（Software function analysis and its architecture）

離散數(shù)學(xué)基礎(chǔ)例題演示軟件Deedm的基本功能是離散數(shù)學(xué)課程中一些問題的例子生成和詳細(xì)求解過程的展示。我們?cè)趨⒖级啾緡鴥?nèi)外離散數(shù)學(xué)優(yōu)秀教材的基礎(chǔ)上，確定Deedm至少能對(duì)下面的問題生成例子并展示其求解過程：

（1）命題邏輯公式真值表的構(gòu)造，以及將命題邏輯公式的析取范式或合取范式擴(kuò)展為等值的主析取范式或主合取范式。

（2）集合的并、交、差、補(bǔ)、對(duì)稱差和冪集運(yùn)算，關(guān)系和函數(shù)的復(fù)合運(yùn)算，關(guān)系逆運(yùn)算，關(guān)系性質(zhì)（自反性、對(duì)稱性、傳遞性等）的判斷，關(guān)系閉包的計(jì)算，函數(shù)性質(zhì)（單函數(shù)、滿函數(shù)、雙函數(shù)）的判斷，等價(jià)關(guān)系等價(jià)類和商集的計(jì)算，偏序集極大元、極小元、最大元、最小元的確定，偏序集子集上界、下界、上確界和下確界的確定。

（3）組合計(jì)數(shù)中n元素集合的r排列生成，n元素集合的r組合生成，n元素集合的允許重復(fù)的r組合生成，滿足指定計(jì)數(shù)條件的字符串枚舉，滿足指定整除性質(zhì)的整數(shù)枚舉，滿足指定條件的不定方程解枚舉。

（4）無向圖或有向圖的遍歷，根樹的遍歷，帶權(quán)圖指定頂點(diǎn)到其他頂點(diǎn)最短路徑的計(jì)算，帶權(quán)圖最小生成樹的確定，給定帶權(quán)葉子的最優(yōu)二叉樹構(gòu)造。

（5）給定運(yùn)算表性質(zhì)（交換律、結(jié)合律、冪等律、分配律、吸收律、單位元、零元、逆元、消去律）的判斷，一些特殊有限群（例如n元素集合上的置換群，與m互質(zhì)的正整數(shù)以模m乘為運(yùn)算構(gòu)成的U（m）群）的群元素階、子群、子群陪集、正規(guī)子群、商群的計(jì)算，一個(gè)偏序集是否是格、分配格、有補(bǔ)格或布爾代數(shù)的判定。

不難看到，這些已經(jīng)覆蓋常見離散數(shù)學(xué)教材中絕大多數(shù)可使用計(jì)算機(jī)程序進(jìn)行求解的問題。為支持這些問題的例子生成和求解過程展示，我們?cè)O(shè)計(jì)了如圖1所示的Deedm軟件的總體架構(gòu)。

我們采用面向?qū)ο蠓椒╗10]設(shè)計(jì)，圖1中每個(gè)方塊包含一個(gè)或多個(gè)實(shí)體（Entity），它們之間的箭頭表示這些實(shí)體間的支持關(guān)系，即一個(gè)實(shí)體在提供某些功能或服務(wù)時(shí)需要另外模塊一些實(shí)體的支持，例如命題邏輯公式范式中的實(shí)體實(shí)現(xiàn)將析取范式或合取范式擴(kuò)展為主范式的功能，需要命題邏輯公式中實(shí)體的支持。

可以看到，Deedm軟件總體分為兩層，即用戶界面層和業(yè)務(wù)邏輯層。業(yè)務(wù)邏輯層又分為五個(gè)模塊，分別支持邏輯、集合關(guān)系函數(shù)、組合計(jì)數(shù)、圖論和代數(shù)中問題的例子生成和求解過程展示。用戶界面層的事件處理器使用基礎(chǔ)構(gòu)件中的實(shí)體實(shí)現(xiàn)與用戶交互，并調(diào)用業(yè)務(wù)邏輯層的實(shí)體提供的功能完成例子生成和求解過程在圖形用戶界面上的展示。

3? 軟件的面向?qū)ο笤O(shè)計(jì)（Object-oriented design of software）

Deedm軟件的設(shè)計(jì)采用面向?qū)ο蠓椒?。在梳理離散數(shù)學(xué)相關(guān)知識(shí)的基礎(chǔ)上，根據(jù)面向?qū)ο笏枷?，在軟件中?chuàng)建對(duì)應(yīng)離散數(shù)學(xué)知識(shí)內(nèi)容的實(shí)體，根據(jù)實(shí)體本身的特點(diǎn)（而非根據(jù)要實(shí)現(xiàn)的功能的需要）設(shè)計(jì)實(shí)體屬性和功能，然后通過這些實(shí)體之間的交互實(shí)現(xiàn)軟件需要實(shí)現(xiàn)的功能。這種面向?qū)ο笤O(shè)計(jì)使得軟件具有很好的可重用性和可擴(kuò)充性。

我們選擇使用Java語言實(shí)現(xiàn)Deedm軟件，軟件的用戶界面層主要是基于JavaSwing組件實(shí)現(xiàn)基礎(chǔ)構(gòu)件支持離散數(shù)學(xué)問題的例子及其求解過程的展示，并基于JavaGUI事件監(jiān)聽機(jī)制實(shí)現(xiàn)事件處理器捕捉與用戶交互過程中的事件，調(diào)用業(yè)務(wù)邏輯層實(shí)體提供的服務(wù)完成離散數(shù)學(xué)問題例子的生成和求解。因此下面只對(duì)業(yè)務(wù)邏輯層的設(shè)計(jì)作更詳細(xì)的介紹。

業(yè)務(wù)邏輯層可分為邏輯、集合關(guān)系函數(shù)、組合計(jì)數(shù)、圖論和代數(shù)五個(gè)模塊，目前邏輯、組合計(jì)數(shù)、圖論和代數(shù)這四個(gè)模塊之間是相互獨(dú)立的，但是集合關(guān)系函數(shù)模塊的實(shí)體支持組合計(jì)數(shù)、圖論和代數(shù)這三個(gè)模塊的實(shí)體，因?yàn)樗鼈兌家玫郊稀Ｏ旅嬷饕灶悎D的形式介紹這五個(gè)模塊設(shè)計(jì)的主要思路。

3.1? ?邏輯模塊的設(shè)計(jì)

邏輯模塊的主要功能是實(shí)現(xiàn)命題邏輯公式真值表的構(gòu)造和將范式擴(kuò)展為主范式。根據(jù)面向?qū)ο笏枷?，?duì)應(yīng)離散數(shù)學(xué)命題邏輯的基礎(chǔ)知識(shí)，這一模塊的主要實(shí)體是命題邏輯公式和命題邏輯公式范式，圖2給出了其中主要實(shí)體及其關(guān)系。

邏輯模塊的核心實(shí)體是命題邏輯公式（為方便起見以下簡稱“公式”），它是一個(gè)抽象類，包含一個(gè)左子公式和一個(gè)右子公式作為它的主要屬性，從而公式本身形成了一個(gè)二叉樹結(jié)構(gòu)，即一個(gè)命題邏輯公式實(shí)際上存放的是該公式的抽象語法樹?；诿}邏輯公式的語法，這個(gè)實(shí)體派生出原子公式、否定式、析取式、合取式、蘊(yùn)涵式和雙蘊(yùn)涵式（邏輯等價(jià)式）六個(gè)實(shí)體，它們重定義公式所提供的計(jì)算真值的服務(wù)。公式真值計(jì)算需要真值賦值函數(shù)，這是真值賦值的列表，每個(gè)真值賦值為一個(gè)變量名指定一個(gè)真值。公式真值表構(gòu)造器可以根據(jù)指定的真值賦值函數(shù)計(jì)算公式的真值，也可收集公式出現(xiàn)的所有變量，生成所有可能的真值賦值函數(shù)從而構(gòu)造公式的真值表。構(gòu)造的結(jié)果是一個(gè)數(shù)據(jù)表管理器，它將真值表當(dāng)作二維表存放。公式構(gòu)造器使用簡單的算符優(yōu)先分析算法分析一個(gè)字符串的語法，并將其轉(zhuǎn)換為命題邏輯公式這個(gè)實(shí)體的一個(gè)實(shí)例，這種字符串里支持使用LaTeX命令表示邏輯運(yùn)算符。公式構(gòu)造器還支持隨機(jī)生成一個(gè)命題邏輯公式。

對(duì)于命題邏輯公式范式，文字包含一個(gè)變量名，并有一個(gè)布爾變量表明該文字是變量本身還是變量的否定。目前無論是原子公式中的變量還是文字中的變量，都只支持由一個(gè)字符表示變量名。簡單析取式和簡單合取式都是文字的列表，而析取范式是簡單合取式的列表，合取范式是簡單析取式的列表。析取范式和合取范式都提供服務(wù)將它的實(shí)例轉(zhuǎn)換為一個(gè)命題邏輯公式的實(shí)例。主析取范式和主合取范式分別集成析取范式和合取范式，提供服務(wù)根據(jù)給定的變量集將范式擴(kuò)展為主范式。

3.2? ?集合關(guān)系函數(shù)模塊的設(shè)計(jì)

集合關(guān)系函數(shù)模塊的主要功能是實(shí)現(xiàn)集合、關(guān)系和函數(shù)的運(yùn)算，關(guān)系性質(zhì)和函數(shù)性質(zhì)的判斷。根據(jù)面向?qū)ο笏枷?，?duì)應(yīng)離散數(shù)學(xué)集合、關(guān)系和函數(shù)部分的基礎(chǔ)知識(shí)，這一模塊的主要實(shí)體是集合、關(guān)系和函數(shù)，圖3給出了其中主要實(shí)體及其關(guān)系。

集合關(guān)系函數(shù)模塊的核心實(shí)體是集合和關(guān)系。目前實(shí)現(xiàn)的集合只支持字符或整數(shù)作為元素（實(shí)際上字符也被看作整數(shù)，只是在屏幕顯示時(shí)作不同處理）。集合實(shí)體提供集合并、交、差、對(duì)稱差、冪集等的計(jì)算。關(guān)系實(shí)體存儲(chǔ)有序?qū)Φ牧斜?，并記錄關(guān)系的源集合和目標(biāo)集合。有序?qū)Φ脑匾仓荒苁亲址蛘麛?shù)。目前設(shè)計(jì)的集合實(shí)體不能存在任意類型的元素，因此關(guān)系實(shí)體與集合實(shí)體之間沒有繼承關(guān)系，關(guān)系實(shí)體也提供并、交、差、復(fù)合、逆及閉包的計(jì)算，并提供對(duì)關(guān)系性質(zhì)的判斷。函數(shù)被看作是一種特殊的關(guān)系，因此繼承關(guān)系的屬性和服務(wù)，并提供對(duì)函數(shù)性質(zhì)的判斷。等價(jià)關(guān)系和偏序關(guān)系也都繼承關(guān)系的屬性和服務(wù)。等價(jià)關(guān)系還可計(jì)算等價(jià)類和商集，偏序關(guān)系可返回極大元、極小元等各種元素，并支持繪制哈斯圖。關(guān)系支持繪制關(guān)系圖，哈斯圖和關(guān)系圖都是圖論模塊中抽象圖的實(shí)例。

3.3? ?組合計(jì)數(shù)模塊的設(shè)計(jì)

組合計(jì)數(shù)模塊的主要功能是實(shí)現(xiàn)滿足各種條件的計(jì)數(shù)對(duì)象枚舉，從而可用于驗(yàn)證計(jì)數(shù)問題求解的正確性。圖4給出了其中主要實(shí)體及其關(guān)系。

采用過濾器模式生成滿足條件的計(jì)數(shù)對(duì)象，即將在合適的、有規(guī)律范圍內(nèi)生成計(jì)數(shù)對(duì)象和根據(jù)計(jì)數(shù)條件過濾計(jì)數(shù)對(duì)象這兩個(gè)功能分離，從而具有更好的靈活性和可擴(kuò)充性。因此，組合計(jì)數(shù)模塊的核心實(shí)體分為兩大類，一類是生成器，一類是過濾器。生成器中最基本的是字符串生成器，它支持生成某個(gè)基集上允許重復(fù)字符的所有字符串，排列生成器、組合生成器和允許重復(fù)組合生成繼承字符串生成器分別生成基集上指定長度的排列（不允許重復(fù)）、組合和允許重復(fù)的組合。不定方程解生成使用允許重復(fù)組合生成器生成不定方程的解。

離散數(shù)學(xué)基礎(chǔ)課程主要關(guān)注字符串的計(jì)數(shù)、基于整數(shù)整除性質(zhì)的整數(shù)計(jì)數(shù)和不定方程解的計(jì)數(shù)，因此分別設(shè)計(jì)了三個(gè)接口，并分別提供字符串位置過濾器、字符串結(jié)構(gòu)過濾器、整數(shù)整除過濾器和不定方程解范圍過濾器作為這些接口最基本的實(shí)現(xiàn)。過濾器模式的一個(gè)優(yōu)勢(shì)是通過組合過濾器實(shí)現(xiàn)復(fù)雜條件的過濾，因此每種過濾器還提供邏輯與關(guān)系和邏輯或關(guān)系的組合過濾器（限于篇幅，圖4沒有畫出），以實(shí)現(xiàn)條件的組合。

3.4? ?圖論模塊的設(shè)計(jì)

圖論模塊的主要功能是實(shí)現(xiàn)圖和樹的遍歷，并實(shí)現(xiàn)帶權(quán)圖最短距離的Dijkstra算法、最小生成樹的Kruskal和Prim算法，以及構(gòu)造最優(yōu)二叉樹的Huffman算法。圖5給出了其中主要實(shí)體及其關(guān)系。

圖論模塊的一個(gè)核心實(shí)體是抽象圖，它維持一個(gè)抽象頂點(diǎn)列表和一個(gè)抽象邊列表。抽象頂點(diǎn)和抽象邊都是接口，實(shí)現(xiàn)它們的實(shí)體都可作為抽象圖的頂點(diǎn)和邊。實(shí)體缺省圖提供了抽象圖的一個(gè)具體實(shí)現(xiàn)，它實(shí)際使用的頂點(diǎn)和邊是實(shí)體缺省頂點(diǎn)和缺省邊的實(shí)例，提供計(jì)算頂點(diǎn)度數(shù)、返回圖的鄰接矩陣和關(guān)聯(lián)矩陣等服務(wù)，并支持對(duì)圖的先深遍歷和先廣遍歷。帶權(quán)圖繼承缺省圖，使用帶權(quán)邊的實(shí)例作為它的邊，實(shí)現(xiàn)Dijkstra算法、Kruskal算法和Prim算法。

圖論模塊的另一個(gè)核心實(shí)體是根樹，它維持一個(gè)根樹節(jié)點(diǎn)作為它的根，根樹節(jié)點(diǎn)維持一個(gè)根樹節(jié)點(diǎn)列表作為它的兒子節(jié)點(diǎn)列表。根樹提供樹的前序、中序和后序遍歷。根樹沒有繼承抽象圖這個(gè)實(shí)體，但可轉(zhuǎn)換為缺省圖。Huffman樹繼承根樹，以帶權(quán)樹節(jié)點(diǎn)作為它的節(jié)點(diǎn)，并實(shí)現(xiàn)Huffman算法。

3.5? ?代數(shù)模塊的設(shè)計(jì)

代數(shù)模塊的主要功能是判斷運(yùn)算的性質(zhì)，展示一些特殊群的子群、陪集，以及判斷格的性質(zhì)。圖6給出了其中主要實(shí)體及其關(guān)系。

代數(shù)模塊的核心實(shí)體是二元運(yùn)算，它的基集類型是一個(gè)類型參數(shù)，因此是一個(gè)類屬類。將二元運(yùn)算作為類屬類是因?yàn)橹脫Q群、U（m）群和格等不同代數(shù)系統(tǒng)的基集元素類型不同，而這些代數(shù)系統(tǒng)都有二元運(yùn)算，都需要二元運(yùn)算這個(gè)實(shí)體提供的有關(guān)運(yùn)算性質(zhì)判斷的服務(wù)。類似地，群這個(gè)實(shí)體也是一個(gè)類屬類，它提供有關(guān)群元素的階，判斷子集是否是子群，計(jì)算所有子群、所有生成子群，計(jì)算子群生成元等服務(wù)。單位模m乘群（U（m）群）繼承群這個(gè)實(shí)體，并且將基集元素的類型定為整數(shù)，提供計(jì)算子群陪集的服務(wù)。置換群繼承群這個(gè)實(shí)體，它的基集元素類型是置換。置換是集合{1，2，…，n}上的一個(gè)雙函數(shù)，使用一個(gè)整數(shù)數(shù)組表示置換結(jié)果，即數(shù)組的第i 個(gè)元素記錄的是這個(gè)雙函數(shù)作用在整數(shù)i的值。置換群這個(gè)實(shí)體提供計(jì)算子群的左右陪集、判斷子群是否是正規(guī)子群，以及計(jì)算給定正規(guī)子群的商群等服務(wù)。格繼承集合關(guān)系函數(shù)模塊中的偏序關(guān)系這個(gè)實(shí)體，并維持兩個(gè)二元運(yùn)算，提供判斷格的性質(zhì)，返回最大元、最小元、補(bǔ)元（如果有的話）等服務(wù)。

4? 軟件實(shí)現(xiàn)關(guān)鍵技術(shù)與運(yùn)行效果（Key technology of the software implementation and its operation effect）

面向?qū)ο蟮脑O(shè)計(jì)使得Deedm軟件的結(jié)構(gòu)與離散數(shù)學(xué)課程的知識(shí)結(jié)構(gòu)有很好的對(duì)應(yīng)關(guān)系，使得整個(gè)軟件具有很好的可理解性和可擴(kuò)充性。Deedm軟件使用面向?qū)ο笳Z言Java語言實(shí)現(xiàn)，在面向?qū)ο笤O(shè)計(jì)的基礎(chǔ)上，實(shí)現(xiàn)階段主要解決的關(guān)鍵問題包括：

（1）如何方便地輸入和顯示數(shù)學(xué)符號(hào)。很多數(shù)學(xué)符號(hào)，例如邏輯運(yùn)算符等都不是可從鍵盤直接輸入的符號(hào)，它們的顯示也不能簡單地以字符串的方式顯示。對(duì)于這個(gè)問題，Deedm軟件支持用戶使用LaTeX命令輸入邏輯運(yùn)算符等數(shù)學(xué)符號(hào)，并使用Java構(gòu)件庫JLaTeXMath解析含有LaTeX命令的字符串并生成符合數(shù)學(xué)風(fēng)格排版的圖片，從而解決了數(shù)學(xué)符號(hào)的輸入和顯示問題。

圖7展示了命題邏輯公式的輸入及其真值表構(gòu)造的效果，可看到用戶使用LaTeX命令，例如＼rightarrow等錄入邏輯運(yùn)算符，Deedm軟件以圖片的形式顯示輸入的公式以及構(gòu)造的真值表。

（2）如何生成離散數(shù)學(xué)課程中一些問題的例子。促使我們開發(fā)Deedm軟件的一個(gè)動(dòng)機(jī)是希望能針對(duì)一些離散數(shù)學(xué)問題生成例子供教師講課、測驗(yàn)和學(xué)生學(xué)習(xí)練習(xí)使用。為此，Deedm軟件的許多實(shí)體（類）都實(shí)現(xiàn)了隨機(jī)生成的功能，例如在命題邏輯公式構(gòu)造器中有隨機(jī)生成命題邏輯公式的Java方法。圖8給出的輸入界面也支持命題邏輯公式的隨機(jī)生成。可以看到，在前文給出主要模塊的設(shè)計(jì)中，很多實(shí)體都提供了隨機(jī)生成的服務(wù)。有些離散數(shù)學(xué)問題的例子生成，如集合、普通關(guān)系的生成比較簡單，采用隨機(jī)函數(shù)從合適集合隨機(jī)選取元素即可，但有些問題的例子生成，例如要生成偏序關(guān)系、等價(jià)關(guān)系等，需要設(shè)計(jì)一些算法才能保證生成的關(guān)系是偏序關(guān)系或等價(jià)關(guān)系。

（3）如何展示一些復(fù)雜問題的求解過程，特別是圖論模塊中最短路徑、最小生成樹和Huffman樹構(gòu)造算法的求解過程。展示問題求解過程是Deedm軟件的重要功能之一，為此我們?cè)趯?shí)現(xiàn)復(fù)雜算法，例如Dijkstra算法、Kruskal算法、Prim算法和Huffman算法的類中設(shè)計(jì)相應(yīng)的記錄執(zhí)行算法步驟的類，例如實(shí)現(xiàn)帶權(quán)圖實(shí)體的類WeightedGraph有內(nèi)部類DijkstraAlgorithmRecorder，這個(gè)類維持一個(gè)內(nèi)部類DijkstraAlgorithmStepRecorder的對(duì)象實(shí)例列表。類WeightedGraph實(shí)現(xiàn)Dijkstra算法的Java方法的主循環(huán)將每一次循環(huán)產(chǎn)生的關(guān)鍵信息記錄在內(nèi)部類DijkstraAlgorithmStepRecorder的一個(gè)對(duì)象實(shí)例，并添加到DijkstraAlgorithmRecorder的列表中。上層程序在調(diào)用實(shí)現(xiàn)Dijkstra算法后可獲得一個(gè)DijkstraAlgorithmRecorder的對(duì)象，根據(jù)這個(gè)對(duì)象可展示算法的求解過程。圖8給出了

Deedm軟件基于這個(gè)設(shè)計(jì)使用一個(gè)表格展示Dijkstra算法求解過程的效果。這種設(shè)計(jì)的缺點(diǎn)是當(dāng)要求解有很多頂點(diǎn)和邊的圖的最短路徑時(shí)，DijkstraAlgorithmRecorder對(duì)象可能占用很多存儲(chǔ);優(yōu)點(diǎn)是容易擴(kuò)充，例如甚至可以設(shè)計(jì)動(dòng)畫展示DijkstraAlgorithmRecorder存儲(chǔ)的信息，實(shí)現(xiàn)Dijkstra算法的動(dòng)畫演示效果。

5? ?結(jié)論（Conclusion）

離散數(shù)學(xué)課程內(nèi)容比較抽象，教師和學(xué)生都需要更多的例子展示離散數(shù)學(xué)問題的求解過程。我們開發(fā)了一款離散數(shù)學(xué)習(xí)題演示軟件Deedm，采用面向?qū)ο笤O(shè)計(jì)，實(shí)現(xiàn)了許多離散數(shù)學(xué)問題的例子生成和求解過程展示。針對(duì)中山大學(xué)2020 級(jí)計(jì)算機(jī)專業(yè)大類一個(gè)班68 人的調(diào)查表明，雖然沒有在課堂上推薦學(xué)生下載該軟件，這個(gè)班仍有19 人從課程的超星在線網(wǎng)站下載并運(yùn)行了該軟件，這19 人中有6 人表示該軟件對(duì)離散數(shù)學(xué)課程作業(yè)的完成非常有幫助，有11 人表示該軟件有幫助。

需要指出的是，Deedm軟件不僅可生成例子和展示求解過程以幫助學(xué)生學(xué)習(xí)，也可以幫助教師在課堂測驗(yàn)和考試出卷時(shí)生成例子和答案，從而減輕教師的備課和出卷工作量。教師還可以Deedm軟件為基礎(chǔ)，開展離散數(shù)學(xué)課程的一些實(shí)驗(yàn)，例如讓學(xué)生自己編寫程序?qū)崿F(xiàn)離散數(shù)學(xué)問題的求解并與Deedm軟件的結(jié)果進(jìn)行比較，甚至在Deedm軟件的基礎(chǔ)上進(jìn)行功能的擴(kuò)展等。下一步我們也會(huì)對(duì)Deedm軟件的例子生成算法、圖論中圖形的展示等做進(jìn)一步優(yōu)化。

參考文獻(xiàn)（References）

[1] 譚作文.離散數(shù)學(xué)課程中實(shí)驗(yàn)教學(xué)探討[J].計(jì)算機(jī)教育，2010（17）：106-109.

[2] Rosen K H. Discrete mathematics and its applications[M]. 7th ed.New York： The McGraw-Hill Companies， 2012：113.

[3] 周曉聰，喬海燕.離散數(shù)學(xué)基礎(chǔ)[M].北京：清華大學(xué)出版社，2021：80.

[4] 姜楠，李宣廷，袁剛.離散數(shù)學(xué)實(shí)驗(yàn)教學(xué)系統(tǒng)設(shè)計(jì)[J].大學(xué)數(shù)學(xué)，2019（2）：50-54.

[5] 李華昱，張千.離散數(shù)學(xué)實(shí)驗(yàn)平臺(tái)構(gòu)建及實(shí)驗(yàn)方法研究[J].科教導(dǎo)刊（下旬），2015（30）：49-50，52.

[6] 鄒樂，華珊珊，呂剛.基于MFC的《離散數(shù)學(xué)》實(shí)驗(yàn)演示系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J]. 安徽廣播電視大學(xué)學(xué)報(bào)，2013（3）：121-124.

[7] 曹曉東，史哲文.離散數(shù)學(xué)及算法[M].北京：機(jī)械工業(yè)出版社，2013：192-248.

[8] 吳修國.離散數(shù)學(xué)基礎(chǔ)及實(shí)用算法[M].北京：清華大學(xué)出版社，2009：61-70.

[9] 周曉聰，喬海燕.面向思維能力培養(yǎng)的離散數(shù)學(xué)課程教學(xué)研究[J].計(jì)算機(jī)教育，2015（15）：27-30.

[10] 譚火彬.UML 2面向?qū)ο蠓治雠c設(shè)計(jì)[M].2版.北京：清華大學(xué)出版社，2019：9-50.

作者簡介：

周曉聰（1971-），男，博士，副教授.研究領(lǐng)域：軟件工程.

趙? ?清（2001-），男，本科生.研究領(lǐng)域：計(jì)算機(jī)科學(xué)與技術(shù).

謝? ?揚(yáng)（2001-），男，本科生.研究領(lǐng)域：計(jì)算機(jī)科學(xué)與技術(shù).

周? ?宇（2001-），男，本科生.研究領(lǐng)域：計(jì)算機(jī)科學(xué)與技術(shù).

喬海燕（1963-），男，博士，副教授.研究領(lǐng)域：理論計(jì)算機(jī)科學(xué).