二元關系性質的組合性

劉云芬，陳敬華

(湖北師范學院 數學與統計學院，湖北 黃石 435002)

0 引言

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

1 二元關系的五種性質

文[4～5]給出了關系的五種性質定義如下：

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

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

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

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

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

2 主要結論

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

性質1 組合模式“11***”不可能出現，即是非空集合上的非空關系，具有自反性和反自反性的的非空關系R是不存在的。

證明 對于非空集合上的非空關系，由定義1和定義2易知自反性和反自反性是不可能同時滿足的，即組合模式“11***”不可能出現。

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

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

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

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

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

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

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

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

例1 設集合X={1,2,3} ， 考察X上關系具有的性質：

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)}.

解 根據定義,可以得如下結論:

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

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

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

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

參考文獻:

[1]石瑞平,張素芬.等價關系的判定及性質[J].數學的實踐與認知，2011,41(14)：230～233.

[2]李梅霞.離散數學中關系性質的判定方法[J].大學數學，2010,26(5)：203～206.

[3]董永紅,朱一心.二元關系的完全計數[J].數學的實踐與認識，2011,41(24)：217～220.

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

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