陳瓊 楊潔 郭妍

摘 要： 高校課程《離散數(shù)學》是應(yīng)用數(shù)學的一個重要分支，也是計算機專業(yè)的核心課程之一，還與《數(shù)據(jù)結(jié)構(gòu)》、《操作系統(tǒng)》、《軟件工程》、《數(shù)據(jù)庫系統(tǒng)》、《人工智能》等課程聯(lián)系緊密.本文對矩陣在離散數(shù)學集合論中的應(yīng)用展開討論，期望為初學者和數(shù)學工作者在學習離散數(shù)學時提供參考.

關(guān)鍵詞： 離散數(shù)學 關(guān)系矩陣 關(guān)系的閉包

《離散數(shù)學》課程主要包括矩陣代數(shù)、集合論、數(shù)理邏輯、代數(shù)系統(tǒng)、圖論五部分.通過離散數(shù)學的學習，可以提高抽象思維和嚴格的邏輯推理能力，養(yǎng)成良好的邏輯性、創(chuàng)新性、系統(tǒng)性、發(fā)散性等思維習慣.矩陣是線性代數(shù)中的一個基本概念，可以使很多抽象的數(shù)學概念得到具體的表示，并且把運算轉(zhuǎn)換成簡單的矩陣運算.矩陣成為解決許多數(shù)學問題的有力工具，在離散數(shù)學中的應(yīng)用也很廣泛.下面就矩陣應(yīng)用的實例進行討論.

1.矩陣的定義

由m×n個數(shù)a■（i=1，2，…，m；j=1，2，…，n），在括號（ ）內(nèi)排列成m行n列（橫的稱行，縱的稱列）的一個長方形數(shù)表a■ a■ … a■a■ a■ … a■… … … …a■ a■ … a■，稱為矩陣A■=（a■）■.通常用大寫字母A、B…表示，其中a■稱為矩陣第i行第j列的元素.

2.關(guān)系矩陣

定義：設(shè)X，Y是任意兩個集合，則稱笛卡爾積X×Y的任一子集為從X到Y(jié)的二元關(guān)系，簡稱關(guān)系，記為R，R？哿X×Y.設(shè)A={x■，x■，…，x■}，R是A上的關(guān)系，

若〈x■，x■〉∈R，則r■=1；若〈x■，x■〉？埸R，則r■=0，則

（r■）=r■ r■ … r■r■ r■ … r■… … … …r■ r■ … r■是R的關(guān)系矩陣，記作M■.

例如：A={1，2，3，4}，R={〈1，1〉，〈1，3〉，〈2，3〉，〈3，2〉，〈4，2〉}，則R的關(guān)系矩陣是M■=1 0 1 00 0 1 00 1 0 00 1 0 0.

3.關(guān)系的五種性質(zhì)

不僅反映在集合表達式上，而且明顯地反映在關(guān)系矩陣上，特點如下表：

4.關(guān)系的閉包

定理：設(shè)R為A上的關(guān)系，則有（1）自反閉包r（R）=R∪R■；（2）對稱閉包s（R）=R∪R■；（3）傳遞閉包t（R）=R∪R■∪R■∪…

例1：已知關(guān)系矩陣M■=1 1 00 0 01 1 0，求它的自反閉包r（R）、對稱閉包s（R）和傳遞閉包的關(guān)系矩陣.

解：M■=M■∪M■=1 1 00 1 01 1 1 M■=M■∪M■=1 1 11 0 11 1 0

M■=1 1 00 0 01 1 0■=1 1 00 0 01 1 0=M■，則得出R=R■=R■=R■（n=1，2，3…）

而t（R）=R∪R■∪R■∪…=R，有M■=M■=1 1 00 0 01 1 0.

關(guān)系的表示方法關(guān)系圖主要表達結(jié)點與結(jié)點間的鄰接關(guān)系，就是使用上面方法直接從R的關(guān)系矩陣得到.

例2：R的關(guān)系圖為 ，

試給出它的自反閉包r（R）、對稱閉包s（R）和傳遞閉包t（R）的關(guān)系圖.

解：自反閉包r（R）的關(guān)系圖為，

對稱閉包s（R）的關(guān)系圖為，

下面求傳遞閉包的關(guān)系矩陣：

M■=0 1 0 0 00 0 1 0 10 0 0 1 00 0 1 0 00 0 0 0 1 M■=0 0 1 0 10 0 0 1 10 0 1 0 00 0 0 1 00 0 0 0 1

M■=M■.M■=0 0 0 1 10 0 1 0 10 0 0 1 00 0 1 0 00 0 0 0 1 M■=M■.M■=0 0 1 0 10 0 0 1 10 0 1 0 00 0 0 1 00 0 0 0 1=M■

M■∪M■∪M■=0 1 1 1 10 0 1 1 10 0 1 1 00 0 1 1 00 0 0 0 1

則t（R）={〈a，b〉，〈a，c〉，〈a，d〉，〈a，e〉，〈b，c〉，〈b，d〉，〈b，e〉，〈c，c〉，〈c，d〉，〈d，c〉，〈d，d〉，〈e，e〉}

得到傳遞閉包的關(guān)系圖為.

參考文獻：

[1]陳華峰，楊勇.離散數(shù)學基礎(chǔ)[M].北京：中國水利水電出版社，2012.

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

[3]李文鈺，杜忠復(fù)，張麗春.淺談關(guān)系矩陣在離散數(shù)學教學中的應(yīng)用研究[J].數(shù)學學習與研究，2015.3.