中南university线性代数演示课件.pptVIP

第三篇 集 合 论Set Theory;主要内容 第4章 集合 4.1 集合的概念与表示 4.2 集合的运算 4.3 Venn氏图及容斥原理 4.4 集合的划分 4.5 自然数集与数学归纳法 第5章 二元关系 第6章 函数;第4章 集合（Set）;4.1 集合的概念与表示;元素与集合的关系 a是集合A的一个元素, 则记为a∈A，读做“a属于A”, 或说“a在A中” a不是集合A的一个元素, 则记为a?A，读做“a不属于A”, 或说“a不在A中” 集合的元素可以是一个集合 例：A={a,b,c,{a,b}} 则{a,b}∈A且{a,b} ?A;有限集与无限集;空集与全集;集合的比较运算;集合的比较运算;集合的比较运算;集合的表示 列举法 将集合中的元素一一列出，写在大括号内 A={1, 2, 3, 4}， B={a,b,c,d}，C={…,-4,-2,0,2,4,…} 谓词描述法(指定原理) 用谓词公式描述元素的共同属性 一般形式： S={a|P(a)}表示a∈S当且仅当P(a)是真 A={a|a∈I∧0＜a∧a＜5}, {a|a∈I∧1≤a≤50} A={x|P(x)}， B={x|Q(x)} 若P(x)?Q(x)，则A = B 若P(x)?Q(x)，则A ? B 递归定义法;递归定义法(归纳定义); 同样集合S能归纳地定义如下： (1) (基础)3∈S; (2) (归纳)如果x∈S和y∈S, 那么x+y∈S; (3) (极小性)S的元素都是由有限次应用条款(1)和(2)得出的。 ;字母表与串;x是Σ上的一个字, 如果x=a1a2…an, （n∈N, 1≤i≤n, ai∈Σ）, 那么x中的符号个数n称为x的长度, 记为‖x‖ 长度为0的串叫做空串，记为Λ(或ε) x和y都是在Σ上的符号串，x连结(或叫并置, 毗连)y, 记为xy x=a1a2…an，y=b1b2…bm 则 xy=a1a2…anb1b2…bm x=Λ则 xy=y z=xy x是z的词头, y是z的词尾 如果x≠z, 称x为真词头 如果y≠z,称y为真词尾 如果w=xyz, 则y是w的子串, 如果y≠w,称y为真子串;设Σ是一个字母表, Σ上的非空串的集合Σ+定义如下： (1) (基础)如果a∈Σ, 那么a∈Σ+； (2) (归纳)如果x∈Σ+且a∈Σ, 那么ax∈Σ+； (3) (极小性)所有集合Σ+的元素仅能由有限次应用条款(1)和(2)构成。 集合Σ+包含长度为1, 2, 3, …的串, 所以是无限集合。然而, 在Σ+中没有一个串包含无限数目的符号, 这是极小性条款限制的结果 例：Σ={a,b} Σ+={a,b, aa,ab,ba,bb,aaa,aab,…};设Σ是字母表, Σ上的所有有限符号串的集合Σ*定义如下： (1) (基础)Λ∈Σ*； (2) (归纳)如果x∈Σ*和a∈Σ, 那么ax∈Σ*； (3) (极小性)所有集合Σ*的元素, 仅能有限次应用条款(1)和条款(2)构成。 Σ*=Σ+∪{Λ} 例 Σ={a,b}, Σ*={Λ,a,b,aa,ab,…};例 :算术表达式集合 设集合仅包含整数，一元运算+和-， 二元运算+、 -、 *、/ (1) (基础) 如果D={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}和x∈D+, 那么x是一算术表达式。 (2) (归纳) 如果x和y都是算术表达式, 那么 (i) (+x) 是一算术表达式 (ii) (-x) 是一算术表达式 (iii) (x+y)是一算术表达式 (iv) (x-y)是一算术表达式 (v) (x*y)是一算术表达式 (vi) (x/y) 是一算术表达式 (3) (极小性)一个符号序列是一算术表达式当且仅当它能由有限次应用条款(1)和(2)得到;小结;集合比较运算的基本事实;证明： (1) ?x, x∈Φ永假, 所以 x∈Φ→x?A永真 ? Φ?A (2) ?x, x∈E永真, 所以x?A→x?E永真 ? A?E (4) 若A?B且 B?C 则对?x ∈E x∈A ? x∈B ? x∈C 即 A?C 得证 ;练习;幂集;例;定理4.1.3 设Ａ是有限集，则：|2A| = 2|A| 幂集元素的编码 例：Ａ＝{a,b,c} P(A)={Φ,{c},{b},{b,c},{a},{a,c},{a,b},{a,b,c}} 八个子集分别表示成：S0, S1, S2, S3, S4, S5, S6, S7 下标写成二进制形式：S000,S001,S010,S011,S100,S101,S110,S111 Φ