離散數學中關系理論的系統實驗設計

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

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

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

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

1 引言

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

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

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

2 關系理論的實驗可行性

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

3 設計模型

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

3.1 關系性質的算法設計

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(2) 令 ， ；

(3) 若 ，則 ；

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

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

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

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

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

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

極小(大)元的判定：

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

(2) 令j=1；

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

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

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

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

最小(大)元的判定：

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

(2) 令 ；

(3.1)若 且 ，則 ，轉(3.1)，否則轉(4.1)；

(3.2)若 且 ，則 ，轉(3.2)，否則轉(4.2)；

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

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

4 小結

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

參考文獻

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

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

[3] 左孝凌．離散數學[M]．上海科學技術文獻出版社，1998.

[4] 徐鳳生．離散數學及其應用[M]．北京：機械工業出版社，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

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