




已阅读5页,还剩63页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第二部分集合论 集合论溯源十六世纪末起源十九世纪德国数学家康托创立古典集合论1900年前后出现各种悖论1908年策莫罗建立集合论的公理系统目前集合论公理系统有两种形式 策莫罗 弗兰克尔 柯很形式 ZFC 贝尔内斯 诺伊曼 葛德尔形式 BNG 在计算机领域得到广泛应用 第二部分集合论 古典集合论康托称集合是 一些确定的 不同的东西的总体 这些东西 人们能够意识到 并且能够判断一个给定的东西是否属于这个总体 悖论 理发师悖论 在一个小岛上有唯一的一位理发师 他宣称 我为岛上所有不为自己理发的人理发 而不给那些为自己理发的人理发 请问 理发师的头发由谁来理呢 罗素悖论 令集合S为包含所有不以自身为元素的那些集合 即S x xx 请问 SS吗 第二部分集合论 ZFC公理 包括九个公理外延公理空集公理无序对公理正则公理替换公理方幂集公理集公理无限公理选择公理 外延公理 假定A和B都是集合 如果任何一个事物属于A也一定属于B 属于B也一定属于A 那么A和B是同一个集合 或称两个集合A和B相等 空集公理 存在一个不包括任何元素的集合 正则公理 任何一个非空集合A一定包含一个元素a A的任何一个元素都不是a的元素 计算机应用领域集合论是学习计算机科学必备的基础知识 计算机领域的大多数基本概念和理论都可以采用集合论的有关术语来描述和论证 集合论被广泛地应用于形式语言 编译理论 信息检索 数据结构 算法分析 程序设计 人工智能等领域 第三章集合与关系 3 1集合的基本概念3 2集合的基本运算3 3集合中元素的计数3 4笛卡尔乘积3 5关系的概念3 6关系的表示与性质3 7关系的运算3 8关系的闭包运算3 9相容关系与覆盖3 10等价关系与划分3 11偏序关系 3 1集合的基本概念 1 集合定义集合没有精确的数学定义理解 由离散个体构成的整体称为集合 称这些个体为集合的元素常见的数集 N Z Q R C等分别表示自然数 整数 有理数 实数 复数集合 2 集合表示法枚举法 通过列出全体元素来表示集合谓词表示法 通过谓词概括集合元素的性质实例 枚举法 谓词法 3 1集合的基本概念 3 集合的元素具有的性质无序性 元素列出的顺序无关相异性 集合的每个元素只计数一次确定性 对任何元素和集合都能确定这个元素是否为该集合的元素任意性 集合的元素也可以是集合4 元素与集合的关系隶属关系 或者 5 集合的树型层次结构 d A a A 3 1集合的基本概念 6 集合与集合之间的关系 定义6 1A B x x A x B A是B的子集定义6 2A B A B B A定义6 3A B A B A B A是B的真子集A B x x A x B 思考 和 的定义注意 和 是不同层次的问题 3 1集合的基本概念 7 空集 不含有任何元素的集合实例 x x R x2 1 0 定理6 1空集是任何集合的子集 证 对于任意集合A A x x x A T 恒真命题 推论 是惟一的一般地 称集合A的子集 和A为A的平凡子集 8 幂集 A x x A 实例 计数 如果 A n 则 A 2n 9 全集E 包含了所有集合的集合全集具有相对性 与问题有关 不存在绝对的全集 3 1集合的基本概念 例A a b c 求A的幂集 A 解 将A的子集从小到大分类 0元子集 即空集 1元子集 即单元集 a b c 2元子集 a b b c a c 3元子集 a b c 集合A有 A a b c a b a c b c a b c 习题 P86 6 d 3 2集合的基本运算 1集合的运算2集合运算算律 集合的基本运算有 并A B x x A x B 交A B x x A x B 相对补A B x x A x B 对称差A B A B B A 绝对补 A E A 文氏图 3 2集合的基本运算 1集合的运算2集合运算算律 说明 1 并和交运算可以推广到有穷个集合上 即A1 A2 An x x A1 x A2 x An A1 A2 An x x A1 x A2 x An 2 A B A B A B A B A 例A 0 1 2 B 2 3 计算解 3 2集合的基本运算 1集合的运算2集合运算算律 任何代数运算都遵从一定的算律 集合运算也不例外 下面给出集合运算的主要算律 其中A B C表示任意的集合 幂等律结合律交换律分配律同一律零律排中律矛盾律吸收律双重否定律德 摩根律 3 2集合的基本运算 1集合的运算2集合运算算律 除了以上算律 还有一些关于集合运算性质的重要结论 在此一并给出 建立了相对补运算和交运算之间的联系 可以利用它将相对补转变成交 给出了的三种等价的定义 为证明两个集合之间包含关系提供了新方法 同时也可以用于集合公式的化简 习题 P95 11 a 3 3集合中元素的计数 包含排斥原理 集合A含有n个元素 可以说集合A的基数是n 记作cardA n 所谓基数就是表示集合中所含元素多少的量 如果集合A的基数是n 也可以记为 A n 显然空集的基数是0 即 0 定义3 3 1设为集合 若存在自然数n 0也是自然数 使得 A cardA n 则称A为有穷集 否则就称A为无穷集 例3 3 1有100名程序员 其中47名熟悉C语言 35名熟悉C 语言 23名熟悉这两种语言 问有多少人对这两种语言都不熟悉 解 设A B分别表示熟悉C和C 语言的程序员的集合 则该问题可以用图3 3 1的文氏图表示 将熟悉两种语言的对应人数23填入A B的区域内 不难得到A B和B A的人数分别为 A B A A B 47 23 24 B A B A B 35 23 12从而得到 A B 24 23 12 59 故 A B 100 59 41 即两种语言都不熟悉的有41人 3 3集合中元素的计数 包含排斥原理 设S是有穷集 P1和P2分别表示两种性质 对于S中的任何一个元素x 只能处于以下四种情况之一 1 只具有性质P1 2 只具有性质P2 3 具有P1和P2两种性质 4 两种性质都没有 令A1和A2分别表示S中具有性质P1和P2的元素的集合 为了使表达式简洁 对任何集合B 用代替 B 由文氏图不难得到以下公式这就是容斥原理的一种简单形式 如果涉及到三条性质 容斥原理的公式则变成 3 3集合中元素的计数 包含排斥原理 定理3 3 1S中不具有性质P1 P2 Pm的元素数是定理3 3 1证明略 推论在S中至少具有一条性质的元素数是 3 3集合中元素的计数 包含排斥原理 例 某班学生150人 数学考试成绩90分以上的有80人 语文考试成绩90分以上的有75人 两门课程均在90分以上的有50人 问 1 只有一门课程成绩90分以上的学生有多少人 2 两门课程成绩均不在90分以上的学生有多少人 解 全集为该班学生组成的集合 设由题意可知 1 即需求 因为所以 即 2 即需求 3 4笛卡尔乘积 定义7 1由两个元素x和y 按照一定的顺序组成的二元组称为有序对 记作 有序对性质 1 有序性 当x y时 2 与相等的充分必要条件是 x u y v 定义7 2设A B为集合 A与B的笛卡儿积记作A B 且A B x A y B 3 4笛卡尔乘积 例1A 1 2 3 B a b c A B B A A B P A A P A B 3 4笛卡尔乘积 笛卡儿积的性质 1 不适合交换律A B B A A B A B 2 不适合结合律 A B C A B C A B C 3 对于并或交运算满足分配律A B C A B A C B C A B A C A A B C A B A C B C A B A C A 4 若A或B中有一个为空集 则A B就是空集 A B 5 若 A m B n 则 A B mn 证明A B C A B A C 证任取 A B C 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 A C 所以有A B C A B A C 3 4笛卡尔乘积 例2 1 证明A B C D A C B D 2 A C B D是否推出A B C D 为什么 解 1 任取 A C x A y C x B y D B D 2 不一定 反例如下 A 1 B 2 C D 则A C B D但是A B 3 5关系的概念 定义3 5 1设A B是任意两个集合 A B的子集R称为从A到B的二元关系 当A B时 称R为A上的二元关系 从上述定义可以看出A到B的二元关系 也是序偶的集合 若 R 则称a与b有关系R 记作aRb 若 则称a与b没有关系R 记作 例如 设A a b c d B 0 1 则R a 0 b 0 c 1 就是一个从A到B的二元关系 定义3 5 2设A B是任意两个集合 R是A到B上的二元关系 若R 则称为空关系 若R A B 则称R为全关系 称为A上的恒等关系 全关系例如 设A 0 1 2 则 3 5关系的概念 定义3 5 3设A B是两个集合 R是从A到B上的二元关系 则 1 若存在b B 使得 R 则所有这样的a A组成的集合 称为二元关系R的定义域 记作dom R 或D R 即 2 若存在a A 使得 R 则所有这样的b B组成的集合 称为二元关系R的值域 记作ran R 或R R 即R的定义域和值域一起称作R的域 记作FLDR 即FLDR dom R ran R 从X到Y的二元关系R 也可以用图解的方式表示 如图3 5 1所示 X和Y是两个集合 xi是集合X中的元素 yj是集合Y中的元素 当且仅当xiRyj时 才有一条从xi指向yj的有向边 3 5关系的概念 图3 5 1图解表示法 3 5关系的概念 定理3 5 1若R和S是从集合A到B上的两个二元关系 则R和S的并 交 补 差也是A到B上的二元关系 证明 因为R和S是从集合A到B上的二元关系所以有R A B S A B 从而有即R S和R S都是A到B上的二元关系 又因为所以 R和 S也是A到B上的二元关系 由于故R S也是A到B上的二元关系 3 6关系的表示与性质 1关系的矩阵表示2关系的图形表示3关系的性质 设X a b c Y 0 1 2 3 R 可得关系R的矩阵表示如下 由上例看出 给定从有限集X到Y的二元关系R 就可以构造出它的关系矩阵 给定两个有限集合和 并且R是从X到Y的二元关系 如果有则称矩阵是R的关系矩阵 并记作 3 6关系的表示与性质 1关系的矩阵表示2关系的图形表示3关系的性质 设画出R的关系图 解 R的关系图如图3 6 1所示 图3 6 1R的关系图 3 6关系的表示与性质 1关系的矩阵表示2关系的图形表示3关系的性质 定义3 6 1设R为A上的关系 1 若 x x A R 则称R在A上是自反的 2 若 x x A R 则称R在A上是反自反的 实例 自反 全域关系EA 恒等关系IA 小于等于关系LA 整除关系DA反自反 实数集上的小于关系 幂集上的真包含关系 A 1 2 3 R1 R2 R3是A上的关系 其中R1 R2 R3 R2自反 R3反自反 R1既不是自反的也不是反自反的 3 6关系的表示与性质 1关系的矩阵表示2关系的图形表示3关系的性质 定义3 6 2设R为A上的关系 1 若 x y x y A R R 则称R为A上对称的关系 2 若 x y x y A R R x y 则称R为A上的反对称关系 实例 对称关系 A上的全域关系EA 恒等关系IA和空关系 反对称关系 恒等关系IA和空关系也是A上的反对称关系 设A 1 2 3 R1 R2 R3和R4都是A上的关系 其中R1 R2 R3 R4 R1 对称和反对称 R2 只有对称 R3 只有反对称 R4 不对称 不反对称 3 6关系的表示与性质 1关系的矩阵表示2关系的图形表示3关系的性质 定义3 6 3设R为A上的关系 若 x y z x y z A R R R 则称R是A上的传递关系 实例 A上的全域关系EA 恒等关系IA和空关系 小于等于和小于关系 整除关系 包含与真包含关系设A 1 2 3 R1 R2 R3是A上的关系 其中R1 R2 R3 R1和R3是A上的传递关系 R2不是A上的传递关系 3 6关系的表示与性质 1关系的矩阵表示2关系的图形表示3关系的性质 3 7关系的运算 1关系的逆运算2关系的合成运算 定义3 7 1设R是从集合X到集合Y的二元关系 如果将R中每一对序偶的元素顺序互换 所得到的新的集合则称为R的逆关系 记作 即由逆关系的定义可知 的关系图可以通过将R的关系图的所有有向弧逆转得到 它的关系矩阵可以通过将R的关系矩阵转置得到 例3 7 1设 求 解 3 7关系的运算 1关系的逆运算2关系的合成运算 定理3 7 1设R和S都是从X到Y的二元关系 则下列各式成立 1 2 3 4 这里 R表示 5 6 若 则 3 7关系的运算 1关系的逆运算2关系的合成运算 定理3 7 2设R是A上的二元关系 则 1 R在A上是自反的 当且仅当 2 R在A上是反自反的 当且仅当 3 R在A上是对称的 当且仅当 4 R在A上是反对称的 当且仅当 3 7关系的运算 1关系的逆运算2关系的合成运算 定义3 7 2设R是从集合X到集合Y的二元关系 S是从集合Y到Z的关系 则R S称为R和S的合成关系 定义为R S称为关系的合成运算 设R是从集合到集合的关系 S是从集合到集合的关系 则是一个的矩阵 是一个的矩阵 依照普通矩阵乘法的运算 可以定义两个关系矩阵的合成运算 3 7关系的运算 由上述前两个矩阵可以构造这两个矩阵的合成矩阵 记作 元素可由下式得到 其中 和 的运算规则如下 两个关系的合成运算 就是将布尔关系矩阵做乘法 所得结果即为合成关系矩阵 1关系的逆运算2关系的合成运算 3 7关系的运算 1关系的逆运算2关系的合成运算 定理3 4 3设X Y Z和W都是集合 R是从集合X到Y的关系 S是从集合Y到Z的关系 T是从集合Z到W的关系 于是有 R S T R S T 即关系的合成运算满足结合律 证明 对任意的 R S T 根据合成关系的定义可知 必然存在z Z 使得 R S T 又因为 R S 故必存在y Y 使得 R并且 S 由 S且 T 根据合成关系的定义知 S T 又因为 R且 S T 得到 R S T 故由的任意性可知 R S T R S T 同理可证R S T R S T 综上所述 得到 R S T R S T 即关系的合成运算满足结合律 一般来说 关系的合成运算是不满足交换律的 即R S S R 3 7关系的运算 定义3 7 3设R是集合X中的二元关系 n N N是自然数集 于是R的n次幂定义为 1 即是R中的恒等关系 2 定理3 7 4设R是集合X中的二元关系 设m n N 则有 1 2 定理3 7 5设R是A上的二元关系 则R在A上是传递的 当且仅当 1关系的逆运算2关系的合成运算 例题1 4 习题 P119 5 6 3 8关系的闭包运算 1关系的闭包定义2关系的闭包构造方法3关系的闭包性质 定义3 7 1设R是非空集合A上的关系 R的自反 对称或传递 闭包是A上的关系R 使得R 满足以下条件 1 R 是自反的 对称的或传递的 2 R R 3 对A上任何包含R的自反 对称或传递 关系R 有R R 则称R 是R的自反闭包 记作r R 对称闭包记作s R 传递闭包记作t R 由定义可知 1 自反 对称或传递 闭包是关系 2 自反 对称或传递 闭包是包含R的最小自反 对称或传递 关系 3 8关系的闭包运算 1关系的闭包定义2关系的闭包构造方法3关系的闭包性质 集合构造方法 设R为A上的关系 则有 1 r R R R0 2 s R R R 1 3 t R R R2 R3 说明 对有穷集A A n 上的关系 3 中的并最多不超过Rn 参见课本P122定理3 8 5 矩阵构造方法 设关系R r R s R t R 的关系矩阵分别为M Mr Ms和Mt则Mr M EMs M M Mt M M2 M3 E是单位矩阵 M 是转置矩阵 相加时使用逻辑加 说明 对有穷集A A n 上的关系 Mt M M2 Mn 3 8关系的闭包运算 1关系的闭包定义2关系的闭包构造方法3关系的闭包性质 关系图构造方法 设关系R r R s R t R 的关系图分别记为G Gr Gs Gt 则Gr Gs Gt的顶点集与G的顶点集相等 除了G的边以外 以下述方法添加新的边 1 考察G的每个顶点 若没环就加一个环 得到Gr 2 考察G的每条边 若有一条xi到xj的单向边 i j 则在G中加一条xj到xi的反向边 得到Gs 3 考察G的每个顶点xi 找xi可达的所有顶点xj 允许i j 如果没有从xi到xj的边 就加上这条边 得到图Gt 3 8关系的闭包运算 1关系的闭包定义2关系的闭包构造方法3关系的闭包性质 例设A a b c d R R和r R s R t R 的关系图如下图所示 3 8关系的闭包运算 1关系的闭包定义2关系的闭包构造方法3关系的闭包性质 定理3 7 1设R是非空集合A上的关系 则 1 R是自反的当且仅当r R R 2 R是对称的当且仅当s R R 3 R是传递的当且仅当t R R 定理3 7 2设R1和R2是非空集合A上的关系 且R1 R2 则 1 r R1 r R2 2 s R1 s R2 3 t R1 t R2 定理3 7 3设R是非空集合A上的关系 1 若R是自反的 则s R 与t R 也是自反的 2 若R是对称的 则r R 与t R 也是对称的 3 若R是传递的 则r R 是传递的 3 8关系的闭包运算 1关系的闭包定义2关系的闭包构造方法3关系的闭包性质 二元关系的闭包仍然是二元关系 还可以求它的闭包 例如 R是A上的二元关系 r R 是它的自反闭包 还可以求r R 的对称闭包 r R 的对称闭包记为s r R 简记为sr R 读作R的自反闭包的对称闭包 其余类似 定理3 7 4设R是集合A上的二元关系 则 1 2 3 例题1 2 习题 P127 1 2 a 3 9集合的覆盖与划分 1覆盖与划分2加细与真加细3交叉划分 定义3 9 1给定非空集合A 设有集合 其中 且 且 则称集合S为集合A的覆盖 若还满足条件则称S是A的划分 说明 划分是覆盖的特殊情形 划分的元素Si称为划分的类 例1 令Z 所有整数的集合A1 所有偶数的集合A2 所有奇数的集合 则 A1 A2 是Z的一个划分 3 9集合的覆盖与划分 1覆盖与划分2加细与真加细3交叉划分 例2 已知下面哪些集合是A的覆盖或划分 最小划分 是由作为类的集合本身构成 如S4最大划分 是由包含单个元素的类组成 如S5 3 9集合的覆盖与划分 1覆盖与划分2加细与真加细3交叉划分 定义3 9 2设A和B是同一集合X的两种划分 且有A A1 A2 Am B B1 B2 Bn 若A的每一个类都是B的某一类的子集 即则称A是B的加细 若A是B的加细 且B A 则称A是B的真加细 例3 已知X a b c d A a b c d 下面的Bi哪些是A的加细 B1 a b c d B2 a b c d B3 a b c d B4 a b c d B5 d a b c B6 a d b c 3 9集合的覆盖与划分 1覆盖与划分2加细与真加细3交叉划分 定义3 9 3若A A1 A2 Ar 与B B1 B2 Bs 是同一个集合X的两种划分 则其中所有Ai Bj 组成的集合 称为是原来两种划分的交叉划分 例4 X 所有生物的集合P 所有植物的集合E 所有史前生物A 所有动物的集合F 所有史后生物则 P A E F 是X的两种划分 其交叉划分为 P E P F A E A F 其中P E表示史前植物P F表示史后植物A E表示史前动物A F表示史后动物 定理1若A B是同一集合X的两种划分 则其交叉划分也是原集合的一种划分 定理2任何两种划分的交叉划分 都是原来划分的一种加细 3 10等价关系与等价类 1等价关系的定义2等价类的定义3商集与划分 定义3 10 1设R为非空集合上的关系 如果R是自反的 对称的和传递的 则称R为A上的等价关系 设R是一个等价关系 若 R 称x等价于y 记做x y 例1设A 1 2 8 如下定义A上的关系R R x y A x y mod3 其中x y mod3 叫做x与y模3相等 即x除以3的余数与y除以3的余数相等 不难验证R为A上的等价关系 因为 1 x A 有x x mod3 2 x y A 若x y mod3 则有y x mod3 3 x y z A 若x y mod3 y z mod3 则有x z mod3 模3等价关系的关系图 3 10等价关系与等价类 1等价关系的定义2等价类的定义与性质3商集与划分 定义3 10 2设R为非空集合A上的等价关系 x A 令 x R y y A xRy 称 x R为x关于R的等价类 简称为x的等价类 简记为 x R实例A 1 2 8 上模3等价关系的等价类 1 4 7 1 4 7 2 5 8 2 5 8 3 6 3 6 定理3 10 1设R是非空集合A上的等价关系 则 1 x A x 是A的非空子集 2 x y A 如果xRy 则 x y 3 x y A 如果xy 则 x 与 y 不交 4 x x A A 3 10等价关系与等价类 1等价关系的定义2等价类的定义与性质3商集与划分 证 1 由定义 x A有 x A 又x x 即 x 非空 2 任取z 则有 z x R R R R R R从而证明了z y 综上所述必有 x y 同理可证 y x 这就得到了 x y 3 假设 x y 则存在z x y 从而有z x z y 即 R R成立 根据R的对称性和传递性必有 R 与xy矛盾 4 先证 x x A A 任取y y x x A x x A y x y x x A y A从而有 x x A A再证A x x A 任取y y A y y y A y x x A 从而有 x x A A成立 综上所述得 x x A A 3 10等价关系与等价类 1等价关系的定义2等价类的定义与性质3商集与划分 定义3 10 3设R为非空集合A上的等价关系 以R的所有等价类作为元素的集合称为A关于R的商集 记做A R A R x R x A 实例设A 1 2 8 A关于模3等价关系R的商集为A R 1 4 7 2 5 8 3 6 A关于恒等关系和全域关系的商集为 A IA 1 2 8 A EA 1 2 8 定义3 10 4设A为非空集合 若A的子集族 P A 满足 1 2 x y x y x y x y 3 A则称 是A的一个划分 称 中的元素为A的划分块 3 10等价关系与等价类 1等价关系的定义2等价类的定义与性质3商集与划分 例3给出A 1 2 3 上所有的等价关系 解先做出A的划分 从左到右分别记作 1 2 3 4 5 1对应EA 5对应IA 2 3和 4分别对应R2 R3和R4 R2 IAR3 IAR4 IA 例题1 4 习题 P134 3 5 3 11偏序关系 1偏序关系与偏序集2盖住与哈斯图3链与全序关系4偏序集中的特殊元素及性质 定义1 设R为定义在集合A上的一个关系 若R是a 自反的b 反对称的c 传递的则R称为偏序关系 记为 序偶称作偏序集 例1证明在实数集R上 是偏序关系 证明 1 对于任何a R 有a a成立 故 是自反的 2 对于任何a b R 如果有a b且b a成立 则必有a b 故 是反对称的 3 如果有a b b c成立 则必有a c 故 是传递的 因此 是偏序关系 3 11偏序关系 1偏序关系与偏序集2盖住与哈斯图3链与全序关系4偏序集中的特殊元素及性质 例2已知A 2 3 6 8 x整除y 验证 是偏序关系 证明 3 11偏序关系 1偏序关系与偏序集2盖住与哈斯图3链与全序关系4偏序集中的特殊元素及性质 定义2 在偏序集合中 如果x y A x y x y 且没有其它元素z 满足x z z y 则称元素y盖住元素x 并且记COVA x y A y盖住x 对于给定偏序集合 它的盖住关系是唯一的 所以可用盖住的性质画出偏序集合图 称为哈斯图 对于给定偏序集合 其哈斯图做图规则如下 1 用小圆圈代表元素 2 如果x y且x y 则将代表y的小圆圈画在代表x的小圆圈之上 3 如果 COVA 则在x与y之间用直线连接 3 11偏序关系 1偏序关系与偏序集2盖住与哈斯图3链与全序关系4偏序集中的特殊元素及性质 例3A是m 12的因子集合 为整除关系 求COVA 并画出哈斯图 解 IA COVA 6 12 哈斯图是简化的关系图 1 自反性 每个顶点都有自回路 省去自回路 2 反对称性 从小到大安置顶点 可省略箭头 3 传递性 由于有 R则 R 故只画 对应的边 省略边 3 11偏序关系 1偏序关系与偏序集2盖住与哈斯图3链与全序关系4偏序集中的特殊元素及性质 例4画出哈斯图 3 11偏序关系 1偏序关系与偏序集2盖住与哈斯图3链与全序关系4偏序集中的特殊元素及性质 A1 1 2 3 4 为小于等于关系 A2 a a b a b c 为包含关系 不同的偏序集 哈斯图可以有同样的结构 3 11偏序关系 1偏序关系与偏序集2盖住与哈斯图3链与全序关系4偏序集中的特殊元素及性质 定义4 设是一偏序集合 在A的一个子集中 如果每两个元素都是有 无 关系的 则称这个子集是链 反链 约定 若A的子集只有单个元素 则它既是链又是反链 例6已知A a b c d e R 验证是偏序集 画出哈斯图 举例说明链和反链 解 关系矩阵对角线都为1 且rij和rji不同时为1 所以R是自反的和反对称的 定义5 在偏序集中 如果A
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 销售咨询运营方案范文
- 云浮商场促销活动策划方案
- 某私立学校关于人工智能教育教学试点工作总结报告
- 教代会民主评议学校领导干部暂行办法
- 农业咨询调查方案范文
- 大连立体植物墙施工方案
- 医疗健康产业新动能前景展望
- 电商平台电商生态圈构建
- 关于举办第六届高效先进破碎筛分与磨矿分级技术交
- 巡察财务方面存在的问题及整改措施
- 医学伦理学全套课件
- 车用驱动电机原理与控制基础(第2版)课件:三相交流绕组及其磁场
- 加油站安全费用提取、使用台账
- 高考政治一轮复习:统编版必修1《中国特色社会主义》必背考点提纲填空练习版(含答案)
- 2025届高考数学一轮复习建议-函数与导数专题讲座课件
- 近代中国交通工具变迁史说课材料
- 《中华民族一家亲-同心共筑中国梦》队会课件
- 2025届高考试题原创命题比赛说题稿
- 资产负债管理与精算风险控制
- 小学道法小课题研究活动记录
- (2024年)人才培养计划方案
评论
0/150
提交评论