离散数学第2章集合

1、(discrete mathematics),(discrete mathematics) 计算机科学与工程系 tianjin university of technology department of computer science ,用小写字母a, b, c, 代表元素。,1)如果a是集合a的一个元素,则记为,aa,读做“a属于a”,或 “a在集合a中”。,2)如果a不是集合a的一个元素,则记为,读做“a不属于a”,或 “a不在集合a中”。,任一元素, 对某一集合而言,或属于该集合,或不属于该集合,二者必居其一,且只居其一。,注：,二、集合的表示法,1、符号表示法,绝不容许界限不分明或

2、含糊不清的情况存在。,注：,离散数学中，只讨论界限清楚、无二义性的描述，,不清晰的对象构成的集合,属于模糊论的研究范畴。,著名理发师问题就属于模糊论的研究范畴。,二、集合的表示法,2、描述集合中元素的方法 1) 列举法 a、全部列举法：,以任意顺序写出集合的所有元素,隔开，,元素间用逗号,并将其放在花括号内。,例如“所有小于5的正整数”，,这个集合的元素为,1, 2, 3, 4,再没有别的元素了。,如果把这个集合命名为a,a=1, 2, 3, 4,就可记为,二、集合的表示法,2、描述集合中元素的方法 1) 列举法 b、部分列举法：,列举集合的部分元素，,素,其他元素可从列举的元,用省略号代替。

3、,例如a表示“全体小写英文字母”的集合，,a=a, b, , y, z,则,归纳出来 ，,列举法仅适用于描述元素个数有限的集合,注：,或,元素具有明显排列规律的集合。,二、集合的表示法,2、描述集合中元素的方法 2) 描述法,把集合元素的共同属性描述出来。,集合中元素的属性。,p(x)表示任何谓词，,则,a= x | p(x) ,即用谓词概括,表示所有使谓词p(x)成立的元素x所组成的集合。,例：x | x2-3x+2=0、,x | x=2n-1nn,如果p(a)为真，,则aa，,否则,(谓词表示法),集合的元素,集合的元素必须满足的条件,二、集合的表示法,1、有些集合可以用两种方法表示，,注

4、：,但是有些,集合不可以用列元素法表示，,如实数集合。,2、集合的元素是彼此不同的，,如果同一个元,素在集合中多次出现,应该认为是一个元素。,如:3,4,4,4,5、,3,4,5、,5,4,3,是同一个集合。,3、集合的元素是无序的。,4、集合的元素可以是一个集合，,但不允许以,集合自身为其元素。,如:s=a,b,s=a,b,s,as，,a，,三、元素和集合之间的关系,元素和集合之间的关系,是隶属关系，,即属于,或不属于，,属于记作，,不属于记作。,例如：a=1，1，2，3，3,1,1，2,3,a，,a，,3,a，,2,3,a，,a。,可以用一种树形图表示 集合与元素的隶属关系。,a,2,1，

5、2，,ab,( ),四、集合间的包含关系,1、子集,如果集合a中每个元素,都是集合b中的元素，,则称a是b的,或a包含于b，,子集，,或者b包含a，,记作ab,如果a不是b的子集，,或 ba。,ab,(x),x,a,x,b,则在a中至少有一个元素,不属于b时，,称b不包含a，,记作,或 ba。,注：,1) aa，,2) ab，,bc，,则ac。,b,( ),四、集合间的包含关系,2、集合相等 1)定义,两个集合相等,当且仅当,它们有相同的元素。,若a和b相等，,记作,a=b,(x),x,a,x,(外延性原理),a=b。,两个集合不相等，,记作a b。,四、集合间的包含关系,2、集合相等 2)判

