四川轻化工大学《离散数学》课件-第1章离散数学的概念

第一章

离散数学的概念1.1 常用数学符号1.2 集合论1.3

容斥原理与鸽巢原理四川轻化工大学《离散数学》E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC24061410课程说明教学目标通过学习常用数学符号（逻辑符号）、集合知识、容斥原理与鸽巢原理并回顾常用数学证明方法等预备知识，使同学们掌握学习本课程其他各章所必备的理论基础。学习要求其他数学符号容斥原理与鸽巢原理主要数学证明方法逻辑符号集合间的关系集合的表示集合的运算及定律幂集P(A)集合的递归表示法无限集的基本概念一般数学证明方法重点掌握四川理工学院计算机学院贺全兵一般掌握了解E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.1 常用数学符号四川理工学院计算机学院贺全兵E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.2 集合论四川理工学院计算机学院贺全兵E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.2.0

集合论简介---集合论的历史罗集合悖论素康 托策梅洛，弗兰克尔四川理工学院计算机学院贺全兵朴素集合论依赖于把集合作为叫做这个集合的“元素”或“成员”的集合，未有形式化的理解。公理化集合论只使用明确定义的公理列表和从中证明的关于集合和成员关系的种种事实E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.2.0

集合论简介---罗素悖论把所有集合分为2类，第一类中的集合以其自身为元素，第二类中的集合不以自身为其元素，假设令第一类集合所组成的集合为P,第二类所组成的集合为Q，则有：P={A∣A∈A},Q={A∣A A}.问题：Q∈P还是

Q∈Q？在某个城市中有一位理发师，他宣称：“我将为本城所有不给自己刮脸的人刮脸，我也只给这些人刮脸。”问他能不能给他自己刮脸呢？一个小岛的国王颁布了一条法律：每个到达这个岛的人都须回答一个问题：“你到这里来做什么？”回答对了就允许在岛上游玩，若答错了就要被绞死。有个人的回答是：“我到这里来是要被绞死的。”请问国王是让他在岛上玩，还是把他绞死呢？四川理工学院计算机学院贺全兵几个世纪前，罗马教廷出了一本书，书中用当时最流行的数学推论，导出“上帝是万能的”。一位智者针锋相对地问：“上帝能创造出一块他自己搬不动的石头吗？”E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.2.0

集合论简介---集合的作用集合不仅可用来表示数及其运算，还可以用于非数值信息及离散结构的表示和处理。数据的删节、插入、排序，数据间关系的描述，数据的组织和查询都很难用传统的数值计算来处理，但可以用集合运算来实现。集合论被广泛应用在计算机科学中，如数据结构、操作系统、数据库、知识库、编译原理、形式语言、程序设计、人工智能、信息检索、CAD等。四川理工学院计算机学院贺全兵E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.2.1

集合及其表示法---描述集合(Set)：由指定范围内的某些特定对象聚集在一起构成的整体，常用A,B,C等表示，又称搜集、族相关概念：元素、基(势)、K元集、有(无)穷集x

A(x属于A):

x是A的元素A

B(A包含于B):

A是B的子集x

A(x不属于A):

x不是A的元素A

B(B不包含A):

A不是B的子集例1.我们班全体同学。例2.A表示所有大于等于5的整数集合。自然数集0,1,2,3,...整数集...-2,-1,0,1,...有理数集p/q,p,q为整数实数集(-

,+

)复数集i2=-1四川理工学院计算机学院贺全兵E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.2.1

集合及其表示法---表示法枚举法：列举出集合中全部或部分元素的方法描述法：刻画集合中元素所具备的某种特性的方法归纳法：归纳定义集合，由基础、归纳、极小性三部分组成递归法：通过计算规则定义集合中的元素文氏图：利用封闭曲线和阴影表示元素的方法四川理工学院计算机学院贺全兵E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.2.2

包含(子集)与相等1、集合的三大特征互异性：集合中的元素各不相同，相同的元素视为同一元素确定性：能够明确的加以“区分的”对象无序性：集合中的元素没有顺序之分包含(子集Subset)： A

B

x(x

A

x

B)四川理工学院计算机学院贺全兵不包含：相等：不相等：A B

x(x

A

x

B)A=B

A

B

B

AA

