離散數學課程改革的實例闡釋

王寧 董廣華

摘要：根據離散數學的內容特點，通過大量實例闡述本課程改革的重點，包括課程連貫性、實用性、與其他學科的關聯性等方面，引導并激發學生的學習興趣，提高邏輯思維和發散思維能力。

關鍵詞：離散數學實例；課程改革；實用性；學科關聯

中圖分類號：G642.0 文獻標志碼：A 文章編號：1674-9324（2018）13-0181-03

離散數學是現代數學的重要分支，它在數學與計算機等領域的學習中具有承上啟下的重要作用。然而因為離散數學理論性較強，部分內容較為抽象。另外，從內容結構上看，離散數學主要包括數理邏輯、集合論、代數結構、圖論等四個基本部分，這四個部分均可自成體系，體現了離散數學課程本身具有較為“離散”的特點。這些原因都有可能限制學生在學習中發揮主觀能動性。因此，在離散數學課程改革中教師需要格外注重引導學生的學習興趣。在教學中，通過引入生動的實例，培養學生掌握處理離散結構的工具和方法，學習抽象的思維模式和嚴格的邏輯推理能力，幫助計算機相關專業的學生建立起學習和使用“0-1”來建模解決問題的思想，并進行發散思維的訓練。

為了達到上述目標，根據離散數學的學科特點，在課程改革中應將以下幾個方面貫穿教學始終，引導學生學習與思考：（1）{0，1}的學習和使用；（2）離散數學各部分間的緊密關聯；（3）實用性與實踐性；（4）離散數學與其他學科的關聯。

一、{0，1}的作用

{0，1}的運用貫穿離散數學課程的始終。比如，在邏輯學中表示命題的真假，集合論中表示元素與集合的隸屬關系，圖論中表示兩結點之間是否有邊相連，等等。目前大部分計算機系統都是二進制系統，{0，1}在計算機相關專業中具有重要地位。在教學中應當讓學生體會到，恰當引入{0，1}構造的模型會帶來研究中的便利。

實例1：引進{0，1}編碼表示有限集S的所有子集。

S（i∈J），J={i|i是n位二進制數，00…0≤i≤11…1}

以S={a，b，c}為例，子集的符號表達形如S=S={b，c}，S=S={a，b}等。

本例的解讀與啟發：在集合論中元素與集合之間具有明確的隸屬關系，即只有{不屬于，屬于}兩種，因此可用{0，1}來簡練表達，方便輸入計算機處理計算等問題。例如計算{b，c}∩{a，b}={b}，通過編碼可轉化為邏輯學中的按位合取運算S∩S=S=S={b}。將本例引申關聯到隸屬函數概念，腳碼實際體現出了特征函數的定義，例如集合S的特征函數為：χ：S→{0，1}

χ（a）=0，χ（b）=1，χ（c）=1

實例2：極小項的二進制與十進制編碼。

在求命題公式的主析取范式和主合取范式時需要用到極大項與極小項的概念。為了方便使用，引入符號表達。例如具有兩個變元的四個極小項的真值表（見表1）。

根據其成真賦值唯一的性質，將成真賦值作為其特征，引入編碼表達，得到m00=m0=?P∧?Q，m01=m1=?P∧Q，m10=m2=P∧?Q，m11=m3=P∧Q

類似的也可定義具有多個變元的極小項與極大項的符號表達，其結果同樣適用于計算機描述和處理大規模問題。

實例3：有向圖的鄰接矩陣。

設G=〈V，E〉是一個簡單圖，它有n個結點依序排列V={v，v，…，v}，則n階方陣A（G）=（a）稱為圖G的鄰接矩陣。其中

a=1

v與

v鄰接

0

v與

v不鄰接或i=j

例如圖1中，圖G的鄰接矩陣為

A（G）=

本例的啟發：結點之間是否有邊相連使用1或0表達，并寫入矩陣的方法簡單易行，同時使用矩陣表示圖，便于計算機存儲和后續計算，已成為圖論中廣泛使用的經典研究方法。

類似的實例還有很多。通過實例可以提高學生的學習興趣，加深對{0，1}應用的廣泛性的認識，啟發學生對{0，1}建模進行思考，并為用計算機解決實際問題開拓思路。

二、離散數學的各部分緊密關聯

離散數學課程主要包含數理邏輯、集合論、代數系統、圖論四個部分。各部分獨立存在，自成體系，在學習的過程中很容易切割其內在聯系。但這四個部分也互相滲透，因此在教學中強調各部分之間的關聯，既有助于加深對課程內容的理解，也對培養學生的發散思維大有裨益。

實例1：邏輯等價式與集合運算的內在關系。

在學習命題邏輯時需要掌握一系列的命題邏輯等值式，同樣，在學習集合的運算時，也有系列的性質。將二者對照會發現其內容、體系雖然不同，但結構完全相似。

例如：設集合A={x|x∈P（x）}，對應謂詞公式P（x）表示集合的屬性：x具有性質P；類似的定義集合B={x|x∈Q（x）}。可以觀察到集合論中的交換律A∪B=B∪A，在邏輯學中的含義為：x∈P（x）∨x∈Q（x）?x∈Q（x）∨x∈P（x）。

本例體現出數理邏輯和集合論可以看作是對同一個問題在兩個體系下的闡述。該實例將數理邏輯、集合論與代數系統三部分內容建立關聯，有助于學生從宏觀角度把握離散數學課程的內容。

