01-离散数学基本原理-离散数学讲义-海南大学(共十一讲)

Example 1.4 Let A={a, b, c, d, e}, B={a, b, e, g, h} ,

C={b, d, e, g, h, k, m, n}. Verify theorem 3.

Solution:

A?B ?C={a, b, c, d, e , g, h, k, m, n}, A?B={a, b, e}, A?C={b, d, e}, B?C={b, e, g, h}, and A?B?C={b, e} |A|=5, |B|=5, |C|=8, | A?B ?C|=10, | A?B|=3, |A?C|=3, | B?C|=4, | A?B ?C |=2.

|A|+|B|+|C|-|A?B|-|B?C|-|A?C|+|A?B ?C| =5+5+8-3-3-4+2=10=| A?B ?C| Theorem 3 is verified.

推论Corrallory

|A?B?C|?|U|?|A|?|B|?|C|?|A?B|?|A?C|?|B?C|?|A?B?C|

Example How many positive integers are there which is less than 1000 and not divided by 5, 6 or 8.

1000以内不能被5，6，或8整除的正整数有多少个？

Solution

Let U denote the set of positive integers less than 1000. Let A, B, C denote the subset of U in which the integers are divided, respectively, by 5, by 6, and by 8. Then |U|=1000,

|A|=200, |B|= 166, |C|=125.

|A?B|?33, |A?C|?25, |B?C|?41,

|A?B?C|?8.

|A?B?C|?1000?200?166?125?33?25?41?8 ?600Hence there are 600 positive integers less than 1000, not divided by 5, 6, or 8.

1.3序列Sequences 1.3.1序列sequence

序列：以一定次序排列的事物

A sequence is simply a list of objects arranged in a definite order

a1,a2,a3,?

到第n个元素终止的序列叫有限finite序列，否则是无限infnite序列。

递归recursived 序列

递归：用前一项定义后一项的方法叫递归，recursive. 递归定义必须先定义第一项。

Example

c1?5, cn?2cn?1，2?n?6，

递归定义序列5，10，20，40，80，160.

字符串string

字符或符号组成的序列叫字符串String

序列所对应的集合

The set corresponding to a sequence

即：序列中的数字或符号组成的集合。

数组array, 线性表linear list有限序列在计算机中的表示

1.3.2特征函数Characteristic Function

If A is a subset of a universe U, A的特征函数 the characteristic function fA of A is defined for each

x?U,

1fA(x)?{ if

x?A 0

Theorem 4. 特征函数的性质Properties of characteristic functions

x?A(a) fA?B?fAfB,

that is fA?B(x)?fA(x)fB(x) , for all x. (b)fA?B?fA?fB?fAfB, that is

fA?B(x)?fA(x)?fB(x)?fA(x)fB(x)for all x.

(c)

fA?B?fA?fB?2fAfB, that is，

fA?B(x)?fA(x)?fB(x)?2fA(x)fB(x) , for all x.

1.3.3特征函数的应用

集合在计算机中的表示

Computer Representation of Sets

计算机中用序列sequence来表示一个集合, 序列由集合的全体元素以一定次序排列而成。

子集在计算机中的表示

Computer Representation of Subsets

如果A是一个有限全集U的一个子集，A的特征函数给出一个0，1序

列可以作为A的表示。 序列的长=|U|。

例 U={1,2,3,4,5,6}, A={1,2}, B={2,4,6}, C={4,5,6} 则

fU?111111,fA?110000,fB?010101 ,fC?000111,

U 1 1 A 1 1 B 0 1 C 0 0 1 0 0 0 1 0 1 1 1 0 0 1 1 0 1 1

可数countable,不可数uncountable

一个集合称为可数的countable, 如果它是某个序列对应的集合，否则

就是不可数uncountable集合。

可数集合的全体元素可以一个一个地数出来，第一个，第二个，第三

个，……。有限集合都是可数集合。However, not all infinite sets are countable. 无限集合并不都是可数的。

实数集合就是不可数集合。

康托Cantor第一个用对角线方法给出证明。 只要证明（0，1）区间内的实数不可数。

反证：假设（0，1）区间内的实数可数，则有一个序列d1d2d3?dn?

列出（0，1）区间内所有的实数。每个i十进制小数表示：

?N, 0

d1?0a11a12a13?

d22122d3.?0.aa?0.aaa23?

3132a33?

?

其中每个0?aij?9。

可以取到一个实数d?0.b1b2b3?bn?

bn?{ if

1不难看出

2ann?1o.w

，dd?(0,1)，对任意n?N?dn。

这与d1d2d3?dn? 列出（0，1）区间内所有的实数矛盾。因此（0，1）区间内的实数不可数，全体实数不可数。

1.3.4字符串和正则表达式

Strings and Regular Expressions

设A是一个字符集合alphabet, 由A中字符组成的有限字符串叫A的单词word，A的全体单词包括空串empty sequence or empty string（不含字符的串）组成的集合记作A*。

字符串的连接catenation