离散数学3.13省公开课一等奖全国示范课微课金奖

集合论1第1页集合论部分第3章集合基本概念和运算第4章二元关系和函数2第2页第3章集合基本概念和运算3.1集合基本概念3.2集合基本运算3.3集合中元素计数3第3页3.1集合基本概念

集合定义与表示集合与元素集合之间关系空集全集幂集4第4页集合定义与表示集合没有准确数学定义了解：一些离散个体组成全体组成集合个体称为它元素或组员集合表示

列元素法

A={a,b,c,d}

谓词表示法

B={x|P(x)}

B由使得P(x)为真x组成惯用数集

N,Z,Q,R,C

分别表示自然数、整数、有理数、实数和复数集合，注意0是自然数.5第5页集合与元素元素与集合关系：隶属关系属于，不属于

实例

A={x|xRx2-1=0},A={-1,1}

1

A,2A注意：对于任何集合A和元素x(能够是集合)，x

A和x

A二者成立其一，且仅成立其一.6第6页隶属关系层次结构例3.1A={a,{b,c},d,{{d}}}{b,c}

Ab

A{{d}}A{d}Ad

A

7第7页集合之间关系

包含（子集）

A

B

x(x

A

x

B)不包含A⊈B

x(x

A

x

B)

相等

A=B

A

B

B

A不相等A

B

真包含

A

B

A

B

A

B

不真包含A

B思索：

和

定义注意

和

是不一样层次问题8第8页空集与全集空集

不含任何元素集合实例{x|x2+1=0xR}就是空集定理空集是任何集合子集

A

x(x

x

A)T

推论空集是惟一.证

假设存在1和2，则1

2且1

2，所以1=2全集E相对性在给定问题中，全集包含任何集合，即

A

(A

E)9第9页幂集定义

P(A)={x|x

A}实例

P(

)={

}，

P({

})={

,{

}}

P({1,{2,3}})={,{1},{{2,3}},{1,{2,3}}}计数假如|A|=n，则|P(A)|=2n

10第10页3.2集合基本运算集合基本运算定义

文氏图（JohnVenn）例题集合运算算律集合包含或恒等式证实11第11页集合基本运算定义并

A

B={x|x

A

x

B}交

A

B={x|x

A

x

B}相对补

A

B={x|x

A

x

B}对称差

A

B=(A

B)

(B

A)=(A

B)(A

B)

绝对补

A=E

A

12第12页文氏图表示13第13页关于运算说明运算次序：和幂集优先，其它由括号确定并和交运算能够推广到有穷个集合上，即

A1

A2

…An={x|x

A1

x

A2

…

x

An}

A1

A2

…An={x|x

A1

x

A2

…

x

An}一些主要结果

A

B

A

A

B

A

B=

（后面证实）

A

B=

A

B=A14第14页只有一、二年级学生才兴趣体育运动

F:一年级大学生集合S：二年级大学生集合

R：计算机系学生集合M：数学系学生集合

T：选修离散数学学生集合

L：兴趣文学学生集合P：兴趣体育运动学生集合T(MR)SRST(MF)T=MLPPFSS(MR)P除去数学和计算机系二年级学生外都不

选修离散数学例1

全部计算机系二年级学生都选修离散数学数学系一年级学生都没有选修离散数学数学系学生或兴趣文学或兴趣体育运动15第15页例2

分别对条件(1)到(5)，确定X集合与下述那些集合相等。

S1={1,2,…,8,9},S2={2,4,6,8},S3={1,3,5,7,9},

S4={3,4,5},S5={3,5}若X

S3=,则X若X

S4,X

S2=,则X若X

S1，XS3,则X若X

S3=,则X若

X

S3，XS1,

则X=S2=S5=S1,S2,S4=S3,S5与S1,...,S5都不等16第16页

交换A

B=B

AA

B=B

AA

B=B

A结合(A

B)C=A

(B

C)(A

B)C=A

(B

C)(A

B)C=A

(B

C)幂等A

A=AA

A=A

与

与

分配A

(B

C)=(A

B)(A

C)A

(B

C)=(A

B)(A

C)A

(B

C)=(A

B)(A

C)吸收A

(A

B)=AA

(A

B)=A集合运算算律吸收律前提：、可交换17第17页集合运算算律（续）

D.M律A

(B

C)=(A

B)(A

C)A

(B

C)=(A

B)(A

C)

(B

C)=B

C

(B

C)=B

C双重否定

A=A

E补元律A

A=A

A=E零律A

=

A

E=E同一律A

=AA

E=A否定

=E

E=18第18页集合包含或相等证实方法证实

X

Y命题演算法包含传递法等价条件法反证法并交运算法证实X=Y命题演算法等式代入法反证法运算法以上X,Y代表集合公式19第19页任取x，

