等價關系判斷系統的設計

姜 楠，焉德軍，李笑牛，王 波，紫春平

(大連民族學院計算機科學與工程學院，遼寧大連 116605)

等價關系判斷系統的設計

姜 楠，焉德軍，李笑牛，王 波，紫春平

(大連民族學院計算機科學與工程學院，遼寧大連 116605)

介紹了關系的定義、關系的自反性和反自反性、對稱性和反對稱性、傳遞性五條性質，及其在計算機領域中的應用。設計了判斷給定集合上關系的各種性質的函數，并進行了相關算法分析。設計了判斷等價關系的流程圖，利用計算機語言編程實現了等價關系判定的實驗系統。該系統簡單易于實現，在離散數學教學中，對學生掌握抽象理論具有較好的幫助作用。

等價關系;系統原理;算法設計;函數

集合的元素之間的關系被表示成一種結構，這種結構叫做關系。在計算機科學中，關系理論具有重要意義。例如，數字計算機的邏輯設計和時序設計中，都應用了等價關系和相容關系的概念。在編譯程序設計，數據結構等領域中，也涉及到關系的部分內容。關系理論在計算機科學技術中的應用還包括計算機程序的輸入、輸出關系、數據庫的數據特性關系等。關系理論在信息安全中的基于角色的訪問控制中也有應用，角色關系就是一種偏序關系。關系理論還被應用在軟件測試中，等價類劃分是黑盒測試的典型方法之一［1－3］。關系的應用是十分廣泛的，尤其是等價關系在計算機科學中有著重要的地位，因而，對等價關系的研究具有重要意義［4－5］。本文主要設計了對關系性質進行判斷的算法，進而設計出判斷給定的關系是否為等價關系的函數，最后通過程序設計實現了該判斷系統。等價關系判斷系統把抽象難以理解的關系性質通過形象直觀的軟件程序表現出來，這樣既可以激發學生的學習興趣，又可以促進學生對抽象理論的理解。

1 系統原理

關系是一個集合，而這個集合滿足以下條件之一:集合非空，且它的元素都是有序對;或者集合是空集［6］。

1.1 關系的性質

1.1.1 自反與反自反性質

設R為集合A上的關系，如果?x(x∈A→＜x，x＞∈R)，則稱R在A上是自反的;如果?x(x∈A→＜x，x＞?R)，則稱R在A上是反自反的。也就是說如果關系R的關系矩陣主對角線上的值全為1，則R是自反的;如果主對角線上的值全為0，則R是反自反的。如果主對角線上的值既有1又有0，則R是既不是自反的也不是反自反的。因而可以通過判斷關系矩陣中的主對角線上元素值是否為1來確定這個關系是自反的或反自反的［6］。

1.1.2 對稱與反對稱性質

設R為集合A上的關系，若?x?y(x，y∈A∧ ＜x，y＞∈R→ ＜y，x＞ ∈R)，則稱 R 為 A 上對稱的關系;若?x?y(x，y∈A∧ ＜x，y＞∈R∧ ＜y，x＞∈R→x=y)，則稱R為A上反對稱的關系。如果關系R是對稱的，則其關系矩陣MR關于主對角線是對稱的;如果關系R是反對稱的，則對于其關系矩陣中第i行第j列的元素mij在i≠j并且mij=1 時，一定有 mji=0。即當 i≠j時 mij與 mji可以同時為0，可以一個是1，一個是0，但是不能同時為1。如果一個關系矩陣只在主對角線位置的元素有1，其他元素都是0，那么這個關系既是對稱的又是反對稱的。

1.1.3 關系傳遞性質

設R為集合A上的關系，若?x?y?z(x，y，z∈A∧ ＜x，y＞∈R∧ ＜y，z＞∈R→ ＜x，z＞∈R)，則稱R是A上的傳遞關系。給定關系R的關系矩陣MR，也可以判斷關系R是否為可傳遞的。由關系R的可傳遞性定義可知，若關系R是可傳遞的，則由mik=1∧mkj=1一定可以推出mij=1。關系R是可傳遞的還可以描述為由mij=0一定可以推出 mik=0∨mkj=0［7］。

