離散數(shù)學中關系理論的系統(tǒng)實驗設計

文章編號：1672-5913(2008)20-0129-02

摘 要：離散數(shù)學作為一門高度抽象的計算機專業(yè)課，為了激發(fā)學生的學習興趣，本文系統(tǒng)地介紹了其關系理論中的實驗設計，意在培養(yǎng)學生理解理論知識的同時鍛煉學生的思維構架和計算機語言操作能力。

關鍵詞：離散數(shù)學；關系理論；實驗設計

中圖分類號：G642 文獻標識碼：A

1 引言

離散數(shù)學是計算機科學與技術專業(yè)的一門重要學科，它以研究離散量的結(jié)構和相互間的關系為主要目標，所涉及到的一些概念、理論和方法被大量地應用于其他學科中。例如，數(shù)理邏輯在應用于人工智能理論研究的同時，著重培養(yǎng)了學生的概括抽象能力、邏輯思維能力、歸納構造能力；圖論和集合論不僅為數(shù)據(jù)結(jié)構和算法科學奠定了數(shù)學基礎，同時也為軟件工程和數(shù)據(jù)庫提供了抽象和描述的重要方法。

然而，由于這門課程具有概念多、理論性強、高度抽象等特點，學生普遍反應難于理解掌握，同時由于學生知識面的局限又導致學生認為該門課程對專業(yè)知識無用，致使學生學習興趣不高，教學效果不理想等現(xiàn)象。因此，激發(fā)學生的學習積極性和主動性，培養(yǎng)學生的創(chuàng)新意識和創(chuàng)新能力成了離散數(shù)學教學的當務之急。而在離散數(shù)學的教學過程中適當?shù)囊胍恍嶒炘O計，不僅是對離散數(shù)學的基本理論的很好驗證，也鍛煉了學生計算機語言的操作能力，同時也為其他課程的學習做了一個很好的鋪墊。

本文將以關系理論為基礎，深入探討離散數(shù)學實驗設計的可行性。

2 關系理論的實驗可行性

在離散數(shù)學中，關系理論是其一個重要的組成部分，它的知識點主要包括關系的性質(zhì)、關系的復合、逆運算和閉包運算、關系的劃分和覆蓋，以及等價關系、相容關系、序關系幾種特殊的關系，這些內(nèi)容都可以建立在矩陣的基礎上，因此本文以關系理論為基礎，設計了一個系統(tǒng)的模型，在加深學生對理論理解掌握程度的同時，也有效地鍛煉了學生的編程操作能力，激發(fā)了學生的學習興趣[1][2]。

3 設計模型

離散數(shù)學中關系的表示可以采用矩陣法，矩陣在計算機中可以以二維數(shù)組來存儲，而數(shù)組的建立和存儲在計算機語言中都有介紹，因此這一部分在本文中將不再贅述，而以算法的實現(xiàn)為討論的重點。這里，假定關系R1、R2均是集合X上的二元關系，其中X中有n個元素，將R1、R2的關系矩陣設為M1、M2。

3.1 關系性質(zhì)的算法設計

關系的性質(zhì)主要有自反性、對稱性、傳遞性、反自發(fā)性、反對稱性，其中除了傳遞性外，其它四個性質(zhì)的判別方法都比較簡單且易于實現(xiàn)[1[2]]，因此，這里主要給出傳遞性的判別方法。從矩陣關系圖上是不能直接得出的，因此可以通過求關系的傳遞閉包來實現(xiàn)傳遞性的判斷，而傳遞閉包的實現(xiàn)需要借助于關系的復合運算，因此可以先給出關系的復合運算和閉包運算的算法設計。

3.2 關系的復合運算算法設計

給定關系R1、R2，計算R1和R2的復合關系R的關系矩陣M：

(1) 置i=1， j=1；

(2) 按邏輯乘和邏輯加計算 ；

(3) j=j+1，若j≤n，轉(zhuǎn)(2)，否則轉(zhuǎn)(4)；

(4) i=i+1，若i≤n，轉(zhuǎn)(2)，否則停止。

3.3 關系的閉包運算算法設計

從關系的已知理論可以方便地計算出一個關系的自反和對稱閉包，因此我們這里重點給出傳遞閉包的算法設計。

若 ，則R具有傳遞性。這里， 表示R的i次復合運算。由此，可以通過調(diào)用關系的復合運算來實現(xiàn)。

(1) 置MR=M， M1=M， M2=M， i=1；

