离散数学-二元关系

2024-01-11 03:36
文章标签 离散数学 二元关系

本文主要是介绍离散数学-二元关系,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

4.1关系的概念

1)序偶及n元有序组

由两个个体x和y,按照一定顺序排序成的、有序数组称为有序偶或有序对、二元有序组,

记作<x,y>,其中x是第一分量,y是第二分量。

相等有序偶:第一分量和第二分量分别相等。

三元有序组:也是一个有序偶,<<x,y>,z> 其中第一分量是一个有序偶。

(注意:<x,<y,y>>不是一个三元有序偶,只能第一分量作为有序偶。)

一般的,n元有序偶的第一分量为n-1元有序偶,第二分量为单独的分量。(举个例子,5元有序偶的第一分量有4个,第二分量只有一个)

2)笛卡尔积/直积

  给定集合A和集合B,若有序偶的第一分量属于集合A,第二份量属于集合B。这样的有序偶的集合叫做集合A和集合B的笛卡尔积或直积、叉积,记作A✖B。

约定:若A是空集,或者B是空集,那么A✖B也是空集。

若A、B是有限集合,则|A×B| = |A| |B|

一般的,笛卡尔积不满足交换律,即A✖B  != B✖A

笛卡尔积运算对集合并运算U和集合交运算n具有分配律。

A✖(B U C) = A ✖B U  A✖C

A的n节笛卡尔积记作A^n,A^n = A ✖ A ✖A ...✖A

一般的,若A1,A2,A3...An都是有限集合,则|A1 ✖ A2 ✖ ...An| = |A1| |A2|... |An|

3)二元关系的基本概念

  定义:任意一个有序偶的集合称为一个二元关系,记作R。如果<x,y>属于R,那么就称x和y有关系R,记作xRy。反之,就是x和y没有关系R。

设X和Y是集合,X✖Y的任意子集R称为X到Y的二元关系。记作R:X->Y。

特别的,当X = Y时,称R为X上的二元关系。

(X✖Y在前面的有序偶我们学习过,就是以X的元素为第一分量,以Y的元素作为第二份量组成的一个有序偶<x,y>的集合,也叫做笛卡尔积。X✖Y的结果是一个二元有序偶的集合)

设R是二元关系,称domR为R的定义域(也就是集合X),称ranR为R的值域(也就是集合Y)。

定义域domR和值域ranR一起称为R的域,记作FLDR。

若|X| =m,|Y| = n,则|X × Y| = mn,X×Y的不同子集共有2^mn个,于是从X到Y的二元关系共有2^mn个。(这里,要怎么理解?要记住,R本质上也是一个关系的集合,也就是X和Y中有关系R的元素的集合,而这个关系R可以是很多种)

注意:设X和Y是集合,则

1)空集是X×Y的子集,称为X到Y的空关系

2)X×Y称X到Y的痊愈关系

3){<x,x> |x属于X}称为X上的恒等关系,记作Ix。

4)二元关系的表示

有限集合的二元关系是一种集合,可以用集合的方法表示。

有三种表示方法:图示法、关系矩阵法、关系图法。

1)图示法

用大圆圈表示集合X和集合Y,放在两边,用小圆圈表示X和Y种所有的元素,旁边写上相应的元素名,有关系就用有方向的弧线连接起来。从第一分量指向第二分量。

2)关系矩阵法

3)关系图法

4.2关系的性质

主要的关系有自反性、反自反性、对称性、反对称性和传递性。

自反:对所有的元素x,都有<x,x>

反自反:多有的有序对不能有任何一个<x,x>

对称:对所有的x和y,只要有<x,y>就有<y,x>

反对称:一个对称都不能有

传递:对所有的<x,y>,必有<y,z>

4.3关系的运算

逆关系:即所有的有序对交换位置:<x,y> 的逆关系就是<y,x>

