李文鈺　杜忠復(fù)　張麗春

【摘要】本文研究總結(jié)了關(guān)系矩陣在離散數(shù)學(xué)教學(xué)中的應(yīng)用，具體包括關(guān)系矩陣、關(guān)系的復(fù)合與逆運(yùn)算、關(guān)系的性質(zhì)、關(guān)系的閉包運(yùn)算和等價(jià)關(guān)系.這樣離散數(shù)學(xué)中的問(wèn)題就可以通過(guò)矩陣?yán)糜?jì)算機(jī)來(lái)解決，進(jìn)而達(dá)到化抽象為具體，化繁為簡(jiǎn)的目的.

【關(guān)鍵詞】離散數(shù)學(xué)；關(guān)系矩陣；二元關(guān)系

離散數(shù)學(xué)是描繪一些離散量與量之間相互邏輯結(jié)構(gòu)及關(guān)系的一門科學(xué)，它的思想方法及內(nèi)容已經(jīng)滲透到計(jì)算機(jī)科學(xué)的各個(gè)領(lǐng)域，因此它成為計(jì)算機(jī)及相關(guān)專業(yè)的一門重要的專業(yè)基礎(chǔ)課.然而這門課程具有概念繁多，理論性較強(qiáng)，高度抽象的特點(diǎn)，容易致使學(xué)生對(duì)這門課的興趣不高，產(chǎn)生畏懼心理.因此，如何提高這門課程的教學(xué)質(zhì)量，具有很強(qiáng)的現(xiàn)實(shí)的意義.矩陣是線性代數(shù)的基本概念之一，矩陣可以使許多抽象的數(shù)學(xué)對(duì)象得到具體的表示，并把相關(guān)的運(yùn)算轉(zhuǎn)化為矩陣的簡(jiǎn)單運(yùn)算，使其在一定程度上化繁為簡(jiǎn)，變抽象為具體.它是解決很多實(shí)際問(wèn)題和數(shù)學(xué)問(wèn)題的強(qiáng)有力工具，在離散數(shù)學(xué)上也有很大程度的應(yīng)用.因此，我們希望把矩陣在離散數(shù)學(xué)中的應(yīng)用實(shí)例總結(jié)出來(lái)，以期能夠達(dá)到更好的教學(xué)效果.

為了更好地說(shuō)明矩陣在二元關(guān)系中的應(yīng)用，首先定義關(guān)系矩陣.

2.關(guān)系的性質(zhì)

關(guān)系的性質(zhì)主要包括：關(guān)系的自反性、反自反性、對(duì)稱性、反對(duì)稱性和傳遞性.這五條性質(zhì)都可以表現(xiàn)在關(guān)系矩陣上.若關(guān)系R具有自反性，當(dāng)且僅當(dāng)其關(guān)系矩陣MR主對(duì)角線上的元素全為1；若關(guān)系R具有反自反性，當(dāng)且僅當(dāng)其關(guān)系矩陣MR主對(duì)角線上的元素均為0；若關(guān)系R既不是自反的也不是非自反的，當(dāng)且僅當(dāng)其關(guān)系矩陣MR主對(duì)角線上既有0又有1；若關(guān)系R具有傳遞性，當(dāng)且僅當(dāng)M2R+MR=MR；若關(guān)系R有對(duì)稱性，當(dāng)且僅當(dāng)MR=MTR，即MR是對(duì)稱陣.這樣一來(lái)，學(xué)生有著對(duì)線性代數(shù)的基礎(chǔ)，原本陌生的二元關(guān)系的性質(zhì)就更直觀，更簡(jiǎn)潔地體現(xiàn)出來(lái)了.

3.關(guān)系的閉包運(yùn)算

二元關(guān)系的閉包運(yùn)算是離散數(shù)學(xué)教學(xué)的一個(gè)重點(diǎn)也是難點(diǎn)，它包括自反閉包、對(duì)稱閉包和傳遞閉包.我們知道閉包是包含有此關(guān)系的最小的關(guān)系.但大部分學(xué)生都會(huì)覺(jué)得閉包概念十分抽象，尤其在傳遞閉包的計(jì)算時(shí)感覺(jué)困難.但我們用矩陣來(lái)表述時(shí)，學(xué)生會(huì)更容易接受.

定理3 設(shè)R是集合A上的一個(gè)關(guān)系，則其自反包r（R）=R∪Q，用矩陣表示即為Mr（R）=MR+MQ，其中Q={（x，x）|x∈A}.

定理4 設(shè)R是集合A上的一個(gè)關(guān)系，則其對(duì)稱閉包s（R）=R∪R-1，用矩陣表示即為Ms（R）=MR+MR-1=MR+MTR.

定理5 設(shè)R是集合A上的一個(gè)關(guān)系，則其傳遞閉包t（R）=∪∞i=1Ri=R∪R2∪….用矩陣表示即為Mt（R）=MR+MR2+….

推論1 設(shè)R是含有n個(gè)元素的有限集合A上的一個(gè)關(guān)系，則其傳遞閉包t（R）=∪ni=1Ri.用矩陣表示即為Mt（R）=MR+MR2+…+MRn.

注：上述矩陣運(yùn)算均為布爾運(yùn)算.

4.等價(jià)關(guān)系

在研究等價(jià)關(guān)系時(shí)，我們?nèi)匀豢梢岳藐P(guān)系矩陣的特征來(lái)進(jìn)行判斷.

定理6 若R是集合A上的等價(jià)關(guān)系，當(dāng)且僅當(dāng)R的矩陣MR具有如下特征：

（1）MR的主對(duì)角線上的元素全為1；

（2）MR是對(duì)稱矩陣；

（3）MR可以經(jīng)過(guò)有限次把行與行及相應(yīng)的列與列調(diào)換為主對(duì)角型分塊矩陣，且對(duì)角線上每個(gè)子塊都是全1方陣.

本文研究總結(jié)了關(guān)系矩陣在二元關(guān)系的復(fù)合與逆運(yùn)算、關(guān)系的性質(zhì)、關(guān)系的閉包運(yùn)算和等價(jià)關(guān)系等幾方面的應(yīng)用.通過(guò)上述研究以及在實(shí)際離散數(shù)學(xué)教學(xué)中的經(jīng)驗(yàn)發(fā)現(xiàn)，矩陣的引入使得這一部分的知識(shí)更直觀，學(xué)生更易于接受.尤其對(duì)于計(jì)算數(shù)學(xué)和計(jì)算機(jī)相關(guān)專業(yè)的學(xué)生可以通過(guò)上機(jī)來(lái)計(jì)算相應(yīng)例題，把原本抽象的問(wèn)題具體化、簡(jiǎn)單化，進(jìn)而也提高了他們的專業(yè)興趣，起到了良好的教學(xué)效果.

【參考文獻(xiàn)】

[1]杜中復(fù)，陳兆均.離散數(shù)學(xué)[M].北京：高等教育出版社，2004.

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