劉云芬，陳敬華

(湖北師范學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，湖北 黃石 435002)

0 引言

二元關(guān)系是離散數(shù)學(xué)中非常重要的內(nèi)容，一般的離散數(shù)學(xué)教材都介紹了關(guān)系的五種性質(zhì)-自反性、反自反性、對(duì)稱性、反對(duì)稱性和傳遞性。我們常見的幾種關(guān)系，比如：相容關(guān)系，等價(jià)關(guān)系和偏序關(guān)系等都是滿足這五種性質(zhì)中若干性質(zhì)的組合。一些文獻(xiàn)從不同的角度探討了二元關(guān)系的性質(zhì)問題，文[1～2]基于二元關(guān)系的矩陣討論了二元關(guān)系性質(zhì)的判別問題，文[3]利用整數(shù)拆分探討了特殊二元關(guān)系的計(jì)數(shù)問題。在教學(xué)過程中，我們發(fā)現(xiàn)部分同學(xué)對(duì)于二元關(guān)系性質(zhì)的把握存在一定的問題，本文從組合數(shù)學(xué)的角度來討論這五種性質(zhì)組合的存在性問題，并給出相關(guān)結(jié)論的證明。為了簡(jiǎn)化問題，本文僅考慮非空集合上的非空關(guān)系。

1 二元關(guān)系的五種性質(zhì)

文[4～5]給出了關(guān)系的五種性質(zhì)定義如下：

定義1 在集合X上的關(guān)系R，如對(duì)任意x∈X,有(x,x)∈R，則稱R是自反的。

定義2 在集合X上的關(guān)系R，如對(duì)任意x∈X,有 (x,x)?R，則稱R是反自反的。

定義3 在集合X上的關(guān)系R，如有(x,y)∈R，必有(y,x)∈R，則稱R是對(duì)稱的。

定義4 在集合X上的關(guān)系R，如有(x,y)∈R且x≠y，必有(y,x)?R，則稱R是反對(duì)稱的。

定義5 在集合X上的關(guān)系R，如有(x,y)∈R且(y,z)∈R，必有(x,y)∈R，則稱R是傳遞的。

2 主要結(jié)論

在這32種組合模式中，不可能出現(xiàn)的組合模式為：11***，*1*01，**110，*11*1，其中“*”號(hào)所在位置可以取1，也可以取0，以下將進(jìn)行證明。

性質(zhì)1 組合模式“11***”不可能出現(xiàn)，即是非空集合上的非空關(guān)系，具有自反性和反自反性的的非空關(guān)系R是不存在的。

證明 對(duì)于非空集合上的非空關(guān)系，由定義1和定義2易知自反性和反自反性是不可能同時(shí)滿足的，即組合模式“11***”不可能出現(xiàn)。

性質(zhì)2 組合模式“*1*01”不可能出現(xiàn)，即是非空集合X上，具有反自反性和傳遞性，而不具有反對(duì)性的非空關(guān)系R是不存在的。

證明 假設(shè)某一非空集合上存在這樣的非空關(guān)系R，設(shè) (a,b)∈R，由于R具有反自反性，則a≠b，若 (b,a)?R，R具有傳遞性，則(a,a)∈R，與R具有反自反性矛盾，若(b,a)?R，與R不具有反對(duì)稱性矛盾。

性質(zhì)3 組合模式“**110”不可能出現(xiàn)，即是非空集合X上，具有對(duì)稱性和反對(duì)稱性，而不具有傳遞性的非空關(guān)系R是不存在的。

證明 假設(shè)某一非空集合X上存在這樣的非空關(guān)系R，設(shè)(a,b)∈R,如a≠b，由于R具有反對(duì)稱性，有(b,a)?R，而R又具有對(duì)稱性，則(b,a)∈R，所以a=b，此時(shí)R應(yīng)有傳遞性，故矛盾。

性質(zhì)4 組合模式“*11*1”不可能出現(xiàn)，即是非空集合X上，具有反自反性、對(duì)稱性和傳遞性的非空關(guān)系R是不存在的。

證明 假設(shè)某一非空集合X上存在這樣的非空關(guān)系R，設(shè)(a,b)∈R，由于R具有反自反性，則a≠b，R具有對(duì)稱性，則 (b,a)∈R，又R具有傳遞性，則(a,a)∈R，這與R具有反自反性矛盾。

