离散数学教案集合论—基本概念部分2.ppt

Discrete Mathematics 西南科技大学计算机科学与技术学院第三章第三章 集集 合合 3.3 3.3 集合的基本运算律集合的基本运算律 1Discrete Mathematics 西南科技大学计算机科学与技术学院交换律：交换律：A B=B A，，A B=B A结合律结合律：：(A B) C=A (B C) (A B)  C=A(B  C) 分配律：分配律：A (B C)=(A B) (A C) A (B C)=(A B) (A C)等幂律：等幂律：A A=A，，A A=A 同一律：同一律：A=A，，A U=A 零一律：零一律：A=，，A U=U 2Discrete Mathematics 西南科技大学计算机科学与技术学院补余律：补余律：AA=，，AA=U 吸收律：吸收律：A (A B)=A A (A B)=A 德德.摩根律：摩根律： (A B)= AB  (A B)= AB 双重否定律：双重否定律： ( A)=A A-B=AB 以上定律均可用集合相等的定义或已知运算律以上定律均可用集合相等的定义或已知运算律相互来证明。

相互来证明3Discrete Mathematics 西南科技大学计算机科学与技术学院证明（德摩根律）：证明（德摩根律）： （（A B））= AB(1) x (A B)(2) x A B x A∧∧x B xA∧∧xB xAB  (A B)AB(2)  xAB xA∧∧xB x A∧∧x B x A B x (A B) AB   (A B) 由由(1)(2)得得:  (A B)=  AB 4Discrete Mathematics 西南科技大学计算机科学与技术学院证明吸收律：证明吸收律：A (A B)=A证明：证明：A (A B) =(A) (A B)（同一律）（同一律） =A (B) （分配律）（分配律） =A （零一律）（零一律） =A （同一律）（同一律）5Discrete Mathematics 西南科技大学计算机科学与技术学院集合基本运算律的应用举例集合基本运算律的应用举例例例1. 求证：求证：A-(B C)=(A-B) (A-C)证明：左边证明：左边=A(B C) =A ( BC) （德摩根律）（德摩根律） =AB AC （幂等律、交换律）（幂等律、交换律） =(A-B) (A-C) 故原等式成立，证毕。

故原等式成立，证毕6Discrete Mathematics 西南科技大学计算机科学与技术学院例例2. 已知已知A B=A C，，A B=A C，求证，求证B=C证明：证明：B=B (A B) (吸收律吸收律) =B (A C) (已知代入已知代入) =(B A) (B C) (分配律分配律) =(A C) (B C) (已知代入已知代入) =(A B) C (分配律分配律) =(A C) C (已知代入已知代入) = C (吸收律吸收律) 证毕7Discrete Mathematics 西南科技大学计算机科学与技术学院例例3. 求证：求证：(A B) C=A (B C)的充要条件是的充要条件是 C A。

证明：证明：(充分性充分性) ∵∵ C A A C=A (A B) C=(A C) (B C) (分配律分配律) =A (B C) (已知代入已知代入)(必要性必要性)  x C x (A B) C ∵∵ (A B) C=A (B C)\x A (B C) x A C A 8Discrete Mathematics 西南科技大学计算机科学与技术学院例例4. 试证：试证：(A B)-(A B)=(A-B) (B-A)证明：证明：左边左边=(A B)(A B)=(A B) ( AB) (德摩根律德摩根律)=(AA) (AB) (BA) (BB) (分分配律配律) =(AB) (BA) (互补律互补律)=(A-B) (B-A) 故原等式成立，证毕。

故原等式成立，证毕9Discrete Mathematics 西南科技大学计算机科学与技术学院关于对称差的一些性质关于对称差的一些性质: 交换律：交换律：A B=B A A ⓧⓧ B=B ⓧⓧ A结合律：结合律：(A B) C=A (B C) (AⓧⓧB)ⓧⓧC=A ⓧⓧ(BⓧⓧC)∩对对 的分配律：的分配律：A (B C)=(A B) (A C)∪∪对对ⓧⓧ的分配律：的分配律： A∪∪(B ⓧⓧ C)=(A∪∪B) ⓧⓧ(A∪∪C) 同一律：同一律： A=A 零律：零律： A A= A ⓧⓧ A=UA (A B)=B （（A (A B)=(A A) B=B=B ））10Discrete Mathematics 西南科技大学计算机科学与技术学院关于幂运算，具有以下性质：关于幂运算，具有以下性质： A B ρ(A)  ρ(B) ρ(A) ∪∪ρ(B)  ρ(A∪∪B) ρ(A∩∩B)= ρ(A) ∩∩ρ(B) （留作习题）（留作习题）11Discrete Mathematics 西南科技大学计算机科学与技术学院第三章第三章 集集 合合 3.4 3.4 有限集合的计数有限集合的计数 12Discrete Mathematics 西南科技大学计算机科学与技术学院q通常用通常用|A|来表示有限集合来表示有限集合A中所含元素的个数。