1.2 等價關系

設R為非空集合A上的關系，如果R是自反的、對稱的和傳遞的，則稱R為A上的等價關系。設R是一個等價關系，若＜x，y＞∈R，稱x等價于y，記做 x～y。

2 算法分析

為了判斷關系的自反、反自反、對稱、反對稱、傳遞性質，可以設計出5個函數對這5條性質分別進行判斷。

2.1 判斷給定的關系是否為自反關系

判斷給定的關系是否為自反的函數記為int Reflexive()。如果給定的關系是自反的，則返回1，否則返回0。通過判斷給定關系R的關系矩陣MR主對角線上元素是否全部為1，來確定給定的關系R是否為自反的。如果MR主對角線上元素全部為1，則R是自反的，否則R不是自反的。

具體步驟如下:

(1)給定包含k個元素的集合A，其上的關系R及n階關系矩陣MR，計數器count=0，i=1;

(2)在關系矩陣MR中查看主對角線第i個元素 m［i］［i］是否等于 1，若 m［i］［i］=1，則計數器count++ ，若 m［i］［i］ =0，則計數器 count值不變，i=i+1;

(3)if i=n，執行(4)，否則，回到(2);

(4)若計數器count值與A中元素個數相等，則R為A上的自反關系;否則，R不是A上的自反關系。

2.2 判斷給定的關系是否為對稱關系

判斷給定的關系R是否對稱的函數為int Symmetric()，如果R是對稱的，則返回1，否則返回0。通過判斷矩陣MR中的所有元素是否關于主對角線對稱來確定給定的關系是否為對稱的，如果MR中的所有元素關于主對角線都是對稱的，則R是對稱的，否則R不是對稱的。

具體步驟如下:

(1)給定包含p個元素的集合A，定義在其上的包含l個元素的關系R，及n階關系矩陣MR。初始化R中對稱元素計數器count=0，對角線計數器 k=0，i=1，j=1;

(2)if m［i］［i］=0，則計數器 k++;否則，k不變，i=i+1;

(3)若 m［i］［j］=1 并且 m［i］［j］=m［j］［i］，則計數器 count++;否則，count不變，j=i+1;j=j+1，i=i+1;

(4)if i=n，j=n，執行(5)，否則，回到(3);

(5)若 count=(l－k)/2，則R具有對稱性;否則R不具有對稱性。

2.3 判斷給定的關系是否為傳遞關系

判斷給定的關系R是否為傳遞的函數為int Transitive()，如果R是傳遞的，則返回1，否則返回0。首先求出該關系R的二次冪R2的關系矩陣MR2，然后判斷 MR2中所有的值為1的元素m'ij與MR中對應位置的元素 mij是否相等且為1，如果是，則R是可傳遞的，否則R不是可傳遞的［8］。

具體步驟如下:

(1)給定包含p個元素的集合A，定義在其上的包含l個元素的關系R，及n階關系矩陣MR。初始化標識符為flag=0，i=1，j=1;

(2)計算R2的關系矩陣MR2的所有元素;

(3)若 m［i］［j］=1，且 m'［i］［j］!=1，則標識符改變為flag=0，且退出循環執行第(5)步;否則，flag 不變，j=i+1;j=j+1，i=i+1;

(4)if i=n，j=n，執行(5)，否則，回到(3);

(5)判斷標識符flag的值，若flag=1，則關系R具有傳遞性;若flag=0，則關系R不具有傳遞性。

3 系統實現流程

對于給定集合A上的關系R，如果是以集合或關系圖的形式表示的，要把它們轉換成關系矩陣的形式，然后才能進行判斷。對于用戶輸入的關系，系統先判斷關系中的定義域和值域中的每一個元素是否為集合A中的元素，如果有不屬于A的元素，則提示用戶的輸入不合法并提示系統停止運行。然后判斷給定的關系是否具有自反性、對稱性和傳遞性，如果具有這些性質，則可以確定關系R是為等價關系。

