一個離散數學輔助教學軟件的設計與開發

2022-03-07 02:21:25周曉聰趙清謝揚周宇喬海燕

軟件工程 2022年3期

周曉聰　趙清　謝揚　周宇　喬海燕

摘? 要：離散數學是計算機專業的核心基礎課程，通常包括邏輯、證明、集合、關系、函數、組合計數、圖論和代數等多個模塊。一個能求解離散數學問題的計算機軟件對離散數學課程的教學和學習都有很好的輔助作用。本文使用面向對象方法設計和開發了一個包含能求解邏輯、集合、組合計數、圖論與代數等離散數學課程模塊中問題的教學輔助軟件。該軟件不僅能展示離散數學問題求解的詳細過程，還能隨機生成問題供學生練習。對學生試用后的調查表明，該軟件對學生學習離散數學課程很有幫助，也有助于培養學生的計算思維。

關鍵詞：離散數學;輔助教學軟件;面向對象設計

中圖分類號：TP31? ? ?文獻標識碼：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）

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

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

我們在編寫教材[3]時為構造特有的例子和驗證解答的正確性，在前期一些零散演示工具[9]的基礎上，使用面向對象方法設計和開發了一個離散數學輔助教學軟件——離散數學基礎例題演示軟件Deedm（Demonstrator for Examples in Elementary Discrete Mathematics），實現了命題邏輯、集合、關系、函數、組合計數、圖論和代數中多個離散數學問題的例子生成和求解過程的展示。學生使用這個軟件可更好地理解教材例子并得到教材許多習題的詳細解答范本;教師使用這個軟件可生成更多例子用于考試或課堂講解，減輕了教師備課和出卷的工作量。

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

離散數學基礎例題演示軟件Deedm的基本功能是離散數學課程中一些問題的例子生成和詳細求解過程的展示。我們在參考多本國內外離散數學優秀教材的基礎上，確定Deedm至少能對下面的問題生成例子并展示其求解過程：

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

（2）集合的并、交、差、補、對稱差和冪集運算，關系和函數的復合運算，關系逆運算，關系性質（自反性、對稱性、傳遞性等）的判斷，關系閉包的計算，函數性質（單函數、滿函數、雙函數）的判斷，等價關系等價類和商集的計算，偏序集極大元、極小元、最大元、最小元的確定，偏序集子集上界、下界、上確界和下確界的確定。

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

（4）無向圖或有向圖的遍歷，根樹的遍歷，帶權圖指定頂點到其他頂點最短路徑的計算，帶權圖最小生成樹的確定，給定帶權葉子的最優二叉樹構造。

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

不難看到，這些已經覆蓋常見離散數學教材中絕大多數可使用計算機程序進行求解的問題。為支持這些問題的例子生成和求解過程展示，我們設計了如圖1所示的Deedm軟件的總體架構。

我們采用面向對象方法[10]設計，圖1中每個方塊包含一個或多個實體（Entity），它們之間的箭頭表示這些實體間的支持關系，即一個實體在提供某些功能或服務時需要另外模塊一些實體的支持，例如命題邏輯公式范式中的實體實現將析取范式或合取范式擴展為主范式的功能，需要命題邏輯公式中實體的支持。

可以看到，Deedm軟件總體分為兩層，即用戶界面層和業務邏輯層。業務邏輯層又分為五個模塊，分別支持邏輯、集合關系函數、組合計數、圖論和代數中問題的例子生成和求解過程展示。用戶界面層的事件處理器使用基礎構件中的實體實現與用戶交互，并調用業務邏輯層的實體提供的功能完成例子生成和求解過程在圖形用戶界面上的展示。

3? 軟件的面向對象設計（Object-oriented design of software）

Deedm軟件的設計采用面向對象方法。在梳理離散數學相關知識的基礎上，根據面向對象思想，在軟件中創建對應離散數學知識內容的實體，根據實體本身的特點（而非根據要實現的功能的需要）設計實體屬性和功能，然后通過這些實體之間的交互實現軟件需要實現的功能。這種面向對象設計使得軟件具有很好的可重用性和可擴充性。

我們選擇使用Java語言實現Deedm軟件，軟件的用戶界面層主要是基于JavaSwing組件實現基礎構件支持離散數學問題的例子及其求解過程的展示，并基于JavaGUI事件監聽機制實現事件處理器捕捉與用戶交互過程中的事件，調用業務邏輯層實體提供的服務完成離散數學問題例子的生成和求解。因此下面只對業務邏輯層的設計作更詳細的介紹。