中所含元素的个数集合中所含元素的个数集合中所含元素的个数 ，也称为，也称为基数（势）基数（势）性质：性质：1. 当当A B=时，时，则则 A B = A + B  2.当当A B=时，时， A B =0，， A-B = A  3.当当B A时，时， A B = A ，， A B = B   A-B = A - B  4.  A B = A + B - A B  13Discrete Mathematics 西南科技大学计算机科学与技术学院性质性质4推广：推广： A B C = A + B + C - A B - A C - B C + A B C  一般地成立以下公式：一般地成立以下公式：14Discrete Mathematics 西南科技大学计算机科学与技术学院上述公式也可表示为：上述公式也可表示为：15Discrete Mathematics 西南科技大学计算机科学与技术学院更一般地成立以下公式：更一般地成立以下公式：16Discrete Mathematics 西南科技大学计算机科学与技术学院例例 求求1到到500之间能被之间能被2，，3，，7任一数整除的整数个数。

任一数整除的整数个数解解：：设设1到到500间间分分别别能能被被2，，3，，7整整除除的的整整数数集集合合为为A，，B，，C，则有：，则有： A =[500/2]=250；；  B =[500/3]=166；； C =[500/7]=75；； A B =[500/(2*3)]=83；； A C =[500/(2*7)]=35;  B C =[500/(3*7]]=23；； A B C  =[500/(2*3*7)]=11A B C = A + B + C - A B - B C - A C + A B C =250+166+71-83-35=23+11=357 17Discrete Mathematics 西南科技大学计算机科学与技术学院例例 某班有某班有25个学生，其中个学生，其中14人会打篮球，人会打篮球，12人会人会打排球，打排球，6人会打篮球和排球，人会打篮球和排球，5人会打篮球和网球，人会打篮球和网球，还有还有2人会打这三种球，而人会打这三种球，而6个会打网球的人都会打个会打网球的人都会打另外一种球另外一种球(指篮球或排球指篮球或排球)，求不会打这三种球的，求不会打这三种球的人数。

人数解解 设会打排球、网球、篮球的学生集合分别为设会打排球、网球、篮球的学生集合分别为A，，B和和C，则有，则有 |S|=25；； |A|=12；； |B|=6；； |C|=14；； |A∩C|=6；； |B∩C|=5；； |A∩B∩C|=2；； 现在求现在求| |A∩ B| |: :18Discrete Mathematics 西南科技大学计算机科学与技术学院因为会打网球的人都会打另一种，即篮球或排因为会打网球的人都会打另一种，即篮球或排球，而其中会打篮球的有球，而其中会打篮球的有5 5人，那么另一个人人，那么另一个人肯定会打排球但不会打篮球再加上会打三种肯定会打排球但不会打篮球再加上会打三种球的球的2 2人，共有人，共有3 3人会打排球和网球人会打排球和网球即即|A∩ B|=3|A∩ B|=3于是，于是，有：有：19Discrete Mathematics 西南科技大学计算机科学与技术学院第三章第三章 集集 合合 3.5 3.5 集合的笛卡尔乘积集合的笛卡尔乘积 20Discrete Mathematics 西南科技大学计算机科学与技术学院一、二重组一、二重组（（序偶序偶））定义定义 由两个元素由两个元素x和和y(允许允许x=y)按一定的顺序排按一定的顺序排列成的二元组叫做一个二重组列成的二元组叫做一个二重组(也称也称序偶序偶)，记作，记作。

其中是其中是x称为二重组的称为二重组的第一个分量第一个分量，，y是是它的它的第二个分量第二个分量平面直角坐标系中点的坐标就是平面直角坐标系中点的坐标就是二重组二重组 例如：例如：<1，，-1>，，<-1，，1>，，<1，，1>，， ……都代表都代表坐标系中不同的点坐标系中不同的点 21Discrete Mathematics 西南科技大学计算机科学与技术学院一般说来一般说来二重组二重组具有以下具有以下特点特点：： 1. 二重组中的元素是有次序的当二重组中的元素是有次序的当x≠y时，时，≠2. 两个二重组相等，即两个二重组相等，即=的充分必要的充分必要条件是条件是x=u且且y=v　　22Discrete Mathematics 西南科技大学计算机科学与技术学院定义定义 一个一个n重组（重组（n≥3））是一个是一个二重组二重组，其中第一，其中第一个元素是一个有序个元素是一个有序n-1重组一个有序重组一个有序n重组记作重组记作，即，即 =< ,xn> 例如例如，有序，有序3重组重组 =<,z>。