复合关系:通俗理解来说,一个二元关系R<x,y>和另一个二元关系S<y,z>做复合运算,将二元关系视作为某种运算或者说操作,通过二元关系R是的x得到y,再通过二元关系S是的y得到z。所以,从这个角度来理解,一般计算二元关系都是使用关系矩阵来实现这种从x到y到z的变换,即使R和S的复合计算即两个关系矩阵的相乘的结果。

关系的幂运算:通俗来说,假设有一个二元关系R,对于其关系图来说,一次幂就是点与点之间只走一步,2次幂就是点与点之间走两步,3次幂就是点与点之间走三步,以此类推。

4.4关系的闭包运算

自反闭包的计算:有一个二元关系R,其自反闭包r(R)等于其恒等关系并上R,恒等关系就是R中所有元素的自反,即<x,x>、<y,y>等。

对称闭包的运算:有一个二元关系R,其对称闭包等于R并上其逆关系(<x,y>的逆关系为<y,x>即二元有序对交换位置)。这很好理解,两个关系矩阵做布尔加法即可,对角线的两边对称。

传递闭包的运算:这个比较复杂,一般的计算方法是,R的传递闭包t(R)等于其关系矩阵的1次幂、2次幂....直到n次幂的矩阵做矩阵相加,得到的最终矩阵即传递闭包。

4.5等价关系与等价类

等价关系:自反、对称、传递。

什么叫做等价?若R是等价关系,其有序对<x,y>称为x等价于y。

等价类:是元素的集合,这个集合内的所有元素都是等价的,只要满足这一条件的都叫做等价类。

商集:R是一个等价关系,其所有元素的集合就是商集,记作A/R

4.6相容关系与相容类

相容关系:自反、对称

相容类:有一个定义在A上的相容关系r,对于任何属于A这个集合的任意两个元素有a1 r a2,即使他们之间构成相容关系,那么其就构成一个相容类。和等价类一样,都是元素的集合,而这个集合的元素都满足这个相容关系。

总结来说就是,等价类和相容类都是元素的集合,而这个元素都有等价的关系或者相容的关系。

4.7序关系与哈塞图

偏序关系:自反、反对称、传递

哈塞图:哈塞图是偏序关系的延申,通俗来说,有一个偏序关系r,有<x,y>必有<y,z>,对于构成的<x,z>,中间再没有其他关系例如<y,w><w,z>。

哈塞图:

以上图为例:

极大元:4

极小元:27,12,24

最大元:4

最小元:没有极小元

(注意:不论是最大还是最小元,都必须能和所有的其他元素能对比,即有路径,这很好理解,即既然都不能和所有的元素对比,那么有没有大小之分,而这很明显不符合最大或者最小的要求)
上界:对于一个哈塞图A,求比B的上确界,那么比B的所有元素大的元素的集合就是上界

下界:对于一个哈塞图A,求比B的上确界,那么比B的所有元素小的元素的集合就是下界

上确界:上界的最小值,很好理解,即从这个点开始以上都是上界

下确界:下界的最大值,也很好理解,即从这个点开始以下都是下届

这篇关于离散数学-二元关系的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/593032

相关文章

离散数学------关系理论

一、序偶和笛卡尔积 序偶 两个序偶如果相等,那么他们相对应的第一第二元素分别相等 笛卡尔积 笛卡尔积是集合之间的一种运算,运算的结果是个序偶,第一元素来自前面的集合,第二元素来自后面的集合。  两集合进行笛卡尔积运算后集合里的元素个数=两集合元素个数的乘积 二、关系 定义 每种关系都可以用序偶表示,关系是两集合笛卡尔积的子集。 表示方式 题型一:求两

离散数学中的逻辑应用(2)

