离散数学第2章集合

离散数学(DiscreteMathematics)离散数学(DiscreteMathematics)计算机科学与工程系TianjinUniversityofTechnologyDepartmentofComputerScience&Engineering魏雪丽离散数学(DiscreteMathematics)计算机科学与工程系TianjinUniversityofTechnologyDepartmentofComputerScience&Engineering魏雪丽第二章集合Sets

本章首先采用朴素集合论的方法，介绍有关集合的一些基本知识，内容显得较为直观，学起来易于接受。但集合及其相关的概念是本门课程后面各章内容的基础，同学们务必熟练的掌握。第一节集合的概念和表示法一集合的概念二集合的表示法

三元素和集合之间的关系四集合间的包含关系五特殊集合六小结一、集合的基本概念1、集合的定义具有某种共同属性的事物的全体称为例如：集合。计算机网络是计算机之间以信息传输为主要目的而连接起来的计算机系统的集合。计算机内存的全体单元构成一集合。一、集合的基本概念2、集合的元素1、集合的元素表示的事物可以是具体的，注：也可以是抽象的。2、集合的元素是任意的，但必须是确定的和可以区分的。集合里含有的对象或客体称为集合的元素。一、集合的基本概念3、集合的分类1)有限集合集合的元素个数是有限的。2)无限集合集合的元素个数是无限的。二、集合的表示法1、符号表示法通常用大写字母A,B,C,…代表集合;用小写字母a,b,c,…代表元素。1)如果a是集合A的一个元素,则记为a∈A,读做“a属于A”,或“a在集合A中”。2)如果a不是集合A的一个元素,则记为读做“a不属于A”,或“a不在集合A中”。a∈A,任一元素,对某一集合而言,或属于该集合,或不属于该集合,二者必居其一,且只居其一。注：二、集合的表示法1、符号表示法绝不容许界限不分明或含糊不清的情况存在。注：离散数学中，只讨论界限清楚、无二义性的描述，不清晰的对象构成的集合属于模糊论的研究范畴。著名理发师问题就属于模糊论的研究范畴。二、集合的表示法2、描述集合中元素的方法

1)列举法

a、全部列举法：以任意顺序写出集合的所有元素,隔开，元素间用逗号并将其放在花括号内。例如“所有小于5的正整数”，这个集合的元素为1,2,3,4,再没有别的元素了。如果把这个集合命名为A,A={1,2,3,4}就可记为二、集合的表示法2、描述集合中元素的方法

1)列举法

b、部分列举法：列举集合的部分元素，素其他元素可从列举的元用省略号代替。例如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-1∧n∈N}如果P(a)为真，则a∈A，否则a∈A,(谓词表示法)集合的元素集合的元素必须满足的条件二、集合的表示法1、有些集合可以用两种方法表示，注：但是有些集合不可以用列元素法表示，如实数集合。2、集合的元素是彼此不同的，如果同一个元素在集合中多次出现应该认为是一个元素。如:{3,4,4,4,5}、{3,4,5}、{5,4,3}是同一个集合。3、集合的元素是无序的。4、集合的元素可以是一个集合，但不允许以集合自身为其元素。如:S={a,{b}},S={a,b,S},a∈S，b∈S,∈A，三、元素和集合之间的关系元素和集合之间的关系,是隶属关系，即属于或不属于，属于记作∈，不属于记作

。例如：A={1，{1，2}，3，{{3}}}1{1，2}3∈A，∈A，{{3}}∈A，2{3}

A，

A。可以用一种树形图表示集合与元素的隶属关系。A1{1,2}3{{3}}12{3}32∈{1，2}，A⊆B

()四、集合间的包含关系1、子集如果集合A中每个元素都是集合B中的元素，则称A是B的或A包含于B，子集，或者B包含A，记作A⊆B如果A不是B的子集，或B⊇A。A⊆B

(x)

x

∈A→x

∈B则在A中至少有一个元素不属于B时，称B不包含A，记作或B⊇A。注：1)A⊆A，2)A⊆B，B⊆C，则A⊆C。B()四、集合间的包含关系2、集合相等1)定义两个集合相等当且仅当它们有相同的元素。若A和B相等，记作A=B

(x)

x

∈Ax

∈(外延性原理)

