离散数学之集合论

离散数学四大核心：代数系统、集合论、数理逻辑、图论。

第二篇 集合与关系

集合论是现代各科数学的基础，它是德国数学家康托（Geog Cantor, 1845～1918）于1874年创立的，1876～1883年康托一系列有关集合论的文章，对任意元的集合进行了深入的探讨，提出了关于基数、序数和良序集等理论，奠定了集合论深厚的基础，19世纪90年代后逐渐为数学家们采用，成为分析数学、代数和几何的有力工具。

随着集合论的发展，以及它与数学哲学密切联系所作的讨论，在1900年前后出现了各种悖论，使集合的发展一度陷入僵滞的局面。1904～1908年，策墨罗（Zermelo）列出了第一个集合论的公理系统，它的公理，使数学哲学中产生的一些矛盾基本上得到了统一，在此基础上以后就逐渐形成了公理化集合论和抽象集合论，使该学科成为在数学中发展最为迅速的一个分支。

现在，集合论已经成为内容充实、实用广泛的一门学科，在近代数学中占据重要地位，它的观点已渗透到古典分析、泛函、概率、函数论、信息论、排队论等现代数学各个分支，正在影响着整个数学科学。集合论在计算机科学中也具有十分广泛的应用，计算机科学领域中的大多数基本概念和理论几乎均采用集合论的有关术语来描述和论证，成为计算机科学工作者必不可少的基础知识。集合论可作为数学学科的通用语言，一切必要的数据结构都可以利用集合这个原始数据结构而构造出来，计算机科学家或许也可以利用这种方法。

本篇介绍集合论的基础知识，主要内容包括集合及其运算、性质、序偶、关系、映射、函数、基数等。

第2-1章 集合及其运算

§2-1-1 集合的概念及其表示

一、集合的概念

“集合”是集合论中的一个原始的概念，因此它不能被精确地定义出来。一般地说，把具有某种共同性质的许多事物，汇集成一个整体，就形成一个集合。构成这个集合的每一个事物称为这个集合的一个成员（或一个元素），构成集合的这些成员可以是具体东西，也可以是抽象东西。例如：教室内的桌椅；图书馆的藏书；全国的高等学校；自然数的全体；程序设计语言C的基本字符的全体等均分别构成一个集合。通常用大写的英文字母表示集合的名称；用小写的英文字母表示元素。若元素a属于集合A记作

离散数学四大核心：代数系统、集合论、数理逻辑、图论。

a A，读作“a属于A”。否则，若a不属于A，就记为a A，读作“a不属于A”。一个集合，若其组成集合的元素个数是有限的，则称作“有限集”，否则就称作“无限集”。

集合的表示方法有两种：一种是列举法又称穷举法，它是将集合中的元素全部列出来，元素之间用逗号“，”隔开，并用花括号“{ }”在两边括起来，表示这些元素构成整体。

例2-1-1.1 A＝｛a , b , c , d｝； B＝｛1 ，2 ，3 ， ｝ ；

D＝｛桌子，台灯，钢笔，计算机，扫描仪，打印机｝；E {a,a2,a3, }。 集合的另一种表示方法叫做谓词法又叫叙述法，它是利用一项规则，概括集合中元素的属性，以便决定某一事物是否属于该集合的方法。设x为某类对象的一般表示，P(x)为关于x的一个命题，我们用{xP(x)}表示“使P(x)成立的对象x所组成的集合”，其中竖线“|”前写的是对象的一般表示，右边写出对象应满足（具有）的属性。

例2-1-1.2 全体正奇数集合表示为 S1 {xx是正奇数}，

所有偶自然数集合可表示为 E {m2m且m N} 其中 2|m表示2能整除m。

[0,1]上的所有连续函数集合表示为 C[0,1] {f(x)f(x)在[0，1]上连续}

集合的元素也可以是集合。例如S {a,{1,2},p,{q}}，

{1,2} S，但必须注意：q {q}，而q S，同理1 {1,2}，S a {1，2} p

1 2 {q} q 而1 S。

两个集合相等是按下述原理定义的。外延性原理：两个集合相等，当且仅当两个集合有相同的元素。两个集合A，B相等，记作A B，两个集合不相等，记作A B。

集合中的元素是无次序的，集合中的元素也是彼此不相同的。

例如： {1,2,4} {1,4,2},{1,2,4} {1,2,2,4},

{{1,2}，4} {1,2,4},{1,3,5, } {xx是正奇数}。

集合中元素可以是任何事物（如例2-1-1.1）。不含任何元素的集合称为空集，记为Φ。例如，方程 x2 1 0的实根的集合是空集。

二、集合与集合间的关系

离散数学四大核心：代数系统、集合论、数理逻辑、图论。

“集合”、“元素”、元素与集合间的“属于”关系是三个没有精确定义的原始概念，对它们仅给出了直观的描述，以说明它们各自的含义。现利用这三个概念定义集合间的相等关系，集合的包含关系，集合的子集和幂集等概念。

定义2-1-1.1 设A，B是任意两个集合，如果A中的每一个元素都是B的元素，则称A是B的子集，或A包含于B内，或B包含A。记作A B，或B A。

即 A B x(x A x B)

