离散数学 第六章的完整PPT课件

。1.主要内容集所属的基本概念，包括幂集和空集等集合的运算。有限集合计数集合恒等式集的运算包括恒等式的计算法则和证明方法。集合论的第二部分，集合代数的第六章，2，6.1集合的基本概念。1.集合定义集合没有精确的数学定义。由离散个体组成的整体称为集合，这些个体称为集合元素的公共数集合：N，Z，Q，R，C等。分别表示自然数、整数、有理数、实数和复数集合。2.集合表示方法列元素方法-列出集合中的所有元素，所有元素用逗号分隔，并用花括号括起来谓词表示方法-使用谓词来总结集合中元素的性质示例：列元素方法自然数集合n=0，1，2，3，谓词表示方法S=x | xrx21=0，3。元素和集合。1.集合中元素的性质是无序的：元素的排列顺序是相互独立的。为了确定性，集合中的每个元素只计算一次：对于任何元素和集合，都可以确定这个元素是否是任意的。集合中的元素也可以是集合2。元素和集合之间的关系是相互从属的。或者3。例如，集合的树层次结构是集合A=a，b，c，d，d，规定：AA，4，集与集，集与集之间的关系：=，定义6.1集A，B为集，如果B中的每个元素都是A中的元素，则B是A的子集，称为子集。这时，也有人说b被a包含，或者a包含b，这被记录为ba。如果b不包含在a中，则记录为ba。符号化为：bax (xbax) bax (xbax)如NZQRC，但zn。显然，任何集合a都有aa。定义6.2将a和b集合为集合。如果ab和ba相等，A和B相等，a=b。如果A和B不相等，则记录为a b。符号为：a=巴巴定义6.3集A和B为集。如果BA和BA，则B称为A的适当子集，并表示为Ba。如果B不是A的适当子集，它被记录为BA。象征为：BABABA，如NZQRC，但nn。注意：求和是一个不同层次的问题，如A=a，a和a。定义6.4空集：没有任何元素的符号集合表示为：=X | X X示例：X | XR X2 1=0定理6.1空集是任何集合的子集。这个证明是对任何集合a，ax (xxa) 1(不变真理命题)的推论的唯一证明：假设有空集1和2，定理6.1有：12和21根据集合等式的定义，有1=2，所以结论是它是唯一的。嘿。6，空集，完备集和幂集，包含n个元素的集合简称为n元素集，包含m(mn)个元素的子集称为m元素子集。如何找到n元集的所有子集？示例6.1A=1，2，3，分类子集：解决方案：0元子集，即空集，只有一个：1元子集，即单位集：1、2、 3 ；2元子集：1，2，1，3，2，3 ；3元的子集：1，2，3。7、空集、全集和幂集，定义6.5幂集：集合A为集合，调用集合A的所有子集构成的集合A的幂集，并将其记录为P(A)(或PA，2A)。符号化为：p (a)=x | xa实例：p ()=，p ()=，计数：如果|A|=n，则|P(A)|=2n，定义6.6个完备集e:包含所有集的集完备集是相对的：与问题相关，没有绝对完备集。6.7集A和B为集合，A和B的并集B，交集A ; B，以及B与a-b的相对补集的定义如下：和ab=x | xaxb交集ab=x | xaxb相对补集ab=x | xaxb例如：A=a，B，c，B=a， d ab=a，b，c，ab=a，Ab=b，c，b-a=，BC=如果两个集合的交集为，则这两个集合称为不相交。9，6.2集运算，定义6.8集A，B为集，A和B对称差集ab定义为：对称差ab=(ab) (ba)另一个定义是：ab=(ab) (ab)例如：A=a，B，c，B=b，d，Ab=a，c，d定义6.9给定完整集E后，AE的绝对补，a a定义如下：绝对补A=E= A= x | xE44，10，Venn图，集合运算的表示，a，b，a，b，a，a，b，a，e，ab，ab，ab，ab， a，11，几个解释，和交叉运算可以扩展到有限集合。也就是a1a2.an= x | xa1xa2.xan a1a2.an= x | xa1xa2.xan abab=ab=ab=a，12，广义运算，1。集合6.10的广义相交定义将a设置为集合，并且a的元素集合被称为a的广义并，表示为 a。符号化表示是广义并a=x | z (zaxz)定义6.11将a设置为非空集合，并且由a的所有元素的公共元素形成的集合被称为a的广义交， 表示为A。符号化为广义交集a=x | z (zaxz)示例6.2设置a=a，b，c，a，c，d，a，e，f b=a c=a，c，d然后A=a，b，c，d，e，f， b=a，c=a c，d a=a， b=a符号化表示是广义并a=x | z (zaxz)定义6.11将a设置为非空集合，由a的所有元素的公共元素构成的集合称为a的广义交，表示为a，符号化为广义交a=x | z (zaxz)练习：a=1、1，2、1，2，3，b=a，c=a解：a ，14，广义运算的描述，2。广义运算的性质(1)=，无意义(2)单位集x的广义并和交集都等于x(3)广义运算约简集(括号约简一层)(4)广义运算的计算：一般来说，它可以转化为主运算a=a1，a2，an=a1a2.ana=a1，a2，安=a1a2.an3。引入广义运算的意义可以表示为无数集合的并运算和交运算，例如x | xr=r，其中r代表一组实数。嘿。15中，操作的优先级规定了一种类型的操作：广义并集、广义交集、幂集、绝对补运算按从右向左的顺序(右组合)执行。两种类型的操作：并集、交集、相对补运算，对称差的优先级由括号决定：一种类型的操作优先于第二种类型的操作。例A=a，a，b，计算a (aa)。解决方案：a (aa)=a，b (a，b a)=(ab) (ab) a)=(ab) (ba)=b，16，例6.5集a=a，a，b计算 a， a和 a a a a- a .解： a=a，b a= a a=aba=aba=aba=aba=aa在书的第97页，第8项，第(4)项，第9项，第(1)、(3)和(5)项，第98项，第18项，第(1)和第(3)项，第18项，第18项，有限集合元素的数量，1。维恩图方法2。集合S包含排除原理定理6.2，集合S定义n个性质，其中具有项I性质的元素构成子集Ai，则集合中不具有任何性质的元素的数目为，并推导出集合S中至少具有一个性质的元素的数目为。19岁。例如，例6.5，找出1到1000(包括1到1000)之间有多少个数字不能被5和6或8整除。解决方案1:Venn图定义了以下集合：s=x | xz1x1000 a=x | xsx可被5整除 b=x | xsx可被6整除 c=x | xsx可被8整除绘制Venn图并填写相应的数字，以获得n=1000-(200 100 33 67)=600，方法二| S |=1000 | A |=1000/5=200，| B |=1000/6=166，| C |=1000/8=125 | AB |=1000/LCM (5，6)=1000/33=33 | AC |=1000/LCM (5，8)=1000/40=25 | BC |=1000/LCM (6，8)=10，21，6.3设置身份。下列等式给出了集合运算的主要计算法则，其中A，B，C代表任何集合。幂等定律a a=aa a=关联定律(ab)c=ad；(b c) (a b) c=a c (b c)交换定律a b=b aa b=b a分配定律ad；(bc)=(abc(ac)abd相同的恒等式a e=aa e=a零定律a e=ea e=排除中间定律a a=e矛盾定律a a=吸收定律aa；(a b)=aa e (a b)=a de morgan定律a-(bc)=(a-b)a-(bc)=(a-b)c)=(a-b)a(a-c)(bc)= bc例如：aba，abb(6.24)aa 8745；b， bab(6.25)a-ba(6.26)a-b=ab b(6.27)ab=Babab=aa-b=(6.28)ab=ba(6.29)(ab)c=a(BC)(6.30)a=a(6.31)aa=(6.32)ab=ACB=c(6.33)。23，88页书，6.5例集a=a，a，b计算解： a=a，b a= a a=aba=aba=aba=aba=aaaa(a-a)=a只涉及一个运算的计算法则：交换法则，结合法则，幂等法则。25，集合计算法则，2。涉及两种不同运算的计算定律：分配定律、吸收定律。26，集合计算法则，3。涉及补运算的计算法则：德摩根法则，双重否定法则。27，集合计算法则，4。包含完整集和空集的计算法则：互补法则、零法则、恒等式法则、否定法则、28，集合证明问题，证明方法：命题算法，命题算法的编写规范等式置换法的证明方法(x和y表示集合公式)(1)证明xy可以取x，xx.方法一证明xy和yx分别为真。方法2采用x，xx.xy注意：当使用方法2的格式时，必须确保推理的每个步骤都是充分和必要的(等效的)，29，集合方程的证明。方法1:命题演算法则1证明a (ab)=a(吸收法则)证明取x，xa(ab)xaxbxa(xaxb)xa，从而得到a (ab)=a，例2证明(6.27)ab=ab取x，xabxaxbxaxbxab从而得到ab=ab，30，平等替换法，方法2:平等替换法3假设交换法，分配法，身份法和零法已经建立。吸收定律的证明a (ab)=A。证明a (ab)=(AE) (ab)(恒等式)=A (EB)(分布定律)=a (be)(交换定律)=AE(零定律)=a(恒等式)。31，包括等价条件的证明，例4证明(6.28) ABAB=BAB=AAB= 证明思路：确定问题中包含的命题：本主题包含命题、确定命题之间的关系(哪些是已知条件，哪些是待证明的结论):本主题中的每个命题都可以作为已知条件，每个命题都是待证明的结论。确定证明顺序： 、 。(4) 依次填写每张证书(证明集合相等或包含)，32，证明ABAB=BAB=AAB= 证书 显然BAB，以下证明ABB被允许带x，XABxAxBxBxBxB因此让ABB.合成上述证书。 AB=A (AB)=A(从可知AB=B，将AB代入B，并结合吸收定律得到证明)。33，证明ABAB=BAB=AAB=AB=A B=(AB) B=A(B B)=A=假设AB不成立，则X (XAXB) X ABAB与条件相矛盾。因此，结论AB成立。事实证明。34，公式(6.28)在简化集公式中的应用，例6.14被简化(abcab)-(ab-c)a)解：由于a ba b c，(a b)-a(来自公式(6.28)=(a b)=(a b)-a(来自公式(6.28)=(a)(交换定律)=B A(恒等式)=b-a(来自等式(6.27)。35，对称差分计算定律的证明(6.33)，例6.15已知ab=AC，证明B=C已知ab=AC，所以有一个(ab)=a (ac) (aa) b=(aa) c(从等式(6.30) b=c(从等式(6.32) b=c(从等式(6.29)B=C(从等式(6.31)。练习：证明下列集合恒等式(1) (ab) c=(AC) b证明