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

(大連民族學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院，遼寧大連 116605)

等價(jià)關(guān)系判斷系統(tǒng)的設(shè)計(jì)

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

(大連民族學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院，遼寧大連 116605)

介紹了關(guān)系的定義、關(guān)系的自反性和反自反性、對(duì)稱性和反對(duì)稱性、傳遞性五條性質(zhì)，及其在計(jì)算機(jī)領(lǐng)域中的應(yīng)用。設(shè)計(jì)了判斷給定集合上關(guān)系的各種性質(zhì)的函數(shù)，并進(jìn)行了相關(guān)算法分析。設(shè)計(jì)了判斷等價(jià)關(guān)系的流程圖，利用計(jì)算機(jī)語言編程實(shí)現(xiàn)了等價(jià)關(guān)系判定的實(shí)驗(yàn)系統(tǒng)。該系統(tǒng)簡(jiǎn)單易于實(shí)現(xiàn)，在離散數(shù)學(xué)教學(xué)中，對(duì)學(xué)生掌握抽象理論具有較好的幫助作用。

等價(jià)關(guān)系;系統(tǒng)原理;算法設(shè)計(jì);函數(shù)

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

1 系統(tǒng)原理

關(guān)系是一個(gè)集合，而這個(gè)集合滿足以下條件之一:集合非空，且它的元素都是有序?qū)?或者集合是空集［6］。

1.1 關(guān)系的性質(zhì)

1.1.1 自反與反自反性質(zhì)

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

1.1.2 對(duì)稱與反對(duì)稱性質(zhì)

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

1.1.3 關(guān)系傳遞性質(zhì)

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

1.2 等價(jià)關(guān)系

設(shè)R為非空集合A上的關(guān)系，如果R是自反的、對(duì)稱的和傳遞的，則稱R為A上的等價(jià)關(guān)系。設(shè)R是一個(gè)等價(jià)關(guān)系，若＜x，y＞∈R，稱x等價(jià)于y，記做 x～y。

2 算法分析

為了判斷關(guān)系的自反、反自反、對(duì)稱、反對(duì)稱、傳遞性質(zhì)，可以設(shè)計(jì)出5個(gè)函數(shù)對(duì)這5條性質(zhì)分別進(jìn)行判斷。

2.1 判斷給定的關(guān)系是否為自反關(guān)系

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

具體步驟如下:

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

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

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

(4)若計(jì)數(shù)器count值與A中元素個(gè)數(shù)相等，則R為A上的自反關(guān)系;否則，R不是A上的自反關(guān)系。

2.2 判斷給定的關(guān)系是否為對(duì)稱關(guān)系

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

具體步驟如下:

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

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

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

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

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

2.3 判斷給定的關(guān)系是否為傳遞關(guān)系

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

具體步驟如下:

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

(2)計(jì)算R2的關(guān)系矩陣MR2的所有元素;

(3)若 m［i］［j］=1，且 m'［i］［j］!=1，則標(biāo)識(shí)符改變?yōu)閒lag=0，且退出循環(huán)執(zhí)行第(5)步;否則，flag 不變，j=i+1;j=j+1，i=i+1;

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

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

3 系統(tǒng)實(shí)現(xiàn)流程

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

創(chuàng)建關(guān)系類，其中包含的函數(shù)有構(gòu)造函數(shù)、賦值函數(shù)、判斷自反性質(zhì)函數(shù)、判斷對(duì)稱性質(zhì)函數(shù)、判斷傳遞性質(zhì)函數(shù);類中包含的數(shù)據(jù)有關(guān)系R的關(guān)系矩陣、集合A的元素個(gè)數(shù)、關(guān)系R的元素個(gè)數(shù)。構(gòu)造函數(shù)首先對(duì)關(guān)系矩陣賦初值全為0的矩陣;在賦值函數(shù)中輸入集合A中各元素值、二元關(guān)系R中的各有序?qū)Γ㈥P(guān)系矩陣中相對(duì)應(yīng)的元素值改為1。在對(duì)關(guān)系自反性質(zhì)的判斷函數(shù)中按照算法2.1編程實(shí)現(xiàn)算法，并完成結(jié)果判斷;在對(duì)關(guān)系對(duì)稱性質(zhì)的判斷函數(shù)中按照算法2.2編程實(shí)現(xiàn)算法，并完成結(jié)果判斷;在對(duì)關(guān)系傳遞性質(zhì)的判斷函數(shù)中按照算法2.3編程實(shí)現(xiàn)算法，并完成結(jié)果判斷。系統(tǒng)主函數(shù)提供菜單供用戶選擇，通過輸入的選項(xiàng)分別調(diào)用不同的函數(shù)。判斷給定的關(guān)系是否為等價(jià)關(guān)系的系統(tǒng)流程如圖1。

圖1 系統(tǒng)流程圖

4 結(jié)論

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

［1］馮玉芬，楊天棟.等價(jià)類劃分測(cè)試用例設(shè)計(jì)［J］.株洲師范高等專科學(xué)校學(xué)報(bào)，2007(10):43－45.

［2］張大陸，童熙.基于二元關(guān)系的語義Web的建立［J］.同濟(jì)大學(xué)學(xué)報(bào):自然科學(xué)版，2004(12):1677－1681.

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

［4］姜楠，王立明，林珅，等.離散數(shù)學(xué)網(wǎng)上學(xué)習(xí)系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)［J］.計(jì)算機(jī)工程與科學(xué)，2008(10):96－98.

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

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

［7］曹曉東.離散數(shù)學(xué)、算法及CAI［M］.大連:大連海事大學(xué)出版社，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(yè)務(wù)專項(xiàng)資金資助項(xiàng)目(DC10020114)，大連民族學(xué)院博士基金項(xiàng)目(20096203)。

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

(責(zé)任編輯 劉敏)