可等价地表示为 A B x(x B x A)。

例2-1-1.3 设N为自然数集合，Q为一切有理数组成的集合。R为全体实数集合，C为全体复数集合，则 N Q R C，

{1} N,{1,1.2,9.9} Q,{2, } R。

如果A不是B的子集，则记为A B（读作A不包含在B内），显然，

A B x((x A) (x B))。

集合间的包含关系“ ”具有下述性质：

2-1-1. 自反性 A A；

2. 传递性 (A B) (B C) (A C)。

证明：采用逻辑演绎的方法证明。

⑴ A B P

⑵ x((x A) (x B)) T(1)E

⑶ (a A) (a B) US(2)

⑷ B C P

⑸ x((x B) (x C)) T(4)E

⑹ (a B) (a C) US(5)

⑺ (a A) (a C) T(3)(6)I

⑻ x((x A) (x C)) UG(8)

⑼ A C T(8)E

离散数学四大核心：代数系统、集合论、数理逻辑、图论。

定义2-1-1.2 如果集合A的每一元素都属于集合B，而集合B中至少有一元素不属于A，则称A为B的真子集，记作A B。

即 A B x((x A) (x B)) x((x B) (x A))

例如：{a,b}是{a,b,c}的真子集；N是Q的真子集，Q是R的真子集；R是C的真子集。

注意符号“∈”和“ ”在概念上的区别，“∈”表示元素与集合间的“属于”关系，“ ”表示集合间的“包含”关系。

定理2-1-1.1 集合A＝B的充分必要条件是：A B且B A。（外延性原则） 证明：必要性， 即证：A B (A B) (B A)

A B ( x((x A) (x B))) ( x((x B) (x A))) (A B) (B A) 充分性，即证：(A B) (B A) A B

A B x((x A) (x B)) A B (A B) (A B) F

或 A B x((x B) (x A)) B A (B A) (B A) F # 定理2-1-1.2 对于任一集合A， A，且空集是唯一的。

证明： 假设 A为假，则至少存在一个元素x，使x 且x A，因为空集 不包含任何元素，所以这是不可能的。

设 与 都是空集，由上述可知， 且 ，根据定理2-1-1.1知 ，所以，空集是唯一的。

注意： { }， {xP(x) P(x)} P(x)是任一谓词。

例2-1-1.4 设 A {2,3},B为方程 x2 5x 6 0的根组成的集合，则 A＝B 。

定理2-1-1.1指出了一个重要原则：要证明两个集合相等，即要证明每一个集合中的任一元素均是另一集合的元素。这种证明是靠逻辑推理理论，而不是靠直观。证明两个集合相等是应该掌握的方法。

定义2-1-1.3 在一定范围内，如果所有集合均为某一集合的子集，则称该集合为全

离散数学四大核心：代数系统、集合论、数理逻辑、图论。

集，记作E。对于任一x A，因A E，所以x E，

也即 x(x E) 恒为真

故 E {xP(x) P(x)} ， P(x)为任一谓词。

注意：全集的概念相当于论域，只包含与讨论有关的所有对象，并不一定包含一切对象与事物。例如：在初等数论中，全体整数组成了全集；方程x2 1 0的解集合，在全集为实数集时为空集，而全集为复数集时解集合就不再是空集，此时解集合为{i, i}，i2 1。

三、幂集

定义2-1-1.4 给定集合A，由集合A的所有子集为元素组成的集合，称为集合A的幂集。记为P (A)（或记为2A）。即 P (A)＝{X|X A}。

例2-1-1.5 A = {0 , 1 , 2 }，则 P (A) ＝ {Φ , {0} , {1} , {2} , {0 , 1} , {0 , 2} , {1 , 2} , {0 , 1 , 2 } }；

P (Φ)＝{Φ}；P ({a})={Φ,{a}}；P ({Φ}) = {Φ,{Φ}}。

定理2-1-1.3 设A {a1,a2, ,an}，则 |P (A)|＝2n。

其中：|P (A)|表示集合P (A)中元素的个数。

证明：集合A的m (m = 0 , 1 , 2 , , n )个元素组成的子集个数为从n个元素中取m

m个元素的组合数，即Cn，故P (A)的元素个数为：

nm|P (A)|＝C C C Cn 0

n1nnn

m 0

n

根据二项式定理 (x y) Cxynm

nm

m 0n mm 令x = y = 1得 2 Cn nm 0n

故 |P (A)|＝2n。

四、集合的数码表示

在中学学习集合时，特别强调了集合中元素的无序性，但是，为了用计算机表示集合及其幂集，需要对集合中元素规定次序，即给集合中元素附上排列指标，以指明一个元素关于集合中其他元素的位置。如A 2= {计算机，打印机}是二个元素的集合，令“计算机”为集合A的第一个元素，“打印机”为集合A 2的第二个元素。改记为A 2 = { x 1 ,

离散数学四大核心：代数系统、集合论、数理逻辑、图论。

x 2 } ，则P (A 2)的四个元素，可记为， S00，{x1} S10，{x2} S01，{x1,x2} S11，其中S的下标，从左到右分别记为第一位，第二位，它们的取值是1还是0由第一个和第二个元素是否在该子集中出现来决定，如果第i个元素出现在该子集中，那么S下标的第i位取值为1，否则取值为0（i = 0 , 1）。即令J = {00 , 01 , 10 , 11 } = { i | i 是二位二进制数，00 ≤ i ≤11 }，则P (A 2) ＝ { S i | i∈J }。类似地，三个元素集合 A 3 = { x1 , x 2 , x 3 }的幂集P (A 3) ＝ { S i | i∈J , J = { i | i二进制数，000 ≤ i ≤ 111} }，因此，