B

A B

B A真包含(真子集)： A

B

A

B

A

B2、集合与集合的关系E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.2.2

包含(子集)与相等两个集合A和B相等，当且仅当他们有相同的成员（即A的每一个元素都是B的一个元素同时B的每一个元素也是A的一个元素），用逻辑符号可以表达为：A=B

<=>

x(x

A↔x

B)或者A=B<=>

x(x

A→x

B)

x(x

B→x

A)如两个集合有相同的元素，那么不管集合是如何表示的，它们都是相等的。四川理工学院计算机学院贺全兵E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.2.3

特殊集合定义：不含任何元素的集合，记为

（Empty

Set）定理：空集是任何集合的子集推论：空集是绝对唯一的；空集是客观存在的定义：包含相对固定范围内所有元素的集合，记为E或U（Universal

Set）推论：全集具有相对唯一性；任意集合是其全集的子集定义：任意集合A的所有不同子集构成的集合，记为P(A)或者2A（Power

Set），符号化表示为P(A)

=

{

x

|

x

A

}定理：如果

|A|

=

n，则

|P(A)|

=

2n四川理工学院计算机学院贺全兵E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.2.4

集合运算四川理工学院计算机学院贺全兵定 义设A、B为两个集合并集 AUB={x|x

A

x

B

}交集 A∩B={x|x

A

x

B

}相对补 A

B={x|x

A

x

B

}绝对补

A=E

A={x|x

A

}对称差 A

B=(A

B)U(B

A)=

(AUB)

(A∩B)说明只使用圆括号运算顺序:

优先级别为(1)括号,(2)

和幂集,(3)其他同级别的按从左到右运算E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.2.4

集合运算四川理工学院计算机学院贺全兵E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.2.4

集合运算---实例问题描述设E={

x

|

x是北京某大学学生},

A,B,C,D是E的子集,A=

{

x

|

x是北京人}, B=

{

x

|

x是走读生}, C=

{

x

|

x是数学系学生},D=

{

x

|x是喜欢听音乐的学生}. 试描述下列各集合中学生的特征:(AUD)∩

~C, ~

A∩B, (A-B)

∩

D, ~D∩~

B题目解答(AUD)∩

~

C

=

{x|x是北京人或喜欢听音乐,但不是数学系学生}~

A∩B={x|

x是外地走读生}(A-B)∩

D

={x|

x是北京住校生,

并且喜欢听音乐}~

D∩

~

B={x|

x是不喜欢听音乐的住校生}四川理工学院计算机学院贺全兵E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.2.4

集合运算---实例问题描述对24名会外语的科技人员进行掌握外语情况的调查。其统计结果如下：会英、日、德和法语的人分别为13，5，10和9人，其中同时会英语和日语的有2人，会英、德和法语中任两种语言的都是4人。已知会日语的人既不懂法语也不懂德语，分别求只会一种语言(英、德、法、日)的人数和会三种语言的人数四川理工学院计算机学院贺全兵题目解答令A，B，C，D分别表示会英、法、德、日语的人的集合。根据题意画出文氏图。设同时会三种语言的有x人，只会英、法或德语一种语言的分别为y1，y2和y3人。将x和y1，y2，y3填入图中相应的区域，然后依次填入其它区域的人数。E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.2.4

集合运算---实例4-x4-x4-xxy2y1y325-2法9 英

13德

10日

5y1+2(4-x)+x+2＝13y2+2(4-x)+x＝9y3+2(4-x)+x＝10y1+y2+y3+3(4-x)+x＝24-5四川理工学院计算机学院贺全兵E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.2.4

集合运算并和交运算推广到有穷个集合上并和交运算推广到无穷个集合上四川理工学院计算机学院贺全兵I

Ai

A1∩A2∩…∩An={x|x

A1

x

A2

…

x

An}i

1n

Ai

A1UA2U…UAn={x|

x

A1

x

A2

…

x

An}i

1n

Ai

A1UA2U…={x|

i(i=1,2,…)x

Ai

}i

1

Ai

A1∩A2∩…={x|

i(i=1,2,…)x

Ai

}i

1E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.2.4

集合运算---实例设Ai=[0,

1/i

),

Bi=(0,i

),

i=1,2,…,

