集合与关系.ppt

第二篇集合论 主要包括如下内容 集合论基础二元关系函数 第三章集合与关系 本章主要介绍如下内容 基本概念及集合的表示方法集合的运算 包含排斥原理二元关系 3 1基本概念 1 集合与元素集合是个最基本的概念 集合 是由确定的对象 客体 构成的集体 用大写的英文字母表示 这里所谓 确定 是指 论域内任何客体 要么属于这个集合 要么不属于这个集合 是唯一确定的 元素 集合中的对象 称之为元素 表示元素与集合的属于关系 例如 N表示自然数集合 2 N 而1 5不属于N写成 1 5 N 或写成1 5 N 2 有限集合与无限集合这里对有限集合与无限集合只给出朴素的定义 以后再给出严格的形式定义 有限集合 元素是有限个的集合 如果A是有限集合 用 A 表示A中元素个数 例如 A 1 2 3 则 A 3 无限集合 元素是无限个的集合 对无限集合的所谓 大小 的讨论 以后再进行 3 集合的表示方法列举法 将集合中的元素一一列出 写在大括号内 例如 N 1 2 3 4 A a b c d 描述法 用句子 或谓词公式 描述元素的属性 例如 B x x是偶数 C x x是实数且2 x 5 一般地 A x P x 其中P x 是谓词公式 如果论域内客体a使得P a 为真 则a A 否则a A 4 说明 集合中的元素间次序是无关紧要的 但是必须是可以区分的 即是不同的 例如A a b c a B c b a 则A与B是一样的 对集合中的元素无任何限制 例如令A 人 石头 1 B 本书中常用的几个集合符号的约定 自然数集合N 1 2 3 整数集合I 实数集合R 有理数集合Q 集合中的元素也可以是集合 下面的集合的含义不同 如a 张书记 a 党支部 只有一个书记 a 分党委 只有一个支部 a 党委 只有一个分党委 a 市党委 只有一个党委 3 2集合的运算 一 被包含关系 子集 1 定义 A B是集合 如果A中元素都是B中元素 则称B包含A A包含于B 也称A是B的子集 记作A B 文氏图表示如右下图 例如 N是自然数集合 R是实数集合 则N R谓词定义 A B x x A x B 2 性质 有自反性 对任何集合A有A A 有传递性 对任何集合A B C 有A B且B C 则A C 有反对称性 对任何集合A B 有A B且B A 则A B 二 相等关系1 定义 A B是集合 如果它们的元素完全相同 则称A与B相等 记作A B 定理 A B 当且仅当A B且B A 证明 充分性 已知A B且B A 假设A B 则至少有一个元素a 使得a A而a B 或者a B而a A 如果a A而a B 则与A B矛盾 如果a B而a A 则与B A矛盾 所以A B 必要性显然成立 因为如果A B 则必有A B且B A 谓词定义 A B A B B A x x A x B x x B x A x x A x B x B x A x x A x B 2 性质 有自反性 对任何集合A 有A A 有传递性 对任何集合A B C 如果有A B且B C 则A C 有对称性 对任何集合A B 如果有A B 则B A 三 真被包含关系 真子集 1 定义 A B是集合 如果A B且A B 则称B真包含A A真包含于B 也称A是B的真子集 记作A B 谓词定义 A B A B A B x x A x B x x A x B x x A x B x x A x B x x B x A x x A x B x x A x B x x A x B x x B x A x x A x B x x B x A 2 性质有传递性 对任何集合A B C 如果有A B且B C 则A C 练习题 设A a a a b a b c 判断下面命题的真值 a A a A c A a a b c a A a b a b c a b A a b a b c c a b c c A a 特殊集合 一 全集E定义 包含所讨论的所有集合的集合 称之为全集 记作E 实际上 就是论域 它的文氏图如右图 由于讨论的问题不同 全集也不同 所以全集不唯一 例如 若讨论数 可以把实数集看成全集 若讨论人 可以把人类看成全集 由于论域内任何客体x都属于E 所以x E为永真式 所以需要用永真式定义E E x P x P x 性质 对于任何集合A 都有A E 二 空集 定义 没有元素的集合 称之为空集 记作 因为论域内如何客体x 是矛盾式 所以要用一个矛盾式定义 x P x P x 性质 1 对于如何集合A 都有 A 因为 x x x A 为永真式 所以 A 2 空集是唯一的 证明假设有两个空集 1 2 则因为是 1空集 则由性质1得 1 2 因为是 2空集 则由性质1得 2 1 所以 1 2 三 集合的幂集定义 A是集合 由A的所有子集构成的集合 称之为A的幂集 记作P A 或2A P A B B A 例如 AP A a a a b a b a b a b c 则P A a b c a b a c b c a b c 性质 1 给定有限集合A 如果 A n 则 P A 2n 证明 因为 有n个元素 故P A 中元素个数为 而 x y n 令x y 1时得2n 所以 P A 2n 2A 2 A 2n 幂集元素的编码 a b c 则P A a b c a b a c b c a b c A的八个子集分别表示成 B0 B1 B2 B3 B4 B5 B6 B7再将它们的下标写成二进制形式得 B000 B001 B010 B011 B100 B101 B110 B111 c b b c a a c a b a b c B000B001B010B011B100B101B110B111B0B1B2B3B4B5B6B7子集Bijk编码的写法 a b c i j k的确定 Bijk A 如果a Bijk 则i 1 b Bijk 则j 1 c Bijk 则k 1 否则为0 如 a b c d 子集B9 B1001 a d a c d B1011 B11作业86页 4 7 练习P86 7 设A B P P A P A 在求P P A 时 一些同学对集合 难理解 实际上你就将 中的元素分别看成 a b 于是 a b B P P A P a b B0 B1 B2 B3 B00 B01 B10 B11 b a a b 然后再将a b代回即可B P P A P 以后熟悉后就可以直接写出 a B Bb B Bc B Ba b c 中命题均为真 集合的运算 介绍五种运算 一 交运算 1 定义 A B是集合 由既属于A 也属于B的元素构成的集合 称之为A与B的交集 记作A B 例如A 1 2 3 B 2 3 4 A B 2 3 谓词定义 A B x x A x B x A B x A x B如果A B 则称A与B不相交 2 性质 幂等律对任何集合A 有A A A 交换律对任何集合A B 有A B B A 结合律对任何集合A B C 有 A B C A B C 同一律对任何集合A 有A E A 零律对任何集合A 有A A B A B A 前5个公式高中都学过 下面只证明 证明 A B A x x A B x A x x A B x A x A x A B x a A B x A x A x A B x x A x B x A x A x A x B x x A x B x A x A x A x B x T T x A x B x x A x B x x A x B A B 二 并运算 1 定义 A B是集合 由或属于A 或属于B的元素构成的集合 称之为A与B的并集 记作A B 例如A 1 2 3 B 2 3 4 A B 1 2 3 4 谓词定义 A B x x A x B x A B x A x B2 性质 幂等律对任何集合A 有A A A 交换律对任何集合A B 有A B B A 结合律对任何集合A B C 有 A B C A B C A B A B 同一律对任何集合A 有A A 零律对任何集合A 有A E E 分配律对任何集合A B C 有A B C A B A C A B C A B A C 吸收律对任何集合A B 有A A B AA A B A 证明A A B A E A B 同一 A E B 分配 A E A 零律 同一 A B A B B 三 差运算 相对补集 1 定义 A B是集合 由属于A 而不属于B的元素构成的集合 称之为A与B的差集 或B对A的相对补集 记作A B 例如A 1 2 3 B 2 3 4 A B 1 谓词定义 A B x x A x B x A B x A x B2 性质设A B C是任意集合 则 A A A A A A B A A B A B A B A B A B C A C B C 证明 任取x A C B C x A C x B C x A x C x B x C x A x C x B x C x A x C x B x A x C x C x A x C x B x A x B x C x A x B x C x A B x C x A B C所以 A B C A C B C A B C A B A C A B C A B A C 证明 任取x A B C x A x B C x A x B x C x A x B x C x A x B x A x C x A B x A C x A B A C 所以A B C A B A C A B C A B A C 但 对 是不可分配的 如A A B A而 A A A B 注意 这不是分配律 四 绝对补集 1 定义 A是集合 由不属于A的元素构成的集合 称之为A的绝对补集 记作 A 实际上 A E A 例如 E 1 2 3 4 A 2 3 A 1 4 谓词定义 A E A x x E x A x x A x A x A2 性质设A B C是任意集合 则 E E A A A A A A E A B A B A A E A B A B A B A B这两个公式称之为底 摩根定律 证明 任取x A B x A B x A B x A x B x A x B x A x B x A B A B A B A B B A证明 A B x x A x B x x B x A x x B x A B A A B当且仅当A B E且A B 证明 A B E A B x x A B x E P T P x x A B x P F P x x A B T x x A B F x x A B x A B x x A x B x A x B x x A x B x A x B x x A x B x B x A x x A x B x B x A x x A x B A B 五 对称差 1 定义 A B是集合 由属于A而不属于B 或者属于B而不属于A的元素构成的集合 称之为A与B的对称差 记作A B 例如A 1 2 3 B 2 3 4 A B 1 4 谓词定义 A B A B B A x x A x B x B x A A B A B A B 2 性质 交换律对任何集合A B 有A B B A 结合律对任何集合A B C 有 A B C A B C 此式证明较繁 教材里有证明 这里从略 同一律对任何集合A 有A A 对任何集合A 有A A 对 可分配A B C A B A C 证明 A B A C A B A C A B A C A B C A B C A B C B C 对 分配 A B C 3 3 包含排斥原理 这节主要解决集合的计数问题 例如有AB两个商店 A店经营1000种商品 B店经营1200种商品 其中有100种商品两个商店都经营 问两个商店共经营多少种商品 显然 A B A B A B 如果有ABC三个有限集合 则 A B C A B C A B C A B A B C A C B C A B A B C A C B C A B C A B C A B A C B C A B C 一般地 有n个有限集合A1 A2 An 则例1某个研究所有170名职工 其中120人会英语 80人会法语 60人会日语 50人会英语和法语 25人会英语和日语 30人会法语和日语 10人会英语 日语和法语 问有多少人不会这三种语言 令U为全集 E F J分别为会英语 法语和日语人的集合 U 170 E 120 F 80 J 60 E F 50 E J 25 F J 30 E F J 10 E F J E F J E F E J F J E F J 120 80 60 50 25 30 10 165 U E F J 170 165 5即有5人不会这三种语言 E F J 10 U 例2 求1到1000之间不能被5 6 8整除的数的个数 解 设全集E x x是1到1000的整数 E 1000A5 A6 A8是E的子集并分别表示可被5 6 8整除的数的集合 x 表示小于或等于x的最大整数 LCM x y 表示x y两个数的最小公倍数 LeastCommonMultiple 不能被5 6 8整除的数的集合为 A5 A6 A8 A5 A6 A8 E A5 A6 A8 E A5 A6 A8 A5 A6 A5 A8 A6 A8 A5 A6 A8 1000 200 166 125 33 25 41 8 600 例3 对24名科技人员掌握外语的情况进行调查结果如下 英 日 德 法四种外语中 每个人至少会一种 会英 日 德 法语的人数分别是13 5 10 9人 同时会英 日语的有2人 同时会英 法语的有4人 同时会德 法语的有4人 同时会英 德语的有4人 会日语的人不会德语 也不会法语 问这24人中 只会一种外语的人各是多少人 同时会英 法 德三种语言的人有多少人 解 设全集为U E F G J分别表示会英 法 德 日语人的集合 U 24 E F G F E G 4又设 E F G x只会英 日 德 法一种外语的人分别是y1 y2 y3 y4 于是可以画出文氏图及方程如下 y1 2 4 x x 2 13y2 2 4 x x 9y3 2 4 x x 10y4 2 5y1 y2 y3 y4 3 4 x x 2 24解得 y1 4 y2 2 y3 3 y4 3x 1 二元关系 二元关系是一个很重要的概念 它在很多数学领域中都有应用 在计算机科学的如下理论都离不开关系 逻辑设计 数据结构 编译原理 软件工程数据库理论 计算理论 算法分析 操作系统等本章主要介绍 关系的概念及表示方法关系的性质关系的运算 关系的复合 求逆关系 关系的闭包 三种关系 等价关系 相容关系 次序关系 3 4序偶与集合的笛卡尔积 实际上 序偶 概念生活中很常见 例如 用序偶表示平面直角坐标系中一个点 a b 设x表示上衣 y表示裤子 x y 可以表示一个人的着装 一 序偶与有序n元组1 定义 由两个对象x y组成的序列称为有序二元组 也称之为序偶 记作 称x y分别为序偶的第一 第二元素 注意 序偶与集合 x y 不同 序偶 元素x和y有次序 集合 x y 元素x和y的次序是无关紧要的 2 定义 设 是两个序偶 如果x u和y v 则称和相等 记作 3 定义 有序3元组是一个序偶 其第一个元素也是个序偶 有序3元组 c 可以简记成 但 不是有序3元组 4 定义 有序n元组是一个序偶 其第一个元素本身是个有序n 1元组 记作 xn 且可以简记成 5 定义 x1 y1 x2 y2 xn yn 二 集合的笛卡尔积 例如 斗兽棋 的16颗棋子 可看成是由两种颜色的集合A和8种动物的集合B组成的 A 红 蓝 B 象 狮 虎 豹 狼 狗 猫 鼠 每个棋子可以看成一个序偶 斗兽棋可记成集合A B 虎 象 狮 豹 狼 鼠 猫 狗 1 定义 设A B是集合 由A的元素为第一元素 B的元素为第二元素组成序偶的集合 称为A和B的笛卡尔积 记作A B 即A B x A y B 例1设A 0 1 B a b 求A B B A A A 解 A B B A A A 可见A B B A所以 集合的笛卡尔积运算不满足交换律 另外 A B C c A B c C A B C a A B C 因 不是有序三元组 所以 A B C A B C 故 也不满足结合律 2 性质1 如果A B都是有限集 且 A m B n 则 A B m n 证明 由笛卡尔积的定义及排列组合中的乘法原理 直接推得此定理 2 A B 3 对 和 满足分配律 设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 证明 任取 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 所以 式成立 其余可以类似证明 4 若C 则A B A C B C C A C B 证明 必要性 设A B 求证A C B C任取 A C x A y C x B y C 因A B B C所以 A C B C 充分性 若C 由A C B C求证A B取C中元素y 任取x A x A y C A C B C 由A C B C x B y C x B所以 A B 所以A B A C B C 类似可以证明A B C A C B 5 设A B C D为非空集合 则A B C D A C B D 证明 首先 由A B C D证明A C B D 任取x A 任取y B 所以x A y B A B C D 由A B C D x C y D所以 A C B D 其次 由A C B D 证明A B C D任取 A B A B x A y B x C y D 由A C B D C D所以 A B C D证毕 6 约定 A1 A2 An 1 An A1 A2 An特别A A A An设R是实数集合 则R2表示笛卡尔坐标平面 R3表示三维空间 Rn表示n维空间 3 应用1 令A1 x x是学号 A2 x x是姓名 A3 男 女 A4 x x是出生日期 A5 x x是班级 A6 x x是籍贯 则A1 A2 A3 A4 A5 A6中一个元素 这就是学生档案数据库的一条信息 所以学生的档案就是A1 A2 A3 A4 A5 A6的一个子集 n个 2 令A a b c d e f g h i j k l m n o p q r s t u v w x y z 是英文字母表一个英文单词可以看成有序n元组 如at boy data computer 于是可以说 at A2 boy A3 data A4 computer A8 于是英文词典中的单词集合可以看成是A A2 An的一个子集 作业第105页 3 5关系及其表示法 关系是一个非常普遍的概念 如数值的大于关系 整除关系 人类的父子关系 师生关系 同学关系等 下面讨论如何从中抽象出关系的定义和如何表示关系 一 例子1 大写英字母与五单位代码的对应关系R1 令 A B C D Z 30 23 16 22 21 是五单位代码集合 11000 10011 01110 10010 10001 R1 2 令 1 2 3 4 A中元素间的 关系R2 R2 A A二 基本概念1 关系的定义定义1 设A 是集合 如果 A B 则称R是一个从A到B的二元关系 如果R A A 则称R是A上的二元关系 二元关系简称为关系 定义2 任何序偶的集合 都称之为一个二元关系 如 R R xRy也称之为x与y有 关系 后缀表示中缀表示 R xRy也称之为x与y没有 关系 例3 R是实数集合 R上的几个熟知的关系 从例3中可以看出关系是序偶 点 的集合 构成线 面 2 关系的定义域与值域定义域 domain 设R A B 由所有 R的第一个元素组成的集合 称为R的定义域 记作domR 即domR x y R 值域 range 设R A B 由所有 R的第二个元素组成的集合 称为R的值域 记作ranR 即ranR y x R 上述R2 domR2 1 2 3 4 ranR2 1 2 3 4 三 关系的表示方法 1 枚举法 即将关系中所有序偶一一列举出 写在大括号内 如前的R2 2 谓词公式法 即用谓词公式表示序偶的第一元素与第二元素间的关系 例如R x R时 从x到y引一条有向弧 边 这样得到的图形称为R的关系图 如R A A 即R是集合A中关系时 可能有 R 则从x到x画一条有向环 自回路 例设A 1 2 3 4 B a b c R3 A B R3 则R3的关系图如下 例设A 1 2 3 4 R4 A A R4 则R4的关系图如右上图 1 4 2 3 R4 R3 4 矩阵表示法 有限集合之间的关系也可以用矩阵来表示 这种表示法便于用计算机来处理关系 设A a1 a2 am B b1 b2 bn 是个有限集 R A B 定义R的m n阶矩阵MR rij m n 其中rij R3 R4 上例中MR MR4 四 三个特殊关系 1 空关系 因为 A B 或 A A 所以 也是一个从A到B 或A上 的关系 称之为空关系 即无任何元素的关系 它的关系图中只有结点 无任何边 它的矩阵中全是0 2 完全关系 全域关系 A B 或A A 本身也是一个从A到B 或A上 的关系 称之为完全关系 即含有全部序偶的关系 它的矩阵中全是1 3 A上的恒等关系IA IA A A 且IA x A 称之为A上的恒等关系 例如A 1 2 3 则IA A上的 完全关系及IA的关系图及矩阵如下 五 关系的集合运算 由于关系就是集合 所以集合的 和 运算对关系也适用 例如 A是学生集合 R是A上的同乡关系 S是A上的同姓关系 则R S 或同乡或同姓关系R S 既同乡又同姓关系R S 同乡而不同姓关系R S 同乡而不同姓 或同姓而不同乡关系 R 不是同乡关系 这里 R A A R 3 6关系的性质 本节将研究关系的一些性质 它们在关系的研究中起着重要的作用 这是本章最重要的一节 本节中所讨论的关系都是集合A中的关系 关系的性质主要有 自反性 反自反性 对称性 反对称性和传递性 一 自反性定义 设R是集合A中的关系 如果对于任意x A都有 R xRx 则称R是A中自反关系 即R是A中自反的 x x A xRx 例如在实数集合中 是自反关系 因为 对任意实数x 有x x 从关系有向图看自反性 每个结点都有环 从关系矩阵看自反性 主对角线都为1 令A 1 2 3 给定A上八个关系如下 可见这八个关系中R1 R3 R4是自反的 二 反自反性定义 设R是集合A中的关系 如果对于任意的x A都有 R 则称R为A中的反自反关系 即R是A中反自反的 x x A R 从关系有向图看反自反性 每个结点都无环 从关系矩阵看反自反性 主对角线都为0 如实数的大于关系 父子关系是反自反的 注意 一个不是自反的关系 不一定就是反自反的 如前边R6 R7非自反 也非反自反 下面R2 R5 R8 均是反自反关系 三 对称性定义 R是集合A中关系 若对任何x y A 如果有xRy 必有yRx 则称R为A中的对称关系 R是A上对称的 x y x A y A xRy yRx 从关系有向图看对称性 在两个不同的结点之间 若有边的话 则有方向相反的两条边 从关系矩阵看对称性 以主对角线为对称的矩阵 邻居关系是对称关系 朋友关系是对称关系 下边R3 R4 R6 R8均是对称关系 四 反对称性定义 设R为集合A中关系 若对任何x y A 如果有xRy 和yRx 就有x y 则称R为A中反对称关系 R是A上反对称的 x y x A y A xRy yRx x y x y x A y A x y xRy yx P112 由R的关系图看反对称性 两个不同的结点之间最多有一条边 从关系矩阵看反对称性 以主对角线为对称的两个元素中最多有一个1 另外对称与反对称不是完全对立的 有些关系它既是对称也是反对称的 如空关系和恒等关系 下边R1 R2 R4 R5 R8均是反对称关系 R4 R8既是对称也是反对称的 五 传递性定义 R是A中关系 对任何x y z A 如果有xRy 和yRz 就有xRz 则称R为A中传递关系 即R在A上传递 x y z x A y A z A xRy yRz xRz 实数集中的 集合 是传递的 从关系关系图和关系矩阵中不易看清是否有传递性 有时 必须直接根据传递的定义来检查 检查时要特别注意使得传递定义表达式的前件为F的时候此表达式为T 即是传递的 即若 R与 R有一个是F时 即定义的前件为假 R是传递的 例如A 1 2 下面A中关系R是传递的 通过带量词的公式在论域展开式说明R在A上传递 x y z x A y A z A xRy yRz xRz x y z xRy yRz xRz 为了简单做些删改 y z 1Ry yRz 1Rz y z 2Ry yRz 2Rz z 1R1 1Rz 1Rz z 1R2 2Rz 1Rz z 2R1 1Rz 2Rz z 2R2 2Rz 2Rz 1R1 1R1 1R1 1R1 1R2 1R2 1R2 2R1 1R1 1R2 2R2 1R2 2R1 1R1 2R1 2R1 1R2 2R2 2R2 2R1 2R1 2R2 2R2 2R2 F F F F T T T F F T F T F F F F T F F F F F F F T 下边R1 R3 R4 R5 R8均是传递的关系 本节要求 1 准确掌握这五个性质的定义 2 熟练掌握五个性质的判断和证明 R是A中自反的 x x A xRx R是A中反自反的 x x A R R是A上对称的 x y x A y A xRy yRx R是A上反对称的 x y x A y A xRy yRx x y x y x A y A x y xRy yx R在A上传递 x y z x A y A z A xRy yRz xRz 上述定义表达式都是蕴涵式 所以判断关系R性质时要特别注意使得性质定义表达式的前件为F的时候此表达式为T 即R是满足此性质的 自反和反自反性除外 从关系的矩阵 从关系的有向图 性质判定 下面归纳这八个关系的性质 Y 有N 无 练习1 令I是整数集合 I上关系R定义为 R x y可被3整除 求证R是自反 对称和传递的 证明 证自反性 任取x I 要证出 R 因x x 0 0可被3整除 所以有 R 故R自反 证对称性 任取x y I 设 R 要证出 R 由R定义得x y可被3整除 即x y 3n n I y x x y 3n 3 n 因 n I R 所以R对称 证传递性 任取x y z I 设xRy yRz 要证出xRz 由R定义得x y 3m y z 3n m n I x z x y y z 3m 3n 3 m n 因m n I 所以xRz 所以R传递 证毕 练习2 设R是集合A上的一个自反关系 求证 R是对称和传递的 当且仅当和在R中 则有也在R中 证明 必要性 已知R是对称和传递的 设 R又 R 要证出 R 因R对称的故 R 又已知 R由传递性得 R 所以有如果和在R中 则有也在R中 充分性 已知任意a b c A 如和在R中 则有也在R中 先证R对称 任取a b A设 R 要证出 R 因R是自反的 所以 R 由 R且 R 根据已知条件得 R 所以R是对称的 再证R传递 任取a b c A设 R R 要证出 R 由R是对称的 得 R 由 R且 R 根据已知条件得 R 所以R是传递的 作业第113页 3 7关系的复合与逆关系 二元关系除了可进行集合并 交 补等运算外 还可以进行一些新的运算 先介绍由两个关系生成一种新的关系 即关系的复合运算 例如 有3个人a b c A a b c R是A上兄妹关系 S是A上母子关系 R S即a是b的哥哥 b是a的妹妹 b是c的母亲 c是b的儿子 则a和c间就是舅舅和外甥的关系 记作R S 称它是R和S的复合关系 1 定义 设是R从X到Y的关系 S是从Y到Z的关系 则R和S的复合关系记作R S 定义为 R S x X z Z y y Y R S 显然 R S是从X到Z的关系 2 复合关系的计算方法 俗称过河拆桥法 A 1 2 3 B 1 2 3 4 C 1 2 3 4 5 R A BS B C 枚举法R S 则R S 有向图法 关系矩阵法令A a1 a2 am B b1 b2 bn C c1 c2 ct R A BS B C c11 a11 b11 a12 b21 a1n bn1 a1k bk1 其中 是逻辑乘 是逻辑加 cij ai1 b1j ai2 b2j ain bnj aik bkj 1 i m 1 j t 谓词公式法设I是实数集合 R和S都是I上的关系 定义如下 R y x2 3x S y 2x 3 所以R S y 2x2 6x 3 三 性质关系复合运算不满足交换律 但是1 满足结合律 R A BS B CT C D则 证明 任取 R ST b b B R ST b b B R c c C S T b c b B R c C S T c b c C b B R S T c c C b b B R S T c c C RS T RS T 所以 可以用下图形象表示 2 R A BS B CT B C R S T RS RT R S T RS RT 证明 任取 R S T b b B R S T b b B R S T b b B R S b B R T b b B R S b b B R T RS RT RS RT 所以R S T RS RT 证明 任取 R S T b b B R S T b b B R S T b b B R S b B R T b b B R S b b B R T RS RT RS RT 所以R S T RS RT x A x B x xA x xB x 3 R是从A到B的关系 则RIB IAR R此式的证明很容易 从略 下面列举一例来验证 令A 1 2 3 B a b c d 从这两个图看出它们的复合都等于R 4 关系的乘幂令R是A上关系 由于复合运算可结合 所以关系的复合可以写成乘幂形式 即RR R2 R2R RR2 R3 一般地R0 IA RmRn Rm n Rm n Rmn m n为非负整数 例如R是A上关系 如上图所示 可见 R2 表明在R图上有从a到c有两条边的路径 abc R3 表明在R图上有从a到d有三条边的路径 abcd 如果 Rk 表明在R图上有从x到y有k条边 长为k 的路径 x y A 逆关系 逆关系 反关系 也是我们经常遇到的概念 例如 与 就是互为逆关系 一 定义R是从A到B的关系 如果将R中的所有序偶的两个元素的位置互换 得到一个从B到A的关系 称之为R的逆关系 记作RC 或R 1 RC R RC R二 计算方法1 R RC 2 RC的有向图 是将R的有向图的所有边的方向颠倒一下即可 3 RC的矩阵M MR T即为R矩阵的转置 如三 性质令R S都是从X到Y的关系 则1 RC C R2 R S C RC SC 3 R S C RC SC 4 R S C RC SC RC 101 证明1 任取 R S C 则 R S C R S R S RC SC RC SC所以 R S C RC SC 其它类似可证 5 R S RC SC 证明 充分性 已知RC SC 则任取 R RC SC S R S必要性 已知R S 则任取 RC R S SC RC SC6 R C RC证明 任取 R C R R RC RC R C RC 7 令R是从X到Y的关系 S是Y到Z的关系 则 RS C SCRC 注意 RCSC 证明 任取 RS C RS y y Y R S y y Y SC RC SCRC所以 RS C SCRC8 R是A上关系 则 R是对称的 当且仅当RC R R是反对称的 当且仅当R RC IA 证明 充分性 已知RC R 证出R对称 任取x y A设 R 则 RC 而RC R所以有 R 所以R对称 必要性 已知R对称 证出RC R 先证RC R 任取 RC 则 R 因R对称所以有 R 所以RC R 再证R RC 任取 R 因R对称 所以有 R 则 RC 所以R RC 最后得RC R 证明 充分性 已知R RC IA 证出R反对称 任取x y A设 R且 R R R R RC R RC IA 因R RC IA x y所以R反对称 必要性 已知R反对称 证出R RC IA 任取 R RC R RC R RC R R x y 因R反对称 IA所以R RC IA 第4 3和4 4节的要求 熟练掌握求复合关系和逆关系的计算方法及性质 作业 第118页 a b 3 8关系的闭包运算 关系的闭包是个很有用的概念 特别是传递闭包 关系的闭包是通过关系的复合和求逆构成的一个新的关系 这里要介绍关系的自反闭包 对称闭包和传递闭包 一 例子给定A中关系R 如图所示 分别求A上另一个关系R 使得它是包含R的 最小的 序偶尽量少 分别具有自反 对称 传递 性的关系 这个R 就分别是R的自反 对称 传递 闭包 这三个关系图分别是R的自反 对称 传递闭包 二 定义 给定A中关系R 若A上另一个关系R 满足 R R R 是自反的 对称的 传递的 R 是 最小的 即对于任何A上自反 对称 传递 的关系R 如果R R 就有R R 则称R 是R的自反 对称 传递 闭包 记作r R s R t R reflexive symmetric transitive 实际上r R s R t R 就是包含R的 最小 的自反 对称 传递 关系 三 计算方法定理1 给定A中关系R 则r R R IA 证明 令R R IA 显然R 是自反的和R R 下面证明R 是 最小的 如果有A上自反关系R 且R R 又IA R 所以R IA R 即R R 所以R 就是R的自反闭包 即r R R IA 定理2 给定A中关系R 则s R R RC 证明方法与1 类似 定理3 给定A中关系R 则t R R R2 R3 证明 令R R R2 R3 显然有R R 证R 是传递的 任取x y z A 设有 R R 由R 定义得必存在整数i j使得 Ri Rj 根据关系的复合得 Ri j 又因Ri j R 所以 R R 传递 证R 是 最小的 如果有A上传递关系R 且R R 证出R R 任取 R 则由R 定义得必存在整数i 使得 Ri 根据关系的复合得A中必存在i 1个元素e1 e2 ei 1 使得 见49页 R R R 因R R 有 R R R 由于R 传递 所以有 R R R 综上所述 R 就是R的传递闭包 即t R R R2 R3 Ri 用上述公式计算t R 要计算R的无穷大次幂 好象无法实现似的 其实则不然 请看下例 A 1 2 3 A中关系R1 R2 R3 如下 R1 R2 R3 所以t R1 R1 IA R2 t R2 R2 t R3 R2 定理4 给定A中关系R 如果A是有限集合 A n则t R R R2 Rn 证明 令R R R2 R3 R R R2 Rn下面证明R R 显然有R R 下面证明R R 任取 R 由R 定义得必存在最小的正整数i使得 Ri 下面证明i n 如果i n 根据关系的复合得A中必存在i 1个元素e1 e2 ei 1 使得 R R R 上述元素序列 x e0 e1 e2 ei 1 y ei中共有i 1个元素 i 1 n 而A中只有n个元素 所以上述元素中至少有两个相同 设ej ek j k 于是R的关系图中会有下面这些边 从此图中删去回路中k j k j 1 条边后得 Ri k j i k j R 于是R R 最后得R R 所以t R R R2 Rn定理证毕 求t R 的矩阵Warshall算法 X n R X X 令MR AR2的矩阵为A2 Rk的矩阵为Ak 于是t R 的矩阵记作MR A A2 Ak 是逻辑加 置新矩阵A MR 置i 1 对所有j 如果A j i 1 则对k 1 2 nA j k A j k A i k 第j行 第i行 送回第j行 i加1 如果i n 则转到步骤 否则停止 下面举例 令X 1 2 3 4 X中关系R图如右图所示 运行该算法求t R 的矩阵 i 1 i 列 j 行 A 4 1 11行 4行 4行i 2A 1 2 1 1行 2行 1行A 2 2 1 2行 2行 2行A不变A 4 2 1 4行 2行 4行 4行全1 A不变i 3A 1 3 1 1行 3行 1行 3行全0 A不变A 2 3 1 2行 3行 2行 3行全0 A不变A 4 3 1 4行 3行 4行 3行全0 A不变i 4A 1 4 1 1行 4行 1行A 4 4 1 4行 4行 4行A不变 最后A Mt R A MR A的初值 A 四 性质定理5 R是A上关系 则 R是自反的 当且仅当r R R R是对称的 当且仅当s R R R是传递的 当且仅当t R R 证明略 因为由闭包定义即可得 定理6 R是A上关系 则 R是自反的 则s R 和t R 也自反 R是对称的 则r R 和t R 也对称 R是传递的 则r R 也传递 证明 因为R自反 由定理5得r R R 即R IA R r s R s R IA R RC IA R IA RC r R RC R RC s R s R 自反 类似可以证明t R 也自反 证明 证明t R 对称 t R C R R2 Rn C RC R2 C Rn C RC RC 2 RC n R R2 Rn R对称 RC R t R 所以t R 也对称 类似可以证明r R 也对称 证明 证明r R 传递 先用归纳法证明下面结论 R IA i IA R R2 Ri i 1时R IA IA R结论成立 假设i k时结论成立 即 R IA k IA R R2 Rk 当i k 1时 R IA k 1 R IA k R IA IA R R2 Rk IA R IA R R2 Rk R R2 Rk 1 IA R R2 Rk Rk 1所以结论成立 t r R t R IA R IA R IA 2 R IA 3 IA R IA R R2 IA R R2 R3 IA R R2 R3 IA t R IA R R传递t R R r R 所以r R 也传递 定理7 设R1 R2是A上关系 如果R1 R2 则 r R1 r R2 s R1 s R2 t R1 t R2 证明 r R1 IA R1 IA R2 r R2 类似可证 定理8 设R是A上关系 则 sr R rs R tr R rt R st R ts R 证明 sr R r R r R c R IA R IA c R IA Rc IAc R IA Rc IA R Rc IA s R IA rs R 的证明用前边证明的结论 R IA k IA R R2 Rk很容易证明 这里从略 因R s R 由定理7得t R ts R st R sts R 因s R 对称 有定理6得ts R 也对称 由定理5得sts R ts R 所以有st R ts R 证明完毕 通常将t R 记成R tr R 记成R 即t R R R R2 Rn tr R rt R R R0 R R2 Rn 练习 给定A中关系R如图所示 分别画出r R s R t R sr R rs R tr R rt R st R ts R 的图 本节重点掌握闭包的定义 计算方法和性质 作业第127页 3 9集合的划分与覆盖 图书馆的图书 要分成许多类存放 学校的学生要按照专业分成许多班 即对集合的元素划分一 定义设X是一个非空集合 A A1 A2 An Ai Ai X i 1 2 n 如果满足A1 A2 An X i 1 2 n 则称A为集合X的覆盖 设A A1 A2 An 是X一个覆盖 且Ai Aj i j 1 i j n 则称A是X的划分 每个Ai均称为这个划分的一个划分 类 例X 1 2 3 A1 1 2 3 A2 1 2 3 A3 1 2 3 A4 1 2 2 3 A5 1 3 A1 A2 A3 A4是覆盖 A1 A2 A3也是划分 划分 一定是覆盖 但覆盖 不一定是划分 二 最小划分与最大划分最小划分 划分块最少的划分 即只有一个划分块的划分 这个划分块就是X本身 如A1 最大划分 划分块最多的划分 即每个划分块里只有一个元素的划分 如A2 A1 A2 A3是一种划分 其中A1是最小划分 A2是最大划分 三 交叉划分例X是东大学生集合 A和B都是X的划分 A M W M X W X M 男生 W 女生 B L N L X N X L 河南人 N 非河南人 C L M L W N M N W 称C是X的交叉划分 定义 若A A1 A2 Am 与B B1 B2 Bn 都是集合X的划分 则其中所有的Ai Bj 组成的集合C 称为C是A与B两种划分的交叉划分 此定理的证明不讲 证明 A1 A2 Am 与 B1 B2 Bn 的交叉划分是C A1 B1 A1 B2 A1 Bn A2 B1 A2 B2 A2 Bn Am B1 Am B2 Am Bn 在C中任取元素 Ai Bh X Ai X Bj X A1 B1 A1 B2 A1 Bs A2 B1 A2 Bs Ar B1 Ar B2 Ar Bs A1 B1 B2 B3 Bs A2 B1 B2 B3 Bs Ar B1 B2 B3 Bs A1 A2 A3 Ar B1 B2 B3 Bs X X X 再验证C中任意两个元素不相交 在C中任取两个不同元素Ai Bh和Aj Bk 考察 Ai Bh Aj Bk i j和h k不同时成立 Ai Aj Bh Bk i j h k Ai Aj Bh Bk Ai i j h k Ai Aj Bh Bk i j h k Ai Aj Bh Bk Bh 综上所述 C是X的划分 作业 第130页 1 3 10等价关系与等价类 等价关系是很重要的关系 它是我们遇到最多的关系 例如 数值相等关系 命题间的等价关系 三角形相似 和全等关系 一 等价关系1 定义 设R是A上关系 若R是自反的 对称的和传递的 则称R是A中的等价关系 若a b A 且aRb 则称a与b等价 例子 集合A 1 2 3 4 5 6 7 R是A上的模3同余关系 即R x y可被3整除 或x 3与y 3的余数相同 即 R x mod3 y mod3 例如4 mod3 7 mod3 3 mod3 6 mod3 R 2 等价关系的有向图1 完全关系 全域关系A A 图 下面分别是当A中只有1 2 3个元素时的完全关系图 2 等价关系的有向图 上边的模3同余关系R的图 从关系图可看出 R是自反 对称 传递的关系 所以R是等价关系 等价关系R的有向图可能由若干个独立子图 R图的一部分 构成的 每个独立子图都是完全关系图 上述关系R图就是由三个独立的完全图构成的 下面给出八个关系如图所示 根据等价关系有向图的特点 判断哪些是等价关系 A 1 2 3 下面是A中关系 思考题 A 1 2 3 可构造多少个A中不同的等价关系 可以根据等价关系有向图的特点来考虑 如果等价关系R中有a 三个独立子图的情形 则 个等价关系 b 二个独立子图的情形 则 个等价关系 c 一个独立子图的情形 则 个等价关系 一共有 个中不同的等价关系 二 等价类 我们经常用等价关系对集合进行划分 得到的划分