離散數學中等價關系的性質

田素霞

（商丘師范學院 計算機與信息技術學院，河南 商丘 476000）

1 預備知識

“離散數學”是計算機專業的重要基礎課程和核心課程，等價關系是離散數學中非常重要的內容之一，本文介紹了等價關系的概念，給出了等價關系的一些性質。

定義1 設R為非空集合A上的二元關系,如果對任意x∈A，都有＜x,x＞∈R，則稱R具有自反性。

定義2 設R為非空集合A上的二元關系,如果對任意x，y∈A，若＜x,y＞∈R，則＜y,x＞∈R，稱 R 具有對稱性。

定義3 設R為非空集合A上的二元關系,如果對任意x，y，z∈A，若＜x,y＞∈R 且＜y,z＞∈R，都有＜x,z＞∈R，稱 R 具有傳遞性。

定義4 設R為非空集合A上的二元關系,如果R具有自反性、對稱性和傳遞性，則稱R為A上的等價關系。

2 主要結果

定理1 設R是集合A上的二元關系，令S={＜x,y＞∣ ?z∈A使＜x,z＞∈R且＜z,y＞∈R},若R是等價關系，則S也是等價關系。

證明:因為R是等價關系

（1）由于R是自反的，所以對任意 x∈A有＜x,x＞∈R，由 S的定義知＜x,x＞∈R 且＜x,x＞∈R，所以＜x,x＞∈S，所以 S 是自反的。

（2）若＜x,y＞∈S,則?z∈A 使＜x,z＞∈R 且＜z,y＞∈R。

因為R是對稱的，所以＜z,x＞∈R且＜y,z＞∈R，由S的定義知＜y,x＞∈S，所以S是對稱的。

（3）若＜x,y＞∈S 且＜y,z＞∈S，

則?u∈A 使＜x,u＞∈R 且＜u,y＞∈R

?v∈A 使＜x,v＞∈R 且＜v,y＞∈R

因為 R 是傳遞的，所以＜x,y＞∈R 且＜y,z＞∈R,所以＜x,z＞∈S

所以S是傳遞的。

故S是A上的等價關系。

定理2 設A,B為非空集合，R1，R2分別為A,B上的等價關系，令R={＜＜x1,y1＞,＜x2,y2＞＞∣＜x1,x2＞ ∈R1且＜y1,y2＞ R2}, 則 R 是 A×B 上的等價關系。

證明:（1）任意＜x,y＞∈A×B,因為 R1，R2分別為 A,B 上的等價關系，所以對任意 x∈A 有＜x,x＞∈R1，任意 y∈B 有＜y,y＞∈R2，所以對任意＜x,y＞∈A×B，由 R 的定義知＜＜x,y＞,＜x,y＞＞∈R。

所以R是自反的。

（2）任意＜x1,y1＞，＜x2,y2＞∈A×B,如果＜＜x1,y1＞,＜x2,y2＞＞∈R，則＜x1,x2＞∈R1且＜y1,y2＞∈R2。 因為 R1，R2都是對稱的， 所以＜x2,x1＞∈R1且＜y2,y1＞∈R2,所以＜＜x2,y2＞,＜x1,y1＞＞∈R，所以 R 是對稱的。

（3）任意＜x1,y1＞，＜x2,y2＞,＜x3,y3＞∈A×B,若＜＜x1,y1＞,＜x2,y2＞＞∈R 且＜＜x2,y2＞,＜x3,y3＞＞∈R， 則＜x1,x2＞∈R1，＜y1,y2＞∈R2且＜x2,x3＞∈R1，＜y2,y3＞∈R2。 由于 R1，R2都是傳遞的，所以＜x1,x3＞∈R1，＜y1,y3＞∈R2，所以＜＜x1,y1＞,＜x3,y3＞＞∈R，因此 R 也是傳遞的。

故R是A上的等價關系。

［1］田素霞.離散數學中等價關系性質探討[J].科技信息,2011(11).

［2］耿素云,屈婉玲.離散數學[M].北京:高等教育出版社,2004.

［3］左孝凌,李為鑒,劉永才.離散數學[M].上海:上海科學技術文獻出版社,1982.

［4］BEMARD K，ROBERT C，BUSBY.離散數學結構[M].北京:清華大學出版社,1997.