離散數(shù)學(xué)課程改革的實(shí)例闡釋

王寧 董廣華

摘要：根據(jù)離散數(shù)學(xué)的內(nèi)容特點(diǎn)，通過(guò)大量實(shí)例闡述本課程改革的重點(diǎn)，包括課程連貫性、實(shí)用性、與其他學(xué)科的關(guān)聯(lián)性等方面，引導(dǎo)并激發(fā)學(xué)生的學(xué)習(xí)興趣，提高邏輯思維和發(fā)散思維能力。

關(guān)鍵詞：離散數(shù)學(xué)實(shí)例；課程改革；實(shí)用性；學(xué)科關(guān)聯(lián)

中圖分類號(hào)：G642.0 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1674-9324（2018）13-0181-03

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

為了達(dá)到上述目標(biāo)，根據(jù)離散數(shù)學(xué)的學(xué)科特點(diǎn)，在課程改革中應(yīng)將以下幾個(gè)方面貫穿教學(xué)始終，引導(dǎo)學(xué)生學(xué)習(xí)與思考：（1）{0，1}的學(xué)習(xí)和使用；（2）離散數(shù)學(xué)各部分間的緊密關(guān)聯(lián)；（3）實(shí)用性與實(shí)踐性；（4）離散數(shù)學(xué)與其他學(xué)科的關(guān)聯(lián)。

一、{0，1}的作用

{0，1}的運(yùn)用貫穿離散數(shù)學(xué)課程的始終。比如，在邏輯學(xué)中表示命題的真假，集合論中表示元素與集合的隸屬關(guān)系，圖論中表示兩結(jié)點(diǎn)之間是否有邊相連，等等。目前大部分計(jì)算機(jī)系統(tǒng)都是二進(jìn)制系統(tǒng)，{0，1}在計(jì)算機(jī)相關(guān)專業(yè)中具有重要地位。在教學(xué)中應(yīng)當(dāng)讓學(xué)生體會(huì)到，恰當(dāng)引入{0，1}構(gòu)造的模型會(huì)帶來(lái)研究中的便利。

實(shí)例1：引進(jìn){0，1}編碼表示有限集S的所有子集。

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

以S={a，b，c}為例，子集的符號(hào)表達(dá)形如S=S={b，c}，S=S={a，b}等。

本例的解讀與啟發(fā)：在集合論中元素與集合之間具有明確的隸屬關(guān)系，即只有{不屬于，屬于}兩種，因此可用{0，1}來(lái)簡(jiǎn)練表達(dá)，方便輸入計(jì)算機(jī)處理計(jì)算等問(wèn)題。例如計(jì)算{b，c}∩{a，b}={b}，通過(guò)編碼可轉(zhuǎn)化為邏輯學(xué)中的按位合取運(yùn)算S∩S=S=S={b}。將本例引申關(guān)聯(lián)到隸屬函數(shù)概念，腳碼實(shí)際體現(xiàn)出了特征函數(shù)的定義，例如集合S的特征函數(shù)為：χ：S→{0，1}

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

實(shí)例2：極小項(xiàng)的二進(jìn)制與十進(jìn)制編碼。

在求命題公式的主析取范式和主合取范式時(shí)需要用到極大項(xiàng)與極小項(xiàng)的概念。為了方便使用，引入符號(hào)表達(dá)。例如具有兩個(gè)變?cè)乃膫€(gè)極小項(xiàng)的真值表（見表1）。

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

類似的也可定義具有多個(gè)變?cè)臉O小項(xiàng)與極大項(xiàng)的符號(hào)表達(dá)，其結(jié)果同樣適用于計(jì)算機(jī)描述和處理大規(guī)模問(wèn)題。

實(shí)例3：有向圖的鄰接矩陣。

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

a=1

v與

v鄰接

0

v與

v不鄰接或i=j

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

A（G）=

本例的啟發(fā)：結(jié)點(diǎn)之間是否有邊相連使用1或0表達(dá)，并寫入矩陣的方法簡(jiǎn)單易行，同時(shí)使用矩陣表示圖，便于計(jì)算機(jī)存儲(chǔ)和后續(xù)計(jì)算，已成為圖論中廣泛使用的經(jīng)典研究方法。

類似的實(shí)例還有很多。通過(guò)實(shí)例可以提高學(xué)生的學(xué)習(xí)興趣，加深對(duì){0，1}應(yīng)用的廣泛性的認(rèn)識(shí)，啟發(fā)學(xué)生對(duì){0，1}建模進(jìn)行思考，并為用計(jì)算機(jī)解決實(shí)際問(wèn)題開拓思路。

二、離散數(shù)學(xué)的各部分緊密關(guān)聯(lián)

離散數(shù)學(xué)課程主要包含數(shù)理邏輯、集合論、代數(shù)系統(tǒng)、圖論四個(gè)部分。各部分獨(dú)立存在，自成體系，在學(xué)習(xí)的過(guò)程中很容易切割其內(nèi)在聯(lián)系。但這四個(gè)部分也互相滲透，因此在教學(xué)中強(qiáng)調(diào)各部分之間的關(guān)聯(lián)，既有助于加深對(duì)課程內(nèi)容的理解，也對(duì)培養(yǎng)學(xué)生的發(fā)散思維大有裨益。