则四川理工学院计算机学院贺全兵nni

1IAi

nni

1

i

1

Ai

[0,

1)i

1

Ai

[0,

1)i

1

Ai

[0,1/n

)i

1{0

}

Bi

(0,

n)i

1

Bi

(0,

+∞)i

1IBi

(0,1)IBi

(0,1)E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.2.5

基本集合恒等式AUA=A, A∩A=A四川理工学院计算机学院贺全兵幂等律交换律结合律4.

分配律AUB=BUA, A∩B=B∩A(AUB)UC=AU(BUC)(A∩B)∩C=A∩(B∩C)AU(B∩C)=(AUB)∩(AUC)A∩(BUC)=(A∩B)U(A∩C)5.

德摩根律绝对形式相对形式

(BUC)=

B∩

C

(B∩C)=

BU

CA

(BUC)=(A

B)∩(A

C)A

(B∩C)=(A

B)U(A

C)6.

吸收律7.

零律8.

同一律9.

排中律10.

矛盾律AU(A∩B)=A,

A∩(AUB)=AAUE=E, A∩

=

AU

=A,A∩E=AAU

A=EA∩

A=

11.

余补律

=E,

E=

12.

双重否定律13.

补交转换律

A=AA-B=

A∩

BE6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.2.5

基本集合恒等式14.

关于对称差的恒等式四川理工学院计算机学院贺全兵交换律结合律∩对

的分配律A

B=B

A(A

B)

C=A

(B

C)A∩(B

C)=(A∩B)

(A∩C)(4)

A

=A, A

E=~A (5)

A

A=

, A

~A=

EB

AUBA∩B

BA

AUB,A∩B

A,A-B

AAUB=B

A

B

A∩B

A

A-B=

A

B=A

C

A=B,

即

有消去律E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.2.5

基本集合恒等式补充定理定理1：A

B当且仅当AUB=B或A∩B=A定理2：设A,B为任意两个集合，则A-B=A-A∩B定理3：设A,B为任意两个集合，若A

B，则

B

A (B-A)UA=B定理4（交对补的分配率）：设A,B,C为任意的3个集合，则A∩(B-C)=(A∩B)-(A∩C)四川理工学院计算机学院贺全兵E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.2.6

集合证明方法常用证明方法方法一：根据定义证明（逻辑符号系统）方法二：利用已知集合等式或包含式,

通过集合演算证明（1）证明：AUB=BUA

(交换律)证：

x四川理工学院计算机学院贺全兵x

AUB

x

A∨x

B

x

B∨x

A

x

BUA得证

AUB

BUA,

同理可证

BUA

AUBE6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.2.6

集合证明方法证明(分配律)：AU(B∩C)=(AUB)∩(AUC)证：

x x

AU(B∩C)

x

A

(x

B

x

C)

(x

A

x

B)

(x

A

x

C)

x

(AUB)∩(AUC)得证AU(B∩C)

(AUB)∩(AUC)类似可证(AUB)∩(AUC)

AU(B∩C)证明(零律)：AUE=E证：根据并的定义,

有E

AUE.根据全集的定义,又有AU

E

E四川理工学院计算机学院贺全兵E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.2.6

集合证明方法(补交转换律)(德摩根律)证明

(A-B)-C=(A-C)-(B-C)证 (A-C)-(B-C)=(A∩~C)∩~(B∩

~C)=(A∩~C)∩(~BU

~~C)=(A∩~C)∩(~B

U

C) (双重否定律)=

(A

∩

~C

∩

~B)

U(A

∩

~C

∩

C)

(分配律)=

(A

∩

~C

∩

~B)

U(A

∩

) (矛盾律)=

A

∩

~C

∩

~B (零律,同一律)=

(A

∩

~B)

∩

~C (交换律,结合律)=

(A

–

B)

–

C (补交转换律)证明

(AUB)

(AUC)=

(B

C)

-

A证 (AUB)

(AUC)=((AUB)-(AUC))U((AUC)-

(AUB))=((AUB)∩~A∩~C)U((AUC)∩~A∩~B)=

(B∩~A∩~C)U(C∩~A∩~B)=((B∩~C)U(C∩~B))∩~A=((B-C)U(C-B))∩~A=(B

C)-