實例2：等價關系與集合劃分的關聯。

引入一個生活中的實例“商販的蘋果”：市場的商販販售蘋果遵循統一進貨，分檔次售出的方法，如圖2所示。

將蘋果編號，記作集合A={1，2，…，8}。

（1）從劃分的角度考慮記S={1，4，7}，S={2，5，8}，S={3，6}，則集族S={S，S，S}為A的一個劃分，意為將蘋果按照大、中、小分為三個子集。

（2）從關系的角度考慮：定義蘋果集合A上的關系R：“售價相同關系”。不難驗證：關系R滿足自反、對稱、傳遞性，為A上的等價關系。

本例再次體現了同一個問題從兩個不同角度闡述和建模的思想，并得到“等價關系與劃分一一對應，可相互求解”這一結論。同時，還可在本例的基礎上繼續引申：設A={1，2，…，8}，定義A上的模3同余關系：R={|x，y∈A∧x≡y（mod 3）}，也可得到相同的劃分

S={1，4，7}，S={2，5，8}，S={3，6}。可見其與“商販的蘋果”二例本質完全相同，或者可以說，前者是后者的數學模型，體現了建模并用數學模型解決實際應用的思路。

三、離散數學課程的實用性

對于一些抽象的概念，如果脫離實用性，則難以激發學生的學習興趣；反之，如果使學生看到其實用價值，則對概念的領悟與記憶會更為深刻。

實例1：將抽象概念“關系閉包”具化為應用案例。

引入簡單的編碼實例：設字母表V={A，B，C，D，e，d，f}，并且給定規則A→Af，B→Dde，C→e，A→B，B→De，D→Bf，R為定義在V上的二元關系：xRx，滿足從x出發使用一條規則推出一串字符，使其第一個字符恰為x。求解每個字母連續應用上述規則可能推出的頭字符。

本例實質是求關系的傳遞閉包，且正是閉包這一抽象概念的實用案例。

實例2：代數系統中關于運算封閉的解釋。

在表3所給出的運算中，運算*不是封閉的。

而在表4的代數系統中，運算“o”是封閉的。

這兩個實例均來自生活中，通俗易懂，可使學生對認識和接受抽象概念變得容易。

四、離散數學與其他學科的關聯

離散數學課程本身具有承上啟下的作用，課程內容中有些引申自數學分析、線性代數等學科，有些可以應用于數據結構、數字電路、概率論、模糊數學等課程。以下列舉一些啟發性實例，幫助學生建立各學科之間的關聯，并在學習中體會融會貫通。

實例1：關系閉包的概念與數學分析中開集的閉包對照，可見閉包的本質含義是一致的。

在數學分析中，例如開區間（a，b）的閉包A。其定義包含三層含義：（1）A包含開區間（a，b）；（2）A是閉區間；（3）A是同時滿足（1）和（2）的“最小”集合，即若有集合B滿足（1）和（2），則A?B，因此A=[a，b]。

在集合論中：例如關系R的自反閉包R′也包含三層含義：（1）R′包含關系R；（2）R′自反；（3）R′是同時滿足（1）和（2）的“最小”關系，即若有集合R"滿足（1）和（2），則R′?R″。

實例2：關系矩陣的復合運算對比線性代數中的矩陣乘法，二者完全類似。

普通矩陣的乘法運算：矩陣A=[a]與B=[b]的乘積C=A×B=[c] 其中c=（a·b）。

關系矩陣的復合運算：關系矩陣M=[r]與M=[s]的復合矩陣M=M·M=[w]，其中w=

（r∧s）。

實例3：集合論與模糊數學。模糊集將元素與集合的隸屬關系由{0，1}擴展到閉區間[0，1]，用隸屬度函數定義，因此可以看作集合論的推廣。

實例4：集合論中的“容斥原理”與概率論中的“加法公式”同出一轍。

容斥原理：|A∪A∪…∪A|=

A-|A∩A|+…+（-1）|A∩A∩…∩A|

將容斥原理變形得到如下公式：=-+…+

（-1）

此公式可理解為概率論中的加法公式的雛形，并可寫成概率論中的加法公式，如下：P{A∪A∪…

∪A}=P{A}-P{A∩A}+…+（-1）P{A∩A∩…∩A}

五、結語

在離散數學授課過程中，對上述四部分內容與觀點應加以強調，并貫穿教學始終，同時要盡量通過實例闡釋使學生在學習過程中對課程的內容有一些宏觀地把握，培養其邏輯思維和發散思維，并獲得應用體驗，最大程度的激發出學生的學習熱情，學好本門課程。

參考文獻：

[1]楊炳儒，謝永紅，劉宏嵐，洪源，羅雄.離散數學[M].北京：高等教育出版社，2012.

[2]屈婉玲，王元元，傅彥，張桂蕓.“離散數學”課程教學實施方案[J].中國大學教學，2011，（1）：39-41.

[3]王霞，顧勛梅，潘祝山.離散數學教學改革及課程建設研究[J].計算機教育，2011，（6）：8-10.

[4]王全，陳樺.“離散數學”課程教學改革研究與實踐[J].計算機科學，2006，33（8）：36-38.

[5]常亮，徐周波，古天龍，董榮勝.離散數學教學中的計算思維培養[J].計算機教育，2011，（14）：90-94.