業務邏輯層可分為邏輯、集合關系函數、組合計數、圖論和代數五個模塊，目前邏輯、組合計數、圖論和代數這四個模塊之間是相互獨立的，但是集合關系函數模塊的實體支持組合計數、圖論和代數這三個模塊的實體，因為它們都要用到集合。下面主要以類圖的形式介紹這五個模塊設計的主要思路。

3.1? ?邏輯模塊的設計

邏輯模塊的主要功能是實現命題邏輯公式真值表的構造和將范式擴展為主范式。根據面向對象思想，對應離散數學命題邏輯的基礎知識，這一模塊的主要實體是命題邏輯公式和命題邏輯公式范式，圖2給出了其中主要實體及其關系。

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

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

3.2? ?集合關系函數模塊的設計

集合關系函數模塊的主要功能是實現集合、關系和函數的運算，關系性質和函數性質的判斷。根據面向對象思想，對應離散數學集合、關系和函數部分的基礎知識，這一模塊的主要實體是集合、關系和函數，圖3給出了其中主要實體及其關系。

集合關系函數模塊的核心實體是集合和關系。目前實現的集合只支持字符或整數作為元素（實際上字符也被看作整數，只是在屏幕顯示時作不同處理）。集合實體提供集合并、交、差、對稱差、冪集等的計算。關系實體存儲有序對的列表，并記錄關系的源集合和目標集合。有序對的元素也只能是字符或整數。目前設計的集合實體不能存在任意類型的元素，因此關系實體與集合實體之間沒有繼承關系，關系實體也提供并、交、差、復合、逆及閉包的計算，并提供對關系性質的判斷。函數被看作是一種特殊的關系，因此繼承關系的屬性和服務，并提供對函數性質的判斷。等價關系和偏序關系也都繼承關系的屬性和服務。等價關系還可計算等價類和商集，偏序關系可返回極大元、極小元等各種元素，并支持繪制哈斯圖。關系支持繪制關系圖，哈斯圖和關系圖都是圖論模塊中抽象圖的實例。

3.3? ?組合計數模塊的設計

組合計數模塊的主要功能是實現滿足各種條件的計數對象枚舉，從而可用于驗證計數問題求解的正確性。圖4給出了其中主要實體及其關系。

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

離散數學基礎課程主要關注字符串的計數、基于整數整除性質的整數計數和不定方程解的計數，因此分別設計了三個接口，并分別提供字符串位置過濾器、字符串結構過濾器、整數整除過濾器和不定方程解范圍過濾器作為這些接口最基本的實現。過濾器模式的一個優勢是通過組合過濾器實現復雜條件的過濾，因此每種過濾器還提供邏輯與關系和邏輯或關系的組合過濾器（限于篇幅，圖4沒有畫出），以實現條件的組合。

3.4? ?圖論模塊的設計

圖論模塊的主要功能是實現圖和樹的遍歷，并實現帶權圖最短距離的Dijkstra算法、最小生成樹的Kruskal和Prim算法，以及構造最優二叉樹的Huffman算法。圖5給出了其中主要實體及其關系。

圖論模塊的一個核心實體是抽象圖，它維持一個抽象頂點列表和一個抽象邊列表。抽象頂點和抽象邊都是接口，實現它們的實體都可作為抽象圖的頂點和邊。實體缺省圖提供了抽象圖的一個具體實現，它實際使用的頂點和邊是實體缺省頂點和缺省邊的實例，提供計算頂點度數、返回圖的鄰接矩陣和關聯矩陣等服務，并支持對圖的先深遍歷和先廣遍歷。帶權圖繼承缺省圖，使用帶權邊的實例作為它的邊，實現Dijkstra算法、Kruskal算法和Prim算法。

圖論模塊的另一個核心實體是根樹，它維持一個根樹節點作為它的根，根樹節點維持一個根樹節點列表作為它的兒子節點列表。根樹提供樹的前序、中序和后序遍歷。根樹沒有繼承抽象圖這個實體，但可轉換為缺省圖。Huffman樹繼承根樹，以帶權樹節點作為它的節點，并實現Huffman算法。

