文档介绍：Chapter 3 Set Theory
Wen-Hsiang Lu (盧文祥)
Department puter Science and Information Engineering,
National Cheng Kung University
2007/03/19
1
Chap 3 Set Theory
Set and Subsets
Set: should be a well-defined collection of objects.
Elements (members): These objects are called elements or members of the set.
Capital letters represent sets: A, B, C lowercase letters represent elements: x, y
.,
A set can be designated by listing its elements within set braces.
., A = {1, 2, 3, 4, 5}, B = {x | x is an integer, and 1 ≤ x ≤ 5}
Cardinality (size): |A| denotes the number of elements in A.
2
Chap 3 Set Theory
Set and Subsets
Universe (Universe of discourse): Ų denotes the range of all elements to form any set.
Definition : If C and D are sets from a universe Ų
Subset: , if every element of C is an element of D.
Proper subset: , if, in addition, D contains an element that is not in C.
3
Chap 3 Set Theory
Set and Subsets
Definition : The sets C and D are equal for a given universe Ų,
Let A, B, C Ų,
Let Ų = {1, 2, 3, 4, 5} with A = {1, 2, 3}, B = {3, 4}, and C = {1, 2, 3, 4}. Then the following subset relations hold:
4
Chap 3 Set Theory
Set and Subsets
Null set (empty set), or { }: is the set containing no elements.
Power set, P(A): is the collection (set) of all subsets of the set A from universe Ų.
Example: A = {1, 2, 3}
P(A) = {Φ, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, A}
For any finite set A with |A|=n
A has 2n subsets and |P(A)|= 2n
There are subsets of size k, 0≤k≤n
Counting the subsets of A (binomial theorem)
5
Chap 3 Set Theory
Set and Subsets
Gray code: There is exactly one bit that changes from one binary string to the next one.
0 Φ
1 {x}
(a)
00 0 Φ
10 0 {x}
11 0 {x, y}
01 0 {y}
01 1 {y, z}
11 1 {x, y, z}
10 1 {x, z}
00 1 {z} (c)
000
100
110
010
011
111
101
001 (d)
000
010
011
001
101
111
110
100 (e)
000
001
101
100
110
010
011
111 (f)
0 0 Φ
1 0 {x}
1 1 {x, y}
0 1 {y}
(b)
Another Gray code
6
Chap 3 Set Theory
Se