3.4次序关系.pdfVIP

离散数学 Discrete Mathematics 3.4次序关系 张晓西北工业大学计算机学院 zhangxiao@nwpu.edu.cn 2011110 目录 3.4.1 偏序集合偏序集合 偏序集合偏序集合 3.4.2 拟序集合拟序集合 拟序集合拟序集合 3.4.3 线序集合和良序集合线序集合和良序集合 线序集合和良序集合线序集合和良序集合 3.4.4 词典序和标准序词典序和标准序 词典序和标准序词典序和标准序 2011110 离散数学 2 3.4.1 偏序集合 定义定义3.4―1 如果集合如果集合A上的二元关系上的二元关系R是是自反自反 定义定义 如果集合如果集合 上的二元关系上的二元关系 是是自反自反 的的,反对称的和传递的反对称的和传递的,那么称那么称R为为A上的上的偏序关偏序关 的的反对称的和传递的反对称的和传递的 那么称那么称 为为 上的上的偏序关偏序关 系系 （（partial order））,称序偶称序偶 〈〈A,R〉为〉为偏序偏序 系系 （（ ））称序偶称序偶 〈〈 〉〉为为偏序偏序 集合集合，记为，记为A,≼≼ 集合集合，，记为记为 ≼≼ 通常用≼≼表示偏序关系,读作 “小于等于小于等于” ≼≼ 小于等于小于等于 x,y∈R ⇔ xRy ⇔ x≼ “严格小于”（拟序）: x≺y ⇔ x≼y ∧x≠ 1 如果R是集合A上的偏序，则R 也是A上的偏序。 如果用≤表示R,可用≥表示R1. 〈A,≤〉和〈A,≥〉都是偏序集 合,并互为对偶。 2011110 离散数学 3 例3.41 (a) 〈〈I,≤ 〉〉是偏序集合,这里≤表示整数中的 “小于或等 〈〈 〉〉 于”关系。 (b) 〈〈ρ(A),⊆⊆〉〉是偏序集合,这里⊆是集合间的包含关系。 〈〈 ⊆⊆〉〉 (c) A ={2,4,6,8}, D代表整除关系整除关系, M代表整倍数关系整倍数关系, 整除关系整除关系 整倍数关系整倍数关系 则 D={ 〈2,2〉, 〈4,4〉, 〈6,6〉, 〈8,8〉, 〈2,4〉, 〈2,6〉, 〈2,8〉, 〈4,8〉} M={ 〈2,2〉, 〈4,4〉, 〈6,6〉, 〈8,8〉, 〈4,2〉, 〈6,2〉, 〈8,2〉, 〈8,4〉} 〈A,D 〉, 〈A,M 〉都是偏序集合,且互为对偶 2011110 离散数学 4 关于偏序 “小于或等于小于或等于”不是指数的大小，而是在偏序关系中的 小于或等于小于或等于 顺序性顺序性。 顺序性顺序性 x“小于或等于小于或等于””y的含义是：依照这个序，x排在 的 小于或等于小于或等于”” 前边或者x就是 。 根据不同偏序的定义根据不同偏序的定义，对序有着不同的解释，对序有着不同的解释。例如。例如 根据不同偏序的定义根据不同偏序的定义，，对序有着不同的解释对序有着不同的解释。。例如例如 整除关系是偏序关系整除关系是偏序关系 ，，3 ≼≼ 6的含义是的含义是3整除整除6。。 整除关系是偏序关系整除关系是偏序关系 ，，