S010 = {x 2 } ， S101 = {x 1 , x 3 }。上述幂集中元素表示法实际上是一种编码，可以推广到n个元素的集合A n的幂集上，P (A n)的2 n个元素可以表示为

n n

Si ，i∈J={i| i是二进制数， ≤ i ≤ }

如果A6 {x1,x2,x3,x4,x5,x6}，P (A 6)的26个元素记为 S0,S1, ,S26 1，此时S

的下标是十进制整数，如何求出S7,S12是A 6的那些元素组成的子集呢？将下标转换为二进制的整数，不足六位的在左边补入需要个数的零，使之成为六位的二进制整数，由排列的六位二进制整数推断出，含有那些元素。凡第i位为0，表示x i不在此子集中，凡第i位为1表示x i在此子集中，故

这种方法可以推广到一般情况，B7 B111 B000111 {x4,x5,x6}，B12 B001100 {x3,x4}。

即将十进制整数转换为二进制整数，在左边补入需要个数的零使之成为n位的二进制数，若第i位为0，表示x i不在此子集中，若第i位为1表示x i在此子集中。

子集的这种编码法，不仅给出了一个子集含那些元素的判别方法，还可以用计算机表示集合、存贮集合以供使用。

§2-1-2 集合的基本运算

集合的运算，就是以集合为对象，按照确定的规则得到另外一些新集合的过程。给定集合A，B，可以通过集合的并（∪）、交（∩）、相对补（－）、绝对补（¯）和对称差（⊕）等运算产生新的集合。

一、集合并（∪）运算

定义2-1-2.1 设A ，B为任意两集合，所有属于集合A或属于集合B的元素组成

离散数学四大核心：代数系统、集合论、数理逻辑、图论。

的集合，称为集合A和B的并集。记作 A∪B

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

并集的文氏（英国数学家Johan Wenn (1834~1883)）图

例2-1-2.1 设A = {1 , 2 , 3 , 4 }，B = {2 , 4 , 5 , 6 }

则 A∪B = {1 , 2 , 3 , 4 , 5 , 6 }。注意：集合是由互不相同元素组成的，在A∪B中2，4各写一次，不能重写。

由集合并运算的定义知，并运算具有如下性质：

定理2-1-2.1 设A，B，C为任意三个集合，则

⑴ 幂等律 A∪A=A；

⑵ 交换律 A∪B = B∪A；

⑶ 结合律 (A∪B)∪C = A∪(B∪C)；

⑷ 同一律 A∪Φ= A；

⑸ 零 律 A∪E = E；

⑹ A A∪B，B A∪B；

⑺ A∪B = B A B。

证明：性质⑴，⑵，⑷，⑸，⑹由定义2-1-2.1立即可以得到。

⑶的证明

(A∪B)∪C ＝ {x | x∈(A∪B)∪C } = { x | (x∈A∪B)∨(x∈B) }

＝ { x | ((x∈A)∨(x∈B))∨(x∈B)}={ x|(x∈A)∨((x∈B)∨(x∈C))}

= { x |( x∈A)∨(x∈B∪C)} = { x | x∈A∪(B∪C)} = A∪(B∪C) 。

⑺的证明：必要性证明 x(x A) x(x A B) x(x B) 所以 A B。 充分性证明 由⑹知B A∪B，现证明 A∪B B

x(x A B) x(x B)

所以有 A∪B = B。

例2-1-2.2 设 A B，C D，则 A∪C B∪D

证明： A C {xx A C} {x(x A) (x C)}A B,C DA BA B B {x(x B) (x D)} ＝{xx B D} B D 即 A∪C B∪D成立。

离散数学四大核心：代数系统、集合论、数理逻辑、图论。

同理可证 A B A C B C。

因为集合的并运算满足结合律，对n个集合A1 , A2 , , A n 的并集A1 A2 An定义为至少属于A1 , A2 , , A n之一的那些元素构成的集合。A1 A2 An通常缩写成 Ai。

i 1n

A1 A2 An An {x n N,x An}其中N是自然数集合。 n 1

一般地， Ak {x k I,x Ak}。

k I

集合的并运算，就是把给定集的那些元素放到一起合并成一个集合，在这个合并中相同的元素只要一个。如设A1 {1,2,3},A2 {3,8},A3 {2,3,6}则 A

i 13i {1,2,3,6,8}。

二、集合的交（∩）运算

定义2-1-2.2 设任意两个集合A 和B，由集合A和B共

同元素组成的集合，称为集合A和B的交集，记作 A∩B。

A B {x(x A) (x B)}。

交集的文图

例2-1-2.3 设A {a,b,c,d,e},B {a,c,e,f} 则 A B {a,c,e}。