創建關系類，其中包含的函數有構造函數、賦值函數、判斷自反性質函數、判斷對稱性質函數、判斷傳遞性質函數;類中包含的數據有關系R的關系矩陣、集合A的元素個數、關系R的元素個數。構造函數首先對關系矩陣賦初值全為0的矩陣;在賦值函數中輸入集合A中各元素值、二元關系R中的各有序對，并將關系矩陣中相對應的元素值改為1。在對關系自反性質的判斷函數中按照算法2.1編程實現算法，并完成結果判斷;在對關系對稱性質的判斷函數中按照算法2.2編程實現算法，并完成結果判斷;在對關系傳遞性質的判斷函數中按照算法2.3編程實現算法，并完成結果判斷。系統主函數提供菜單供用戶選擇，通過輸入的選項分別調用不同的函數。判斷給定的關系是否為等價關系的系統流程如圖1。

圖1 系統流程圖

4 結論

關系是離散數學課程的重要部分，在計算機和通信等領域中也有廣泛的應用。本文主要研究等價關系判斷系統的原理與算法設計，對任意輸入的表示有窮集上的關系，確定這個關系是否為自反的或反自反的、對稱的或反對稱的、是否傳遞的，進而判斷出這個關系是否為等價關系。該系統設計的目的是使學生掌握利用計算機語言實現判斷關系性質的基本方法，這不僅可以使學生鞏固書本上學過的理論知識，把抽象知識轉化為具體的程序設計，提高學生的學習興趣，而且可以培養學生的算法設計和程序設計能力。使學生在做中學，學中做，進而提高學生的抽象思維能力、分析問題和解決問題能力。

［1］馮玉芬，楊天棟.等價類劃分測試用例設計［J］.株洲師范高等專科學校學報，2007(10):43－45.

［2］張大陸，童熙.基于二元關系的語義Web的建立［J］.同濟大學學報:自然科學版，2004(12):1677－1681.

［3］易國洪，盧炎生.基于EFSM模型的等價類測試［J］.計算機科學，2007，34(1):281 －284.

［4］姜楠，王立明，林珅，等.離散數學網上學習系統的設計與實現［J］.計算機工程與科學，2008(10):96－98.

［5］姜楠.離散數學課程建設與教學改革探討［J］.大連民族學院學報，2005(6):86－87.

［6］屈婉玲，耿淑云，張立昂.離散數學［M］.北京:清華大學出版社，2005.

［7］曹曉東.離散數學、算法及CAI［M］.大連:大連海事大學出版社，1996.

［8］ BERNARD K，ROBERT C B，SHARON C R.Discrete Mathematical Structures［M］.Higher Education Press，2001.

Design of Equivalence Relations Judge System

JIANG Nan，YAN De－jun，LI Xiao －niu，WANG Bo，Zi Chun －ping
(College of Computer Science and Engineering，
Dalian Nationalities University，Dalian Liaoning 116605 ，China)

The definition of relation，relations properties about to reflexive and irreflexive，symmetric and antisymmetric and transitive，and its application in computer science has been recited.The functions for judging relations properties in the set has been designed，and the interrelated algorithms have been analyzed.The flow chart for determining equivalence relations has been developed，and the experiment system of equivalence relations judgement has been implemented based on computer programming language.The system is easy to be realized and can be used in discrete mathematics teaching to help the students to understanding of abstract theory.Key words:equivalence relations;system principle;algorithm design;function

O158

A

1009－315X(2011)05－0496－03

2011－07－04

中央高?；究蒲袠I務專項資金資助項目(DC10020114)，大連民族學院博士基金項目(20096203)。

姜楠(1964－)，女，山東龍口人，教授，主要從事信息安全研究。

(責任編輯 劉敏)