Microsoft PowerPoint - ls03.ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - ls03.ppt"

宇肠那
7 years ago
Views:

1 第二部分集合论集合论是研究集合一般性质的数学分支, 创始人是康托尔 (G.Cator ) 现代数学中, 每个对象 ( 数, 函数等 ) 本质上都是集合, 即可以用某种集合来示义, 数学的各个分支本质上都是在研究某一种对象集合的性质, 集合论的特点是研究对象的广泛性, 是计算机科学的基础理论表达工具 3. 集合的基本概念. 集合的定义第三章集合代数集合是现代数学中最重要的基本概念之一我们知道, 在任何一个数学理论中, 不可能对其中的每个概念都严格定义, 这样的概念一般为数学理论中的原始概念, 而称其余的概念为它的派生概念如欧几里得几何学中, 点和线是原始概念, 而三角形和圆则为派生概念今天我们介绍的集合也是一个不能严格定义的原始概念但是为了理解上的方便, 我们仍然给一个不严格的定义 /8 /8 3. 集合的基本概念定义 3.: 任何被称为成员或元素的对象的聚集称为集合 (Set) 例如 : 自然数的全体 N, 有理数的全体 Q, 实数的全体 R, 复数的全体 C, 整数的全体 Z, 都是集合通常情况下, 用带 ( 或不带 ) 下标的大写英文字母表示集合, 而用带 ( 或不带 ) 下标的小写英文字母表示集合的元素或成员 3/8 3. 集合的基本概念. 集合的表示集合是由它所包含的元素完全确定的, 有多种方法来表示一个集合 (). 枚举法 : 当一个集合仅有有限个元素或元素之间有明显的关系时, 采用列出集合中全部元素或部分元素的方法, 叫枚举法例 :A={,,3,4},B={a, b, c, x, y, z},n ={0,,,3, } 这种方法实际上是一种显示表示法, 优点是具有透明性, 缺点是当集合中元素比较多时会占据大量内存 4/8 3. 集合的基本概念 (). 描述法 : 一般用谓词来概括集合中元素的特性, 由谓词 P(x) 所定义的集合常记为 : A={x P(x)} 例 :B={x x R x -=0} 谓词表示法是一种隐式表示法, 所表示的集合元素可以是很少的或无穷多个, 从计算机的角度来看, 是种动态的表示法, 不用占据大量内存 (3). 文氏图法 (Ve): 文氏图解法是一种利用平面上的点的集合作成的对集合的图解, 一般用平面上的圆形或方形表示一个集合 5/8 3. 集合的基本概念 3. 集合与元素的关系元素和集合之间的关系是隶属关系, 即属于或不属于, 属于记作, 不属于记作例 :A={a,{b,c},{{d}}},a A, {b,c} A,b A 例 3-: 在一个很偏僻的孤岛上, 住着一些人家, 岛上只有一个理发师, 该理发师专给那些并且只给那些自己不刮脸的人刮脸那么该给这位理发师刮脸? 6/8