例2-1-2.4 设A = {X高等学校的本科学生}，B = {X高等学校计算机专业的学生}，则

A∩B = {X高等学校计算机专业的本科学生}

例2-1-2.5 设A是所有能被k整除的整数集合，B是所有能被l 整除的整数集合，则A∩B是所有能被k与l最小公倍数整除的整数集合。

由集合交运算的定义知，集合交运算具有如下性质：

定理2-1-2. 2 设A , B , C是任意三个集合，则

(1) 幂等律 A∩A = A ；

(2) 交换律 A∩B = B∩A ；

(3) 结合律 (A∩B)∩C = A∩(B∩C) ；

离散数学四大核心：代数系统、集合论、数理逻辑、图论。

(4) 零 律 Φ∩A = Φ；

(5) 同一律 E∩A = A ；

(6) A∩B A , A∩B B ；

(7) A∩B = A A B。

证明：根据定义2-1-2.2，性质(1) , (2) , (4) , (5) , (6)立即可以得到。

性质（3）的证明：

(A∩B)∩C = { x | x∈(A∩B)∩C } = { x|(x∈A∩B)∧(x∈C)}

= {x|((x∈A)∧(x∈B))∧(x∈C)} = {x | (x∈A)∧((x∈B)∧(x∈C)}

= {x|(x∈A)∧(x∈B∩C)} = {x | x∈A∩(B∩C)} = A∩(B∩C)

性质（7）的证明：

x(x A) x(x A B) x(x B) 即得A∩B = A A B 必要性的证明：A B A

充分性得证明：由性质（6）知A∩B A , 现证 A A∩B

采用逻辑演绎推理法

(1) x(x A) P(附加前提)

（2） a A US(1)

(3) A B P

(4) x((x A) (x B)) T(3)E

(5) (a A) (a B) US(4)

(6) a B T(2 , 5) I

(7) (a A) (a B) T(2 , 6) I

(8) x((x A) (x B)) UG(7)

(9) x(x A B) T(8)E

（10） A A∩B CP

若集合A , B没有共同的元素，则可记为A∩B = Φ,这时称A , B不相交。

由集合的交运算具有结合律，同样可以定义n个集合A 1 , A 2 , , A n的交集，也可以定义集序列A 1 , A 2 , , A n , 的交集，分别记为

离散数学四大核心：代数系统、集合论、数理逻辑、图论。

A1 A2 An Ai {xi {1,2, ,n},x Ai}

i 1n

A1 A2 An An {xn {1,2, ,n, },x An}

n 1

一般地，集合族{A k}k∈I 中各集的交记成 A

k Ik其定义为

A

k Ik {x l I,x Al}。

若序列A 1 , A 2 , , A n , 任意两集合A i , A j (i j) 不相交，则称

A 1 , A 2 , , A n , 是两两不相交的集序列。

三、交运算与并运算之间的联系

定理2-1-2.3 （分配律） 设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∩(B∪C)} = {x |(x∈A)∧(x∈B∪C)}

= {x |(x∈A)∧(（x∈B）∨(x∈C))}

= { x |(( x∈A)∧(x∈B))∨((x∈A)∧(x∈C))}

= {x |(x∈A∩B)∨(x∈A∩C)}

= {x |x∈(A∩B)∪(A∩C)} = (A∩B)∪(A∩C)

当然可以仿照（1）的证明方法证明（2）的成立，现在采用（1）来证明（2），注意到 A A∪B，A∩C A，由（1）可得

(A∪B)∩(A∪C) =( (A∪B)∩A)∪((A∪B)∩C) = A∪(A∩C)∪(B∩C) = A∪(B∩C) 。 同理可以利用（2）证得（1）成立（读者自行完成），于是（1）成立 （2）的成立。

定理2-1-2.4 （吸收律）设A , B为任意两集合，则

（1） A∪(A∩B) = A ；

（2）A∩(A∪B) = A ；

证明： 由分配律可得

（1） A∪(A∩B) = (A∩E)∪(A∩B) = A∩(E∪B) = A∩E = A

（2） A∩(A∪B) = (A∪Φ)∩(A∪B ) = A∪(Φ∩B) = A∪Φ = A ﹟

离散数学四大核心：代数系统、集合论、数理逻辑、图论。

四、集合的补运算

定义2-1-2.3 设A , B为任意两集合，由属于A而不属于B的一切元素构成的集合，称为A与B的差运算（又称B对于A的补运算，或相对补），记为A-B，A-B称为A与B的差集（或B对于A的补集）。

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

若A = E ，对任意集合B关于E的补集

E-B ，称为集合B的绝对补，记作 。

E B {x(x E) (x B)}

例2-1-2.6 设A = {1 , 2 , 3 , 4 , 5} ，

B = {1 , 2 , 4 , 7 , 9 } ，则 A-B = {3 , 5 }。

例2-1-2.7 设A是素数集合，B是奇数集合，则A-B = {2}。

例2-1-2.8 设E = {X高校计算机专业学生}，A = {X高校校计算机专业本科学生}， 则= {X高校计算机专业研究生}。

由集合补运算的定义知，补（差）集合有如下性质

定理2-1-2.5 设A , B , C 为任意三集合，则

（1） 对合律 A A；