A=B。两个集合不相等，记作A

B。四、集合间的包含关系2、集合相等2)判断A与B互为子集。定理若A和B相等当且仅当A⊆B且B⊆A。即A()∈()四、集合间的包含关系3、真子集如果集合A中每个元素都属于集合B，但B中不属于A，则称A是B的记作A⊂

B或B⊃A。A⊂B

(x)

x

∈A→x

∈B至少有一个元素真子集。∧

(

x)x

∈B∧x

A⊆B∧A

B例A={a，b}B={a，{b}}不是的子集。（真）四、集合间的包含关系3、真子集可以用文氏图了表示集合间的包含关系。文氏(Venn)图是一种利用平面上的点构成的图形来形象展示集合的一种方法。集合用矩形、园面如果A⊂B，或一封闭曲线来表示。则表示A的圆面一般完全落在表示B的圆面内。ABBAA⊂B四、集合间的包含关系4、隶属和包含关系的区别例A={a，{a}}，B={a}B∈A，B

A，B是A的元素，B的元素a是A的元素，B是A的子集。隶属是元素和集合的关系，包含是集合和集合的关系，某些集合可以同时成立这两种关系。是个体与整体的关系，是部分与整体的关系。五、特殊集合1、空集定义不含任何元素的集合空集，称为记作。例两条平行线交点的集合为。例{x|x>0∧x≤0∧x∈R}=

。注：1)

与{}的区别。是集合，没有元素有1个元素的集合2){

}，

{

}

∈五、特殊集合1、空集

定理空集

是任一集合A的子集，即⊆A。下列命题是否为真。练习

1)⊆;2)

∈

;3)

⊆{};4)

∈{}。√√√五、特殊集合1、空集

推理空集

是唯一的。设

1，

2是两个空集,则

1

2，且2

1，得

1=

2，所以空集是唯一的。证明：证明唯一性一般采用反证法(绝对唯一)证毕。五、特殊集合1、空集

2)证明一个集合是空集，或证明集合的唯一性，常采用反证方法，即假设该集合不是空集，或不唯一，导致与已知条件的矛盾或导致唯一。注：1)任何非空集合A，至少有子集：两个、和A。

只有子集一个。五、特殊集合2、全集

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

(A){}{}{、}a{}五、特殊集合3、幂集例的幂集：

{}=A={a}的幂集：

={、、、}a{}A={a，b}的幂集：

=ba、b有个元素1有个元素2有个元素4202122

(A)五、特殊集合3、幂集

一般地，集合A={a1、a2、…、an}，则有个元素。2n它的m(0≤m≤n)元子集有个，不同的子集共有+…+=(1+1)n=2n个。A={x|}，理发师问题在一个很僻静的孤岛上，住着一些人家，岛上只有一位理发师，该理发师专给那些并且只给那些自己不刮脸的人刮脸。那么，谁给这位理发师刮脸？解：设不给自己刮脸的人x是b是这位理发师。1)若b∈A，则b是不给自己刮脸的人，而由题意，b只给集合A中的人刮脸。∴b要给b刮脸，即bA。∈∈2)若bA，理发师问题在一个很僻静的孤岛上，住着一些人家，岛上只有一位理发师，该理发师专给那些并且只给那些自己不刮脸的人刮脸。那么，谁给这位理发师刮脸？解：则b是要给自己刮脸的人，而由题意，理发师只给自己不刮脸的人刮脸。∴b是不给自己刮脸的人，即b∈A。无论1)和2)，都有b∈A∈及bA同时成立。这种情况称为罗索悖论，是模糊论的范畴。返回第二节集合的运算一集合的交二集合的并

三集合的补四集合的对称差五集合恒等式六小结一、集合的交1、定义2、文氏图任意两个集合A和B，由A和B的所有共同元素组成的集合，称为A和B的交集，记为A∩B。A∩B={x|x∈A

x∈B}即(Intersection)A∩BAB一、集合的交如果两个集合没有任何共同的元素，(Intersection)例如，A={a,b,c,e,f}，B={b,e,f,r,s}，C={a,t,u,v},则A∩B={b,e,f}A∩C={a

}B∩C=

则称它们是不相交集合。EAB一、集合的交三个或更多的集合的交集运算：(Intersection)A∩B∩C