6、断,a与b互为,子集。,定理 若a和b相等,当且仅当,ab,且,ba。,即,a,( ),( ),四、集合间的包含关系,3、真子集,如果集合a中每个元素,都属于集合b，,但b中,不属于a，,则称a是b的,记作a b,或 ba。,ab,(x),x,a,x,b,至少有一个元素,真子集。,(x),x,b,x,ab,a b,例 a=a，b,b=a，b,不是,的 子集。,（真）,四、集合间的包含关系,3、真子集,可以用文氏图了表示集合间的包含关系。,文氏(venn) 图是一种利用平面上的点构成的 图形来形象展示集合的一种方法。,集合用矩形、园面,如果ab，,或一封闭曲线来表示。,则表示a的圆面,一般完全落

7、在,表示b,的圆面内。,a,b,b,a,ab,四、集合间的包含关系,4、隶属和包含关系的区别,例 a=a，a，b=a,ba，,ba，,b是a的元素，,b的元素a,是a的元素，,b是a的子集。,隶属是,元素,和,集合,的关系，,包含是,集合,和,集合,的关系，,某些集合可以同时成立这两种关系。,是个体与整体的关系，,是部分与整体的关系。,五、特殊集合,1、空集 定义,不含任何元素的集合,空集，,称为,记作,。,例 两条平行线交点的集合,为。,例 x| x 0 x 0 x r,=。,注：,1) 与 的区别。,是集合，没有元素,有1个元素的集合,2) ，, ,五、特殊集合,1、空集 定理,空集是任一

8、集合a的子集，,即 a。,下列命题是否为真。,练习,1); 2) ; 3) ; 4) 。,五、特殊集合,1、空集 推理,空集是唯一的。,设1，2是两个空集,则1 2，,且2 1，,得1= 2，,所以空集是唯一的。,证明：,证明唯一性一般采用反证法,(绝对唯一),证毕。,五、特殊集合,1、空集,2)证明一个集合是空集，或证明集合的唯一性，,常采用反证方法，,即假设该集合不是空集，,或不唯一，,导致与已知条件的矛盾或导致唯一。,注：,1)任何非空集合a，,至少有 子集：,两个,、,和a。,只有 子集,一个,。,五、特殊集合,2、全集 定义,在一定范围内，如果所有集合都是某一集合的子集，,则称此集合

9、为,全集,记作,u。,注：,1) 全集是相对的，不同的问题有不同的全集，,即使是同一个问题也可以取不同的全集。,2) 一般地说，全集取得小一些，问题的描述和 处理会简单些。,3) 全集u 用一个矩形的内部表示，,u,五、特殊集合,3、幂集 定义,由集合a的所有子集为元素所组成的集合,称为a的,幂集,记作,注：,1) 幂集的元素都是,集合。,或p(a),或2 a。,2) 任一集合的幂集,都非空。,3) 在 a 的所有子集中，,a,和,又叫平凡子集。,(a), , , 、 ,a, ,五、特殊集合,3、幂集 例 的幂集：, ,=,a=a的幂集：,=, 、 、 、 ,a, ,a=a，b的幂集：,=,b

10、,a、b,有 个元素,1,有 个元素,2,有 个元素,4,20,21,22,(a),五、特殊集合,3、幂集 一般地，,集合a=a1、 a2、 an，,则,有 个元素。,2n,它的m (0 m n)元子集有 个，,不同的子集共有,+,=(1+1)n,=2n个。,a= x| ，,理发师问题,在一个很僻静的孤岛上，住着一些人家，岛上只 有一位理发师，该理发师专给那些并且只给那些自己 不刮脸的人刮脸。那么，谁给这位理发师刮脸？,解：,设,不给自己刮脸的人,x 是,b是这位理发师。,1) 若ba，,则b是不给自己刮脸的人，,而由题意，,b只给集合a中的人刮脸。,b 要给b 刮脸，,即b a。,理发师问题

