离散数学_九章:关系(6)(一)

简介: 离散数学_九章:关系(6)(一)

1、⛺偏序关系和偏序集


⛲偏序关系

定义:定义在集合 S 上的关系 R,如果它是自反的、反对称的和传递的,就称为偏序(或 偏序关系)。


❗注意:在一个集合的偏序关系中,并不是任何2个元素之间都具有偏序关系,例如 aRb cRd,但是 a与c之间可能不具有偏序关系R


⛲偏序(关系)的例子

证明是否是偏序,要依次验证自反性、反对称性、传递性满足与否


a. “大于或等于” 关系

证明:“ 大于或等于 ” ( ≥ )关系是整数集合上的偏序关系。


🔴解:

自反性: 对所有整数 a 有 a ≥ a,✔️


反对称性: 如果 a ≥ b 且 b ≥ a,那么 a = b,✔️


传递性: 因为 a ≥ b 且 b ≥ c 蕴涵 a ≥ c,✔️


综上所述, ≥ 关系是整数集上的偏序关系


b. “整除” 关系

证明:“ 整除 ”( | )关系是正整数集合上的偏序关系。


🔴解:

自反性: 对所有整数 a,有 a | a,✔️


反对称性: 如果 a 和 b 是正整数,且有 a | b 和 b | a,那么 a = b,✔️


传递性: 假设 a 整除 b 并且 b 整除 c。则有正整数 k 和 l 使得 b = ak 和 c = bl 成立。因此,c = a(kl),所以 a 整除 c,✔️


综上所述, 整除 关系是正整数集合上的偏序关系


c. “包含” 关系

证明:集合的包含(⊆)关系 是定义在集合 S 的幂集上的偏序。


🔴解:

自反性: 只要 A 是 S 的子集,就有 A ⊆ A,✔️


反对称性: A ⊆ B 和 B ⊆ A 蕴涵 A = B,✔️


传递性: A ⊆ B 和 B ⊆ C 蕴涵 A ⊆ C,✔️


综上所述, 包含关系是定义在集合 S 的幂集上的偏序。


🎬偏序集

集合 S 与定义在其上的偏序关系R 一起称为偏序集,记作 (S, R)。


集合 S 中的成员称为偏序集的元素


🎬可比性(comparability)

" ≼ " 符号

符号" ≼ " 用于表示任何偏序集中的关系。


在不同的偏序集中,会使用不同的符号表示偏序,如≤、⊆ 和 │


👉然而,我们需要一个符号用来表示任意一个偏序集中的序关系:


通常,在一个偏序集 (S,R)中,记号a ≼ b表示( a , b )∈R。使用这个记号是由于 “ 小于或等于 ” 关系是偏序关系的范例,而且符号" ≼ " 和 " ≤ "很相似。


(注意符号" ≼ " 用来表示任意偏序集中的关系,并不仅仅是“小于或等于”关系)


❗当 a 与 b 是偏序集 (S, ≼ ) 的元素时,不一定有 a ≤ b 或 b ≤ a


例如,在偏序集 ( P(Z),⊆ ) 中,{1,2}与{1,3}没有关系,反之亦然,因为没有一个集合被另一个集合包含。


a. 可比 & 不可比

定义:偏序集 (S, ≼) 中的元素 a 和 b 称为可比的,如果 a ≼ b 或 b ≼ a。

当 a 和 b 是 S 中的元素并且既没有 a ≼ b,也没有 b ≼ a,则称 a 与 b 是不可比的(incomparable)。


❗注意:这里的“ ≼ ” 不同于 “ ≤ ”,写的时候要尽可能弯一点,便于区分


“ ≼ ”:


“ ≤ ”:


b. 全序( =线序 )

定义:如果(S, ≼)是偏序集,且 S 中的每对元素都是可比的,则 S 称为全序集(totally ordered set)或线序集(linearly ordered set),且 " ≼ " 称为全序或线序。


一个全序集也称为链(chain)


c. 良序集、良序归纳原理及其应用

良序集定义:


对于偏序集( S, ≼ ),如果 " ≼ "是全序,并且 S 的每个非空子集都有一个最小元素,就称它为良序集(well-ordered set)。


(良序是对于结构很好的全序(线序)而言的)


良序归纳原理:


