S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,1
1.4 集合
Sets
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,2
集合 / Sets:
As a collection of some objects
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,3
DEFINITION 1,
The objects in a set are also called the elements,
or members,of the set,A set is said to contain its
elements.
Null Set,There are no anything in the set.
={x | x?P(x) ∧?(x?P(x) )}
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,4
EXAMPLE 1
The set V of all vowels in the English alphabet can
written as ----
V = {a,e,i,o,u},
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,5
EXAMPLE 2
The set O of odd positive integers less than 10 can be
expressed by
O = {1,3,5,7,9}.
O = {x | x >=1 ∧ x <=10 ∧ x is odd number}.
A = {a,b,c,…… n} 枚举法
A = {x | x?P(x)} 谓词公式法 /set builder
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,6
DEFINTION 2,
Two sets are equal if and only if they have the
same elements,Presented as A=B otherwise A? B
A = B x ( x? A? x? B)
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,7
EXAMPLE 5
The sets {1,3,5} and {3,5,1} are equal,since they
have the same elements,Note that the order in which the
elements of a set are listed does not matter,Note also that
it does not matter if an element of a set is listed more than
once,so that {1,3,3,3,5,5,5,5} is the same as the set {1,
3,5} since they have the same elements.
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,8
1、集合中的元素互异
2、集合中的元素无次序和大小之分
3、集合中的元素不一定同类
4、集合中的元素也可以是集合
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,9
DEFINITION 3,
The set A is said to be a subset of B if and only if
every element of A is also an element of B,We use the
notation A?B to indicate that A is a subset of the set B.
A是 B的子集、
B包含 A、
A包含在 B中
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,10
The set A is said to be a proper subset of B if A?B
and there is a?B and a?A
A是 B的真子集、
B真包含 A、
A真包含在 B中
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,11
定理 1,A = B 当且仅当 A? B? B? A
定理 2：对任意的集合 A,A? A
定理 3,对任意的集合 A,B,C，
如果 A? B,B? C，则 A? C
定理 4：对任意的集合 A,A
定理 5：空集?是唯一的
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,12
DEFINITION 3,
The set U is said to be a universal set,
U = {x | x?P(x) V?(x?P(x) )}
全集
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,13
DEFINITION 4,
Let S be a set,If there are exactly n distinct
elements in S where n is a nonnegative integer,we say
that S is a finite set and that n is the cardinality of S,
The cardinality of S is denoted by ∣ S∣,
集合的基、势
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,14
EXAMPLE 7
Let A be the set of odd positive integers less than
10,Then ︱ A︱ = 5
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,15
EXAMPLE 8
Let S be the set of letters in the English
alphabet,Then ︱ S︱ = 26
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,16
EXAMPLE 9
Since the null set has no elements,
it follows that ︱ ︱ = 0
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,17
DEFINITION 5,
A set is said to be infinite if it is not finite,
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,18
EXAMPLE 10
The set of positive integers is infinite.
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,19
DEFINITION 6,
Given a set S,the power set of S is the set of all subsets
of the set S,The power set of S is denoted by P(S).
幂集
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,20
EXAMPLE 11
What is the power set of the set {0,1,2}?
p({0,1,2}) = {,{0},{1},{2},{0,1},
{0,2},{1,2},{0,1,2}}.
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,21
EXAMPLE 12
What is the power set of the empty set? What is the
power set of the set {}?
P({ }) = {,{ }}.
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,22
DEFINITION 7,
The ordered n-tuple(a1,a2,…,an) is the ordered collection that
has a1 as its first element,a2 as its second element,…,and an as its
nth element.
有序 n元组 或 n元 有序组 (a1,a2,…,an)
n=2 (a1,a2)
有序对 /序偶 /ordered pairs
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,23
DEFINITION 8,
Let A and B be sets,The Cartesian product of A and
B,denoted by A × B,is the set of all ordered pairs (a,b)
where a∈ A and b∈ B,Hence,
A × B = {(a,b)∣ a∈ A∧ b∈ B}.
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,24
EXAMPLE 14
What is the Cartesian product of A = {1,
2} and B = {a,b,c}?
A × B = {(1,a),(1,b),(1,c),
(2,a),(2,b),(2,c)}
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,25
DEFINITION 9,
The Cartesian product of the sets A1,A2,…,An,denoted
by A1 × A2 × … × An,is the set of ordered n-tuples (a1,
a2,…,an),where ai belongs to Ai for i=1,2,….,n,In other
words
A1 × A2 × … × An = {(a1,a2,…,an) ∣ ai∈ Ai
for i=1,2,….,n}.
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,26
EXAMPLE 16
What is the Cartesian product A x B x C,
where A = {0,1},B = {1,2},and C = {0,1,2}?
A× B× C = {(0,1,0),(0,1,1),(0,1,2),
(0,2,0),(0,2,1),(0,2,2),
(1,1,0),(1,1,1),(1,1,2),
(1,2,0),(1,2,1),(1,2,2)}.
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,27
1.5 Set Operations
集合的运算
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,28
DEFINITION 1,
Let A and B be sets,The union of the sets A and B,
denoted by A∪ B,is the set that contains those elements
that are either in A or in B,or in both..
集合的并
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,29
DEFINITION 2,
Let A and B be sets,The intersection of the sets A and
B,denoted by A∩B,is the set containing those elements
in both A and B.
集合的交
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,30
DEFINITION 3,
Two sets are called disjoint if their intersection is
the empty set.
A∩B =? A与 B不相交
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,31
DEFINITION 4,
Let A and B be sets,The difference of A and B,denoted by
A﹣ B,is the set containing those elements that are in A but not in
B,The difference of A and B is also called the complement of B
with respect to A.
差集、补集、余集
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,32
DEFINITION 5,
Let U be the universal set.The complement of the set
A,denoted by,is the complement of A with respect
to U,In other words,the complement of the set A is
U﹣ A.
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,33
Venn diagram 文氏图
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,34
Table 1
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,35
命题演算的基本等值定理
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,36
EXAMPLE 11
Use set builder notation and logical equivalences to
show that =
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,37
Table 2
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,38
EXAMPLE 13
Let A,B,and C be sets,Show that
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,39
EXAMPLE 14
Let A = {0,2,4,6,8},B = {0,1,2,3,4},and C = {0,3,6,
9},What are A∪ B∪ C and A∩B∩C?
A∪ B∪ C={0,1,2,3,4,6,8,9}.
A∩B∩C= {0}.
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,40
证明两个集合相等的方法：
1、定义方法：谓词公式
2、相等定理：互相包含
3、集合相等运算：基本相等定理
4,Venn 图（文氏图）：图解
5、位运算
*6、特征函数
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,41
DEFINITION 6,
The union of a collection of sets is the set that contains
those elements that are members of at least one set in the
collection.
多个集合的并
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,42
DEFINITION 7,
The intersection of a collection of sets is the set that
contains those elements that are members of all the sets
in the collection.
多个集合的交
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,43
EXAMPLE 18
The bit strings for the sets {1,2,3,4,5} and (1,3,5,7,
9) are 11 1110 0000 and 10 1010 1010,respectively,Use
bit strings to find the union and intersection of these sets.
11 1110 0000∨ 10 1010 1010 = 11 1110 1010,
11 1101 0000∧ 10 1010 1010 = 10 1010 0000,
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,44
小 结
1、一些特殊集合
2、集合的运算
3、两个集合相等的证明
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,45
进一步的思考
2、集合概念的拓广：
有序集 (ordered sets)
重集 (multisets)
模糊集 (fuzzy sets)
可拓集 (extension sets)
1、集合概念的矛盾：
S = { x? x }
Russell’s paradox
pp45 ex26
S e t s
集合
7/31/2009 11:27 AM Deren Chen,Zhejiang Univ,46
练 习
pp,45 7,13,15
pp,54 12(e),31,36
其中 12（ e）用三种不同的方法证明
ex31,symmetric difference