3.5? ?代數模塊的設計

代數模塊的主要功能是判斷運算的性質，展示一些特殊群的子群、陪集，以及判斷格的性質。圖6給出了其中主要實體及其關系。

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

4? 軟件實現關鍵技術與運行效果（Key technology of the software implementation and its operation effect）

面向對象的設計使得Deedm軟件的結構與離散數學課程的知識結構有很好的對應關系，使得整個軟件具有很好的可理解性和可擴充性。Deedm軟件使用面向對象語言Java語言實現，在面向對象設計的基礎上，實現階段主要解決的關鍵問題包括：

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

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

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

（3）如何展示一些復雜問題的求解過程，特別是圖論模塊中最短路徑、最小生成樹和Huffman樹構造算法的求解過程。展示問題求解過程是Deedm軟件的重要功能之一，為此我們在實現復雜算法，例如Dijkstra算法、Kruskal算法、Prim算法和Huffman算法的類中設計相應的記錄執行算法步驟的類，例如實現帶權圖實體的類WeightedGraph有內部類DijkstraAlgorithmRecorder，這個類維持一個內部類DijkstraAlgorithmStepRecorder的對象實例列表。類WeightedGraph實現Dijkstra算法的Java方法的主循環將每一次循環產生的關鍵信息記錄在內部類DijkstraAlgorithmStepRecorder的一個對象實例，并添加到DijkstraAlgorithmRecorder的列表中。上層程序在調用實現Dijkstra算法后可獲得一個DijkstraAlgorithmRecorder的對象，根據這個對象可展示算法的求解過程。圖8給出了

Deedm軟件基于這個設計使用一個表格展示Dijkstra算法求解過程的效果。這種設計的缺點是當要求解有很多頂點和邊的圖的最短路徑時，DijkstraAlgorithmRecorder對象可能占用很多存儲;優點是容易擴充，例如甚至可以設計動畫展示DijkstraAlgorithmRecorder存儲的信息，實現Dijkstra算法的動畫演示效果。

5? ?結論（Conclusion）

離散數學課程內容比較抽象，教師和學生都需要更多的例子展示離散數學問題的求解過程。我們開發了一款離散數學習題演示軟件Deedm，采用面向對象設計，實現了許多離散數學問題的例子生成和求解過程展示。針對中山大學2020 級計算機專業大類一個班68 人的調查表明，雖然沒有在課堂上推薦學生下載該軟件，這個班仍有19 人從課程的超星在線網站下載并運行了該軟件，這19 人中有6 人表示該軟件對離散數學課程作業的完成非常有幫助，有11 人表示該軟件有幫助。

需要指出的是，Deedm軟件不僅可生成例子和展示求解過程以幫助學生學習，也可以幫助教師在課堂測驗和考試出卷時生成例子和答案，從而減輕教師的備課和出卷工作量。教師還可以Deedm軟件為基礎，開展離散數學課程的一些實驗，例如讓學生自己編寫程序實現離散數學問題的求解并與Deedm軟件的結果進行比較，甚至在Deedm軟件的基礎上進行功能的擴展等。下一步我們也會對Deedm軟件的例子生成算法、圖論中圖形的展示等做進一步優化。

參考文獻（References）

[1] 譚作文.離散數學課程中實驗教學探討[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] 周曉聰，喬海燕.離散數學基礎[M].北京：清華大學出版社，2021：80.

[4] 姜楠，李宣廷，袁剛.離散數學實驗教學系統設計[J].大學數學，2019（2）：50-54.

[5] 李華昱，張千.離散數學實驗平臺構建及實驗方法研究[J].科教導刊（下旬），2015（30）：49-50，52.

[6] 鄒樂，華珊珊，呂剛.基于MFC的《離散數學》實驗演示系統的設計與實現[J]. 安徽廣播電視大學學報，2013（3）：121-124.

[7] 曹曉東，史哲文.離散數學及算法[M].北京：機械工業出版社，2013：192-248.

[8] 吳修國.離散數學基礎及實用算法[M].北京：清華大學出版社，2009：61-70.

[9] 周曉聰，喬海燕.面向思維能力培養的離散數學課程教學研究[J].計算機教育，2015（15）：27-30.

[10] 譚火彬.UML 2面向對象分析與設計[M].2版.北京：清華大學出版社，2019：9-50.

作者簡介：