设S是一个良序集。如果(归纳步骤)对所有y∈𝑆,如果 P(x) 对所有 x∈𝑆 且 x ≺ y 为真,则P(y)为真,那么P(x)对所有的 x∈𝑆 为真


(证明:假设P(x)不对所有的x∈𝑆为真。那么存在一个元素 y∈𝑆,使得P(y)为假。于是集合A = {x∈𝑆|P(x)为假} 是非空集合。因为S是良序的,所以A有最小元素a, 根据a是选自A的最小元素,对所有 x∈𝑆 且 x ≺ a 都有 P(x) 为真。由归纳步骤得P(a)为真。这个矛盾就证明了P(x)必须对所有的x∈𝑆为真。)


良序归纳原理的应用:


比数学归纳法更简单,使用良序归纳法进行证明时,不需要基础步骤


因为若 x0 是良序集的最小元素,由归纳步骤可知 P(x0) 为真。因为不存在 x∈S 且x≺x0,所以P(x) 对所有 x∈S 且 x≺x0 为真


🎬偏序集的例子

a. 可比

在偏序集 ( Z+ , | )中,整数 3 和 9 是可比的吗?5 和 7 是可比的吗?


🔴解:


整数 3 和 9 是可比的,因为 3|9

整数 5 和 7 是不可比的,因为 5不可整除7,且 7 不可整除 5


b. 全序

全序:每对元素都是可比的


①偏序集(Z,≤ )是全序集,因为只要a,b是整数,就有a ≤ b 或者b ≤ a


②偏序集(Z+,| )不是全序集,因为它包含不可比的元素,比如 3 和 5


c. 良序集

正整数的有序对的集合:Z+ × Z+,与 ≼ 构成良序集(因为存在最小元素),其中如果a1 < b1 ,或如果a1 = b1且a2 < b2 ,则(a1 ,a2 )≼(b1 ,b2 )


集合 Z 与通常的 ≤ 不是良序的,因为 Z 中包含负整数集合,而负整数集合中没有最小元素


2、⛺字典序(Lexicographic Orderings)


定义:给定两个偏序集 ( A1 , ≼1 ) 和 ( A2, ≼2 ) ,在 A1 × A2 上的字典顺序 ≼ 定义为 (a1, a2) 小于 (b1, b2),即 (a1, a2) ≺ (b1, b2),或者a1 ≺ 1 b1,或者 a1 = b1 且 a2 ≺2 b2


(把相等增加到 A1 × A2 的序 ≺ 上,就得到一个偏序 ≼ )


例:考虑由小写英语组成的字符串的集合。使用字母在字母表中的顺序,可以构造在字符串的集合上的字典顺序。这与字典中使用的顺序相同。

🔴

discreet ≺ discrete,因为字符串在第7位出现不同字母,且 e ≺ t

discreet ≺ discreetness,因为这两个字符串前8个字母相同,但是第二个字符串更长

相关文章
|
算法 Android开发 Python
LeetCode 周赛上分之旅 #43 计算机科学本质上是数学吗?
学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭与你分享每场 LeetCode 周赛的解题报告,一起体会上分之旅。
63 0
LeetCode 周赛上分之旅 #43 计算机科学本质上是数学吗?
|
机器学习/深度学习 数据库
离散数学_九章:关系(2)
离散数学_九章:关系(2)
110 1
|
编译器 C语言
C语言程序设计(王立柱)第八章答案 链表
只有聪明人才能看见的摘要~( ̄▽ ̄~)~
79 1
离散数学_九章:关系(4)(一)
离散数学_九章:关系(4)(一)
101 0
|
机器学习/深度学习 移动开发
离散数学_九章:关系(4)(二)
离散数学_九章:关系(4)(二)
148 0
|
人工智能
离散数学_九章:关系(3)(一)
离散数学_九章:关系(3)(一)
139 0
离散数学_九章:关系(3)(二)
离散数学_九章:关系(3)(二)
87 0
|
数据可视化
离散数学_九章:关系(6)(二)
离散数学_九章:关系(6)(二)
366 0
|
移动开发 vr&ar
离散数学_九章:关系(1)
离散数学_九章:关系(1)
133 0
|
机器学习/深度学习 人工智能 语音技术
离散数学_九章:关系(5)
离散数学_九章:关系(5)
261 0