离散数学之集合论(4)

设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 ≠ Φ 时，