目录 引言 1. 逻辑在决策分析中的应用 2. 逻辑在算法设计中的应用 3. 逻辑在数学证明中的应用 4. 逻辑在编程中的应用 5. 逻辑应用工具 6. 总结 引言 在上一篇文章中,我们介绍了逻辑的基本概念和运算。本篇文章将深入探讨如何将逻辑应用于实际问题中,如问题求解、决策分析和数学证明。通过具体的例子和推理步骤,你将能够理解逻辑在离散数学及其他领域中的广泛应用。

离散数学中的逻辑基础(1)

目录 引言 1. 命题及其逻辑运算 2. 逻辑等价与范式 3. 逻辑推理规则 4. 逻辑问题练习 5. 总结 引言 逻辑是离散数学的核心概念之一,它用于精确描述数学命题并分析其关系。逻辑不仅是数学证明的基础,也是计算机科学中算法设计和编程的基石。本篇文章将详细介绍逻辑学中的命题、逻辑运算和推理规则,帮助读者建立扎实的逻辑基础。 1. 命题及其逻辑运算 1.1 命题的定义

组合数学、圆排列、离散数学多重集合笔记

自用 如果能帮到您,那也值得高兴 知识点 离散数学经典题目 多重集合组合 补充容斥原理公式 隔板法题目 全排列题目:

离散数学-代数系统证明题归类

什么是独异点?  运算° 在B上封闭,运算° 可结合,且存在幺元。 学会合理套用题目公式+结合律       零元? 群中不可能有零元 几个结论要熟记: 1.当群的阶为1时,它的唯一元素视作幺元e 2.若群的阶大于1时,且同时存在幺元和零元的话,幺元不等于零元 纯个人理解: 因为零元和什么相乘,依旧是零元。 而零元又不等于幺元。 我们知道,一个

离散数学答疑 5

知识点:单侧连通,强连通,弱连通     前缀码:比如001和00101就不是。因为后者的前三位和前者的重复了  有向图的邻接矩阵求法:横着看 数据结构21-4分钟搞定邻接矩阵_哔哩哔哩_bilibili    可达矩阵是包含自反性的。可达矩阵是一个自反矩阵,这意味着对角线上的元素都是1,表示每个节点到自身是可达的。在图论中,可达矩阵用来描述有向图中所

离散数学---树

目录 1.基本概念及其相关运用 2.生成树 3.有向树 4.最优树 5.前缀码 1.基本概念及其相关运用 (1)无向树:连通而且没有回路的无向图就是无向树; 森林就是有多个连通分支,每个连通分支都是树的无连通的无向图; 树叶就是这个无向图里面的度数是1的节点,分支点就是度数大于等于2的节点,简单的讲就是没有其他的分支的顶点就叫做树叶,还可以从这个地方继续细分的顶点就叫

离散数学答疑 3

~A:A的补集 有时候空集是元素,有时候就是纯粹的空集 A-B的定义:   笛卡尔积:  求等价关系:先求划分再一一列举  不同划分:分几块。一块:两块:三块:分别计算  Ix是X上的恒等关系指包含:<a,a><b,b><c,c> Rc:逆矩阵 比如:<2,1>就变成了<1,2> 交:合取 并:析取 蓝色这里,是指把A补全了,让他变成一个等价关系的东西

破解凯撒密码(离散数学)

首先来看以下恺撒密码。 离散数学的一道作业题。 凯撒密码作为一种最为古老的对称加密体制,在古罗马的时候都已经很流行,他的基本思想是:通过把字母移动一定的位数来实现加密和解密。例如,如果密匙是把明文字母的位数向后移动三位,那么明文字母B就变成了密文的E,依次类推,X将变成A,Y变成B,Z变成C,由此可见,位数就是凯撒密码加密和解密的密钥。 题目如下: It is known t

C++实现离散数学中求合式表达式

在输入任何一个合式公式后,该段程序就会自动检测里面的命题变元,并要求为之输入真假值, 在输入完毕后就会得出该合式公式的真假值,运用的是递归的思想。 ----------YYC #include<iostream> #include<string> #include<map> using namespace std; /* *说明: *     用!表示 否定