离散数学知识点总结(10)“关系” 知识的总结 <1>:关系的基础概念 |
您所在的位置:网站首页 › 集合运算知识点总结图 › 离散数学知识点总结(10)“关系” 知识的总结 <1>:关系的基础概念 |
文章目录
有序 n 元组和集合的笛卡尔积序偶关系有序二元组序偶相等有序三元组有序n元组有序 n 元组相等
集合的笛卡尔积集合笛卡尔积的性质
集合的二元关系及其表示方法相关关系的定义关系的定义域和值域关系的表示方法枚举法谓词公式法有向图法矩阵法
特殊的关系空关系
∅
\empty
∅全域关系(完全关系)恒等关系
关系的基本运算
关系的性质自反性反自反性对称性反对称性传递性
有序 n 元组和集合的笛卡尔积
序偶关系
有序二元组
有两个对象
x
,
y
x,y
x,y 组成的序列称为有序二元组,也称之为序偶,记作
<
x
,
y
>
序偶与集合不同,次序非常重要
序偶相等
设
<
x
,
y
>
,
<
u
,
v
>
,
, 是两个序偶,如果
x
=
u
且
y
=
v
x=u 且 y=v
x=u且y=v 那么这两个序偶被认为是相等的,记作
<
x
,
y
>
=
<
u
,
v
>
=
=
有序三元组
有序三元组是一个序偶,其第一个元素也是个序偶
因为第一个元素不是个序偶
有序n元组
有序n元组是一个序偶,其第一个元素本身是一个有序的 n-1 元组,记作
<
<
x
1
,
x
2
,
.
.
.
,
x
n
−
1
>
,
x
n
>
,简记为
<
x
1
,
x
2
,
.
.
.
,
x
n
−
1
,
x
n
>
有序 n 元组相等
集合的笛卡尔积
设集合
A
,
B
A,B
A,B 由
A
A
A 的元素为第一元素,
B
B
B 的元素为第二元素组成的全部序偶的集合,称为
A
A
A 和
B
B
B 的笛卡尔积,记作
A
×
B
A×B
A×B
A × B = { < x , y > ∣ x ∈ A ∧ y ∈ B } A×B=\{|x\in A \wedge y \in B\} A×B={∣x∈A∧y∈B} 集合的笛卡尔积不满足交换律集合的笛卡尔积也不满足结合律集合笛卡尔积的性质 笛卡尔积后的元素个数笛卡尔积对空集笛卡尔积对 ∩ , ∪ \cap, \cup ∩,∪ 满足分配律笛卡尔积对 ⊆ \subseteq ⊆ 的性质多个集合的笛卡尔积的符号描述 集合的二元关系及其表示方法 相关 我们可以认为,两个集合的关系是两个集合笛卡尔积的一个子集。或者说,两个集合的笛卡尔积代表了这两个集合之间可能发生的所有关系(即组合) 关系的定义 关系可以看做是 序偶的集合 关系的定义域和值域 定义域就是关系集合 R R R 中的所有的第一元素 x x x 组成的集合值域就是 关系集合 R R R 中所有的 第二元素 y y y 组成的集合 关系的表示方法 枚举法 谓词公式法 有向图法 - 第一个图表示的是在两个集合上的关系:在 A , B A, B A,B 上的关系 R 1 R_1 R1 - 第二种图表示的是一个集合和自身的关系: A , A A, A A,A 的关系, R 2 R_2 R2 矩阵法特殊的关系 空关系 ∅ \empty ∅ 全域关系(完全关系) 任意节点之间都有成对出现的边每个节点都有指向自己的环 恒等关系 关系的基本运算 由于关系的本质还是集合,因此对于集合的基本运算 ∩ , ∪ , ∼ , ⊕ , − \cap, \cup, \sim, \oplus, - ∩,∪,∼,⊕,− 也同样适用。 关系的性质 自反性反自反性对称性反对称性传递性 Note: 这里涉及到的所有的关系,都是某个集合和自身的关系,即集合 A A A,关系 R ⊆ A × A R \subseteq A×A R⊆A×A 自反性 有向图的每个节点都有指向自己的环矩阵的主对角线值都为 1 反自反性 有向图的每个节点都没有指向自己的环矩阵的主对角线值都为 0一个关系,不是 自反的,也不一定就是 反自反的 图中的 R 6 , R 7 R_6,R_7 R6,R7 既不是自反关系,也不是反自反关系 对称性 有向图的不同节点之间 只要有边,就是方向相反的两条边矩阵特点:矩阵关于主对角线对称特别注意:恒等关系(主对角线全为1)、空关系(矩阵全为0) 都是 对称关系 图中 R 4 , R 8 R_4, R_8 R4,R8 分别是 恒等关系 和 空关系,他们都是对称关系 反对称性 有向图的不同节点之间 只要有边,最多只有一条单方向的边矩阵特点:矩阵关于主对角线对称的位置,最多只有一个 1对称关系和反对称关系不是完全对立的,有些对称关系,也同样是反对称关系 反对称或者对称的概念是对所有节点来说的,比如下图中的 R 7 R_7 R7 他是反对称的,虽然他在 1,2 节点的关系是对称的;如果我们要说一个关系是对称的,就需要它里面所有的出现的边都是对称的;而只要找到一个反例,他就是反对称的了 R 4 , R 8 R_4, R_8 R4,R8 他们既是对称的,也是反对称的 传递性 通过有向图和矩阵不容易识别是否具有传递性,要通过传递性的定义来检查。 R 1 R_1 R1 中, x R y xRy xRy 为假,即 ∀ x ∀ y ∀ z ( ( x ∈ A ∧ y ∈ A ∧ z ∈ A ∧ x R y ∧ y R z ) → x R z ) \forall x \forall y \forall z((x \in A \wedge y \in A \wedge z \in A \wedge xRy \wedge yRz) \rightarrow xRz) ∀x∀y∀z((x∈A∧y∈A∧z∈A∧xRy∧yRz)→xRz) 中的前件为假,因此整个谓词公式为真,因此满足传递性。所以我们可以得到结论,独立无环的节点不影响传递性 R 2 R_2 R2 中,图中存在 x R x xRx xRx 因此 x R y xRy xRy 为假,即 ∀ x ∀ y ∀ z ( ( x ∈ A ∧ y ∈ A ∧ z ∈ A ∧ x R y ∧ y R z ) → x R z ) \forall x \forall y \forall z((x \in A \wedge y \in A \wedge z \in A \wedge xRy \wedge yRz) \rightarrow xRz) ∀x∀y∀z((x∈A∧y∈A∧z∈A∧xRy∧yRz)→xRz) 中的前件为假,因此依然满足传递性,所以我们得到另一个结论 独立有环的节点不影响传递性 R 3 R_3 R3 中,图中存在 x R x xRx xRx , x R y xRy xRy,即 ∀ x ∀ y ∀ z ( ( x ∈ A ∧ y ∈ A ∧ z ∈ A ∧ x R y ∧ y R z ) → x R z ) \forall x \forall y \forall z((x \in A \wedge y \in A \wedge z \in A \wedge xRy \wedge yRz) \rightarrow xRz) ∀x∀y∀z((x∈A∧y∈A∧z∈A∧xRy∧yRz)→xRz) 中的前件为假,依然满足传递性。 R 4 R_4 R4 中,图中存在 y R x yRx yRx 也有 x R x xRx xRx (可以把 y R x yRx yRx 和 x R x xRx xRx 看做是 x R y , y R z xRy, yRz xRy,yRz 的特殊情况),即 ∀ x ∀ y ∀ z ( ( x ∈ A ∧ y ∈ A ∧ z ∈ A ∧ x R y ∧ y R z ) → x R z ) \forall x \forall y \forall z((x \in A \wedge y \in A \wedge z \in A \wedge xRy \wedge yRz) \rightarrow xRz) ∀x∀y∀z((x∈A∧y∈A∧z∈A∧xRy∧yRz)→xRz) 中的前件为真,而确实后件也确实为真,因为 x R x xRx xRx 确实存在,所以 R 4 R_4 R4 满足传递性 R 5 R_5 R5 中,图中存在 x R y xRy xRy , 不存在 y R z yRz yRz,即 ∀ x ∀ y ∀ z ( ( x ∈ A ∧ y ∈ A ∧ z ∈ A ∧ x R y ∧ y R z ) → x R z ) \forall x \forall y \forall z((x \in A \wedge y \in A \wedge z \in A \wedge xRy \wedge yRz) \rightarrow xRz) ∀x∀y∀z((x∈A∧y∈A∧z∈A∧xRy∧yRz)→xRz) 中的前件为假,依然满足传递性。 R 6 R_6 R6 中,图中存在 x R y xRy xRy , y R x yRx yRx,即 ∀ x ∀ y ∀ z ( ( x ∈ A ∧ y ∈ A ∧ z ∈ A ∧ x R y ∧ y R z ) → x R z ) \forall x \forall y \forall z((x \in A \wedge y \in A \wedge z \in A \wedge xRy \wedge yRz) \rightarrow xRz) ∀x∀y∀z((x∈A∧y∈A∧z∈A∧xRy∧yRz)→xRz) 中的前件为真,但不存在后件 x R x xRx xRx 因此不满足传递性。 R 7 R_7 R7 中,图中存在 x R y xRy xRy , y R x yRx yRx,即 ∀ x ∀ y ∀ z ( ( x ∈ A ∧ y ∈ A ∧ z ∈ A ∧ x R y ∧ y R z ) → x R z ) \forall x \forall y \forall z((x \in A \wedge y \in A \wedge z \in A \wedge xRy \wedge yRz) \rightarrow xRz) ∀x∀y∀z((x∈A∧y∈A∧z∈A∧xRy∧yRz)→xRz) 中的前件为真,同时也存在后件为真 x R x xRx xRx 因此满足传递性。 R 8 R_8 R8 中,图中存在 x R y xRy xRy , x R z xRz xRz,即 ∀ x ∀ y ∀ z ( ( x ∈ A ∧ y ∈ A ∧ z ∈ A ∧ x R y ∧ y R z ) → x R z ) \forall x \forall y \forall z((x \in A \wedge y \in A \wedge z \in A \wedge xRy \wedge yRz) \rightarrow xRz) ∀x∀y∀z((x∈A∧y∈A∧z∈A∧xRy∧yRz)→xRz) 中的前件为假,因此满足传递性。 R 9 R_9 R9 中,图中存在 x R y xRy xRy , y R z yRz yRz,即 ∀ x ∀ y ∀ z ( ( x ∈ A ∧ y ∈ A ∧ z ∈ A ∧ x R y ∧ y R z ) → x R z ) \forall x \forall y \forall z((x \in A \wedge y \in A \wedge z \in A \wedge xRy \wedge yRz) \rightarrow xRz) ∀x∀y∀z((x∈A∧y∈A∧z∈A∧xRy∧yRz)→xRz) 中的前件为真,但不存在后件 x R z xRz xRz 因此不满足传递性。 R 10 R_{10} R10 中,图中存在 x R y xRy xRy , y R x yRx yRx,即 ∀ x ∀ y ∀ z ( ( x ∈ A ∧ y ∈ A ∧ z ∈ A ∧ x R y ∧ y R z ) → x R z ) \forall x \forall y \forall z((x \in A \wedge y \in A \wedge z \in A \wedge xRy \wedge yRz) \rightarrow xRz) ∀x∀y∀z((x∈A∧y∈A∧z∈A∧xRy∧yRz)→xRz) 中的前件为真,也存在后件 x R z xRz xRz 因此满足传递性。 R 11 R_{11} R11 中,图中存在 x R y xRy xRy , y R x yRx yRx,即 ∀ x ∀ y ∀ z ( ( x ∈ A ∧ y ∈ A ∧ z ∈ A ∧ x R y ∧ y R z ) → x R z ) \forall x \forall y \forall z((x \in A \wedge y \in A \wedge z \in A \wedge xRy \wedge yRz) \rightarrow xRz) ∀x∀y∀z((x∈A∧y∈A∧z∈A∧xRy∧yRz)→xRz) 中的前件为真,但后件为 z R x zRx zRx 因此后件为假,不满足传递性。此外,我们还可以推导出 空关系 和 恒等关系 以及 完全关系 也是满足传递性的 因为空关系就是三个独立的点,使得传递性的前件为假恒等关系就是三个独立的成环的点,也使得传递性的前件为假完全关系就是所有点之间的线都是双向的并且有自己成环,因此他的传递性关系判断的前件为真,后件也为真 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |