离散数学中等价关系的性质

田素霞

（商丘师范学院 计算机与信息技术学院，河南 商丘 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.