离散数学课件].ppt

集合论 由于集合论的语言适合于描述和研究离散对象及其关系 所以也是计算机科学与工程的理论基础 在程序设计 关系数据库 排队论 开关理论 形式语言和自动机理论等学科领域中都有重要的应用 本篇主要介绍 集合 二元关系和函数 以及集合的基数问题 集合论 第三章集合与关系 1集合的概念和表示法 2集合的运算 4序偶与笛卡尔积 5关系及其表示 6关系的性质 7复合关系和逆关系 8关系的闭包运算 9集合的划分和覆盖 10等价关系与等价类 11相容关系 12序关系 1集合的概念和表示法 1 集合与元素 1 集合 就是把人们直观的或想象中的某些确定的能够区分的对象汇合在一起组成的一个整体 讨论 一些不同的确定的对象之全体 例 1000以内的素数的集合 这个班里高个子学生的集合 不是集合 元素 成员 组成集合的各个对象 符号 用大写英文字母表示集合 用小写英文字母或其它符号表示元素 集合 A B 元素 a b 1集合的概念和表示法 元素与集合间的关系 若a是集合S中的元素 则可写成a S 若b不是集S合中的元素 则可写成b S 集合S的基数 势 S中的元素个数 用 S 表示 有限集合 集合的基数 元素 是有限的 无限集合 集合的基数 元素 是无限的 1集合的概念和表示法 本书中常用集合符 Im m 1 有限个正整数的集合 1 2 3 m Nm m 0 有限个自然数的集合 0 1 2 m 以上是有限集合 下面是无限集合 N自然数集合 0 1 2 I 正整数集合 1 2 3 I整数集合 1 0 1 2 P素数集合 大于1的正整数 只能被1和自己整除 Q有理数集合 i j i j均为整数且j 0 R实数集合 有理数 无理数 C复数集合 a bi a b可为实数 1集合的概念和表示法 2 集合的表示方法 a 枚举法 列举法 把集合的元素列于花括号内 例 命题的真假值组成的集合 S T F 自然数0 1 2 3 4五个元素的集合 P 0 1 2 3 4 b 谓词公式描述法所有集合均可用谓词公式来表示 S x p x 1集合的概念和表示法 例 大于10的整数的集合 S1 x x I x 10 偶整数集合 S2 x y y I x 2y 有限个元素集合 S3 1 2 3 4 5 x x I 1 x 5 S4 F T x x T x F S5 1 4 x x 5x 4 0 c 同一集合可以用多种不同的形式表示 d 集合也可作为某一集合的元素 例 S a 1 2 p q 1集合的概念和表示法 3 三个特殊集合 空集 全集合 集合族 定义 如果一个集合包含了所要讨论的每一个集合 则称该集合为全集合 简称全集 用E表示 E x p x p x p x 为任何谓词公式 定义 不拥有任何元素的集合称为空集 或称零集 用 表示 x p x p x 注意 前者是空集 是没有元素的集合 后者是以 作为元素的集合 1集合的概念和表示法 定义 集合中的元素均为集合 称这样的集合为集合族 例A a b c d 2 集合之间的关系 公理 给定二个集合A和B 当且仅当A和B具有同样的元素 成员 则A和B才是相等的 记作A B并规定 A B x x A x B 例 a b c b a a c c 1集合的概念和表示法 例 a b c b c a 例 设P 1 2 4 Q 1 2 4 则P Q 定义 设A B是任意二个集合 如果集合A的每一个元素都是B的一个元素 则称A是B的子集 或者说A包含于B 或者说B包含A 记作A B 或者B A 并规定 A B B A x x A x B 1集合的概念和表示法 例 A1 1 2 3 A2 0 A3 1 2 3 0 B 1 2 3 0 则A1 A2 A3均为B的子集合 并记为A1 B A2 B A3 B 定义 设A B是任意二个集合 若A B且A B 则称A是B的真子集 记作A B A真包含于B 并规定 A B A B A B 1集合的概念和表示法 注意 区分 和 的关系 关系是指集合和该集合中元素之间的关系 例 S a b c 则a S b S c S而 关系是指二个集合之间的关系 例 S1 a b S2 a b 1 2 则S1 S2若A不包含于B 则也可表示成A B 定理 设E是全集 A是一个集合 则一定有A E 1集合的概念和表示法 定理 设A B是任意二个集合 当且仅当A B和B A才有A B 证明 充分性 A B A B B A A B x x A x B x B x A x x A x B x x B x A A B B A 必要性 A B B A A B A B B A x x A x B x x B x A A B 1集合的概念和表示法 推论 对于任一集合A 则有A A 定理 设A B C是任意集合 如果A B和B C 则A C 推论 若A B和B C 则A C 定理 设有空集 和任一集合A 则 A证明 设x A 要证明 A 只要证 x x x A 为 T 中没有元素 x 为假 x x x A 为 T 定理 是唯一的 1集合的概念和表示法 证明 设有二个空集合 1和 2 是任何集合的子集 1 2 2 1 1 2 3 幂集和索引集合 1 幂集 例 给定S1 a 则子集为 a S2 1 2 则子集为 1 2 1 2 S3 则子集有 而不是 1集合的概念和表示法 定义 设A是集合 A的所有子集 作为元素 的集合称为A的幂集 记作 A 或2A且有 A 2A x x A 例 若A1 则 A1 若A2 a 则 A2 a 若A3 1 2 则 A3 1 2 1 2 注 S 2 s 为幂集 S 的基数 1集合的概念和表示法 2 索引集合为了在计算机上表示集合 必须给每一个集合的元素加上标记 以用来表示元素在集合中的位置 例 S1 a b 假设集合S1中 a b的位置已经固定 则用二进制下标法来表示S的所有子集 B00 a B10 b B01 a b B11这样 S1 B00 B01 B10 B11 Bi i J 而其中J 00 01 10 11 索引集合或指标集合 1集合的概念和表示法 例 已知集合S a1 a2 a3 a4 S的子集有24个可以分别表示成B0 B1 B 24 1 则B7 B0111 a2 a3 a4 B15 B1111 a1 a2 a3 a4 2集合的运算 1 交集 交运算 定义 任何二个集合A和B的交集A B是由A和B所共有的全部元素构成的集合 即 A B x x A x B 例 A a b B a c A B a 定理 集合的相交运算是可交换的和可结合的 即对于任何集合A B C有A B B A A B C A B C 证明 设x是A B中任一元素则x A B x x x A x B x x x B x A x B A A B B A 2集合的运算 定理 设A是E的任一子集 则有 1 A A A 2 A 3 A E A 定义 A B是二个集合 若A B 则称A和B是不相交的 或者说A和B没有相同的元素 若C是一个集合族 集合族 元素均为集合的集合 且C的任何二个元素都不相交 则称C为不相交的集合族 例 A a b c A为不相交的集合族 2集合的运算 2 并集 并运算 定义 A B是任意二个集合 A和B的并集A B是由A和B的所有元素构成的集合 即 A B x x A x B 例 A a b c B 1 2 3 则A B a b c 1 2 3 定理 集合的并运算是可交换的和可结合的 即对任何A B C有A B B A和 A B C A B C 2集合的运算 定理 集合的并和交运算 每一个对另一个都是可分配的 即 1 A B C A B A C 2 A B C A B A C 定理 设A B C是全集E的任意子集 则有 1 A A A 2 A A 3 A E E 2集合的运算 3 相对补集 定义 设A和B是二个任意集合 B对A的相对补集 A B 是由属于A且不属于B的所有元素组成的集合 即 A B x x A x B x x A x B 例 设A 0 1 2 B 2 3 4 则A B 0 1 B A 3 4 A B B A相对补集不满足交换律 2集合的运算 定理 设A B C D是E的子集 则有 1 A B A 2 若A B和C D 则A C B D 3 若A B和C D 则A C B D 4 若A A B 则B A B 5 若A B A 则A B B 6 若A B 则A B B 7 若A B 则A B A 8 A A 9 A B A 10 A B A A B 2集合的运算 4 绝对补集 补运算 定义 设E是全集 任一集合A对E的相对补集称为A的绝对补集 或称补集 记作 A 或 A 即 A E A x x E x A x x A 例 设E a b c d A a b 则 A c d 定理 A是E的任一子集 则有 1 A A E 2 A A 2集合的运算 补集的性质 1 A A 2 A B A B 3 A B A B 4 E 5 A B A B例 设A 2 5 6 B 2 3 4 C 1 3 4 E 1 2 3 4 5 6 则A B 5 6 A B 2 5 6 1 5 6 5 6 2集合的运算 5 环和 对称差 定义 设A B是任意二集合 A和B的环和记作A B 即 A B A B B A A B B A 或者x A B x x x A x B 例 设A 2 5 6 B 2 3 4 则A B 3 4 5 6 2集合的运算 对称差的性质 1 A B B A可交换的 2 A B C A B C 可结合的 3 A A 4 A A 5 A B C A B A C 对 是可以分配的 2集合的运算 6 文氏图 1 文氏图的画法规则 规定矩形表示E 子集用圆画在E中 2 文氏图应用 a 表示集合和运算的关系可用文氏图画出各种运算 b 证明集合恒等式例 A B C A B A C 下图中的阴影部分表示了每个图下边所指出的集合 A B A B A B A B A A A A A A A B B B B B A B 2集合的运算 3序偶与笛卡尔乘积 1 序偶 定义 由二个具有给定次序的客体所组成的序列称为序偶 记作 x y 例 X Y二维平面上的一个点的坐标 x y 就是一个序偶 说明 在序偶中二个元素要有确定的排列次序 即 若a b时 则 a b b a 若 x y a b x a y b 下面定义多重序元 三元组 x y z x y z n元组 x1 x2 x3 xn x1 xn 3序偶与笛卡尔乘积 2 笛卡尔乘积 定义 设A B为二个任意集合 若序偶的第一个成员 左元素 是A的一个元素 序偶的第二个成员 右元素 是B的一个元素 则所有这样的序偶的集合称为A和B的笛卡尔乘积 记作 A B x y x A y B 例 设A 1 2 B a b 则A B 1 a 1 b 2 a 2 b B A a 1 a 2 b 1 b 2 A B B A即 是不满足交换律 3序偶与笛卡尔乘积 例 设A a b B 1 2 C z 则 A B C a 1 a 2 b 1 b 2 z a 1 z a 2 z b 1 z b 2 z A B C a b 1 z 2 z a 1 z a 2 z b 1 z b 2 z A B C A B C 不满足结合律 定理 若A B C是三个集合 则有 A B C A B A C A B C A B A C A B C A C B C A B C A C B C 3序偶与笛卡尔乘积 证明 2 设 x y 是A B C 中的任一元素 则 x y A B C x y x y x A y B C x A y B y C x A y B x A y C A B A C 即A B C A B A C 例 设A 1 B 1 2 C 2 3 则A B C 1 1 2 3 1 1 1 2 1 3 3序偶与笛卡尔乘积 A B A C 1 1 2 1 2 3 1 1 1 2 1 3 A B C 1 2 1 2 A B A C 1 1 1 2 1 2 1 3 1 2 n个集合的笛卡儿乘积的定义 A2 A AA3 A A AAn A A A N个A 4关系及其表示 序偶 a b 实际上反映了二个元素之间的关系 1 关系 指事物之间 客体之间 的相互联系 在数学上关系可表达集合中元素间的联系 日常生活中 父子关系 母子关系 兄弟关系等均为二个客体之间的关系 n元笛卡尔积A1 A2 An是n元关系 4关系及其表示 定义 若则是一个二元关系 即 以序偶作为元素的任何集合是一个二元关系 关系表示方法 1 枚举法 直观法 列举法 设R表示二元关系 若用表示 若 则也可写成 xRy 4关系及其表示 例 二元关系定义如图 可写成 由定义可见 关系是一个集合 定义集合的方法都可以来定义关系 2 谓词公式表示法前面讲述 一个集合可用谓词公式来表达 所以关系也可用谓词公式来表达 4关系及其表示 例 实数集合R上的 关系可表达为 大于关系 父子关系 F 3 关系矩阵表示法规定 a 二元关系中的左元素表示行 右元素表示列 b 若 则在对应位置记上 1 否则为 0 4关系及其表示 例1 设并定义为列出关系矩阵 4关系及其表示例2 设X a b c Y 1 2 R2是 的关系 是 的全域关系 4关系及其表示 4 关系图表示法规定 a 把 集合中的元素以点的形式全部画在平面上 b 若 则xi和yi之间画一箭头弧线 其箭头指向yi 反之不画任何联线 4关系及其表示 用关系图表示 例 是X中的二元关系 4关系及其表示 关系的前域和值域 定义 设R是一个二元关系 由的所有x组成的集合domR称R的前域 即 R的前域和值域一起称做R的域 记做FLDR 即FLDR domR ranR 设R是一个二元关系 由的所有y组成的集合ranR称R的值域 即 4关系及其表示 4关系及其表示 均为二元关系 4关系及其表示 三个特殊关系 空白关系 全域关系 恒等关系 定义 集合X2定义了X集合中的一种关系 通称为X中的全域关系 用Ex表示 4关系及其表示 5关系的性质 自反性 例 设 是自反的关系 R的关系矩阵 5关系的性质 定义 设R是X中的二元关系 对于每一个 有xx 则称R是反自反的关系 表示成 R是X中的反自反的关系xx 例 设X 1 2 3 5关系的性质 S4既不是自反的 又不是反自反的 5关系的性质 例 设X 1 2 3 R 则R是对称的关系 5关系的性质 即当且仅当 X中的R才是反对称的 5关系的性质 反对称的另一定义如下 下面举例说明 定义 设R是X集合中的二元关系 对于每一个 来讲 如果x y且xRy 则yRx 称R是反对称的关系 5关系的性质 例 设X a b c 均是反对称的 5关系的性质 例 X a b c 下列关系不是对称的 也不是反对称的 5关系的性质 5关系的性质 X上的全域关系 是自反的 对称的 X上的空关系是反自反 对称 反对称的 5关系的性质 传递性 5关系的性质 例 设X a b c 则下列关系均是可传递的 5关系的性质 下列关系是不可传递的 5关系的性质 确定二元关系性质举例 1 设X 1 2 3 反自反 反对称 可传递的 反对称的 5关系的性质 自反 对称 反对称 可传递的 自反 对称 可传递的 反自反的 对称的 反对称的 可传递的 5关系的性质 2 若 则X上的空关系 自反的 反自反的 对称的 反对称的 可传递的 6复合关系和逆关系 关系的复合 定义 设 R关系 S关系 于是可用 R S 的关系 称 R S 为R和S的复合关系 并规定为 例 设A 1 2 3 4 5 R S均为A A的关系 且R S 则R S S R 6复合关系和逆关系 是不可交换的 讨论 1 R S为新的二元关系 2 R S X Z 6复合关系和逆关系 定理 设 则有 即 关系的复合运算满足结合律 下面定义关系R的幂次 6复合关系和逆关系 定义 给定集合X R是X中的二元关系 设 于是R的n次幂 可以定义成 例 6复合关系和逆关系 复合关系的矩阵表示 设有三个集合 而 X m Y n Z p 则关系矩阵 6复合关系和逆关系 例 设X 1 2 3 4 5 R S均是X中的二元关系 R S 3 6复合关系和逆关系 逆关系 讨论定义 1 只要将R中每一个序偶中的元素全部调换位置 就可得到R的逆关系 3 6复合关系和逆关系 例 X 0 1 2 R 3 6复合关系和逆关系 定理 设 则可有 3 6复合关系和逆关系 例 试求 3 6复合关系和逆关系 3 6复合关系和逆关系 证明 充分性 R是对称的 3 6复合关系和逆关系 定理 给定集合X Y 于是可有 7关系的闭包运算 定义 给定集合X R是X中的二元关系 若有另一R 满足下列条件 1 R 是自反的 对称 可传递的 2 3 对于任一自反 对称 传递的 关系R 若 则 则称R 是R的自反 对称 传递的 闭包 并依次用r R s R t R 来表示之 7关系的闭包运算 讨论定义 1 已知一个集合中的二元关系R 则r R s R t R 是唯一的 它是包含R的最小的自反 对称 传递 关系 2 若R是自反 对称 传递 的 则r R s R t R 就是R本身 3 若R不是自反 对称 传递 的 则我们可以补上最少序偶 使之变为自反 对称 传递关系 从而得到r R s R t R 7关系的闭包运算 定理 给定集合X R是X中的二元关系 于是可有 1 当且仅当r R R 则R是自反的 2 当且仅当s R R 则R是对称的 3 当且仅当t R R 则R是可传递的 例 设X a b c R 求r R 解 r R 7关系的闭包运算 7关系的闭包运算 定理 给定集合X R是X中的二元关系 则有 定理 设X是一集合 R是X中的二元关系 则 例 设X a b c R 求s R s R 7关系的闭包运算 例 X a b c R X 3 则 定理 设 X n R是X中的二元关系 则 7关系的闭包运算 例 X a b c d R 则 例 设X a b R 求r R s R t R r R s R t R R 定理 设X是一集合 R是X中的二元关系 则有 1 r S R S r R 2 r t R t r R 3 t S R 7关系的闭包运算 S t R 7关系的闭包运算 证明 1 r S R 常用下列符号表示一些闭包 R加 传递闭包 R星 自反可传递闭包 7关系的闭包运算 例 设X a b c R 1 rS R r Sr R s 2 rt R r tr R t 3 tS R t St R S t S R St R 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的覆盖 8集合的划分和覆盖 定义 给定一非空集合S 设非空集合 如果有 i j 1 2 m 则称集合A是集合S的一个划分 8集合的划分和覆盖 讨论定义 1 划分和覆盖主要差别在第 2 条 3 若A为有限集合 则A的秩是有限的 为 A 若A为无限集合 则划分的秩是无限的 4 集合的划分必定是一个覆盖 而覆盖不一定是划分 5 集合S上的秩最大的划分称最大划分 最小的称最小划分 8集合的划分和覆盖 例 设S a b c 下列 均为S的一个划分 类有二个 a b c 2 秩 类有二个 a b c 2 秩 类有二个 a c b 2 秩 最大划分 秩为3 最小划分 秩为1 8集合的划分和覆盖 定义 设A和A 是非空集合S的二种划分 并可表示成 若A 的每一个类 都是A的某一个类 的子集 则称划分A 是划分A的加细 或讲A 加细了A 若A 加细了A且 则称A 是A的真加细 8集合的划分和覆盖 例 S a b c d S的划分 A a b c d A a b c d 则A 是A的真加细 A a b c d 则A 是A的真加细 9等价关系与等价类 定义 设X是一个集合 R是X中的二元关系 若R是自反的 对称的和可传递的 则称R是等价关系 例 设X 1 2 3 4 5 6 7 为整数 9等价关系与等价类 试验证R是等价关系 画出R的关系图 列出R的关系矩阵 解 1 R 2 R的关系矩阵 9等价关系与等价类 R满足自反 对称和可传递的 R是一等价关系 例 设A 0 1 2 3 6 R x y x y x y A y x mod3 则domR ranR 9等价关系与等价类 9等价关系与等价类 定义 设R是X集合中的等价关系 对于任何的 来讲 可把集合 规定成 并称是由 生成的R等价类 讨论定义 2 9等价关系与等价类 例 设X a b c d R是X中的等价关系 R 则 9等价关系与等价类 例 设X N 关系R 是一等价关系 则R可以找出三个等价类 0 3 6 9 此集合中的元素除以3的余数为 0 1 4 7 10 此集合中的元素除以3的余数为 1 2 5 8 11 此集合中的元素除以3的余数为 2 9等价关系与等价类 定理 设X是一非空集合 R是X中的等价关系 R等价类的集合 x R x X 是X的一个划分 且此集合称为X关于R的商集 用 表示之 9等价关系与等价类 2 X中的恒等关系 它形成了X的一个最大划分 9等价关系与等价类 定理 X是一非空集合 A为X的一个划分 且A A1 A2 An 则由A导出的X中的一个等价关系 例 X a b c d A a b c d 则R a b a b c d c d 由此我们看到 集合X上的等价关系与X的划分之间有对应关系 定义 设X是一个集合 R是X中的二元关系 若R是自反的 对称的 则称R是相容关系 由定义知 等价关系是具有传递性的相容关系 相容关系是一个比等价关系更为普遍的关系 因为相容关系是自反和对称的 其关系矩阵是对称的且主对角线元素全为1 因此我们可仅用下三角矩阵T来表示和存储就够了 即关系矩阵可以简化为 阶梯形 10相容关系 EX 设A cat teacher cold desk knife by R x y x y A且x和y至少有一个相同的字母 R是A上的一个相容关系 简记A中元素依次为x1 x2 x3 x4 x5 x6 则R的关系矩阵MR和对应简化的下三角矩阵TR为 catteachercolddeskknifeby catteachercolddeskknifeby EX 在相容关系的关系图上 每个顶点都有自环且每两个顶点间的弧线都是成对出现的 为简化相容关系的关系图 不画自环 并用无箭头的单线段代替来回弧线 使之成为无向图 上例的关系图如下 定义1 设R是集合A上的相容关系 若C A 若任意a b C 有aRb 则称C是由R产生的相容类 例如上例的相容关系R可产生相容类 x1 x2 x1 x3 x2 x3 x6 x2 x4 x5 等等 对于前三个相容类 都能加进新的元素组成新的相容类 而后两个相容类 加入任一新元素 就不能组成相容类 我们称它为最大相容类 x3 x2 x1 也可以这样理解最大相容类CR 对CR中的任意元素x x必与CR中所有元素有相容关系 而在差集A CR中没有任何元素与CR中所有元素都是相容的 求最大相容类的方法 关系图法 确定最大完全多边形即 每个顶点都与其他所有顶点相联结的多边形 1 孤立结点是最大的完全多边形 2 二个相互联结的结点是最大完全多边形 3 三角形是三个结点的最大完全多边形 4 四个结点 5 五个结点 画出简化相容关系的关系图后 先确定结点最多的完全多边形 以后逐次减少 例 已知相容关系图 求出最大相容类 最大相容类集合为 完全覆盖 设有集合A上的相容关系R 其中最大相容类的集合 称作集合A的完全覆盖 定理 A上的每个相容关系 唯一的定义一个完全覆盖 g 最大相容类 b g f e b a e b c d 该集合的完全覆盖为 b g f e b a e b c d 1 偏序关系的定义 设A是一个集合 如果A上的一个关系R 满足自反性 反对称性和传递性 则称R是A上的一个偏序关系 记作 EX1 在实数集Z上 证明小于等于关系是偏序关系EX2 在实数集Z上 小于关系是偏序关系 EX3 设A 1 2 3 则定义在 A 上的关系 是偏序关系吗 EX4 设A 2 3 6 8 则定义在A上的整除关系R 2 2 3 3 6 6 8 8 2 6 2 8 3 6 是偏序关系吗 偏序关系 设 为偏序关系 如果 则记作x y 读作 小于或等于 注意 这里的 小于或等于 不是指数的大小 而是在偏序关系中的顺序性 x 小于或等于 y的含义是 依照这个序 x排在y的前边或者x就是y 不同偏序的定义有不同的序解释 例如整除关系是偏序关系 3 6的含义是3整除6 大于或等于关系也是偏序关系 针对这个关系写5 4是说大于或等于关系中5排在4的前边 也就是5比4大 偏序关系 偏序关系 定义集合A和A上的偏序关系一起叫做偏序集 记作 例如 整数集合Z和数的小于等于关系 构成偏序集 集合A的幂集P A 和包含关系R构成偏序集 利用偏序关系的自反性 反对称性和传递性可简化偏序关系的关系图 该关系图称为哈斯图 HasseDiagram 为了说明哈斯图的画法 先定义偏序集中顶点之间的覆盖关系 偏序关系 定义 对于任意 R且a b 则 IR 令R1 R IR 则R1 R1oR1 为盖住集 以上所给的等价定义是立足于集合的观点 应用此等价定义判定偏序关系的盖住集 不仅有条理 而且步骤清晰 可从以下几步求盖住集 1 首先从R中找出所有a b的序对集合IR 2 计算集合R和IR的差R1 即R1 R IR 3 将R1与其自身复合 得集合R2 4 计算集合R1和R2的差 则R1 R2为盖住集 偏序关系 例设集合A a b c d e R是A上的偏序关系 R 试判定R上的盖住集COVR 解 IR R1 R IR R1oR1 COVR R1 R1oR1 偏序关系 在画偏序集的哈斯图时 首先适当排列顶点的顺序 使得 x y A 1 若x y 则将x画在y的下方 2 对于A中的两个不同元素x和y 如果y覆盖x 就用一条线段连接x和y 给定偏序集 A 它的盖住集是唯一的 我们可以画出盖住集的关系图 称为 A 的哈斯图 偏序关系 则 P1 是一偏序集合 全序集合 良序集合其哈斯图为 偏序关系 例 设X a b X 是一偏序关系 其哈斯图为 偏序关系 下面考虑偏序集中的一些特殊元素 定义设为偏序集 B A y B 1 若 x x B y x 成立 则称y为B的最小元 2 若 x x B x y 成立 则称y为B的最大元 3 若在B中找不到一个y 使y y 则称y为B的极小元 4 若在B中找不到一个y 使y y 则称y为B的极大元 偏序关系 最大元 最小元举例 例 设有集合A 1 2 3 4 5 6 9 10 15 上的整除关系R B1 1 2 3 B2 3 5 15 B3 AB1的最大元是 B1的最小元是 1 B2的最大元是 15 B2的最小元是 B3的最大元是 B3的最小元是 1 1 偏序关系 极大元 极小元举例 例 设有集合A 1 2 3 4 5 6 9 10 15 上的整除关系R B1 1 2 3 B2 3 5 15 B3 AB1的极大元是 2 3 B1的极小元是 1 B2的极大元是 15 B2的极小元是 3 5 B3的极大元是 4 6 9