x

X…x

Y

命题演算法证X

Y

例3证实A

B

P(A)

P(B)任取x

x

P(A)x

A

x

B

x

P(B)任取x

x

A{x}A{x}P(A){x}P(B){x}B

x

B20第20页包含传递法证X

Y找到集合T满足X

T且T

Y，从而有X

Y例4A

B

A

B证A

B

AA

A

B

所以A

B

A

B

21第21页利用包含等价条件证X

Y例5A

C

B

C

A

B

C

证A

C

A

C=C

B

C

B

C=C

(A

B)C=A(B

C)=A

C=C(A

B)C=C

A

B

C命题得证22第22页反证法证X

Y欲证X

Y,假设命题不成立，必存在x使得

x

X且x

Y.然后推出矛盾.例6证实A

C

B

C

A

B

C证假设A

B

C不成立，则

x(x

A

B

x

C)

所以x

A或x

B，且x

C

若x

A,则与A

C矛盾；

若x

B,则与B

C矛盾.

23第23页利用已知包含式并交运算例7证实A

C

B

C

A

C

B

C

A

B证A

C

B

C，A

C

B

C

上式两边求并，得(A

C)(A

C)(B

C)(B

C)

(A

C)(A

C)(B

C)(B

C)

A(C

C)

B(C

C)

A

E

B

E

A

B由已知包含式经过运算产生新包含式

X

Y

X

Z

Y

Z,X

Z

Y

Z24第24页

例8证实A(A

B)=A（吸收律）证任取x,

x

A(A

B)x

A

x

A

B

x

A(x

A

x

B)x

A

命题演算法证实X=Y任取x，

x

X…x

Y

x

Y…x

X或者

x

X…x

Y25第25页等式替换证实X=Y例9证实A

(A

B)=A（吸收律）证(假设交换律、分配律、同一律、零律成立)

A

(A

B)=(A

E)

(A

B)同一律=A

(E

B)分配律=A

(B

E)交换律=A

E零律=A同一律不停进行代入化简，最终得到两边相等26第26页反证法证实X=Y例10证实以下等价条件

A

B

A

B=B

A

B=A

A

B=

(1)(2)(3)(4)证实次序：(1)(2),(2)(3),(3)(4),(4)(1)假设X=Y不成立，则存在x使得x

X且x

Y，或者存在x使得x

Y且x

X，然后推出矛盾.27第27页(1)(2)显然B

A

B，下面证实A

B

B.任取x，

x

A

B

x

A

x

B

x

B

x

B

x

B所以有A

B

B.综合上述（2）得证.(2)(3)

A=A

(A

B)

A=A

B

（将A

B用B代入)28第28页(3)(4)假设A

B

,即

x

A

B，那么x

A且x

B.而

x

B

x

A

B.从而与A

B=A矛盾.(4)(1)假设A

B不成立，那么

x(x

A

x

B)

x

A

B

A

B

与条件（4）矛盾.29第29页集合运算法证实X=Y例11证实A

C=B

C

A

C=B

C

A=B证由A

C=B

C和A

C=B

C得到(A

C)-(A

C)=(B

C)-(B

C)从而有A

C=B

C所以

A

C=B

C(A

C)C=(B

C)C

A(C

C)=B(C

C)A=B

A=B由已知等式经过运算产生新等式

X=Y

X

Z=Y

Z,X

Z=Y

Z，X-Z=Y-Z30第30页集合基数与有穷集合包含排斥原理有穷集计数3.3集合中元素计数31第31页集合A基数：集合A中元素数，记作cardA有穷集

A：cardA=|A|=n，n为自然数.有穷集实例：

A={a,b,c},cardA=|A|=3；

B={x|x2+1=0,x

R},cardB=|B|=0无穷集实例：

N,Z,Q,R,C等集合基数与有穷集合32第32页包含排斥原理定理设S为有穷集，P1,P2,…,Pm

是m种性质，Ai是S中含有性质Pi

元素组成子集，i=1,2,…,m.则S中不含有性质P1,P2,…,Pm元素数为33第33页证实证设x不含有性质P1,P2,…,Pm,

x

Ai

,i=1,2,…,m

x

Ai

Aj

,1i<j

m

…

x

A1

A2…Am

,x对右边计数贡献为10+00+…+(1)m·0=1证实关键点：任何元素

x，假如不含有任何性质，则对等式右边计数贡献为１，不然为０34第34页证实（续）设x含有n条性质，1n

m

x对|S|贡献为1

x对贡献为

x对贡献为….

x对|A1

A2…Am|贡献为

x对右边计数贡献为35第35页S中最少含有一条性质元素数为证实将定理1代入即可推论36第36页解：S={x|xZ,1x1000},以下定义S3个子集A,B,C：