2 3. 集合的基本概念在离散数学中, 我们仅讨论界限清楚无二义性的元素与集合的隶属关系, 即元素 a 要么属于集合 A, 要么不属于集合 A, 两者必居其一 4. 集合的特性 (). 确定性 : 即 a A 或 a A, 两者必居其一且仅居其一 ; (). 互异性 : 集合中相同的元素被视为同一元素, 即 :{,,,} 与 {,} 相同 ; (3). 无序性 : 集合中的元素顺序并不重要, 如 {,,3,4} 与 {,3,4,} 相同 7/8 3. 集合的基本概念 5. 集合之间的关系定义 3.: 设 A,B 是两个集合, 如果 B 中的每个元素都是 A 中的元素, 则称 B 是 A 的子集合, 简称子集 (Subset), 这时也称 B 被 A 包含, 或 A 包含 B, 记作 B A, 或 A B, 称或为包含关系 (Icluso Relato) 如果 B 不被 A 包含, 则记作 B A 例 :N Z Q R C, 但 Z N ; A={,,3,4},B={,},C={,3},D={, 3}, 则 B,C,D A; C D; D C; B C,D; C,D B; A B,C,D 对任意的集合 A, 都有 A A 8/8 3. 集合的基本概念定义 3.3: 设 A,B 为集合, 如果 A B 且 B A, 则称 A 与 B 相等, 记作 A=B, 如果 A 与 B 不相等, 则记作 A B 相等的符号化表示为 :A=B A B B A 例 :A={x x N, 且 x 4},B={0,,,3,4} 则 A=B 定义 3.4: 设 A,B 为集合, 如果 B A 且 B A, 则称 B 是 A 的真子集 (Proper Subset), 记作 B A, 称为真包含关系 (Properly Icluso Relato), 如果 B 不是 A 的真子集, 则记作 B A 9/8 3. 集合的基本概念这时或者 B A, 或者 B=A, 符号化表示为 : B A B A B A 例 : N Z Q R C, 但 N N,{0,},{,3} 是 {0,,,3} 的真子集, 但 {,4} 不是定义 3.5: 不含任何元素的集合叫做空集 (Empty Set), 记作空集符号化表示为: ={x x x} 例 : 设 A = {x x R x + = 0}, 是方程 x + = 0的实数解集, 而该方程无实数解, 所以 A= 0/8 3. 集合的基本概念定理 3.:(): 空集是一切集合的子集, (): 空集是唯一的例 3-: 确定下列命题的真值 : ():φ φ, ():φ φ, (3):φ {φ}, (4): φ {φ} 3. 集合的基本概念定义 3.6: 在一个具体问题中, 如果涉及的集合都是某个集合的子集, 则称这个集合问全集 (Uversal Ser), 用 U 或 E 表示全集是唯一的, 它包含了该问题所涉及的所有元素例 :() 在平面几何中, 全集是由平面上全体点组成 ; () 在人口研究中, 全集是由世界上的所有人组成定义 3.7: 集合中的所有元素的个数称为集合的基数 (Base Number), 记为 A ; 如果一个集合的基数是有限的, 则称集合为有限集 (Fte Set), 如果一个集合的基数是无限的, 则称集合为无限集 (Ifte Set) /8 /8