11、,在一个很僻静的孤岛上，住着一些人家，岛上只 有一位理发师，该理发师专给那些并且只给那些自己 不刮脸的人刮脸。那么，谁给这位理发师刮脸？,解：,则b是要给自己刮脸的人，,而由题意，,理发师只给自己不刮脸的人刮脸。,b 是不给自己 刮脸的人，,即ba。,无论1) 和2) ，,都有,ba,同时成立。,这种情况称为罗索悖论，,是模糊论的范畴。,第二节 集合的运算,一 集合的交,二 集合的并,三 集合的补,四 集合的对称差,五 集合恒等式,六 小结,一、集合的交,1、定义 2、文氏图,任意两个集合a和b，,由a和b的,所有共同元素,组成的集合，,称为a和b的,交集，,记为,ab。,ab= x | xa

12、 xb,即,(intersection),ab,a,b,一、集合的交,如果两个集合没有任何共同的元素，,(intersection),例如，a=a,b,c,e,f ，b=b,e,f, r, s，c=a,t,u,v,则,ab=,b,e,f ,ac=,a,bc=,则称它们是,不相交,集合。,e,a,b,一、集合的交,三个或更多的集合的交集运算：,(intersection),abc =,x |,xa, xb, xc,一、集合的交,3、性质,aa,1)幂等律,(intersection),=a,a,2)零律,=,ae,3)同一律,=a,ab,4)交换律,=ba,a(bc),5)结合律,=(ab)c,

13、( ),b,一、集合的交,3、性质,(intersection),若ab，,6),则ac,bc。,反之,不然。,证：,ab,(x),x,a,x,分析：,若xac，,即,xa,xc,ab, xa,xb,则,xb,xc,xbc。,反之，,取c= ，,a=a，,b=b，,则,ac,=,bc,=,证毕,一、集合的交,3、性质,(intersection),ab,7),a,ab,b,（集合越交,越小）,注：,集合运算的规律和命题演算的某些规律是一致的，所以命题演算的方法是证明集合恒等式的基本方法。,二、集合的并,1、定义 2、文氏图,任意两个集合a和b，,由属于a,或属于b,组成的集合，,称为a和b的,

14、并集，,记为,ab。,ab=x | xa xb,即,(union),的元素,a,b,二、集合的并,三个或更多的集合的并集运算：,(union),e,a,b,abc =,x |,xa,c, xb, xc,二、集合的并,3、性质,aa,1)幂等律,(union),=a,au,2)零律,=u,a,3)同一律,=a,ab,4)交换律,=ba,a(bc),5)结合律,=(ab)c,二、集合的并,3、性质 ，,(union),若ab，,6),则ac,bd。,反之,不然。,若xac，,即,xa,xc,cd，,1)若xa，,则xb，,xbd，,2)若xc，,则xd，,xbd，,始终有xbd。,反之，,取c=d

