集合的基本概念和运算PPT课件

华中师范大学计算机科学系，离散数学，第3章集合的基本概念和运算，第3章集合的基本概念和运算，3.1集合的基本概念，3.2集合的基本运算，3.3集合中元素的计数，3.4笛卡儿积，3.1集合的基本概念，集合是不能精确定义的基本数学概念，直观地说，集合是由一些可以相互区别的东西组成的整体。对于给定的集合和事物，应该有可能确定这个特定的事物是否属于这个集合。如果它属于，则称为该集合的元素。集合通常用大写英文字母表示。集合可以用两种方式表示：枚举和谓词。前一种方法是列出集合中的所有元素，用逗号分隔这些元素，并用花括号将它们括起来。例如，是合法表示。谓词符号使用谓词来总结集合中元素的属性。例如，一个集合的元素彼此不同。如果同一个元素在一个集合中出现多次，则应将其视为一个元素。集合的元素也是无序的，元素的排列顺序对集合没有影响。3.1集合的基本概念定义了3.1.1将A和B集合为集合。如果B中的每个元素都是A中的一个元素，那么B被称为A的子集，简称子集。这时，也叫b被a包含，或a包含b。记为ba。内含物的符号表示在3.1.2中定义。设A和B。如果Ba和AB相等，则A和B相等，并记录为A=B。相等的符号化表示为上述定义，表明两个集合相等的充分必要条件是它们具有相同的元素。例如，A=B。3.1集合的基本概念定义3.1.3将A和B集合为集合。如果Ba和BA，则B称为A的适当子集，并表示为Ba。适当子集的符号化被表示为巴巴 B A。如果B不是A的适当子集，它被记录为。例如，0，1是0，1，2的适当子集，但0，3和0，1，2都不是0，1，2的适当子集。定义3.1.4不包含任何元素的集合称为空集。请注意，空集可以象征性地表示为=x|xx定理3.1.1空集是所有集的子集。证明：对于任何集合，子集定义的蕴涵公式都有右边。因为前一个是假的，整个蕴涵公式对所有的X都是真的，因此是真的。3.1集的基本概念，演绎空集是独一无二的。一般来说，集合A和A的子集称为A的平凡子集，包含n个元素的集合简称为n元素集，包含m (mn)个元素的集合称为m元素子集。如何找到n元集的所有子集？例3.1.4A=a，b，c，找出A的所有子集。解决方法：将A的子集从小到大分类：0元子集，即空集；1元子集，即单位集，a、b、 c ；2元子集，a，b，b，c，a，c ；3元子集，a，b，c。一般来说，对于n元素集a，其m(0mn)个元素子集具有，并且不同子集的总数为、3.1集。3.1.5集的基本概念被定义为一个集，由A的所有子集构成的集称为A的幂集，表示为(A)。对于例3.1.4中的集合a，幂集的符号表示为 (a)=x | xa， (a)=、a、b、c、a，b、a，c、b，c。定义3.1.6在一个特定的问题中，如果所涉及的所有集合都是某个集合的子集，那么这个集合就被称为完备集，并被表示为U。完备的工作是相对的，不同的问题有不同的完备工作，即使是同一个问题也可以有不同的完备工作。例如，当研究平面上直线之间的关系时，整个平面(平面上所有点的集合)可以作为一个完整的集合，整个空间(空间上所有点的集合)也可以作为一个完整的集合。一般来说，完整的集合更小，问题的描述和处理也更简单。第三章集合的基本概念和运算3.1集合的基本概念3.2集合的基本运算3.3集合中元素的计数3.4笛卡儿积，集合的基本运算3.2，集合的运算3.2.1 3.2 2集合运算法则，集合的运算3.2.1，给定集合A和B，通过集合的并交8745，相对补，绝对补和对称差运算可以生成一个新的集合。定义3.2.1设A和B是集合，A和B的并A B，交集A B，以及B到A的相对补A-B定义如下：显然AB由A或B中的元素组成，AB由A和B中的公共元素组成，而A-B由属于A但不属于B的元素组成。3.2.1集合运算，并定义3.2.2将U集合为完备集，将Au集合为A的相对补，将U集合为A的绝对补，表示为A.定义3.2.3如果设置了A和B，那么A和B之间的对称差就是A和B之间的对称差。还有一个等价的定义，即。示例3.2.1A=0，1，2，B=2，3，计算或集合与相关操作之间的相互关系可以用文丘里图进行图形化描述。3.2集、3.2.1集、3.2.2集、3.2.2集、3.2.2集的基本运算，任何代数运算都要遵循一定的规律，集合运算也不例外。以下是集合运算的主要计算法则，其中A、B和C代表任何集合。幂等律、结合律、交换律、分配律、同态零律、排除中间律、吸收律、双负律、摩根律、和、和、和、和、和、和、和、和、和、和、和、和给出了三个等价定义，为证明两个集合之间的包含关系提供了一种新方法，也可用于简化集合公式。第三章集合的基本概念和运算；3.1集的基本操作；3.2集的基本运算；3.4 3.3集中元素的笛卡尔乘积；3 . 3 . 1 3.3组中元素的计数；3.3.1包含-排除原则；3.3.2包含-排除原则；3.3.1包含-排除原则；集合A包含N个元素；可以说集合A的基数是N，表示为CARDA=N。所谓的基数是指集合中包含的元素数量。如果集合a的基数是n，它也可以写成| a |=n。显然，空集合的基数是0，也就是|=0。定义3.3.1被设置为一组。如果有一个自然数n(0也是一个自然数)，那么|A|=cardA=n，那么A称为有限集合，否则，A称为无限集合。例3.3.1有100名程序员，其中47人熟悉C语言，35人熟悉C语言，23人精通两种语言。有多少人不熟悉这两种语言？解决方案：如果A和B分别代表一组熟悉C和C语言的程序员，那么问题可以用图3.3.1中的文丘里图来表示。如果在AB区域中填充了熟悉这两种语言的相应人数23，则不难得出A-B和B-A的人数是| A-B |=| A |-| AB |=47-23=24 | B-A |=| B |-| AB |=35-23=12，从而得到| AB |=24 23 12=59，所以| (AB)根据包含和排除原理，设S是一个有限集合，P1和P2分别表示两个性质，对于S中的任何元素X，它只能处于以下四种情况之一：(1)它只具有性质P1；(二)只有P2财产；(3)它具有P1和P2的两个属性；(4)没有自然。设A1和A2分别代表S中具有P1和P2性质的元素集。为了简化表达式，对任何集合B使用B而不是 b。从维恩图中不难得到下列公式。这是包含和排除原则的简单形式。如果涉及三个性质，则包含-排除原理的公式变为、3.3.1包含-排除原理，并且定理3.3.1S中不具有性质P1、p2，定理3.3.1稍微证明了pm。可以推断，在S中具有至少一个属性的元素的数量是、3.3集合、3.3.1包含/排除原则、3.3.2包含/排除原则、3.3.2包含/排除原则和3 . 3 . 4 150名学生的班级中的元素的数量。有80名学生在数学考试中得了90分以上，75名学生在语文考试中得了90分以上，50名学生在两门课程中都得了90分以上。问(1)有多少学生在一门课程中得分超过90？(2)有多少学生在两门课程中都没有得分超过90分？解决方案：整套是一个coll因此，给出了包含和排除原理的下列例子：(2)要求，(3)集合的基本概念和运算，集合的基本概念，集合的基本运算，3.4笛卡儿积，3.4笛卡儿积，3.4.1 3 . 4 . 2笛卡儿积的有序对，3.4.3n阶笛卡儿积，3 . 4 . 1 3 . 4 . 2笛卡儿积的有序对，定义3 . 4 . 1由两个元素X和Y(允许x=y)按一定顺序排列组成的二元组称为有序一般来说，有序对具有以下特征：(1)当xy u x，y u y，x u y时，(2)两个有序对相等的充要条件，即u x，y u，v u是x=u和y=v，这两个特征不为集合x，y所拥有，因为有序对强调x和y的序列，而集合x，y中的x和y例如，3.4.1证明了x=u和y=v的充分必要条件是x=u和y=v。必要性如果u x，y u，v u;那么x x ， x，y= x，y u，v u，u，u，v (1)如果x=u，那么u=x，因为u u = x 。(2)如果x=u，v，那么因为uu，v=x，就有x=u，u=x。因此，总是有x=u和x=u，从x、x，y=u、u，v、x=u x，y=u，v和从x，y=u，v和x=u，y=v可以获得。定义3.4.2有序N元组(n3)是有序对，其中第一个元素是第一个有序n-1元组，有序N元组表示为u x1，x2，xn；即、等。3.4笛卡儿积，3.4.1有序对的笛卡儿积3.4.2 3.4.3阶笛卡儿积，3 . 4 . 2笛卡儿积，定义3 . 4 . 3设A和B为集合，A中的元素是第一个元素，B中的元素是形成有序对的第二个元素。所有这些有序对的集合被称为A和B的笛卡儿积，它被表示为AB。符号化是由笛卡尔乘积的定义和逻辑演算的知识来表示的，如果有和的话。如果是，则有或。根据排列组合的知识，不难证明如果a有m个元素，b有n个元素，那么AB和BA都有mn个元素。例如，如果A和B中有一个空集，那么它们的笛卡儿积就是一个空集，也就是说，(2)如果AB和A和B都不是空集，那么笛卡儿积运算就不满足交换定律。(3)当A、