={x|x∈A

x∈B

x∈C}一、集合的交3、性质A∩A1)幂等律(Intersection)=AA∩

2)零律=

A∩E3)同一律=AA∩B4)交换律=B∩AA∩(B∩C)5)结合律=(A∩B)∩C()B一、集合的交3、性质(Intersection)若A⊆B，6)则A∩C

B∩C。

⊆反之

不然。

证：A⊆B

(x)

x

∈A→x

∈分析：若x∈A∩C，

即x∈Ax∈C,

∵A⊆B∴x∈A→x∈B则x∈Bx∈C,

∴x∈B∩C。反之，

取C=

，

A={a}，B={b}，则A∩C

=

B∩C=

⊆但A⊆B证毕一、集合的交3、性质(Intersection)A∩B7)A,A∩B⊆⊆B（集合越交越小）注：集合运算的规律和命题演算的某些规律是一致的，所以命题演算的方法是证明集合恒等式的基本方法。二、集合的并1、定义2、文氏图任意两个集合A和B，由属于A或属于B组成的集合，称为A和B的并集，记为A∪B。A∪B={x|x∈A∨x∈B}即(Union)的元素AB二、集合的并三个或更多的集合的并集运算：(Union)EABA∪B∪C

={x|x∈AC∨

x∈B∨

x∈C}A∪B∪C

二、集合的并3、性质A∪A1)幂等律(Union)=AA∪U2)零律=UA∪

3)同一律=AA∪B4)交换律=B∪AA∪(B∪C)5)结合律=(A∪B)∪C二、集合的并3、性质，(Union)若A⊆B，6)则A∪C

B∪D。

反之

不然。

若x∈A∪C，

即x∈Ax∈C,

∨C⊆D，⊆1)若x∈A，则x∈B，∴x∈B∪D，

2)若x∈C，则x∈D，∴x∈B∪D，

∴始终有x∈B∪D。

反之，

取C=D=E，

A={a}，B={b}，则A∪CE=

B∪D=E⊆但A⊆B证：证毕。二、集合的并3、性质(Union)A∪B，7)A⊆（集合越并越大）A∪BB⊆x∈B()}x∈Bx∈A()∨()}二、集合的并4、∩和∪的关系(Union)定理对任意集合A、B和C有:1)A∪(B∩C)=(A∪B)∩(A∪C);2)A∩(B∪C)=(A∩B)∪(A∩C)。即∩对∪可以分配,∩对∪可以分配。1)A∪(B∩C)={x|x∈A

x∈C={x|∨

x∈A∨x∈C=(A∪B)(A∪C)∩

={x|x∈A∨x∈B}∩x∈A∨x∈C}{x|分配律分配律证：x∈B∨()}x∈A二、集合的并4、∩和∪的关系(Union)定理对任意集合A、B有:1)A∪(A∩B)=A2)A∩(A∪B)=A证一：1)A∪(A∩B)={x|x∈A

={x|x∈A}=A吸收律吸收律命题逻辑中的吸收律二、集合的并4、∩和∪的关系吸收律(Union)定理对任意集合A、B有:A⊆BA∪B=B或A∩B=A。当且仅当∵A⊆B，B⊆B，∴A∪B⊆B∪B=B由性质7)BA∪B⊆∴A∪B=B反之，

由性质7)AA∪B,⊆A∪B=B∴A⊆B证：证毕。三、集合的补1、定义2、文氏图任意两个集合A和B，由属于A但不属于B组成的集合，称为B对于A的补集记为A－B。A－B={x|x∈A∧x∈B}即(Relative

Complement)所有元素或相对的补或A和B的差。={x|x∈A∧﹁(

x∈B)}BA三、集合的补3、绝对补集全集U和集合A的差集称为A的绝对补记为U－

A～A

=即(Relative

Complement)或A的余集或A的补集。={x|x∈U∧

x∈A}～A或﹁A或A。U－

Ax∈～AÛx∈A(AbsoluteComplement).三、集合的补4、性质(Relative

Complement)~(~A)1)双重否定律=A~U2)=

~3)=UA∪~A4)排中律=UA∩～A5)矛盾律=