15、=e，,a=a，,b=b，,则,ac,e=,bd,=e,证：,证毕。,二、集合的并,3、性质,(union),ab，,7),a,（集合越并,越大）,ab,b,xb,( ) ,xb,xa,( ),( ),二、集合的并,4、和的关系,(union),定理,对任意集合a、b和c有:,1) a(bc)=(ab)(ac) ;,2) a(bc)=(ab)(ac)。,即对可以分配,对可以分配。,1) a(bc),= x |,xa,xc,= x |,xa,xc,=(ab),(ac),= x |,xa,xb,xa,xc, x |,分配律,分配律,证：,xb,( ),xa,二、集合的并,4、和的关系,(union

16、),定理,对任意集合a、b有:,1) a(ab)=a,2) a(ab)=a,证一：,1) a(ab),= x |,xa,= x |,xa,=a,吸收律,吸收律,命题逻辑中的吸收律,二、集合的并,4、和的关系吸收律,(union),定理,对任意集合a、b有:,ab,ab=b,或,ab=a。,当且仅当,ab，,bb，,ab,bb,=b,由性质7),b,ab,ab,=b,反之，,由性质7),a,ab,ab=b,ab,证：,证毕。,三、集合的补,1、定义 2、文氏图,任意两个集合a和b，,由属于a,但不属于b,组成的集合，,称为b 对于a的,补集,记为,ab。,ab=x | xa xb,即,(rela

17、tive complement),所有元素,或相对,的,补,或a和b的差。,=x | xa ( xb),b,a,三、集合的补,3、绝对补集,全集u 和集合a的差集,称为a的,绝对补,记为,u a,a =,即,(relative complement),或a的余集,或a的补集。,=x | xu xa,a,或a,u a,xa,xa,(absolute complement).,三、集合的补,4、性质,(relative complement),(a),1)双重否定律,=a,u,2),=,3),=u,aa,4)排中律,=u,aa,5)矛盾律,=,三、集合的补,4、性质,(relative compl

18、ement),(1)(ab),6)德摩根律,= ab,(2)(ab),= ab,(ab),=x | xu, (xab ),=x | xu, (xa,=x | xu, (xa), ( xb ),=x | (xu, (xa), ( xb ),(xu,= a,b,xb ),证: (1), a,( ), b,( ),三、集合的补,5、定理：,(relative complement),2),利用(3)的结论。,a-(ab),= a,(a b),= a, a,(3)的结论,德摩根律,= a,a, b,( ),= a-b,1) a-b,= ab,2) a-b,= a-(ab),分配律,三、集合的补,5、定

19、理,(relative complement),4) a(b - c)=(ab) - (ac),三、集合的补,5、定理,(relative complement),4) a)ab b a,b)ab (b-a)a =b,证：a) ,若xa,则必有xb，,因此 xb，,必有xa，,即 xb,xa, b a,ab,由上述证明可知：,(a), b a,(b),a=,=b,ab b a,四、集合的对称差,1、定义,(symmetric difference),设a、b 是两个集合，,其元素,但,集合 a 和 b 的对称差(环和）是,集合，,记作ab,或属于 a，,或属于b,不能既属于a,又属于 b，,即

20、：,a b = (a - b)(b - a),例如 a = a, b, c , b = b, d ,则ab,=,a,c,d ,=x|(xaxb)(xbxa),四、集合的对称差,2、 文氏图,(symmetric difference),四、集合的对称差,3、 性质,(symmetric difference),1)交换律,2)同一律,3)零律,ab=,4),ab,= ba,a,= a,aa,= , b),(a,(a,b),四、集合的对称差,3、 性质,(symmetric difference),(ab)c=a(bc),5)结合律,定义 2.2-6a、b两集合的环积记为a b，是集合。,定理

21、2.2-12 (1) =a b，(2) a b=b a，(3) a a=u。,定理2.2-13,定理 2.2-14,例1 已知abac，是否必须bc？,解：,是。,ab =ac，,a(ab),=a(ac),(aa)b,= (aa) c,b,=,c,b= c。,例2 已知ab=ac，是否必须b=c？,解：,否。,例：,设a=1、2， b=1， c=2,例3 已知ab=ac，是否必须b=c？ 解： 例：,设a=1， b=1、2， c=1、3,否。,2-5 集合的笛卡尔积,1、序偶(有序2元组)：两个具有固定次序的客体组成一个序偶(有序2元组)，记作，其中x是它的第一元素，y是它的第二元素。,一、有序n元组,例：平面直角坐标系中的一个点的坐标就构成为一个有序序偶，我们可用表示。 注：序偶是讲究次序的。 例和表示平面上两个不同的点，这与集合不同，1，3和3，1是两个相等的集合。 2、定义：两个序偶相等，=，当且仅当x=u且y=v。,一、有序n元组,3、有序元组：是一个序偶，其第一元素本身也是一个序偶，表示为，z或。 4、有序n元组：有序n元组也是一个序偶，其第一元素是一个n-1元组。 ，xn，通常简记为：，其中xi称作它的第i坐标，i=1，2，n。 =的充要条