离散数学笔记(2):关系1.有序组、关系及其表示

By | 2020年4月4日

注:仅为个人学习笔记(上学天天翘课学得稀烂,现在回头再学。。。),内容一定会有不严谨(甚至错误)的地方,内容仅供参考。另求各路大佬批评指点,将感激涕零。

有序组和序偶

有序组是关系的一种表达方式。

例如 <a1, a2, … an>,表示了n个元素的关系,被称为“n元有序组”,它是有序对(也就是序偶)的推广。

其可以表达任何有序的东西,比如年月日是个三元有序组、空间中的xyz坐标也是个三元有序组,身份证号各个段的独立编码也是有序组。

<a1, a2, … an>=<b1, b2, … bn>, iff. a1=b1,a2=b2,……an=bn

以下主要研究二元关系。

关系

二元关系是什么?是【描述元素间联系的序偶】的集合

设 A、B 为两非空集合, A×B 的任意子集 R 就是从 A 到 B 的一个二元关系,简称关系。A 叫做前域,B 叫做后域。如果这里的 A=B ,那么 R 就叫“ A 上的一个二元关系”。对 <x, y>∈R ,可以记作 xRy,称为“ x 对 y 有关系 R” 。

从上面这堆话中,我们可以发现:关系,是一个以序偶为元素的集合。

对两个集合求笛卡尔积,会得到一个以序偶为元素的集合,这个集合描述了前后域元素在固定次序下的所有组合情况,即,穷举了所有元素间所有可能的有序关系。那么,符合实际情况的、真正的关系,必然就存在于该集合中。所以对任意的非空 A、B ,他们之间共可以有 2|A×B|=2|A|×|B| 个不同的关系。

(因为任意集合A的子集有 2|A| 个;对有限集,笛卡尔积的基数等于基数的积)

例:对 A={a, b}、B={c, d},求从 A 到 B 的所有不同关系

  1. 求 A×B = {<a, c>, <a, d>, <b,c >, <b, d>}
  2. 再求 A×B 的所有子集。包含空集和全集在内一共有16个,这16个集合就是从A到B的所有不同关系。

空关系、全关系、恒等关系:

  1. 若 R=Ø ,则 R 叫做“空关系”;
  2. 若 R=A×B ,则 R 叫做“全关系”,记作 EA
  3. 若 R=A×A ,则 R 叫做“恒等关系”,记作 IA

n元关系

n个非空集合的笛卡尔积的任意子集。不做更多研究。

定义域和值域

既然关系是从一个集合中的元素到另一个集合中的元素的对应关系,那么其实一个关系就是一个映射。有映射,就有定义域(Domain)和值域(Range)

对集合 A、B 的关系 R,其定义域记作 domR,值域记作 ranR。另,将 fldR=domR∪ranR 称作 R 的域(Field)。如下图所示

例如,对 H = {Father, Mother, Son, Daughter},R 是 H 上的长幼关系

则: domR = {Father, Mother}, ranR = {Son, Daughter}, fldR = {Father, Mother, Son, Daughter}

关系的表示

有三种表示方法——集合表示、图表示和矩阵表示。

集合表示

枚举:

就是写个集合,把所有有序组全都列出来。。

比如A={1,2,3,4},其上的整除关系R={<1,1>, <1,2>, <1,3>, <1,4>, <2,2>, <2,4>, <3,3>, <4,4>}

叙述:

比如:实数集 R 上的相等关系:S={<x, y>|(x, y∈R)∧(x=y)}

图表示

元素画成小圆圈,哪两个元素之间有关系,就从第一个元素到第二个元素画个有向边

两个集合之间关系的图表示:

例:选课关系 R

某集合上的关系:

例:A ={1,2,3,4}上的小于等于关系

矩阵表示

对A={a1, a2, … an},B={b1, b2, … bm},R 从 A 到 B,我们可以建立一个 n×m 的矩阵。谁是前域谁定义行。对应位置有关系的就记为1,没关系的就是0。这个矩阵叫做关系矩阵,也叫做邻接矩阵。这种矩阵以0和1为值,是一种布尔矩阵。

以上面的选课关系 R 为例,我们可以为其建立一个关系矩阵 MR

注意,灰色的行标列标不要写出来。。上图中写出来仅用于提示,方便观看和记忆。


写博不易,如果读的开心,可以考虑请我吃包辣条 ~

人间自有真情在,五毛一块也是爱

点击量:741

发表评论

邮箱地址不会被公开。 必填项已用*标注