(2)，調(diào)用3.2中算法計算M，按邏輯加計算；

(3) 若 ， 置 ，轉(zhuǎn)(2)，否則轉(zhuǎn)(4)；

(4)為 的傳遞閉包，同時若 ，則 具有傳遞性，否則 不具有傳遞性。

3.4 等價關系與劃分的判定算法設計

由等價關系的定義可知，等價關系具有自反、對稱、傳遞性。其中，自反、對稱性的判定可以直接通過矩陣得出，傳遞關系可以通過調(diào)用3.3算法驗證。當驗證了一個關系是等價關系后，就可以由該關系得到相應的劃分。已知等價關系和劃分是一一對應性的，因此可以通過等價關系來判斷劃分。設集合 上有一個等價關系 ，把與 的固定元 有等價關系的元素放在一起做成一個子集 ，則所有這樣的子集就是由關系確定的一個劃分 。具體算法如下：

(1) 設X中有n個元素，xi是X中第i個元素，置i=1，；

(2) 令 ， ；

(3) 若 ，則 ；

(4) j=j+1，若i≤n，轉(zhuǎn)(3)，否則置 ，轉(zhuǎn)(5)；

(5) 若i≤n，則置i=i+1，轉(zhuǎn)(2)，否則結(jié)束；

3.5 相容關系與覆蓋的判定算法設計

相容關系具有自反、對稱性。因此一個關系是否是相容關系可以參照3.4中算法判定。

3.6 序關系中各個特殊元素的確定

一個偏序集合 ，且 是 一個非空子集，則 上一定有極大元、極小元，但最大元、最小元卻不一定存在。設 中有 個元素，下面給出這幾個元素的判定算法：

極小(大)元的判定：

(1) 設bi是B中第i個元素，置i=1；

(2) 令j=1；

(3.1)若 或( 且 )，則 ，轉(zhuǎn)(3.1)，否則轉(zhuǎn)(4.1)；

(3.2)若 或( 且 )，則 ，轉(zhuǎn)(3.2)，否則轉(zhuǎn)(4.2)；

(4.1)若 ，則 ，轉(zhuǎn)(2)，若 ，則 是 中極小元。

(4.2)若 ，則 ，轉(zhuǎn)(2)，若 ，則 是 中極大元。

最小(大)元的判定：

(1) 設 是 中第 個元素，置 ；

(2) 令 ；

(3.1)若 且 ，則 ，轉(zhuǎn)(3.1)，否則轉(zhuǎn)(4.1)；

(3.2)若 且 ，則 ，轉(zhuǎn)(3.2)，否則轉(zhuǎn)(4.2)；

(4.1)若 ，則 ，轉(zhuǎn)(2)，若 ，則 是 中最大元。

(4.2)若 ，則 ，轉(zhuǎn)(2)，若 ，則 是 中最小元。

4 小結(jié)

本文以關系理論為基礎，重點討論了其各個知識點的算法設計并給出了具體的算法設計思想。通過本文的算法練習，可以培養(yǎng)學生的想象能力、探索能力和知識遷移能力，使學生的思維具有發(fā)散性，激發(fā)了學生的學習興趣，實驗設計的成功也給了學生一定的成就感，同時使得學生在練習計算機語言操作的同時加深了對離散數(shù)學中理論的理解，可謂一舉兩得。

參考文獻

[1] 涂建斌，周小強．離散數(shù)學課程教學改革初探[J]．數(shù)學理論與應用，2001，(11)，41-42.

[2] 何鋒．離散數(shù)學教學中的命題符號化難點討論[J]．計算機教育，2007，(9).38-40.

[3] 左孝凌．離散數(shù)學[M]．上?？茖W技術文獻出版社，1998.

[4] 徐鳳生．離散數(shù)學及其應用[M]．北京：機械工業(yè)出版社，2006.

Systemic Experiment Design of Relation Theory in Discrete Mathematics

YU Hong-bin

(School of Computer and Information technology， Henan Normal University ，Henan Xinxiang 453007)

Abstract: Discrete Mathematics is a height abstract of the calculator professional lesson， give tremendous pressure when student's study it. In order to string up student's interesting， a systemic experiment about relation theory is introduced in this paper introduced， to toughens student's thinking frame and develop the ability in operate computer language， at the time to train students’ comprehension of theories knowledge.

Keyword: Discrete Mathematics， relation theory， experiment designs

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”