3 3. 集合的基本概念例 3-3: 求集合 A,B,C,D 的基数 : A=φ;B={,,3};C={,{,3}};D={φ} 解 : A =0; B =3; C =; D = 定义 3.8: 含有个元素的集合 A 称为元集, 它的含义 m 个 (m ) 元素的子集称作它的 m 元子集例 3-4: 设 A={,,3}, 求 A 的全部子集 : 解 : 将 A 的全部子集按从小到大进行分类 : 0 元子集 : 即空集, 有 C 0 3 个 :φ; 元子集 : 即单元素, 有 C 3 个 :{},{},{3}; 元子集 : 有 C 3 个 :{,},{,3},{,3}; 3 元子集 : 有 C 3 3 个 :{,,3} 3/8 3. 集合的基本概念集合 A={,,3} 的全部子集共有 : 0 3 C3 + C3 + C3 + C3 = = 8 一般来说, 对于元集 A, 它的 m(0 m ) 元子集有个, 所以它的不同子集总数为 : 0 C + C C = ( + ) = 定义 3.9: 设 A 为集合, 把 A 的全体子集构成的集合叫做 A 的幂集 (Power Set), 记作 P(A) 或 A, 符号化为 :P(A)={x x A} 例 : 设 A={,,3}, 则 P(A)={φ,{},{},{3}, {,},{,3},{,3},{,,3}}, P(A) = m C 4/8 3. 集合的基本概念例 3-5: 求下列幂集 : ():P( );():P({ });(3):P({,{ }});(4): P({,{,3}}) 3. 集合的运算为了更好的研究集合的性质, 我们定义了集合的几个基本运算定义 3.0: 设 A,B 是两个集合, 则 A 与 B 的并集 (Uo) 定义为 : A U B = { x x A x B}, 称为并运算 (Uo Operato) 例 :{,,3,4} {3,4,5}={,,3,4,5},Q N=Q 定义 3.: 设 A,B 是两个集合, 则 A 与 B 的交集 (Itersecto) 定义为 : A I B = { x x A x B}, 称为交运算 (Itersecto Operato) 例 :{,,3,4} {3,4,5}={3,4},{a, b} φ = φ, Q N=N 5/8 6/8 3. 集合的运算可以将以上定义推广到个甚至无穷个集合的并集或交集 : U A = A U A ULU A = { x x A x A L x A } I A = A I A ILI A = { x x A x A L x A } U A = A U A UL = { x x A x A L} I A = A I A IL = { x x A x A L} 例 :{,} {,3} {0,}={0,,,3}; {,} {,3} {0,}= φ 3. 集合的运算定义 3.: 设 A,B 是两个集合, 则 A 与 B 的差集 (Subtracto) 定义为 : A B = { x x A x B} ; - 称为差运算 (Subtracto Operato),A-B 也可叫做相对补集例 :{,,3,4}-{3,4,5,6}={,};{,}- φ ={,}; φ - {,}= φ ;{,}-{,}= φ 定义 3.3: 设 U 为全集,A 是 U 的子集, 则集合 A 的补集 (Complemet) 定义为 : A = U A = { x x U x A} 也可记为 ~A, -, ~ 称为补运算 (Complemet Operato) 例 :U={,,3,4},A={,},~A={3,4} 7/8 8/8

