您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 管理学资料 > 离散数学 教案 集合论―基本概念部分(2)
DiscreteMathematics西南科技大学计算机科学与技术学院1第三章集合3.3集合的基本运算律DiscreteMathematics西南科技大学计算机科学与技术学院2交换律:AB=BA,AB=BA结合律:(AB)C=A(BC)(AB)C=A(BC)分配律:A(BC)=(AB)(AC)A(BC)=(AB)(AC)等幂律:AA=A,AA=A同一律:A=A,AU=A零一律:A=,AU=UDiscreteMathematics西南科技大学计算机科学与技术学院3补余律:AA=,AA=U吸收律:A(AB)=AA(AB)=A德.摩根律:(AB)=AB(AB)=AB双重否定律:(A)=AA-B=AB以上定律均可用集合相等的定义或已知运算律相互来证明。DiscreteMathematics西南科技大学计算机科学与技术学院4证明(德摩根律):(AB)=AB(1)x(AB)xABxA∧xBxA∧xBxAB(AB)AB(2)xABxA∧xBxA∧xBxABx(AB)AB(AB)由(1)(2)得:(AB)=ABDiscreteMathematics西南科技大学计算机科学与技术学院5证明吸收律:A(AB)=A证明:A(AB)=(A)(AB)(同一律)=A(B)(分配律)=A(零一律)=A(同一律)DiscreteMathematics西南科技大学计算机科学与技术学院6集合基本运算律的应用举例例1.求证:A-(BC)=(A-B)(A-C)证明:左边=A(BC)=A(BC)(德摩根律)=ABAC(幂等律、交换律)=(A-B)(A-C)故原等式成立,证毕。DiscreteMathematics西南科技大学计算机科学与技术学院7例2.已知AB=AC,AB=AC,求证B=C证明:B=B(AB)(吸收律)=B(AC)(已知代入)=(BA)(BC)(分配律)=(AC)(BC)(已知代入)=(AB)C(分配律)=(AC)C(已知代入)=C(吸收律)证毕。DiscreteMathematics西南科技大学计算机科学与技术学院8例3.求证:(AB)C=A(BC)的充要条件是CA。证明:(充分性)∵CAAC=A(AB)C=(AC)(BC)(分配律)=A(BC)(已知代入)(必要性)xCx(AB)C∵(AB)C=A(BC)xA(BC)xACA。DiscreteMathematics西南科技大学计算机科学与技术学院9例4.试证:(AB)-(AB)=(A-B)(B-A)证明:左边=(AB)(AB)=(AB)(AB)(德摩根律)=(AA)(AB)(BA)(BB)(分配律)=(AB)(BA)(互补律)=(A-B)(B-A)故原等式成立,证毕。DiscreteMathematics西南科技大学计算机科学与技术学院10关于对称差的一些性质:交换律:AB=BAAⓧB=BⓧA结合律:(AB)C=A(BC)(AⓧB)ⓧC=Aⓧ(BⓧC)∩对的分配律:A(BC)=(AB)(AC)∪对ⓧ的分配律:A∪(BⓧC)=(A∪B)ⓧ(A∪C)同一律:A=A零律:AA=AⓧA=UA(AB)=B(A(AB)=(AA)B=B=B)DiscreteMathematics西南科技大学计算机科学与技术学院11关于幂运算,具有以下性质:ABρ(A)ρ(B)ρ(A)∪ρ(B)ρ(A∪B)ρ(A∩B)=ρ(A)∩ρ(B)(留作习题)DiscreteMathematics西南科技大学计算机科学与技术学院12第三章集合3.4有限集合的计数DiscreteMathematics西南科技大学计算机科学与技术学院13通常用|A|来表示有限集合A中所含元素的个数。集合中所含元素的个数,也称为基数(势)。性质:1.当AB=时,则AB=A+B2.当AB=时,AB=0,A-B=A3.当BA时,AB=A,AB=BA-B=A-B4.AB=A+B-ABDiscreteMathematics西南科技大学计算机科学与技术学院14性质4推广:ABC=A+B+C-AB-AC-BC+ABC一般地成立以下公式:DiscreteMathematics西南科技大学计算机科学与技术学院15上述公式也可表示为:DiscreteMathematics西南科技大学计算机科学与技术学院16更一般地成立以下公式:DiscreteMathematics西南科技大学计算机科学与技术学院17例求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;AB=[500/(2*3)]=83;AC=[500/(2*7)]=35;BC=[500/(3*7]]=23;ABC=[500/(2*3*7)]=11ABC=A+B+C-AB-BC-AC+ABC=250+166+71-83-35=23+11=357DiscreteMathematics西南科技大学计算机科学与技术学院18例某班有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|:DiscreteMathematics西南科技大学计算机科学与技术学院19因为会打网球的人都会打另一种,即篮球或排球,而其中会打篮球的有5人,那么另一个人肯定会打排球但不会打篮球。再加上会打三种球的2人,共有3人会打排球和网球。即|A∩B|=3。于是,有:DiscreteMathematics西南科技大学计算机科学与技术学院20第三章集合3.5集合的笛卡尔乘积DiscreteMathematics西南科技大学计算机科学与技术学院21一、二重组(序偶)定义由两个元素x和y(允许x=y)按一定的顺序排列成的二元组叫做一个二重组(也称序偶),记作x,y。其中是x称为二重组的第一个分量,y是它的第二个分量。平面直角坐标系中点的坐标就是二重组。例如:1,-1,-1,1,1,1,…都代表坐标系中不同的点。DiscreteMathematics西南科技大学计算机科学与技术学院22一般说来二重组具有以下特点:1.二重组中的元素是有次序的。当x≠y时,x,y≠y,x。2.两个二重组相等,即x,y=u,v的充分必要条件是x=u且y=v。DiscreteMathematics西南科技大学计算机科学与技术学院23定义一个n重组(n≥3)是一个二重组,其中第一个元素是一个有序n-1重组。一个有序n重组记作x1,x2,…,xn,即x1,x2,…,xn=x1,x2,…,xn-1,xn。例如,有序3重组x,y,z=x,y,z。同样:x,y,z=u,v,w的充分必要条件是x,y=u,v,z=w。即x=u,y=v,z=w。DiscreteMathematics西南科技大学计算机科学与技术学院24例如:空间直角坐标系中点的坐标都是有序3重组。n维空间中点的坐标或n维向量都是有序n重组。DiscreteMathematics西南科技大学计算机科学与技术学院25二、笛卡尔乘积(叉积)定义设A,B为集合,所有以A中元素为第一元素,B中元素为第二元素所构成二重组为元素的集合叫做集合A和B的笛卡儿乘积(叉积)。记作A×B。表示为:例如,,则,不难证明,如果A中有m个元素,B中有n个元素,则A×B和B×A中都有mn个元素。DiscreteMathematics西南科技大学计算机科学与技术学院26从笛卡儿积的定义和逻辑演算的知识可以看出,若x,yA×B,则有xA且yB。若x,yA×B,则有xA或yB。笛卡儿积运算具有以下性质:1.若A,B中有一个是空集,则它们的笛卡儿积是空集,即:×B=A×=2.当A≠B,且A、B都不是空集时,有:A×B≠B×A。3.当A、B、C都不是空集时,有:DiscreteMathematics西南科技大学计算机科学与技术学院27显然:(A×B)×C≠A×(B×C),这条性质说明笛卡儿积运算不满足结合律。4.笛卡儿积运算对∪或∩运算满足分配律,即DiscreteMathematics西南科技大学计算机科学与技术学院28证明:设x,y是A×(B∪C)的任一元素,那么所以,DiscreteMathematics西南科技大学计算机科学与技术学院29例1设A={1,2},求ρ(A)×A解ρ(A)×A例2设A,B,C,D为任意集合,判断以下等式是否成立,说明为什么?(1)(2)DiscreteMathematics西南科技大学计算机科学与技术学院30解:(1)成立。因为对任一x,y,如果DiscreteMathematics西南科技大学计算机科学与技术学院31解:(2)不成立。举一反例如下:若B=C=,则有DiscreteMathematics西南科技大学计算机科学与技术学院32三、n阶笛卡儿乘积定义设A1,A2,…,An是集合(n≥2),它们的n阶笛卡儿积记作A1×A2×…×An,其中可见,A1×A2×…×An是n重组构成的集合。当A1=A2=…=An=A时,可将它们的n阶笛卡儿积简记为。DiscreteMathematics西南科技大学计算机科学与技术学院33例如,A={a,b},则在后面的“二元关系”学习中,将主要利用2阶笛卡儿乘积的概念。DiscreteMathematics西南科技大学计算机科学与技术学院34
本文标题:离散数学 教案 集合论―基本概念部分(2)
链接地址:https://www.777doc.com/doc-3164227 .html