實(shí)例1：邏輯等價(jià)式與集合運(yùn)算的內(nèi)在關(guān)系。

在學(xué)習(xí)命題邏輯時(shí)需要掌握一系列的命題邏輯等值式，同樣，在學(xué)習(xí)集合的運(yùn)算時(shí)，也有系列的性質(zhì)。將二者對(duì)照會(huì)發(fā)現(xiàn)其內(nèi)容、體系雖然不同，但結(jié)構(gòu)完全相似。

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

本例體現(xiàn)出數(shù)理邏輯和集合論可以看作是對(duì)同一個(gè)問(wèn)題在兩個(gè)體系下的闡述。該實(shí)例將數(shù)理邏輯、集合論與代數(shù)系統(tǒng)三部分內(nèi)容建立關(guān)聯(lián)，有助于學(xué)生從宏觀角度把握離散數(shù)學(xué)課程的內(nèi)容。

實(shí)例2：等價(jià)關(guān)系與集合劃分的關(guān)聯(lián)。

引入一個(gè)生活中的實(shí)例“商販的蘋果”：市場(chǎng)的商販販?zhǔn)厶O果遵循統(tǒng)一進(jìn)貨，分檔次售出的方法，如圖2所示。

將蘋果編號(hào)，記作集合A={1，2，…，8}。

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

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

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

S={1，4，7}，S={2，5，8}，S={3，6}。可見其與“商販的蘋果”二例本質(zhì)完全相同，或者可以說(shuō)，前者是后者的數(shù)學(xué)模型，體現(xiàn)了建模并用數(shù)學(xué)模型解決實(shí)際應(yīng)用的思路。

三、離散數(shù)學(xué)課程的實(shí)用性

對(duì)于一些抽象的概念，如果脫離實(shí)用性，則難以激發(fā)學(xué)生的學(xué)習(xí)興趣；反之，如果使學(xué)生看到其實(shí)用價(jià)值，則對(duì)概念的領(lǐng)悟與記憶會(huì)更為深刻。

實(shí)例1：將抽象概念“關(guān)系閉包”具化為應(yīng)用案例。

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

本例實(shí)質(zhì)是求關(guān)系的傳遞閉包，且正是閉包這一抽象概念的實(shí)用案例。

實(shí)例2：代數(shù)系統(tǒng)中關(guān)于運(yùn)算封閉的解釋。

在表3所給出的運(yùn)算中，運(yùn)算*不是封閉的。

而在表4的代數(shù)系統(tǒng)中，運(yùn)算“o”是封閉的。

這兩個(gè)實(shí)例均來(lái)自生活中，通俗易懂，可使學(xué)生對(duì)認(rèn)識(shí)和接受抽象概念變得容易。

四、離散數(shù)學(xué)與其他學(xué)科的關(guān)聯(lián)

離散數(shù)學(xué)課程本身具有承上啟下的作用，課程內(nèi)容中有些引申自數(shù)學(xué)分析、線性代數(shù)等學(xué)科，有些可以應(yīng)用于數(shù)據(jù)結(jié)構(gòu)、數(shù)字電路、概率論、模糊數(shù)學(xué)等課程。以下列舉一些啟發(fā)性實(shí)例，幫助學(xué)生建立各學(xué)科之間的關(guān)聯(lián)，并在學(xué)習(xí)中體會(huì)融會(huì)貫通。

實(shí)例1：關(guān)系閉包的概念與數(shù)學(xué)分析中開集的閉包對(duì)照，可見閉包的本質(zhì)含義是一致的。

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

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

實(shí)例2：關(guān)系矩陣的復(fù)合運(yùn)算對(duì)比線性代數(shù)中的矩陣乘法，二者完全類似。

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

關(guān)系矩陣的復(fù)合運(yùn)算：關(guān)系矩陣M=[r]與M=[s]的復(fù)合矩陣M=M·M=[w]，其中w=

（r∧s）。

實(shí)例3：集合論與模糊數(shù)學(xué)。模糊集將元素與集合的隸屬關(guān)系由{0，1}擴(kuò)展到閉區(qū)間[0，1]，用隸屬度函數(shù)定義，因此可以看作集合論的推廣。

實(shí)例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}

五、結(jié)語(yǔ)

在離散數(shù)學(xué)授課過(guò)程中，對(duì)上述四部分內(nèi)容與觀點(diǎn)應(yīng)加以強(qiáng)調(diào)，并貫穿教學(xué)始終，同時(shí)要盡量通過(guò)實(shí)例闡釋使學(xué)生在學(xué)習(xí)過(guò)程中對(duì)課程的內(nèi)容有一些宏觀地把握，培養(yǎng)其邏輯思維和發(fā)散思維，并獲得應(yīng)用體驗(yàn)，最大程度的激發(fā)出學(xué)生的學(xué)習(xí)熱情，學(xué)好本門課程。

參考文獻(xiàn)：

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

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

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

[4]王全，陳樺.“離散數(shù)學(xué)”課程教學(xué)改革研究與實(shí)踐[J].計(jì)算機(jī)科學(xué)，2006，33（8）：36-38.

[5]常亮，徐周波，古天龍，董榮勝.離散數(shù)學(xué)教學(xué)中的計(jì)算思維培養(yǎng)[J].計(jì)算機(jī)教育，2011，（14）：90-94.