A四川理工学院计算机学院贺全兵请加上依据E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.2.6

集合证明方法求A-B=B成立的条件解：

∵

A(A=

∨A

)设

A-B

则

x(x

A-B→x

A∧x

B)又

A-B=B∴

这个属于A-B的x肯定属于B故

x(x

A-B→x

A∧x

B∧x

B) 矛盾∴ A-B=B=

将B=

带入A-B=B得 A-

=

而 A-

=A∩~

=A∩

E=A∴ A=

又 当A=

且B=

时有 A-B=

-

=

∩

~

=

=B故 上式成立的条件为A=

且B=

求A-B=A成立的条件解：∵ A-B=A-A∩B∴ 要使A-B=A必须：使

A-A∩B=A而当A∩B=

时有

A-A∩B=A-

=A∩

~

=A∩

E=A∴

上式成立的条件为A∩B=

四川理工学院计算机学院贺全兵E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.2.6

集合证明方法求A

-

B

=

B

-

A成立的条件解：设

A-B

则

x(x

A-B→x

A∧x

B)又A-B=B-

A∴ 属于A-B的x同样属于B-A即

x(x

B-A→x

B∧x

A)∴

x(x

A∧x

B∧x

B∧x

A)矛盾故

A

-

B=

且B

-

A=

∵ A-

B=

∴ (A-

B)UB=

UB四川理工学院计算机学院贺全兵续：故

AUB=B得

A

B又

B

-

A=

得B

A∴ A=B∵ 当A=B时有A-B=A-A=A∩~A=

B-A=A-A=A∩~A=

∴ A-B=B-

A故上式成立的条件为A=BE6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.2.6

集合证明方法若A-B

=

A-C，是否有B=C?若不成立，求其成立的条件解：

不一定∵

A∩B

B A∩C

C∴

B=(B-A∩B)U(A∩B)=(B-A)U(A∩B)C=(C-A∩C)U(A∩C)=(C-A)U(A∩C)又∵

A-B=A-C ∴

不难得到A∩B=A∩C而 (B-A)∩(A∩B)=(B∩~A)∩(A∩B)=

∴

B-A与A∩B不相交则肯定不会有B-A

A∩B同理不会有C-A

A∩C故若

B-A≠C-A，则：(B-A)U(A∩B)≠(C-A)U(A∩C)∴

在此情况下B≠C续：

根据前面的分析若

B-A=C-A则

B=(B-A)U(A∩B)=(C-A)U(A∩C)=C故

B=C成立的条件为：B-A=C-

A四川理工学院计算机学院贺全兵E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.2.6

集合证明方法求A-(B-C)=(A-B)-

C成立的条件四川理工学院计算机学院贺全兵E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.3

容斥原理与鸽巢原理容斥原理研究若干有限集合交与并的计数问题，又称包含排斥原理鸽笼原理研究某些特定对象的存在性问题，又称抽屉原理，由狄利克雷提出四川理工学院计算机学院贺全兵E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.3.1

容斥原理定义

所谓容斥，是指我们计算某类物体的数目时，要排斥那些不应包含在这个计数中的数目，但同时要包容那些被错误地排斥了的数目，以此补偿。这种原理称为容斥原理(The

Principleof

Inclusion-exclusion)，又称为包含排斥原理四川理工学院计算机学院贺全兵E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.3.1

容斥原理定理 设A和B是任意有限集合，有|A∪B|=

|A|＋|B|－|A∩B|分析 由图容易看出，A∪B=(A-B)∪(A∩B)∪(B-

A)A=(A-

B)∪(A∩B)B=(A∩B)∪(B-

A)附 |A-B|=|A|-|A

B|UABA∩BA-BB-A|A| = |A-B|+|A∩B||B| = |A∩B|+|B-A||A

B|=|A

B|+|A

B||A∪B| = |A-B|+|A∩B|+|B-A|推论

设U为全集，A和B是任意有限集合，则A

B

U

(A

B

)

A

B四川理工学院计算机学院贺全兵E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.3.1

容斥原理验证定理（1）A={1,2,3,4}，B=

{2,3,5,6,8}（2）A={1,2,3,4}，B=

{5,6,7,8}四川理工学院计算机学院贺全兵E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.3.1

容斥原理|A