同样：同样：<,z>=<,w>的充分必要条件是的充分必要条件是= ,z=w即x=u，，y=v，，z=w23Discrete Mathematics 西南科技大学计算机科学与技术学院例如：例如：q 空间直角坐标系中点的坐标都是有序空间直角坐标系中点的坐标都是有序3重组重组q n维空间中点的坐标或维空间中点的坐标或n维向量都是有序维向量都是有序n重组重组24Discrete Mathematics 西南科技大学计算机科学与技术学院二、二、笛卡尔乘积（笛卡尔乘积（叉积叉积））定义定义 设设A，，B为集合，所有以为集合，所有以A中元素为第一元素，中元素为第一元素，B中元素为第二元素所构成中元素为第二元素所构成二重组为元素二重组为元素的集合叫的集合叫做集合做集合A和和B的的笛卡儿乘积笛卡儿乘积（（叉积叉积））记作A×B 表示为表示为 ：：例如，例如， ，， 则，则，不难证明，如果不难证明，如果A中有中有m个元素，个元素，B中有中有n个元素，则个元素，则A×B和和B×A中都有中都有mn个元素 25Discrete Mathematics 西南科技大学计算机科学与技术学院从笛卡儿积的定义和逻辑演算的知识可以看出，若从笛卡儿积的定义和逻辑演算的知识可以看出，若 A×B ，则有，则有x A且且y B。

若若  A×B，，则有则有x A或或y B 笛卡儿积运算具有以下笛卡儿积运算具有以下性质性质：：1.若若A，，B中有一个是空集，则它们的笛卡儿积是空中有一个是空集，则它们的笛卡儿积是空集，即：集，即： ×B= A×=2.当当A≠B，且，且A、、B都不是空集时，有：都不是空集时，有：A×B≠B×A3.当当A、、B、、C都不是空集时，有：都不是空集时，有： 26Discrete Mathematics 西南科技大学计算机科学与技术学院显然：显然：(A×B)×C≠ A×(B×C)，这条性质说明笛，这条性质说明笛卡儿积运算卡儿积运算不满足结合律不满足结合律 4. 笛卡儿积运算对笛卡儿积运算对∪∪或或∩运算满足分配律，即运算满足分配律，即 27Discrete Mathematics 西南科技大学计算机科学与技术学院证明：证明： 设设 是是A×(B∪∪C)的任一元素，那么的任一元素，那么所以，所以，28Discrete Mathematics 西南科技大学计算机科学与技术学院例例1 设设A={1A={1，，2}2}，求，求ρ(A) ×A解解 ρ(A) ×A例例2 2 设设A，，B，，C，，D为任意集合，判断以下等式为任意集合，判断以下等式是否成立，说明为什么？是否成立，说明为什么？（（1 1））（（2 2）） 29Discrete Mathematics 西南科技大学计算机科学与技术学院解解：：(1)(1)成立。

成立因为对因为对任一任一，如果，如果 30Discrete Mathematics 西南科技大学计算机科学与技术学院解解：：(2)(2)不不成立举一反例如下：举一反例如下： 若若B=C=B=C=，则有，则有 31Discrete Mathematics 西南科技大学计算机科学与技术学院三、三、n阶笛卡儿乘积阶笛卡儿乘积 定义定义 设设A1，，A2，，…，，An是集合是集合(n≥2)，它们的，它们的n阶笛卡儿积记作阶笛卡儿积记作A1×A2×…×An ，其中，其中 可见，可见，A1×A2×…×An是是n重组重组构成的集合构成的集合 　当　当A1=A2=…=An=A时，可将它们的时，可将它们的n阶笛卡儿阶笛卡儿积简记为积简记为 32Discrete Mathematics 西南科技大学计算机科学与技术学院例如例如，，A={a,b}，则，则 在后面的在后面的“二元关系二元关系”学习中，将主要利用学习中，将主要利用2阶笛卡儿乘积的概念阶笛卡儿乘积的概念 33Discrete Mathematics 西南科技大学计算机科学与技术学院34。