由以上討論容易看出，不可能出現(xiàn)的性質(zhì)組合模式具體有14種：11000,01001，00110,11100,11010,11001,10110，01110,01101，11110,11101,11011 ,01111,111111；以下將對(duì)其余18種性質(zhì)組合模式進(jìn)行實(shí)例說明。

性質(zhì)5 非空集合X上的非空關(guān)系R，不具備5種性質(zhì)中的任何一種的組合模式數(shù)是1，僅具有1種性質(zhì)的組合模式數(shù)是5，僅具有2種性質(zhì)的組合模式數(shù)為7，僅具有3種性質(zhì)的組合模式數(shù)為4，僅具有4種性質(zhì)的組合模式數(shù)為1，具有5種性質(zhì)的組合模式數(shù)是0.

例1 設(shè)集合X={1,2,3} ， 考察X上關(guān)系具有的性質(zhì)：

R1={(1,1),(1,2),(2,1),(1,3)},R2={(1,1),(2,2),(3,3),(1,3),(3,1),(3,2)},R3={(1,2),(2,1),(1,3)},R4={(1,2),(2,1) ,(3,3)},R5={(1,1),(1,2),(2,3),(3,1)},R6={(1,1),(1,2),(2,1),(2,2),(1,3)}.

R7={(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2)},R8={(1,1),(2,2),(3,3),(1,2),(2,3)},R9={(1,1),(2,2),(3,3),(1,2),(2,1),(1,3)},R10={(1,2),(2,1)},R11={(1,3),(3,2)},R12={(1,1),(2,2),(1,2),(2,1)},R13={(1,1),(1,2)}.

R14={(1,1),(2,2),(3,3),(1,2),(2,1)},R15={(1,1),(2,2),(3,3),(1,2)},R16={(1,2),(2,3),(1,3)},R17={(1,1)} ,R18={(1,1),(2,2),(3,3)}.

解 根據(jù)定義,可以得如下結(jié)論:

1)R1不具備五種性質(zhì)中的任意一種，R2僅具有自反性，R3僅具有反自反性，R4僅具有對(duì)稱性，R5僅具有反對(duì)稱性，R6僅具有傳遞性；

2)R7僅具有自反性和對(duì)稱性，R8僅具有自反和反對(duì)稱性，R9僅具有自反性和傳遞性，R10僅具有反自反性和對(duì)稱性，R11僅具有反自反性和反對(duì)稱性，R12僅具有對(duì)稱性和傳遞性，R13僅具有反對(duì)稱和傳遞性;

3)R14僅具有自反性、對(duì)稱性和傳遞性，R15僅具有自反性、反對(duì)稱性和傳遞性，R16僅具有反自反性、反對(duì)稱性和傳遞性，R17僅具有對(duì)稱性，反對(duì)稱性和傳遞性，R18僅具有自反性、對(duì)稱性、反對(duì)稱性和傳遞性。

從上面的討論可以看出：R1至R6對(duì)應(yīng)性質(zhì)組合模式分別為:00000,10000,01000,00100, 00010,00001；R7至R13對(duì)應(yīng)性質(zhì)組合模式分別為:10100,10010,10001,01100,01010,00101,00011；R14至R18對(duì)應(yīng)性質(zhì)組合模式分別為:10101,10011,01011,00111,10111.我們常見的相容關(guān)系只能由性質(zhì)組合模式“10100，10101, 10111”構(gòu)成，在上面的例子中R7，R14，R18便是相容關(guān)系，等價(jià)關(guān)系只能由性質(zhì)組合模式“10101,10111”構(gòu)成，比如上例中R14、R18便是等價(jià)關(guān)系。

參考文獻(xiàn):

[1]石瑞平,張素芬.等價(jià)關(guān)系的判定及性質(zhì)[J].數(shù)學(xué)的實(shí)踐與認(rèn)知，2011,41(14)：230～233.

[2]李梅霞.離散數(shù)學(xué)中關(guān)系性質(zhì)的判定方法[J].大學(xué)數(shù)學(xué)，2010,26(5)：203～206.

[3]董永紅,朱一心.二元關(guān)系的完全計(jì)數(shù)[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2011,41(24)：217～220.

[4]徐潔磐.離散數(shù)學(xué)導(dǎo)論(第三版)[M].北京：高等教育出版社，2006.

[5]耿素云,屈婉玲.離散數(shù)學(xué) [M].北京：高等教育出版社，2006.