（2） E ；

（3） E；

（4） 排中律 A E；

（5） 矛盾律 A ；

（6） （De . Morgan定理）

① A B , ② A B ；

（7） ① A B A ， ② A B A (A B)；

（8） A (B C) (A B) (A C)；

（9）若A B，当且仅当 ① ； ② (B A) A B。

证明：由补运算的定义立即可得性质（1）～（5）。

A-B

离散数学四大核心：代数系统、集合论、数理逻辑、图论。

（6）的证明：

① A B {xx A B} {xx A B} {x(x A) (x B)}

{x(x ) (x )} {xx }

②的证法与①类似，请读者自行证明。

（7）的证明：

① A B {x(x A) (x B)} {x(x A) (x )} {xx A A ； ② A (A B) A A B A ( ) (A ) (A ) A A B。

（8）的证明：

(A B) (A C) (A B) (A C) (A B) ( )

(A B ) (A B ) A B A (B C)。

（9）的证明：

证明①

必要性 x(x ) x(x B) x(x A) x(x ) 即 ；

充分性 x(x A) x(x ) x(x ) x(x B) 即 A B。

证明②

必要性 (B A) A (B ) A (B A) ( A) B A B；

充分性 A A (B A) (B A) A B。﹟

五、集合的对称差运算

定义2-1-2.4 设A , B为任意两集合，由“属于A而不属于

B”或“属于B而不属于A”的一切元素构成的集合，称为A , B

的对称差,记作A⊕B。 A BA B A

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

A B 对称差运算的性质

定理2-1-2.6 设A , B , C为任意三集合，则

（1） A B B A；

（2） A A；

（3） A A ；

离散数学四大核心：代数系统、集合论、数理逻辑、图论。

（4） A B (A ) ( B)；

（5） (A B) C＝A (B C)；

（6）交关于对称差的分配律 A (B C) (A B) (A C)；

（7） 若A B A C，则 B = C 。

证明：

由对称差的定义立即可得（1），（2），（3），（4）的证明。

（5）的证明

(A B) C ((A ) ( B)) C

((A ) ( B) C) (((A ) ( B)) )

(( B) (A ) C) (A ) ( B )

(A B C) ( B ) (A ) ( C)

A (B C) A ((B ) ( C))

(A ((B ) ( C))) ( ((B ) ( C)))

(A ( C) (B )) (( B ) ( C))

(A B C) (A ) ( B ) ( C)

所以 (A B) C＝A (B C)。

（6）的证明

(A B) (A C) ((A B) (A C)) ((A B) (A C))

((A B) ( )) (( ) (A C))

(A B ) (A C)

A ((B ) ( C))

A (B C)

（7）的证明

(A B) (A C) A (A B) A (A C) (A A) B (A A) C B C B C

从对称差定义或文图容易看出

A B (A ) ( B) (A B) (A B) (A B)，

A B (A B) (A B)。

离散数学四大核心：代数系统、集合论、数理逻辑、图论。

§2-1-3 集合中元素的计数

一、两个基本原理

加法原理：若一个事件以m种方式出现（这些方式构成集合A），另一个事件以n种方式出现（这些方式构成集合B），这两个事件完成一件即能达到目的（构成集合A∪B），则达到目的的方式数为m+n。

例2-1-3.1 假设从城市A到城市B有铁路两条，公路三条，航线一条，那么按加法原理，从城市A到城市B有2＋3＋1＝6种走法。

乘法原理：若一个事件以m种方式出现（这些方式构成集合A），另一个事件以n种方式出现（这些方式构成集合B），这两个事件同时完成才能达到目的（构成集合A∩B），则达到目的的方式数为m n。

例2-1-3.2 一位学生想从图书馆借离散数学和C# 语言书各一本，书架上有三种不同作者的离散数学书，有两种不同作者的C# 语言书，那么这位学生共有3×2＝6种不同的选法。

二、排列、组合

中学里已学过的计数公式是排列组合公式。从n个元素的集合中每次取m个的排列和组合的公式分别为：

Pnmn!n!m ，Cn P n(n 1) (n m 1) (n m)!m!m!(n m)!m

n

对排列Pnm：若m = n时称为全排列，m < n时称为选排列。排列和组合的最基本恒等式有：

mPnm m!Cnmn m,Cn Cnmmm 1,Cn Cn 1 Cn 1

例2-1-3.3 将computer的字母全部取出进行全排列，其中c不在第一位，r不在末位，问共有多少种排法？

解：computer字母的全排列数为P88 8!，其中c排在第一位的排法共有7！种，r排在末位的排法共有7！，除去这些不合要求的排法，还有8！-（7！＋7！）= 30240种，然而这还不是答案，因为c在第一位的7！种排法中r可能排至末位的7！中c可能排在第一位，即c在第一位，r在末位的排法被减去了两次，实际上应该只减一次，故把不应该减的加回去才能得到正确的答案。所求的答案为：

。 P88 2P77 P66 30960（种）

离散数学四大核心：代数系统、集合论、数理逻辑、图论。

这种分析问题的方法称为“多退少补法”，这种思想在“包含排斥原理”中还要用到。

例2-1-3.4 将1 , 2 , 3三个数字排成2行3列的矩阵，要求同行和同列上都没有相同的数字，问这样的数字矩阵有多少？（实际上这就是集合{1 , 2 , 3 }到自身上的一些双射或置换，这些双射不允许一个元素以自身为像）

解： 先排矩阵的第一行共有P33 3! 6种排法，如果不管题目的要求，第二行也有6种排法，由乘法原理，知共有6×6＝36种矩阵。这些矩阵包含了有一列数字相同的情况，有两列因而就有三列数字相同的情况，按题目要求这些矩阵都应该除去，这些矩阵

112的个数可如下计算：一列数字相同其余两列数字不同的矩阵数有C3C3P2种；有两列数

字相同从而就有三列数字相同的矩阵数有3！＝6个，因此所求的矩阵个数为

112P33 P33 C3C3P2 P33 12。

m是从n个元素中任意取m个元素（不重复抽取）的排列与组合，但是有些Pnm与Cn

实际问题需要在n个元素中重复抽取若干个元素来排列，如用0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9这十个数字来编制代码，，每个号码就可以重复使用某个数字。一般地，从n个元素的集合中抽取m个元素，允许重复的排列数为：nm。实际上可以设想有m个位子，每个位子都可以放上n个元素中的任一个，允许

m

重复，由乘法原理即知有×n× = n m 种排法。

例2-1-3.5 求电子计算机中的6位二进制数。

解：电子计算机中的数码第一位数不能为0，故首位必须为1，后面五位每位都可选0或1，固有25 32种排法，因而6位二进制数有32个。

例2-1-3.6 考试时有25个正确或错误的问题，学生也可能不作答，问有多少种不同的考试结果？

解：对每一问题的回答有三种情况：正确、错误和不作答，因而考试结果共有325个。

m关于重复组合数Hn的计算问题。先从一个实例来研究它的计算公式，从{1 , 2 , 3}

中每次取出两个（允许重复抽取）的组合按自然数顺序写出来（即枚举）为：

11 , 12 , 13 , 22 , 23 , 33 (a)

现将各种组合分别加上01，就得到

12 , 13 , 14 , 23 , 24 , 34 (b)

离散数学四大核心：代数系统、集合论、数理逻辑、图论。

(b)中的6个组合恰好是从{1 , 2 , 3 , 4}中任取两个元素不重复的组合情况。反之从(b)中的组合中分别减去01即得(a)，说明(a) 与(b)存在1—1对应关系（双射），因而从三个相异元素中任取两个的重复组合数可化为从四个相异元素中任取两个不重复的组合数

222m来计算，即H3一般地计算Hn仿上面的讨论，即从{1 , 2 , , C3 (2 1) C4 6得到。

n}中任取m个允许重复的每一个组合，将其元素分别加上0 , 1 , 2 , , m-1即变成从{1 ,

mm2 , , n , n +1 , , n + (m-1) }中任取m个不重复的组合，故Hn Cn m 1。

例2-1-3.7 求成自然序的四位数码个数。

解：四位数码是从{0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9}中选四个数字组成，数字可以重复使用，由于规定自然顺序，故只有一种排法，因而变为10个相异元素中任取四个允许

444重复的组合问题，所求个数为 H10 C10 (4 1) C13 715。

关于环状排列问题，由于环状排列旋转后仍是同一种排列，故可以令其中任一个元素固定位置，不让它移动，其余n-1个元素任意排列，因而n个相异元素的环状排列数为（n-1）!，它恰好为n个相异元素的全排列数n!被n除的结果，这种想法可以推广到不尽相异元素的排列情形。

例2-1-3.8 8为朋友围圆桌而坐，若座位不编号有多少种坐法？座位编号又有多少种坐法？

座位不编号为环状排列问题，有

7！= 5040种坐法。

座位编号为非环状排列问题，故有

8！= 40320 种坐法。

例2-1-3.9 5颗红珠，3颗白珠穿在一个项链上，有多少种方法？

解：如果只穿在一条线上就是不尽相异元素的全排列问题。排列数为

现在项链上是环状排列问题，因而穿法为

三、容斥原理

设集合A = { a1 , a2 , , an }，它含有n 个元素，可以说集合A的基数是n，记作CardA = n。基数是表示集合中所含元素多少的量。如果集合A的基数是n ，可记为|A| = n , 这时称A为有穷集，显然空集的基数是0，即|Φ| = 0。如果A不是有穷集，则称A为无穷集。

8! 56。5!3!56 7种。 8

离散数学四大核心：代数系统、集合论、数理逻辑、图论。

容斥原理也称包含与排斥原理或逐步淘汰原则，它也是“多退少补”计数思想的应用。

定理2-1-3.1 (容斥原理) 设A , B 为有限集合，则

A B A B A B。

证明：① 当A , B不相交，即A B 时，A B A B

② 当A B 时

A A A B ， B B A B 所以，A B A B 2A B

但是， A B A B A B

因此， A B A B A B

定理2-1-3.2 设A , B是有限集合，则 A B A B 2A B。

证明：

A B (A B) (A B) A B A B (A B A B) A B

A B 2A B

例2-1-3.10 假设10名青年中有5名是工人，7名是学生，其中既是工人又是学生的青年有3名，问既不是工人又不是学生的青年的有几名？

解：设该10名青年组成集合Y，|Y|=10,其中工人集合设为W，|W|=5；学生集合设为S,| S|=7。|W∩S|=3，又因为Y (W S) ( )

所以 Y W S 10

即 10 W S 10 (W S W S) 10 (5 7 3) 1 因此，既不是工人又不是学生的青年有1人。

这个例子的计算过程用到了容斥原理。一般，令有限集A的元素具有m个不同的性质P1 , P2 , , Pm 。A中具有性质Pi 的元素组成子集记为A i i = 1 , 2 , , m ；A i∩A j（i≠j）表示A中同时具有性质Pi和Pj的元素组成的子集；A i∩A j∩A k（i≠j≠k）表示A中同时具有性质Pi , P j , P k 的元素组成的子集； ；A 1 ∩ A 2 ∩ ∩A m 表示A中同时具有性质P 1 , P 2 , , P m 的元素组成的子集。i表示A中不具有性质Pi的元

离散数学四大核心：代数系统、集合论、数理逻辑、图论。

素组成的子集。那么包含排斥原理可以叙述为

定理2-1-3.3 （容斥原理的推广）A中不具有性质P1 , P 2 , , P m 的元素数是，

1 2 m A Ai

i 1m1 i j m A Aij

1 i j k m mAi Aj Ak ( 1)A1 A2 Am

12m注意：上式右边共 1 Cm Cm Cm 2m 项

证明：等式左边是A中不具有性质P 1 , P 2 , , P m的元素数。下面我们要证明：对A中的任何元素a，如果它不具有这m条性质，那么它对等式右边的贡献是1；如果a至少具有这m条性质中的一条，那么它对等式右边的贡献是0。

设a不具有性质P 1 , P 2 , , P m，那么a Ai,i 1,2, ,m。对任何整数i和j，1 i j m，都有a Ai Aj。对任何整数i、j和k，1 i j k m，都有a Ai Aj Ak， ，a A1 A2 Am。但是a A，所以在等式右边的计数中它的贡献是： 1 – 0 + 0 – 0 +…+ (-1) m · 0 = 1 。

设a具有这m条性质中的k条性质，1 k m，则a对|A|的贡献是1；对 Ai的

i 1m

1贡献是Ck对 k；1 i j m Ai Aj的贡献是Ck2； ；对A1 A2 Am的贡献是Ckm,

所以a对等式右边计数的总贡献是：

11 Ck Ck2 ( 1)mCkm(k m)

k

kk C C C ( 1)C ( 1)jCkj (1 1)k 0 ﹟ 0

k1k2kk

j 0

推论 A中至少具有m个性质之一的元素个数为

A1 A2 Am Ai

i 1m1 i jm A Aij

1 i j k m Ai Aj Ak ( 1)m 1A1 A2 Am

证明： 因为 A1 A2 Am A (A1 A2 Am) A (1 2 m) 所以 A1 A2 Am A 1 2 m Ai

i 1mi1 i j m A Aj

离散数学四大核心：代数系统、集合论、数理逻辑、图论。

1 i j m Ai Aj Ak ( 1)m 1A1 A2 Am 。

例2-1-3.11 试求不超过1000的自然数中能被2或3或5整除的数的个数。 解：设A = {1 , 2 , , 1000 }，这是研究对象的集合，在A上定义性质P1 , P 2 , P3 。对任意n∈A，若n具有性质P 1 (P 2 , P 3) 当且仅当2|n (3|n , 5|n )。令A i为A中具有性质Pi 的数组成的子集，i = 1 , 2 , 3，则

A 1 = {2 , 4 , 6 , , 1000 } = {2 k | k = 1 , 2 , , 500 }，

1000] }， 3