4 3. 集合的运算定义 3.4: 设 A,B 是两个集合,A 与 B 的对称差集 (Symmetrc Dffereces) 定义为 : A B = ( A U ( B A) 称为对称差运算 (Symmetrc Dffereces Operato) 例 :{,,3,4} {3,4,5,6}={,,5,6}; {a, b, c} φ ={a, b, c} 定理 3.: 集合恒等式 :. 等幂律 :A A=A,A A=A;. 结合律 :(A C=A (B C),(A C=A (B C); 3. 交换律 :A B=B A,A B=B A; 3. 集合的运算 4. 分配律 :A (B C)=(A (A C),A (B C)=(A (A C); 5. 同一律 :A φ =A,A U=A; 6. 零律 :A U=U,A φ = φ ; 7. 排中律 : A U A = U ; 8. 矛盾律 : AI A = φ ; 9. 吸收律 :A (A =A, A (A =A; 0. 德摩根律 :~(A =~A ~B,~(A =~A ~B. 双重否定律 : A = A;. 补交转换律 : A B = AI B 9/8 0/8 3. 集合的运算例 3-6: 证 : () : A B = ( A U ( A I ; () : ( A B = A U B; (3):A,B 为集合, 已知 A-B=B-A, 证明 :A=B 证 :(): A B = ( A U ( B A) = ( A I U ( B I A) I ( A U A) I ( B U I ( B U A) IU IU ~ ( A I I ~ ( A I ( A I 3. 集合的运算 (): ( A B B = (( A I U ( B ( AI ) B I U ( BI ~ ( AI ) U ( B I ( A U ) U B = A U B (3): A B = B A A I B = B I A A I B I B = B I A I B Ο/ = B I A Ο/ = B A B A 同理 :A B, A=B /8 /8. 鸽笼原理 (Pgeohole Prcple) 定理 3.3: 若有 + 个鸽子住进个鸽笼, 则至少有一个鸽笼至少住进只鸽子证明 :( 用反证法 ) 假设每个鸽笼至多只住进只鸽子, 则个鸽笼至多住进只鸽子, 这与有 + 只鸽子矛盾命题成立例 3-7: 求证 : 设有 + 个正整数 a, a, L, a +, 则总可以找到一对数 a 和 a j ( <j +) 使得它们的差能被整除证明 : a a ( =, L, + ) 取被整除的余数, 若个余数互不相同, 则必有一个为 0, 不妨设为 a a 0 则 a a 能被整除否则, 由鸽笼原理, 必有个 0 3/8 余数相同, 不妨设为 a a与 a j a, 则 a a j 能被整除定理 3.4:( 鸽笼原理的推广 ) 若有只鸽子住进 m 个鸽笼, 则至少有一个鸽笼至少住进 - 只鸽子 m +. 容斥原理 ( 包含排斥原理 ) 所谓容斥, 是指我们计算某类物的数目时, 要排斥那些不应包含在这个计数中的数目, 但同时要包含那些被错误地排斥了的数目, 以此补偿, 这种原理称为容斥原理 (The Prcple of Iclusoexcluso), 又称为包含排斥原理定理 3.5: 设 A 和 B 是任意有限集合, 则 A B = A + B - A B 4/8

5 证 : 当 A B 为空时, A B = A + B ; 当 A B 不空时, A = A I B + AI B, B = A I B + A I B 而 AI B + A I B + A I B = AU B 所以 : A B = A + B - A B 推论 3.: 设 U 为全集,A 和 B 是任意有限集合, 则 A I B = U ( A + B ) + A I B 证 : A I B = ~ ( AU = U ( AU = U AU B = U ( A + B ) + A I B 推广到个有限集合的情况 : A 定理 3.6: 设 A, A, L ( ) 推论 3.: 设 U 为全集, A, A, L U A UL A U + ( ) A + ( ) A 证明 : 用数学归纳法 A A I A ILI A 是任意有限集合, 则 3 A U A UL A = A + ( ) A + ( ) A I Ak ( ) A I A ILI A < j 则 < j< k A = 3 + ( ) A I Ak < j < j< k 5/8 6/8 例 3-8: 某软件公司的程序员都熟悉 Java 或 VB, 其中熟悉 Java 的共 47 人, 熟悉 VB 的共 35 人, 两者都熟悉的共 3 人, 问该软件公司共有多少程序员? 解 : 设 A,B 分别表示为熟悉 Java 和 VB 的程序员, 则该公式的程序员集合为 A B 由容斥原理得 : A B = A + B - A B = =59. 例 3-9: 计算中心要安排 Pascal,VB,C 三门课程的上机, 三门课程的学生分别有 0 人,98 人,75 人, 同时学 Pascal 和 VB 的有 35 人, 同时学 Pascal 和 C 的有 50 人, 三门都学的有 6 人, 同时学 VB 和 C 的有 9 人, 求一共有多少学生? 7/8 解 : 设 x 是同时学 Pascal 和 VB, 但没有学 C 的学生数, y 是同时学 Pascal 和 C, 但没有学 VB 的学生数, z 是同时学 C 和 VB, 但没有学 Pascal 的学生数, P 是仅学 Pascal 的学生,B 是仅学 VB 的学生,C 是仅学 C 的学生 ; 则 :x+6=35=>x=9, y+6=50=>y=44, z+6=9=>z=3, x+y+6=0-p=>p=3, x+z+6=98-b=>b=50, y+z+6=75-c=>c=, 总计 = =85; 解二 : 用容斥原理 : 总计 = =85 8/8

Microsoft PowerPoint - chapter ppt

Microsoft PowerPoint - chapter ppt 第 3 讲集合的概念与运算 1. 集合的概念 2. 集合之间的关系 3. 集合的运算 4. 文氏图容斥原理 2005-7-5 集合论与图论第 3 讲 1 集合论 (set theory) 十九世纪数学最伟大成就之一集合论体系朴素 (naive) 集合论公理 (axiomatic) 集合论创始人康托 (Cantor) Georg Ferdinand Philip Cantor 1845 ~