第三章集合与关系介绍.ppt

§3.11 序关系 （2）若 ，且x≤y和 ，则把x画在y的下面； （3）若y盖住x，则在x和y之间画一条联线，并箭头向上， 若y不盖住x，但又存在“≤”关系，则必定通过x和y之间的其它中间结点把x和y联结起来； （4）所有边的方向均是向上的，所以实际画时， 箭头均可省去。 例：(a)设 “≤”表示P中元素的小于和等于关系， （1）用“?”表示P中的结点（具有自反性）； 画〈P，≤〉的哈斯图的方法： §3.11 序关系 则〈P1，≤〉是一偏序集合，全序集合，良序集合 其哈斯图为： (b)若设 是一偏序集合， 例：设X={2,3,6,12,24,36} “≤”定义为：若 x整除y，则x≤y， 〈X，≤〉是一偏序集合, §3.11 序关系 例：(a)设X={a,b},ρ(X)= 是一偏序关系， 其哈斯图为： (b)设X={a,b,c} 的哈斯图为： §3.11 序关系 [定义]设P, ≤为一偏序集，且Q?P (1)若对每一个q’∈Q有q≤q’,则称q∈Q为Q的最小元素。 (2)若对每一个q’∈Q有q≥q’,则称q∈Q为Q的最大元素。 (3)若q∈Q，且不存在一个q’∈Q，使q’? q且q’≤ q， 则称q为Q的极小元素。 (4)若q∈Q，且不存在一个q’∈Q，使q’? q且q’≥ q， 则称q为Q的极大元素。 讨论： (1) q∈Q，?Q的极大，小，最大，小元，若有的话，必定在Q中。 §3.11 序关系 (2)最大，最小元是Q中所有元素比较而言的， 极大，极小元是对Q中能够比较的元素而言的。 (3)Q中如有最大，最小元则一定是唯一的，极大，极小元一定存在，且不一定是唯一的。 [定义]给P, ≤，且Q?P，若 (1)对每个q’∈Q有q’≤q,则称q∈P为Q的上界，其中最小的一个，称为Q的最小上界，记为LUB(上确界)。 (2)对每个q’∈Q有q’≥q,则称q∈P为Q的下界，其中最大的一个，称为Q的最大下界，记为GLB(下确界)。 §3.11 序关系 讨论定义： (1)上，下界是对Q中所有元素比较而言的。 (2)Q若有上，下界，则不一定是唯一的。 (3)Q若有LUB，GLB，则Q一定有上，下界，且是唯 一的。 (4)Q的上，下界，LUB，GLB，则可能在Q中，可能不在Q中，但一定在P中。 §3.11 序关系 例：设X={a,b,c}, 是一偏序集合， 其哈斯图如右， 求下列子集的上界、下界、 最小上界和最大下界 §3.11 序关系 {b} {b} ,? {b} {b}{a,b}{b,c}{a,b,c} {{b}} {c} {c} ,? {a,c} {a,c}{a,b,c} {{a,c}{c}} {b} {b} ,? {a,b,c} {a,b,c} {{a,b}{b,c}} ? ? {a,b,c} {a,b,c} {{a,b}{c}} ? ? {a,b,c} {a,b,c} {{a}{b}{c}} ? ? {a,c} {a,c}{a,b,c} {{a}{c}} GLB 下界 LUB 上界 子集 人有了知识，就会具备各种分析能力， 明辨是非的能力。 所以我们要勤恳读书，广泛阅读， 古人说“书中自有黄金屋。 ”通过阅读科技书籍，我们能丰富知识， 培养逻辑思维能力； 通过阅读文学作品，我们能提高文学鉴赏水平， 培养文学情趣； 通过阅读报刊，我们能增长见识，扩大自己的知识面。 有许多书籍还能培养我们的道德情操， 给我们巨大的精神力量， 鼓舞我们前进。 * §3.8 集合的划分和覆盖 [定义]给定一非空集合Ｓ，又设 若（1） （2） 则称A为S的覆盖。 例：S={a,b,c}，A={{a,b},{b,c}}，B={{a},{a,b},{c}}， C={{a},{b},{c}}，D={{a},{b},{a,c}} 均为S的覆盖。 §3.8 集合的划分和覆盖 例：四个半圆覆盖一正方形。 [定义]给定一非空集合S，设非空集合 如果有： 或 （i,j=1,2…,m） § 3.8 集合的划分和覆盖 则称集合A是集合S的一个划分。 讨论定义： （1）划分和覆盖主要差别在第（2）条； （2）划分A中的元素，称为划分的类，在定义中 均是A中的一个类，类的个数称为划分的秩； （3）若A为有限集合，则A的秩是有限的，为|A|， 若A为无限集合，则划分的秩是无限的； （4）集合的划分必定是一个覆盖，而覆盖不一定是划分； （5）集合S上的秩最大的划分称最大划分，最小的称最小划分。 § 3.8 集合的划分和覆盖 例：设S={a,b,c}，下列 均为S的一个划分： 类有二个