B

C|=?定理 设A，B和C是任意三个有限集合，有A

B

C

?推论 设U为全集，A，B和C是任意有限集合，则四川理工学院计算机学院贺全兵E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.3.1

容斥原理问题描述调查260个大学生，获得如下数据：64人选修数学，94人选修计算机，58人选修商贸，28人同时选修数学和商贸，26人同时选修数学和计算机，22人同时选修计算机和商贸，14人对三种课程都选修。问调查中三种课程都不选的学生有多少？调查中只选修计算机科学课程的学生有多少？题目解答设A、B、C分别表示选修数学课程，计算机课程和商贸课程的人构成的集合，则三种课程都不选的学生集合为

A

∩

B

∩

C只选修计算机科学课程学生的集合为

A

∩

B

∩

C四川理工学院计算机学院贺全兵E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.3.1

容斥原理（1）∵|U|=260,|A|=64,|B|=94,

|C|=58,|UBAA∩C|=28,|A∩B|=26

,|B∩C|=22,C|A∩B

∩

C|=14，所以利用容斥原理得A∩B∩C

=

U

-(

A

+

B

+

C

)+(

A∩B

+

A∩C

+

B∩C

)-

A∩B∩C=106（2）四川理工学院计算机学院贺全兵E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.3.1

容斥原理求1到1000之间(含1和1000)既不能被5和6也不能被8整除的数有多少个解

设S＝{x|x∈Z∧1≤x≤1000}B＝{

x|x∈S∧x可被6整除}|T|表示有穷集T中的元素数A＝{

x|x∈S∧x可被5整除}C＝{

x|x∈S∧x可被8整除}

x

表示小于等于x的最大整数lcm(x1,x2,…,xn)表示x1,x2,…,xn的最小公倍数|B|B|＝|＝

11000000/6/6

＝116666|A|A∩BB|＝|＝

11000000/l/clcmm((55,6,6)

)

＝3333|B|B∩CC|＝|＝

11000000/l/clcmm((66,8,8)

)

＝4411|A|A|＝|＝

11000000/5/5

＝220000|C|C|＝|＝

11000000/8/8

＝112255|A|A∩CC|＝|＝

11000000/l/clcmm((55,8,8)

)

＝2255|A|A∩BB∩CC|＝|＝

11000000/l/clcmm((55,6,6,8,8)

)

＝88四川理工学院计算机学院贺全兵E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.3.1

容斥原理将这些数字依次填入文氏图得到如右图所示的图。根据包含排斥原理，所求不能被5，6和8整除的数应为由文氏图也可得知，不能被5，6和8整除的数有1000－(200+100＋33＋67)＝600个四川理工学院计算机学院贺全兵E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.3.1

容斥原理某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6人会打网球的人都会打另一种球（篮球或者排球）。求不会打这三种球的人？四川理工学院计算机学院贺全兵E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.3.1

容斥原理解

设会打排球、网球和篮球的学生集合分别为A、B和C，则：|A|=12, |B|=12, |C|=14, |E|=12,|A

C|=6, |B

C|=5, |A

B

C|=2现在求|A

B|。因为会打网球的人都会打另一种球，即篮球或者排球。而其中会打篮球的有5人，那么另一人肯定会打排球打不会打篮球。再加上会打3种球的2人，共有3人会打排球和网球。即|A

B|=3.则：|~A

~B

~C|=25-(12+6+14)+(3+6+5)-2=5四川理工学院计算机学院贺全兵E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.3.1

容斥原理的推广定

理

1定理 设A1, A2, …, An是任意n个有限集合，有定

理

2推论 设U为全集，A1, A2, …, An是任意n个有限集合，则四川理工学院计算机学院贺全兵E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.3.1

容斥原理的推广对24名科技人员进行掌握外语情况的调查，其统计资料如下：会英、日、德、法语的人数分别为13、5、10和9。其中同时会英语、日语的人数为2；同时会英语和德语、同时会英语和法语、同时会德语和法语两种语言的人数均为4；会日语的人既不会法语也不会德语。试求(1)只会一种语言的人数各为多少？(2)同时会英、德、法语的人数为多少？四川理工学院计算机学院贺全兵E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.3.1

容斥原理的推广解