三、集合的补4、性质(Relative

Complement)(1)~(A∪B)6)德摩根律=~A∩~B(2)~(A∩B)=~A∪~B~(A∪B)={x|x∈U∧﹁(x∈A∪B)}={x|x∈U﹁(x∈A∧∨={x|x∈U﹁(x∈A)∧∧﹁(

x∈B)}={x|(x∈U﹁(x∈A))∧∧﹁(

x∈B))}(x∈U∧=~A~B∩x∈B)}证:(1)~A∩

()~B

()三、集合的补5、定理：(Relative

Complement)2)利用(3)的结论。A-(A∩B)=A∩

(A∩

B)~=A∩~A∪(3)的结论德摩根律=A∪A∩~B

()

=A-B1)A-B=A∩~B2)A-B=A-(A∩B)分配律三、集合的补5、定理(Relative

Complement)4)A∩(B-C)=(A∩B)-(A∩C)三、集合的补5、定理(Relative

Complement)4)a)A⊆B

~B⊆~Ab)A⊆B

(B-A)∪A=B证：a)

若x∈A则必有x∈B，因此x∈B，必有x∈A，即x∈~B

x∈~A∴

~B⊆~A∵A⊆B

由上述证明可知：~(~A)∵

~B⊆~A~(~B)⊆A==B∴A⊆B

~B⊆~A四、集合的对称差1、定义(SymmetricDifference)设A、B是两个集合，其元素但集合A和B的对称差(环和）是集合，记作A

B,或属于A，或属于B,不能既属于A

又属于B，即：A

B=(A-B)∪(B-A)例如A={a,b,c},B={b,d},则A

B={a,c,d}={x|(x∈A

x∈B)

(x∈B

x∈A)}

四、集合的对称差2、文氏图(SymmetricDifference)AB四、集合的对称差3、性质(SymmetricDifference)1)交换律2)同一律3)零律A

B=4)A

B=B

AA

=AAA=

∪∩

B)(A(A∩B)四、集合的对称差3、性质(SymmetricDifference)(A

B)C=A(BC)5)结合律定义2.2-6

A、B两集合的环积记为A

B，是集合。

定理2.2-12(1)

=A

B，(2)A

B=B

A，

(3)A

A=U。

定理2.2-13定理2.2-14

例1

已知A

B＝A

C，是否必须B＝C？解：是。∵A

B=A

C，∴A(A

B)=A(A

C)(A

A)

B∴

=(A

A)

C∴

B=

C∴B=C。例2

已知A∪B=A∪C，是否必须B=C？解：否。例：设A={1、2}，B={1}，C={2}例3

已知A∩B=A∩C，是否必须B=C？解：例：设A={1}，B={1、2}，C={1、3}否。2-5集合的笛卡尔积

1、序偶(有序2元组)：两个具有固定次序的客体组成一个序偶(有序2元组)，记作<x，y>，其中x是它的第一元素，y是它的第二元素。一、有序n元组例：平面直角坐标系中的一个点的坐标就构成为一个有序序偶，我们可用<x，y>表示。注：序偶是讲究次序的。例<1，3>和<3，1>表示平面上两个不同的点，这与集合不同，{1，3}和{3，1}是两个相等的集合。2、定义：两个序偶相等，<x，y>=<u，v>，当且仅当x=u且y=v。一、有序n元组3、有序３元组：是一个序偶，其第一元素本身也是一个序偶，表示为<<x，y>，z>或<x，y，z>。4、有序n元组：有序n元组也是一个序偶，其第一元素是一个n-1元组。<<x1，x2，…，xn-1>，xn>，通常简记为：<x1，x2，…，xn-1，xn>，其中xi称作它的第i坐标，i=1，2，…，n。<x1，x2，…，xn-1，xn>=<y1，y2，…，yn-1，yn>的充要条件是xi=yi，i=1，2，…，n。序偶<x,y>其元素可以分别属于不同的集合，因此任给两个集合A和B，我们可以定义一种序偶的集合。1、定义：设A和B是任意两个集合，由A中元素作第一元素，B中元素作第二元素构成序偶，所有这样序偶的集合称集合A和B的笛卡尔积或直积。记作AB。即

AB={<x，y>|xA∧yB}二、笛卡尔积2、n个集合的笛卡尔积：集合A1，A2，…，An，则