1000] }。 A 3 = {5 , 10 , 15 , , 1000 } = { 5 k | k = 1 , 2 , , [5A 2 = {3 , 6 , 9 , , 999 } = {3 k| k = 1 , 2 , , [

1000 1000 1000 于是，|A 1 |= = 500 ，|A | = = 333 ，|A| = 2 3 3 5 = 200 。 2

1000 1000 而 A1 A2 {6kk 1,2, , } 166； 6 6

1000 1000 A1 A3 {10kk 1,2, , ； } 10 10010

1000 1000 A2 A3 {15kk 1,2, , } 66； 15 15

1000 1000 A1 A2 A3 {30kk 1,2, , } 33。 30 30

由定理2-1-3.3推论知

|A 1 ∪A 2∪ A 3 | = (500 + 333 + 200 ) - ( 166 + 100 + 66 ) + 33 = 1033 – 332 + 33 = 734。

所以，不超过1000的自然数中，至少能被2，3，5之一整除的数共有734个。

例2-1-3.12 某汽车工厂装配了三十辆汽车，可供选择的设备是收录机，空调器，防盗器，三十辆汽车中有15辆汽车装有收录机，8辆装有空调器，8辆装有防盗器，三种设备都具有的汽车有3辆，问这三种设备都没有的汽车有几辆？

解： 设 A 1 , A 2 , A 3 分别表示具有收录机，空调器，防盗器的汽车的集合。由题设知

|A 1 | = 15 ，|A 2 | = 8，|A 3 | = 8，| A 1∩A 2∩ A 3 | = 3。

由定理2-1-3.3推论知，

| A 1∪A 2∪ A 3 | = 15 + 8 + 8 - ( |A 1∩A 2| + |A 1∩A 3 | + |A 2∩ A 3 | ) + 3

离散数学四大核心：代数系统、集合论、数理逻辑、图论。

= 34- ( |A 1∩A 2| + |A 1∩A 3 | + |A 2∩ A 3 | ) 。

|A 1∩A 2| ≥|A 1∩A 2∩ A 3 |＝3，

|A 1∩A 3 | ≥|A 1∩A 2∩ A 3 |＝3，

|A 2∩ A 3 | ≥|A 1∩A 2∩ A 3 |＝3，

所以，| A 1∪A 2∪ A 3 | ≤ 34 - (3 + 3 + 3) ＝25，

故 1 2 3 A A1 A2 A3 30 25 5，

即三种设备都没有的汽车至少有5辆。

第2-2章 二元关系

在现实世界中，事物不是孤立的，事物之间都有联系，单值依赖联系是事物之间联系中比较简单的，比如说日常生活中事物的成对出现，而这种成对出现的事物具有一定的顺序，例如，上、下；大、小；左、右；父、子；高、矮等等。通过这种联系，研究事物的运动规律或状态变化。世界是复杂的，运动也是复杂的，事物之间的联系形式是各种各样的，不仅有单值依赖关系，更有多值依赖关系。“关系”这个概念就提供了一种描述事物多值依赖的数学工具。这样，集合，映射关系等概念是描述自然现象及其相互联系的有力工具，为建立系统的、技术过程的数学模型提供了描述工具和研究方法。映射是关系的一种特例。

系统地研究“关系”这个概念及其数学性质，是本章的任务。本章将通过笛卡尔积的给出关系的数学定义，特别给出关系的几种等价定义和常用性质、二元关系的运算，特别研究了计算机科学中具有重要应用的关系闭包运算、等价关系和偏序关系。等价关系和偏序关系不仅在计算机科学中，而且在数学中都是极为重要的。

§2-2-1 集合的笛卡尔积

一、 序 偶

定义2-2-1.1 由两个元素x 和y（允许x = y）按一定的顺序排列成的二元组叫做有序对（也称序偶），记作< x , y > 。其中x是它的第一元素，y是它的第二元素。

上述例子可表示为<上，下>；<大，小>；<左，右>；<父，子>；<高，矮>等。平面直角坐标系中点的坐标就是有序对，如<1 , -1> , <-1 , 1> , <1 , 1> , <2 , 0> , 代表着不同的点。

离散数学四大核心：代数系统、集合论、数理逻辑、图论。

一般来说序偶具有以下特点：

定义2-2-1.1序偶可以看成是两个具有固定次序的客体组成的有序对，常常用它来表达两个客体之间的关系，它与一般集合不同的是序偶具有确定的次序。在集合中{ a , b } = { b , a }，但对序偶< a , b > ≠ < b , a >（这里a≠b）。

2.两个序偶相等，< x , y > = < u , v >, 当且仅当 x = u ， y = v 。

3.序偶< a , b >中两个元素不一定来自同一集合，它们可以代表不同类型的事物。如a代表操作码，b代表地址码，则序偶< a , b >代表一条单地址指令；当然也可以用b代表操作码，a代表地址码，则序偶< a , b >也代表一条单地址指令。但上述约定，已经确定，序偶的次序就不能再变化了。

在实际问题中，有时会用到有序3元组，有序4元组， ，有序n元组。

定义2-2-1.2 一个有序n元组（n≥3）是一个序偶，其中第一个元素是一个有序n-1元组，第二个元素是一个客体。一个有序n元组记作< x1 , x 2 , , x n >，

即< x1 , x 2 , , x n > = << x1 , x 2 , , x n-1 > , x n >。

由序偶相等的定义，<< x , y > , z > = << u , v> , w > 当且仅当 < x , y > = < u , v> , z = w, 也即

x = u , y = v , z = w。应该注意的是：当x ≠ y时，< x , y , z > ≠ < y , x , z > 。<< x , y > , z > ≠ <x , < y , z> >，因为<x , < y , z> >不是三元组。

<< x1 , x 2 , , x n-1 > , x n > = << y1 , y 2 , , y n-1 > , y n >

(x1 = y1)∧(x 2 = y2 )∧(x n-1 = yn-1)∧(x n = y n )。

二、笛卡尔积

定义2-2-1.3 设A , B为任意两个集合，则称集合

B。 { x,y (x A) (y B)}为A , B的笛卡尔积，记为A×

即 A×B = { x,y (x A) (y B)}。

注意：2-1-1.A×B与A , B的次序有关，一般地 A×B≠B×A，即交换律不成立。

2.若A S , B S 则 A B,A B,A B,A B,都是S的子集，但是A B S。

3.对任意集合A ,有 A A 。

4.笛卡尔积不满足结合律，即(A B) C A (B C)

实际上，当A ≠ Φ , B ≠ Φ , C ≠ Φ 时，

本文来源：https://www.bwwdw.com/article/x0lj.html