淺談關系矩陣在離散數學教學中的應用

李文鈺　杜忠復　張麗春

【摘要】本文研究總結了關系矩陣在離散數學教學中的應用，具體包括關系矩陣、關系的復合與逆運算、關系的性質、關系的閉包運算和等價關系.這樣離散數學中的問題就可以通過矩陣利用計算機來解決，進而達到化抽象為具體，化繁為簡的目的.

【關鍵詞】離散數學；關系矩陣；二元關系

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

為了更好地說明矩陣在二元關系中的應用，首先定義關系矩陣.

2.關系的性質

關系的性質主要包括：關系的自反性、反自反性、對稱性、反對稱性和傳遞性.這五條性質都可以表現在關系矩陣上.若關系R具有自反性，當且僅當其關系矩陣MR主對角線上的元素全為1；若關系R具有反自反性，當且僅當其關系矩陣MR主對角線上的元素均為0；若關系R既不是自反的也不是非自反的，當且僅當其關系矩陣MR主對角線上既有0又有1；若關系R具有傳遞性，當且僅當M2R+MR=MR；若關系R有對稱性，當且僅當MR=MTR，即MR是對稱陣.這樣一來，學生有著對線性代數的基礎，原本陌生的二元關系的性質就更直觀，更簡潔地體現出來了.

3.關系的閉包運算

二元關系的閉包運算是離散數學教學的一個重點也是難點，它包括自反閉包、對稱閉包和傳遞閉包.我們知道閉包是包含有此關系的最小的關系.但大部分學生都會覺得閉包概念十分抽象，尤其在傳遞閉包的計算時感覺困難.但我們用矩陣來表述時，學生會更容易接受.

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

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

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

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

注：上述矩陣運算均為布爾運算.

4.等價關系

在研究等價關系時，我們仍然可以利用關系矩陣的特征來進行判斷.

定理6 若R是集合A上的等價關系，當且僅當R的矩陣MR具有如下特征：

（1）MR的主對角線上的元素全為1；

（2）MR是對稱矩陣；

（3）MR可以經過有限次把行與行及相應的列與列調換為主對角型分塊矩陣，且對角線上每個子塊都是全1方陣.

本文研究總結了關系矩陣在二元關系的復合與逆運算、關系的性質、關系的閉包運算和等價關系等幾方面的應用.通過上述研究以及在實際離散數學教學中的經驗發現，矩陣的引入使得這一部分的知識更直觀，學生更易于接受.尤其對于計算數學和計算機相關專業的學生可以通過上機來計算相應例題，把原本抽象的問題具體化、簡單化，進而也提高了他們的專業興趣，起到了良好的教學效果.

【參考文獻】

[1]杜中復，陳兆均.離散數學[M].北京：高等教育出版社，2004.

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