离散数学第03章集合代数.ppt

第三章集合代数 集合论是现代数学的基础 德国数学家康托尔 G Cantor 被誉为集合论的创始人 集合论在计算机科学 人工智能领域 逻辑学及语言学等方面都有着重要的应用 对于从事计算机科学的工作者来说 集合论是不可缺少的理论知识 熟悉和掌握它是十分必要的 第三章集合代数 3 1集合的概念和表示法3 2集合的运算3 3包含排斥原理3 4集合的笛卡尔积与无序积 3 1集合的概念与表示法 一 集合与元素1 集合的描述定义所谓集合 是指某些可辨别的不同对象的全体 将用大写字母A B X Y 表示之 组成集合的对象称为集合的元素或成员 将用小写字母a b x y 表示之 a是A的元素或a属于A 记作a A a不是A的元素或a不属于A 记作a A 或者 a A 2 集合的表示 表示一个特定集合 基本上有两种方法 枚举法 列出集合的所有元素 元素之间用逗号分开 再用花括号括起 如 A a e i o u 表明集合A是由字母a e i o和u为元素构成的 谓词法 用谓词公式来确定集合 即个体域中能使谓词公式为真的那些元素 确定了一个集合 因为这些元素都具有某种特殊性质 若P x 含有一个自由变元的谓词公式 则 x P x 定义了集合S 并可表为 S x P x 由此可见 P c 为真当且仅当c S 从而有x S P x T 集合的元素是彼此不同的 如 1 1 2 2 3 1 2 3 集合的元素是无序的 如 1 2 3 3 1 2 元素和集合之间的关系是隶属关系 属于记作 不属于记作 如 A a b c d d 这里a A b c A d A d A 但b A d A 可以用一种树形图来表示这种隶属关系 该图分层构成 每个层上的结点都表示一个集合 它的儿子就是它的元素 上例中集合A a b c d d 的树形图如图所示 图中的a b c d也是集合 由于所讨论的问题与a b c d的元素无关 所以没有列出它们的元素 鉴于集合的元素是集合这一规定 隶属关系可以看作是处在不同层次上的集合之间的关系 集合的元素一旦给定 这一集合便完全确立 这一事实被形式地叙述为外延公理 外延公理 两集合A和B相等 当且仅当它们有相同的元素 若A与B相等 记为 A B 否则 记为 A B 外延公理可形式表为 A B x x A x B 或者A B x x A x B x x B x A 顺便指出 在应用外延公理证明集合A与B相等时 只需考察 对于任意元素x 应有 x A x B成立即可 这就是说 证明两集合相等时可按此法行事 子集是描述一个集合与另一个集合之间的关系 其定义如下 定义3 1 1设A和B是任意两个集合 如果集合A的每个元素 都是集合B中的一个元素 则称A是B的子集 或称A被包含于B中 或者说B包含A 并记为A B 二 集合之间的关系 集合包含的符号化表示 A B x x A x B 表明 要证明A B 只需对任意元素x 有下式x A x B成立即可 如果A B且B A 则称A与B相等 记作A B 若集合B不包含集合A 记为A B 定义3 1 2设A和B是两个集合 若A B且A B 则称A是B的真子集 记为A B 也称B真包含A 该定义也可表为A B A B A B 如果A不是B的真子集 则记作A B 定义3 1 3如果一个集合包含了所要讨论的每一个集合 则称该集合为全集 记为E 它可形式地表为E x P x P x 其中 P x 为任何谓词公式 显然 全集E即是第二章中的全总个体域 于是 每个元素x都属于全集E 即命题 x x E 为真 由定义易知 对任意集合A 都有A E 在实际应用中 常常把某个适当大的集合看成全集E 全集是有相对性的 定义3 1 4不含任何元素的集合 称为空集 记作 它可形式地表为 x P x P x 其中 P x 为任何谓词公式 由定义可知 对任何集合A 有 A 这是因为任意元素x 公式x x A总是为真 注意 与 是不同的 是以 为元素的集合 而 没有任何元素 能用 构成集合的无限序列 1 该序列除第一项外 每项均以前一项为元素的集合 2 该序列除第一项外 每项均以前面各项为元素的集合 它即是冯 诺依曼在1924年使用空集 给出自然数的集合表示 0 1 2 定理3 1 1空集是一切集合的子集 推论空集是唯一的 定理3 1 2 对任一集合A 有A A 若A B且B C 则A C 三 集合的基数 表示集合中元素多少或度量集合大小的数 称作集合的基数或势 一个集合A的基数 记为 A 如果一个集合恰有m个不同的元素 且m是某个非负整数 称该集合是有限的或有穷的 否则称这个集合为无限的或无穷的 例如 Nm 0 1 2 m 1 为含m个元素的有穷集 常见的无穷集合有 N 0 1 2 3 即自然数集合 Z 2 1 0 1 2 3 即整数集合 Z 1 2 3 即正整数集合 Q 有理数集合 R 实数集合 C 复数集合 四 集合的幂集 一个集合的幂集是指以该集合所有子集为元素的集合 即是由这些子集所组成的集合族 定义3 1 5设A为一集合 A的幂集是一集合族 记为 A A B B A 由定义可知 A A A 任给一个n元集 怎样求出它的全部子集 定理3 1 3如果有限集合A有n个元素 则其幂集 A 有2n个元素 五 文氏图 文氏 Venn 图是一种利用平面上的点构成的图形来形象展示集合的一种方法 全集E用一个矩形的内部表示 其他集合用矩形内的园面或一封闭曲线圈成的面积来表示 如果A B 则表示A的圆面一般将完全落在表示B的圆面内 如图中 a 如果A与B没有公共元素 那么表示A的圆面将同表示B的圆面分开 如图中 b 当A和B是两个任意的集合时 可能会是 有些元素在A中但不在B中 有些元素在B中却不在A中 有些元素同时在A和B中 有些元素则既不在A中也不在B中 因此用图中 c 表示任意两个集合A和B 3 2集合的运算 集合运算是指用已知的集合去生成新的集合 假设所有集合都是全集E的子集 即这些集合是利用子集公理得到的 下面依次介绍常见的集合运算 定义3 2 1设A和B是任意两个集合 A和B的并是集合 记为 A B A B x x A x B A和B的交是集合 记为 A B A B x x A x B A和B的差 或B关于A的相对补是集合 记为 A B A B x x A x B 一 并 交和差运算 定义3 2 2若A和B是集合 且A B 则称A和B是不相交的 如果C是个集合族 且C中任意两个不同元素都不相交 则称C中的集合是互不相交的 或称C是两两不相交的集合族 定理3 2 1任给集合A B和C 则 A B B A A B B A A B C A B C A B C A B C 该定理表明 集合并和交运算满足交换律和结合律 定理3 2 2任给集合A B和C 则 A B C A B A C A B C A B A C 该定理表明 集合运算并对交 交对并都是可分配的 定理3 2 3任给集合A B C和D 则 若A B 则A B B A B A 若A B和C D 则A C B D A C B D 推论3 2 3 A E E A E A定理3 2 4任给集合A B和C 则 A B C A B A C A B C A B A C 定义3 2 4集合A的补是集合 记为 A A E A x x E x A x x A 定理3 2 5任给集合A 则 A A E A A 定理3 2 6任给集合A和B 则B AiffA B E且A B 该定理表明了 若A的补是B 则B的补是A 即A和B互补 补的唯一性 推论3 2 5 E E定理3 2 7任给集合A 则 A A 该定理表明了 A的补的补是A 定理3 2 8任给集合A和B 则 A B A B A B A B 定义3 2 5任给集合A和B A和B的对称差是集合 记为A B A B A B B A x x A x B x B x A 定理3 2 9任给集合A和B 则A B A B A B A B A B 推论3 2 9 A B A B A B B A A A A A 集合之间的关系和运算可以用文氏图给予形象的描述 二 集合代数与对偶原理这里将形式地讨论由集合 集合变元 集合运算和圆括号所构成的集合代数以及集合代数中的对偶原理 与命题逻辑相似 对于给定集合实行集合运算 可以生成新的集合 同用大写英文字母表示确定集合一样 也用大写字母表示不确定的集合 前者称为集合常元 后者称为集合变元 集合变元用以集合常元代替后 才表示确定的集合 下面将给出集合的合式公式定义 定义3 2 6可按下列规则生成集合合式公式 单个集合变元是集合合式公式 若A是集合合式公式 则 A也是集合合式公式 若A和B是集合合式公式 则 A B A B A B 和 A B 也都是集合合式公式 只有有限次使用 和 构成的符号串才是集合合式公式 简称集合合式公式为公式 定义3 2 7用任意集合常元取代两个集合公式中的各个集合变元 若所得集合是相等的 则称该两个集合公式是相等的 简称等式 因为集合公式相等 不依赖于取代集合变元的集合 故常称这些等式为集合恒等式 或集合定律 它们刻划了集合运算的某些性质 这些性质描述一个代数 称为集合代数 下面列出常用集合定律 1 等幂律A A AA A A 2 结合律 A B C A B C A B C A B C 3 交换律A B B AA B B A 4 分配律A B C A B A C A B C A B A C 5 同一律A AA E A 6 零律A E EA 7 补余律A A EA A 8 吸收律A A B AA A B A 9 德 摩根律 A B A B A B A B 10 双重否定律 A A 3 3包含排斥原理 一 有限集基数的有关结果设A B为任意有限集合 则有 A B A B A B A B min A B A B A B 2 A B A B A B A B B A B A 定理3 3 1任给集合A和B 则 A B A B A B 证明 当A B 则有 A B A B 当A B 则 A A B B A B A B B B A B A A B A B A B A B A B A B A B A B A B A B 包含排斥原理 例 设某班有60名同学 其中班足球队员有28名 篮球队员有15名 若有25名同学没有参加这二个队 问同时参加这二个队的队员有多少名 解 设A为足球队员集合 B为篮球队员集合 则 A B 60 25 35 A B A B A B 28 15 35 8 二 包含n个集合的包含排斥原理 A1 A2 An i 1n Ai 1 i j n Ai Aj 1 i j k n Ai Aj Ak 1 n 1 A1 A2 An 特别地 n 3 A1 A2 A3 A1 A2 A3 A1 A2 A1 A3 A2 A3 A1 A2 A3 证明 当n 2时 结论成立 设n 1时 结论成立 则 A1 A2 An i 1n 1Ai An i 1n 1Ai An i 1n Ai 1 i j n 1 Ai Aj 1 n 2 i 1n 1Ai I 1n 1 Ai An 1 i j n 1 Ai Aj An 1 n 2 i 1n 1Ai An i 1n Ai 1 i j n Ai Aj 1 n 1 i 1nAi 例 试决定在1到100之间能被2 3 5中某一数整除的数的个数 解 A1表示1到100之间能被2整除的整数集 A2表示1到100之间能被3整除的整数集 A3表示1到100之间能被5整除的整数集 则 A1 int 100 2 50 A2 int 100 3 33 A3 int 100 5 20 A1 A2 int 100 2 3 16 A1 A3 int 100 2 5 10 A2 A3 int 100 3 5 6 A1 A2 A3 int 100 2 3 5 3所以 A1 A2 A3 A1 A2 A3 A1 A2 A1 A3 A2 A3 A1 A2 A3 50 33 20 16 10 6 3 74 3 4集合的笛卡尔积与无序积 笛卡尔积与无序积在后面讨论关系和图论时 都有重要应用 首先引入有序对和无序对的概念 一 序偶定义3 4 1由两个具有固定次序的元素a b组成的有序对叫序偶 并记作 其中 称a为第一元素 b为第二元素 若它们无次序区分 称为二元无序组或无序对 记为 a b 注 若a b时 但 a b b a 序偶的性质 由两个元素组成的序偶是有序的 即当x y时 有 若 iffx y 两个序偶相等 iff 例 已知 求 x和y 解 由有序对相等的充要条件有x 2 52x y 4解得x 3 y 2 二 n元序偶序偶的概念可进一步推广 三元组 四元组 n元组 1 三元组是一个序偶 其第一元素是序偶 记作 注 据定义 z z 2 n元组 一个有序n元组 n 3 是一个有序对 其中第一元素是一个有序n 1元组 记作即 xn 注 xn iff x1 y1 x2 y2 xn 1 yn 1 xn yn 三 笛卡尔积定义3 4 2设A B是任意两个集合 则由第一元素属于A 第二元素属于B的所有序偶构成的集合 叫做集合A和B的笛卡尔积 记为A B 即A B x A y B 笛卡尔积举例 1 假设A表示某大学所有学生的集合 B表示大学开设的所有课程的集合 则A B可用来表示该校学生选课的所有可能情况 2 令A是直角坐标系中x轴上的点集 B是直角坐标系中y轴上的点集 则A B就与平面点集一一对应 3 设A a b B 0 1 2 则A B B A 定理3 4 1若 A n B m 则 A B n m 笛卡尔积运算的性质 B A 当A B且A B均不空时 有A B B A A B C A B C 笛卡尔积对 满足分配律 A C B D A B C D 定理3 4 2任给集合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 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 3若C 则A B A C B C C A C B 定理3 4 4设A B C D为四个非空集合 则A B C D的充要条件为A C B D 关于A C B D A B C D的讨论 该性质的逆命题不成立 可分以下情况讨论 1 当A B 时 显然有A C和B D成立 2 当A 且B 时 也有A C和B D成立 证 任取x A 由于B 必存在y B 因此有x A y B A B C D x C y D x C从而证明了A C 同理可证B D 关于A C B D A B C D的讨论 该性质的逆命题不成立 可分以下情况讨论