设A、B、C、D分别为会英、日、德、法语的人的集合，由已知条件可知：

|A|＝13，|B|＝5，|C|＝10，|D|＝9，|A∩B|＝2|A∩C|＝|A∩D|＝|C∩D|＝4，|B∩C|＝|B∩D|＝0|A∩B∩C|＝|A∩B∩D|＝|B∩C∩D|＝0|A∩B∩C∩D|＝0，|A∪B∪C∪D|＝24利用容斥原理，并代入已知条件得24＝13＋5＋10＋9－2－4－4－4－0－0＋0＋0＋0＋|A∩C∩D|－0。得：|A∩C∩D|＝1，即同时会英、德、法语的只有1人。四川理工学院计算机学院贺全兵E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.3.1

容斥原理的推广续设只会英、日、德、法语的人数分别为x1,x2,x3,x4，则x1＝|A|－|(B∪C∪D)∩A|＝|A|－|(B∩A)∪(C∩A)∪(D∩A)|对B∩A、C∩A、D∩A应用容斥原理，得|(B∩A)∪(C∩A)∪(D∩A)|＝2＋4＋4－0－0－1＋0＝9故，x1＝13-9＝4 类似地可求出：x2＝3，x3＝3，x4＝2四川理工学院计算机学院贺全兵E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.3.2

鸽巢原理

鸽笼原理（Pigeonhole

Principle）又称为抽屉原理、鸽舍原理，是指如下定理：

定理(鸽笼原理) 若有n+1只鸽子住进n个鸽笼，则有一个鸽笼至少住进2只鸽子。

注证意明：(反证法) 假设每个鸽笼至多住进1只鸽子，则n个鸽笼（至1）多鸽住笼进原n只理鸽仅子提，供这了与存有在n性+1证只明鸽；子矛盾。故存在一个鸽笼注意：（1）鸽笼原理仅提供了存在性证明；至少住进2只鸽子。

（2）使用鸽笼原理，必须能够正确识别鸽子(对象)和鸽巢(某类要求的特征)，并且能够计算出鸽子数和鸽巢数。四川理工学院计算机学院贺全兵E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.3.2

鸽巢原理

例1：抽屉里有3双手套，问从中至少取多少只，才能保证配成一双？答：4只

例2：设1到10中任意选出六个数，那么其中有两个数的和是11。证明：构造5个鸽笼A1={1,10}，A2={2,9}，A3={3,8}，A4={4,7}，A5={5,6}选出的6个数为鸽子根据鸽笼原理，所选出的6个数中一定有两个数属于同一个集合，这两个数的和为11。四川理工学院计算机学院贺全兵E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.3.2

鸽巢原理鸽巢原理推广若有n只鸽子住进m(m>n)个鸽笼，则存在表示小于等于x的最大整数。

m一个鸽笼至少住进

n

-

1

+

1只鸽子。这里

x

四川理工学院计算机学院贺全兵E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.3.2

鸽巢原理如果一个图书馆里30本离散数学书共有1203页，那么必然有一本离散数学书至少有41页解

设页是鸽子，离散数学书是鸽笼，把每页分配到它所出现的离散数学书中，根据定理2.4.5，则存在一个鸽笼至少住进=

41即结论得证四川理工学院计算机学院贺全兵E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.4

数学证明方法四川理工学院计算机学院贺全兵

逻辑推理的形式结构(*)A1

A2

…

Ak

B当(*)为重言式时,

记作A1

A2

…

Ak

B(**)并称推理有效或推理正确,

又称B是A1,A2,…,Ak的有效(或逻辑)结论;

否则称推理不正确ABA

B(1)001(2)011(3)100(4)111(1),(2),(4)推理正确(3)推理不正确(1)中B是A的逻辑结论,但不是正确结论(2)和(4)中B既是逻辑结论,又是正确结论E6636B02012BD195C019CE06C16E3004C83D0EE32711A616D0819A143DE998F98FE45903BC41BA96CB46D7F0472B73A72FC0F2BE2AA536FE6A0E217857F2C1EDBF2DB6715F2B3FB87DC240614101.4

数学证明方法数学归纳法后件真证明法前件假证明法构造证明法直接证明法间接证明法归谬法反例法列举法四川理工学院计算机学院贺全