《中南大学线性代数课件》由会员分享，可在线阅读，更多相关《中南大学线性代数课件（63页珍藏版）》请在金锄头文库上搜索。
1、第三篇 集 合 论 Set Theory,主要内容 第4章 集合 4.1 集合的概念与表示 4.2 集合的运算 4.3 Venn氏图及容斥原理 4.4 集合的划分 4.5 自然数集与数学归纳法 第5章 二元关系 第6章 函数,第4章 集合（Set）,4.1 集合的概念与表示,集合的概念 又称为类、族或搜集 是数学中最基本的概念之一 不可精确定义(原始概念) 集合的描述 笼统地说，一些可以互相区分的任意对象(统称为元素)聚集在一起形成的整体就叫做集合，用大写的英文字母表示，如A，B 这些对象就是这个集合的元素(或称成员) ，一般用小写字母表示，如a，b 集合中的元素不计次序 a,b,c,a=c,
2、b,a,d 集合中的元素不计重度 x,y,x =x,y =x,x,x,y,元素与集合的关系 a是集合A的一个元素, 则记为aA，读做“a属于A”, 或说“a在A中” a不是集合A的一个元素, 则记为aA，读做“a不属于A”, 或说“a不在A中” 集合的元素可以是一个集合 例：A=a,b,c,a,b 则a,bA且a,b A,有限集与无限集,定义4.1.1 设A是一个集合。 用A或#A表示A含有的元素的个数，称做A的基数，或阶。 若#A =0，则称为空集；否则称为非空集。 若#A为一非负整数，则称A为有限集；否则称为无限集。 例： A=a,b,a, b |A|=3；|A|=1 基数为n的非空有限集
3、称为n元(或n阶)集合,空集与全集,显然，空集是不含有任何元素的有限集，常用符号 表示定义4.1.2 全集 恒用E表示，是指包含了讨论中涉及的全体元素的特殊集合 全集也是有相对性的，不同的问题有不同的全集，即使是同一个问题也可以有不同的全集,集合的比较运算,定义4.1.3 集合相等(外延公理) 两个集合A和B相等, 即A=B, 当且仅当它们有相同的成员A = B x(xAxB)x(xAxB)x(xBxA) 否则，用AB表示集合A和B不相等，即A B x(xAxB) 定义4.1.4 设A和B是集合, 如果A的每一元素是B的一个元素, 那么A是B的子集,也称B是A的母集(或称扩集)，记为AB, 读
4、做“B包含A”或“A包含于B”,即ABx(xAxB),集合的比较运算,定理4.1.1设A和B是集合, A=B当且仅当A B和BA（ 的反对称性） 证明：ABBAx(xAxB)x(xBxA)x(xAxB)(xBxA)x(xAxB) A=B,集合的比较运算,定义4.1.5 设A和B是集合, 如果AB且AB, 那么称A是B的真子集,记作AB , 读作“B真包含A”或“A真包含于B”,即ABA BABx(xAxB)x(xAxB)x(xAxB)(x(xAxB)x(xBxA)(x(xAxB)x(xAxB)(x(xAxB) x(xBxA) x(xAxB) x(xBxA),集合的表示 列举法 将集合中的元素一
5、一列出，写在大括号内 A=1, 2, 3, 4， B=a,b,c,d，C=,-4,-2,0,2,4, 谓词描述法(指定原理) 用谓词公式描述元素的共同属性 一般形式： S=a|P(a)表示aS当且仅当P(a)是真 A=a|aI0aa5, a|aI1a50 A=x|P(x)， B=x|Q(x) 若P(x)Q(x)，则A = B 若P(x)Q(x)，则A B 递归定义法,S被称为谓词P的广延,集合应该是充分定义(良定)的,递归定义法(归纳定义),用这种方法定义一个非空集合A时，一般应包括以下三个部分： 基本项已知某些元素(常用S0表示由这些元素组成的非空集合)属于A，即S0 A 。这是构造A的基础
6、，并保证非空。 递归项给出一组规则，从A中(已获得的)元素出发，依照这些规则所获得的元素，仍然是A中的元素。这是构造A的关键部分。 极小化如果集合S A也满足和，则S = A 。这说明， A中的每个元素都可以通过有限次使用和来获得(或称A是满足条款(1)和(2)的最小集合)，它保证所构造出的集合A是唯一的。,同样集合S能归纳地定义如下：(1) (基础)3S;(2) (归纳)如果xS和yS, 那么x+yS;(3) (极小性)S的元素都是由有限次应用条款(1)和(2)得出的。,例,如果全集是整数集合I, 那么能为3 整除的正整数集合S的谓词定义如下:,字母表与串,设表示一个有限的非空的符号(字符)
7、集合、我们称为字母表。由字母表中有限个字符拼接起来的符号串叫做字母表上的一个字(或叫串) 例 (a) 如果=a,b, , z, 那么is, then都是上的字 (b) 如果=你, 我, 人, 工, , 是, 那么“你是工人”是上的串 (c) 如果=a, b, , z,_, 这里“_”是代表空白。那么that_was_long_ago是上的串, 习惯上印成that was long ago (d) 如果=0,1, 那么000,010,011010等都是上的串,x是上的一个字, 如果x=a1a2an, （nN, 1in, ai）, 那么x中的符号个数n称为x的长度, 记为x 长度为0的串叫做空串，
8、记为(或) x和y都是在上的符号串，x连结(或叫并置, 毗连)y, 记为xy x=a1a2an，y=b1b2bm 则 xy=a1a2anb1b2bm x=则 xy=y z=xy x是z的词头, y是z的词尾 如果xz, 称x为真词头 如果yz,称y为真词尾 如果w=xyz, 则y是w的子串, 如果yw,称y为真子串,设是一个字母表, 上的非空串的集合+定义如下： (1) (基础)如果a, 那么a+； (2) (归纳)如果x+且a, 那么ax+； (3) (极小性)所有集合+的元素仅能由有限次应用条款(1)和(2)构成。 集合+包含长度为1, 2, 3, 的串, 所以是无限集合。然而, 在+中没
9、有一个串包含无限数目的符号, 这是极小性条款限制的结果 例：=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和xD+, 那么x是一算术表达式。 (2) (归纳) 如
10、果x和y都是算术表达式, 那么 (i) (+x) 是一算术表达式 (ii) (-x) 是一算术表达式 (iii) (x+y)是一算术表达式 (iv) (x-y)是一算术表达式 (v) (x*y)是一算术表达式 (vi) (x/y) 是一算术表达式 (3) (极小性)一个符号序列是一算术表达式当且仅当它能由有限次应用条款(1)和(2)得到,小结,递归定义 (1) 基础条款(简称基础) 已知哪些元素属于集合 (2) 归纳条款(简称归纳) 一般为一些递推规则(3) 极小性条款(简称极小性) 断言一个事物仅能有限次应用基础和归纳条款构成 其它形式 (i) 集合S是满足基础和归纳条款的最小集合 (ii)
11、 如果T是S的子集, 使T满足基础和归纳条款, 那么T=S,集合比较运算的基本事实,定理4.1.2 设A、B和C是任意三个集合，则有AAEAA （ 的自反性） 若AB且BC, 则AC（ 的传递性） 若AB且B C, 则A C 若A=B, 则B = A 若A=B且B = C, 则A = C,证明：(1) x, x永假, 所以 xxA永真 A(2) x, xE永真, 所以xAxE永真 AE(4) 若AB且 BC则对x ExA xB xC即 AC得证,练习,设A=a,a,a,b,a,b,c, 判断下面命题的真值 aA A A aa,b,c aA a,ba,b,c a,bA a,ba,b,c ca,b
12、,c (cA)(a ),幂集,定义4.1.6 A是集合，由A的所有子集构成的集合，称之为A的幂集。记作P(A)或2A P(A) =B| BA 例 (a) A= P(A)= (b) A=a,bP(A)= , a, b, a, b A是任意集合 AP(A) P(A),例,设A=P(a, )判断下列结论是否正确 (1) A (2) A (3) A， (4) A (5) aA (6) aA, (7) aA (8) aA 解：(1)，(2)，(3)，(4)，(7)是正确的若| A|=n，则|P(A) |=？ 解: |P(A) |= 2n,定理4.1.3 设是有限集，则：|2A| = 2|A| 幂集元素的
13、编码 例：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 c b b,c a a,c a,b a,b,cS000 S001 S010 S011 S100 S101 S110 S111 若a,b,c,d，则： S9 =？S9 =a,d a,c,d=S？a,c,d= S1011 = S11,练习,1.设A=， B=P(P(A)，则以下哪些是真命题？ (1) B (2)B (3)B (4) B (
14、5)B (6)B 解： P(A)= , B = , , , , 对一般集合A，有：aAaAaP(A)2.证明：AB iff P(A)P(B),运算共性的研究(如何理解一个新的运算),运算,基本概念,基本性质,一元运算：对合律等,二元运算：交换律、结合律等,与比较运算的关系,与其他运算的关系,对性质的封闭性,证明：AB iff P(A)P(B),必要性：AB时根据指定原理，为了证明P(A)P(B)，只需证明：SSP(A) SP(B)P(A)P(B),充分性：P(A)P(B)时xxA xBAB, SA,SB,(A)的成员都是(B)的成员,A的子集都是B的子集,xA,或证：因为A P(A)所以A P(B),
