离散数学等价关系

离散数学中等价关系的性质【摘要】等价关系是离散数学中非常重要的内容之一，文[1]研究了等价关系的一些性质，本文在[1]的基础上对等价关系的性质做进一步的研究，得出了新的结论。

【关键词】离散数学；二元关系；等价关系1 预备知识“离散数学”是计算机专业的重要基础课程和核心课程，等价关系是离散数学中非常重要的内容之一，本文介绍了等价关系的概念，给出了等价关系的一些性质。

定义 1 设R 为非空集合A 上的二元关系，如果对任意x∈A，都有∈R，则称R具有自反性。

定义 2 设R 为非空集合A 上的二元关系，如果对任意x，y∈A，若∈R，则∈R，称R具有对称性。

定义 3 设R 为非空集合A 上的二元关系，如果对任意x，y，z∈A，若∈R且∈R，都有∈R，称R具有传递性。

定义 4 设R 为非空集合A 上的二元关系，如果R具有自反性、对称性和传递性，则称R 为A 上的等价关系。

2 主要结果定理1 设R是集合A上的二元关系，令S={∣？埚z∈A使∈R且∈R}，若R是等价关系，则S也是等价关系。

证明：因为R是等价关系（1）由于R是自反的，所以对任意x∈A有∈R，由S的定义知∈R且∈R，所以∈S，所以S是自反的。

（2）若∈S，则？埚z∈A使∈R且∈R。

因为R是对称的，所以∈R且∈R，由S的定义知∈S，所以S是对称的。

（3）若∈S且∈S，则？埚u∈A使∈R且∈R？埚v∈A使∈R且∈R因为R是传递的，所以∈R且∈R，所以∈S所以S是传递的。

故S是A上的等价关系。

定理2 设A，B为非空集合，R1，R2分别为A，B上的等价关系，令R={，>∣∈R1且R2} ，则R是A×B上的等价关系。

证明：（1）任意∈A×B，因为R1，R2分别为A，B上的等价关系，所以对任意x∈A有∈R1，任意y∈B有∈R2，所以对任意∈A×B，由R的定义知，>∈R。

所以R是自反的。

（2）任意，∈A×B，如果，>∈R，则∈R1且∈R2。

离散数学等价关系一、离散数学是一门什么样的学科？与数学的主流分支不同，离散数学看上去似乎没有一个确定的中心话题，内容很庞杂。

我曾做过一个粗略的统计，离散数学的内容涉及大约43个左右大大小小不同的话题，从集合、函数、关系、命题逻辑、谓词逻辑，到算法、计数、数据结构、递归、图论、概率、数论、形式语言与自动机，布尔代数、向量与矩阵，线性规划、抽象代数，编码理论、信息论，博弈论、运筹学、理论计算机科学等，真是那句俗话，XXXX是个筐，什么都可以往里装。

由于离散数学的内容包括面很广，一本通常意义上的教科书不可能全部涵盖，因此我们看到的教科书基本是上述内容集合的不同子集。

那么到底应当如何定义「离散数学」这门学科呢？如果我们使用集合的语言表达就是：（1）离散数学= {x∈数学| 离散结构(x)}其中，「离散数学」是「数学」的一个子集，「离散结构」是一个谓词，x代表任意数学学科。

现在来详细考察一下这个「离散数学」的定义式。

我们的考察，从为什么会出现这样一个学科开始。

首先，离散数学和其它数学分支不同，它并没有开辟数学的新领域，而是在既有的数学领域划出一个范围，以「离散结构」这个性质为标准，若某个数学内容具有「离散结构」的属性就划入。

那为什么会出现「离散数学」这门学科呢？回答是——是因为计算机的出现！！！因为计算机只能处理「离散」对象。

生活中「离散」对象和「连续」对象的例子是大米和水，前者是离散的，后者是连续的，因为米粒是可列举的、可数的，英语属于可数名词，中文可以用单位量词「粒」等表示，水是无法列举的、也是不可数的，因而在英语中属于不可数名词，中文则不可直接用单位量词表示。

形象地说，计算机可以处理像米粒这样的离散对象而无法直接处理像水这样的连续对象。

例如，我们在计算机屏幕上看到一条光滑的曲线。

按照微积分定义，一条光滑曲线在某个区间一定是连续的，因而一定可以找到区间内任意一点的极限。

换句话说，在这个区间内你是无法确定一个离散点的确切位置的，因为在这个区间内，所有的点都是无穷小，而这些无穷小的点的数量是无穷多。

-----WORD 格式--可编辑--专业资料-----
--完整版学习资料分享---- 离散数学作业
作业6 ——等价关系
1. 设R 和S 均为A 上的等价关系，确定下列各式，哪些是A 上的等价关系？如果是，证明之；否则，举反例说明。

（1）R ∩S （2）R ∪S （3）r (R-S)
（4）R- S （5）R ◦S （6）R 2
2. R 是集合A 上的二元关系，∀ a,b,c ,若aRb,且bRc,有cRa ,则称R 是循环关系。

证明R 是自反和循环的，当且仅当R 是一等价关系。

3. 设|A|=n ，在A 上可以确定多少个不同的等价关系？
4. 给定集合S={ 1 , 2 , 3, 4, 5 }，找出S 上的等价关系R ，此关系R 能够产生划分{{1，2}，{3}，{4，5}}，并画出关系图。

5. 设A={1，2，3，4，5}。

R 是集合A 上的二元关系，其关系矩阵如下图所示。

求包含R 的最小等价关系和该等价关系所确定的划分。

⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=0010001000
000000101000001R
M
6. （选做题）设R 与S 是A 上的等价关系，证明：
（1）R S 是A 上的等价关系，iff R S=S R ；
（2）R ∪S 是A 上的等价关系，iff R S ⊆S 且 S R ⊆R.。

选择题设R是集合A上的一个关系，若R具有自反性、对称性和传递性，则R称为：A. 偏序关系B. 全序关系C. 等价关系（正确答案）D. 函数关系下列哪个性质不是等价关系必须满足的？A. 自反性B. 对称性C. 传递性D. 反身性（正确答案）设R是集合A上的一个等价关系，若a, b ∈ A且(a, b) ∈ R，则下列哪个元素也一定属于R？A. (b, c)B. (a, c)C. (b, a)（正确答案）D. (c, a)给定集合A = {1, 2, 3}，若R是A上的一个等价关系，且1R2，2R3，则下列哪个元素也必然属于R？A. (1, 3)（正确答案）B. (2, 4)C. (3, 1, 2)D. (1, 1, 2)下列哪个关系不是等价关系？A. 整数集上的“等于”关系B. 实数集上的“大于等于”关系（正确答案）C. 人名集上的“同名”关系D. 图形集上的“全等”关系设R是集合A上的一个等价关系，对于a, b, c ∈ A，若aRb且bRc，则根据等价关系的性质，下列哪个结论成立？A. aRcB. bRaC. cRaD. aRc且cRa（正确答案）若R是集合A上的一个等价关系，且a, b ∈ A，但(a, b) ∈ R，则下列哪个结论可能成立？A. aRa且bRb（正确答案）B. aRbC. aRc且cRbD. aRb且bRc下列关于等价类的说法，哪个是正确的？A. 一个元素可以属于多个等价类B. 等价类中的元素不一定相互关联C. 等价类是集合的一个子集，且其中的元素两两等价（正确答案）D. 等价类中的元素数量必须相同设R是集合A上的一个等价关系，对于A中的任意元素a，由所有与a等价的元素组成的集合称为a的：A. 等价类（正确答案）B. 等价关系C. 等价元素D. 等价集。