大学线性代数课件

1、大学线性代数课件第三篇第三篇 集集 合合 论论Set Theory2/63大学线性代数课件主要内容主要内容n第4章 集合4.1 集合的概念与表示4.2 集合的运算4.3 Venn氏图及容斥原理4.4 集合的划分4.5 自然数集与数学归纳法n第5章 二元关系二元关系n第6章 函数大学线性代数课件第4章 集合（Set）4/63大学线性代数课件4.1 集合的概念与表示集合的概念与表示n集合的概念又称为类、族或搜集是数学中最基本的概念之一不可精确定义(原始概念原始概念)集合的描述n笼统地说，一些可以互相区分的任意对象对象(统称为元素元素)聚集在一起形成的整体就叫做集合，用大写的英文字母表示，如A，Bn

2、这些对象对象就是这个集合的元素(或称成员) ，一般用小写字母表示，如a，b集合中的元素不计次序不计次序na,b,c,a=c,b,a,d集合中的元素不计重度不计重度nx,y,x =x,y =x,x,x,y5/63大学线性代数课件n元素与集合的关系a是集合A的一个元素, 则记为aA，读做“a属于A”, 或说“a在A中”a不是集合A的一个元素, 则记为aA，读做“a不属于A”, 或说“a不在A中”集合的元素可以是一个集合n例：A=a,b,c,a,b则a,bA且a,b A6/63大学线性代数课件有限集与无限集n定义定义4.1.1 设A是一个集合。用A或#A表示A含有的元素的个数，称做A的基数，或阶。若

3、#A =0，则称为空集；否则称为非空集。若#A为一非负整数，则称A为有限集；否则称为无限集。例： nA=a,b,a, bn|A|=3；|A|=11.基数为n的非空有限集称为n元(或n阶)集合7/63大学线性代数课件空集与全集n显然，空集是不含有任何元素的有限集，常用符号 表示n定义定义4.1.2 全集全集恒用E表示，是指包含了讨论中涉及的全体元素的特殊集合n全集也是有相对性的，不同的问题有不同的全集，即使是同一个问题也可以有不同的全集8/63大学线性代数课件集合的比较运算n定义定义4.1.3 集合相等(外延公理外延公理)两个集合A和B相等, 即A=B, 当且仅当它们有相同的成员A = B x(

4、xAxB) x(xAxB)x(xBxA)否则，用AB表示集合A和B不相等，即 A B x(xAxB) n定义定义4.1.4 设A和B是集合, 如果A的每一元素是B的一个元素, 那么A是B的子集子集,也称B是A的母集(或称扩集)，记为AB, 读做“B包含A”或“A包含于B”,即 ABx(xAxB)9/63大学线性代数课件集合的比较运算n定理定理4.1.1设A和B是集合, A=B当且仅当A B和BA（ 的反对称性）证明：证明： ABBA x(xAxB)x(xBxA) x(xAxB)(xBxA) x(xAxB) A=B10/63大学线性代数课件集合的比较运算n定义定义4.1.5 设A和B是集合, 如

5、果AB且AB, 那么称A是B的真子集真子集,记作AB , 读作“B真包含A”或“A真包含于B”,即A BA BABx(xAxB)x(xAxB)x(xAxB)(x(xAxB)x(xBxA)(x(xAxB)x(xAxB)(x(xAxB) x(xBxA) x(xAxB) x(xB x A)11/63大学线性代数课件n集合的表示列举法n将集合中的元素一一列出，写在大括号内nA=1, 2, 3, 4， B=a,b,c,d，C=,-4,-2,0,2,4,谓词描述法谓词描述法(指定原理)n用谓词公式谓词公式描述元素的共同属性n一般形式：S=a|P(a)表示aS当且仅当P(a)是真A=a|aI0aa5, a|

6、aI1a50nA=x|P(x)， B=x|Q(x)若P(x)Q(x)，则A = B若P(x)Q(x)，则A B递归定义法完全列举部分列举S被称为谓词P的广延广延集合应该是充分定义(良定)的12/63大学线性代数课件递归定义法(归纳定义)n用这种方法定义一个非空集合A时，一般应包括以下三个部分： 基本项 已知某些元素(常用S0表示由这些元素组成的非空集合)属于A，即S0 A 。这是构造A的基础，并保证非空。 递归项 给出一组规则，从A中(已获得的)元素出发，依照这些规则所获得的元素，仍然是A中的元素。这是构造A的关键部分。 极小化 如果集合S A也满足和，则S = A 。这说明， A中的每个元素

7、都可以通过有限次使用和来获得(或称A是满足条款(1)和(2)的最小集合)，它保证所构造出的集合A是唯一的。谁是谁不是13/63大学线性代数课件)3(0|yxyxxS 同样集合S能归纳地定义如下： (1) (基础)3S; (2) (归纳)如果xS和yS, 那么x+yS; (3) (极小性)S的元素都是由有限次应用条款(1)和(2)得出的。 例n如果全集是整数集合I, 那么能为3 整除的正整数集合S的谓词定义如下:14/63大学线性代数课件字母表与串n设表示一个有限的非空的符号(字符)集合、我们称为字母表。由字母表中有限个字符拼接起来的符号串叫做字母表上的一个字(或叫串)例(a) 如果=a,b,

8、, z, 那么is, then都是上的字(b) 如果=你, 我, 人, 工, , 是, 那么“你是工人”是上的串(c) 如果=a, b, , z,_, 这里“_”是代表空白。那么that_was_long_ago是上的串, 习惯上印成that was long ago(d) 如果=0,1, 那么000,010,011010等都是上的串15/63大学线性代数课件nx是上的一个字, 如果x=a1a2an, （nN, 1in, ai）, 那么x中的符号个数n称为x的长度, 记为xn长度为0的串叫做空串空串，记为(或)nx和y都是在上的符号串，x连结连结(或叫并置并置, 毗连毗连)y, 记为xyx=a

9、1a2an，y=b1b2bm 则 xy=a1a2anb1b2bmx=则 xy=ynz=xyx是z的词头词头, y是z的词尾词尾如果xz, 称x为真词头真词头如果yz,称y为真词尾真词尾如果w=xyz, 则y是w的子串子串, 如果yw,称y为真子串真子串16/63大学线性代数课件n设是一个字母表, 上的非空串非空串的集合+定义如下：(1) (基础)如果a, 那么a+；(2) (归纳)如果x+且a, 那么ax+；(3) (极小性)所有集合+的元素仅能由有限次应用条款(1)和(2)构成。n集合+包含长度为1, 2, 3, 的串, 所以是无限集合。然而, 在+中没有一个串包含无限数目的符号, 这是极小

10、性条款限制的结果n例：例：=a,b+=a,b, aa,ab,ba,bb,aaa,aab,17/63大学线性代数课件n设是字母表, 上的所有有限符号串的集合*定义如下：(1) (基础)*；(2) (归纳)如果x*和a, 那么ax*； (3) (极小性)所有集合*的元素, 仅能有限次应用条款(1)和条款(2)构成。n*=+n例例=a,b, *=,a,b,aa,ab,18/63大学线性代数课件n例例 :算术表达式集合设集合仅包含整数，一元运算+和-， 二元运算+、 -、 *、/(1) (基础) 如果D=0, 1, 2, 3, 4, 5, 6, 7, 8, 9和xD+, 那么x是一算术表达式。(2)

11、(归纳) 如果x和y都是算术表达式, 那么(i) (+x) 是一算术表达式 (ii) (-x) 是一算术表达式(iii) (x+y)是一算术表达式(iv) (x-y)是一算术表达式 (v) (x*y)是一算术表达式(vi) (x/y) 是一算术表达式(3) (极小性)一个符号序列是一算术表达式当且仅当它能由有限次应用条款(1)和(2)得到19/63大学线性代数课件小结n递归定义(1) 基础条款(简称基础)n已知哪些元素属于集合(2) 归纳条款(简称归纳)n一般为一些递推规则 (3) 极小性条款(简称极小性)n断言一个事物仅能有限次应用基础和归纳条款构成n其它形式(i) 集合S是满足基础和归纳条

12、款的最小集合(ii) 如果T是S的子集, 使T满足基础和归纳条款, 那么T=S20/63大学线性代数课件集合比较运算的基本事实n定理定理4.1.2 设A、B和C是任意三个集合，则有 A AE AA （ 的自反性）若AB且BC, 则AC（ 的传递性）若AB且B C, 则A C若A=B, 则B = A(1)若A=B且B = C, 则A = C21/63大学线性代数课件证明：证明： (1) x, x永假, 所以 xxA永真 A(2) x, xE永真, 所以xAxE永真 AE(4) 若AB且 BC则对x ExA xB xC即 AC得证22/63大学线性代数课件练习n设A=a,a,a,b,a,b,c,

13、判断下面命题的真值 aA A A aa,b,c aA a,ba,b,c a,bA a,ba,b,c ca,b,c (cA)(a )23/63大学线性代数课件幂集n定义定义4.1.6 A是集合，由A的所有子集构成的集合，称之为A的幂集幂集。记作P(A)或2AP(A) =B| BA例(a) A= P(A)= (b) A=a,bP(A)= , a, b, a, b A是任意集合nAP(A)nP(A)24/63大学线性代数课件例n设A=P(a, )判断下列结论是否正确(1) A(2) A(3) A，(4) A(5) aA(6) aA,(7) aA(8) aA解解：(1)，(2)，(3)，(4)，(7)

14、是正确的n若| A|=n，则|P(A) |=？解解: : |P(A) |= 2n 25/63大学线性代数课件n定理定理4.1.3 设是有限集，则：|2A| = 2|A|n幂集元素的编码例：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,c S000 S001 S010 S011 S100 S101 S110 S111若a,b,c,d，则： n S9 =

15、？ S9 =a,dna,c,d=S？a,c,d= S1011 = S1126/63大学线性代数课件练习n1.设A=， B=P(P(A)，则以下哪些是真命题？(1) B (2)B(3)B (4) B (5)B (6)B解： P(A)= , B = , , , , 对一般集合A，有：aAaAaP(A)n2.证明：AB iff P(A)P(B)27/63大学线性代数课件运算共性的研究(如何理解一个新的运算)运算运算基本概念基本概念基本性质基本性质一元运算：对合律等二元运算：交换律、结合律等与比较运算的关系与比较运算的关系与其他运算的关系与其他运算的关系对性质的封闭性28/63大学线性代数课件证明：A

16、B iff P(A)P(B)n必要性：AB时 根据指定原理，为了证明P(A)P(B)，只需证明： S SP(A) SP(B)P(A)P(B)n充分性：P(A)P(B)时 x xA xB AB SA SB (A)的成员都是(B)的成员A的子集都是B的子集xA 或证：因为A P(A) 所以A P(B) 自己补充完整29/63大学线性代数课件罗素悖论n1901年罗素(Bertrand Russell)提出不存在集合S=A|A是集合，且AA证明：假设S是一个集合，则以下两种情况有且仅有一种出现：(1) SS ，这时由S的定义知SS(2) SS ，这时由S的定义知SS总之，恒有 SS iff SS矛盾，

17、所以S不可能是一个集合一个“集合”, 如S, 它能导致矛盾，称为非良定非良定的的30/63大学线性代数课件4.2 集合的运算n定义定义4.2.1 设A和B是集合(a) A和B的并记为AB AB=x|xAxBxAB xAxB(b) A和B的交记为AB AB=x|xAxB xAB xAxB(c) A和B的差, 或B关于A的相对补, 记为A-BA-B=x|xAxB xA-B xAxB(d) A和B对称差,记为AB AB = x|xAxBxAB xA xB绝对补:E-A31/63大学线性代数课件例n例例4.2.1 若取E0,1,2,3,4,5，A1,2,4及B2,5，则有： AB 1,2,4,5， A

18、B 2， A-B 1,4，A B 1,4,5， A c0,3,5， B c0,1,3,4。n例例4.2.2 设是一个字母表，用n表示上全体长度为n的串组成的集合(n)，则：*012 +*1232/63大学线性代数课件n定义定义4.2.2 如果A和B是集合, AB= , 那么称A和B是不相交的。如果C是一个集合的族, 使C的任意两个不同元素都不相交, 那么C是(两两)不相交集合的族。例：四个集合：1,2,3、4、5,6和7,8,9,10是两两互不相交的n定理定理4.2.1 设A 、 B和C是三个集合，则有 A A B ， B A B ； A B A ， A B B ； A - B A ； 若A

19、B ，则B c A c ； 若A C且B C ，则A B C ； 若A B且A C ，则A B C 。 特别重要特别重要 1.子集之并仍为子集子集之并仍为子集 2.扩集之交仍为扩集扩集之交仍为扩集33/63大学线性代数课件n定理定理4.2.2 设A 、 B 、 C和D是四个集合，且A B ， C D ，则 A C B D ； A C B D 。n定理定理4.2.3 设A和B是两个集合，则下面三个关系式互相等价。 A B ； A B B ； A B A 。 n集合运算的基本恒等式集合运算的基本恒等式 (集合运算基本律集合运算基本律) P98-P9934/63大学线性代数课件集合等式与不等式证明的

20、一般方法(1)试证明： A(AB) = A 方法1： A(AB) = (AE)(AB) = A(EB) = AE = A不足：强调技巧，不规范 死记公式 难以推广应用方法2：显然，AA(AB)；另一方面，AA且ABA 故A(AB)A。总之， A(AB) = A 。适用于子集之并为子集、母集之交为母集的问题引用集合运算基本律引用集合运算基本律35/63大学线性代数课件集合等式与不等式证明的一般方法(2)依据指定原理依据指定原理n根据指定原理，为了证明A=B(A、B为集合表达式)，只需证明： x xA xB 为了证明AB，只需证明： x xA xBn这样集合等式与不等式的证明转变成谓词公式等价与蕴

21、含的证明了。证明谓词公式等价与蕴含可采用等价变换或逻辑推证。n一般而言，等价变换比逻辑推证有明显优点。n但等价变换也有缺点。36/63大学线性代数课件集合等式与不等式证明的一般方法(3)n证明：P(AB) = P(A)P(B) 证：(等价变换) S SP(AB) SP(A)P(B)依据指定原理依据指定原理 SAB SP(A)SP(B) SASB？证：一方面，因为ABA，ABB所以P(AB)P(A)， P(AB)P(B)从而P(AB)P(A)P(B)另一方面，SP(A)P(B)，即 SP(A)且SP(B)来说，有SA且SB所以SAB，即SP(AB)这表明P(A)P(B)P(AB)(逻辑推证)思考

22、:P(AB) = P(A)P(B)？37/63大学线性代数课件集合等式与不等式证明的一般方法(4)试证明：A(B-A) = 证明：x xA(B-A) xAxB-A xAxBxA x A(B-A) = 注意到空集被定义为矛盾式的广延，所以这个证明可以简化。反证法反证法假若不然，即x：x A(B-A)这说明xA，且xB-A与B-A的定义相矛盾38/63大学线性代数课件总结(集合等式与不等式证明的一般方法)n引用集合运算基本律p子集之并仍为子集子集之并仍为子集p扩集之交仍为扩集扩集之交仍为扩集n指定原理p等价变换等价变换(例4.2.5，定理5.1.3、5.4.5的证明)p逻辑推证逻辑推证(例4.2.

23、4)n反证法p主要适用于证明某集合表达式为空集的情形主要适用于证明某集合表达式为空集的情形39/63大学线性代数课件n文氏图文氏图 ( ( Venn diagram ) )A AB BA AB BA A-B B= =A A-A AB B4.3 Venn氏图及容斥原理氏图及容斥原理40/63大学线性代数课件容斥原理BAMBAMBAMBAM3210|AB|= |M1|+ |M2|+ |M3|= |B|- |AB|+ |A|- |AB|+ |AB|= |A| + |B| - |AB|由A和B生成的最小集合 41/63大学线性代数课件容斥原理n定理定理 4.3.1 设A和B都是有限集合|BABABA|

24、2| )(|2|)| |,min(|AAPBABABABABABABA42/63大学线性代数课件例n在20名青年有10名是公司职员,12名是学生,其中5名既是职员又是学生,问有几名既不是职员,又不是学生？解 设职员和学生的集合分别是A和B。由已知条件A=10, B =12, AB=5AB=A+B-AB=10+12-5=17则有3名既不是职员又不是学生31720|BAUBA43/63大学线性代数课件n三个集合的容斥定理|ABC|=|A|+|B|+|C|-|AB|-|AC|-|BC|+|ABC| n例：某研究所有170名职工，其中120人会英语，80人会法语，60人会日语，50人会英语和法语，25

25、人会英语和日语，30人会法语和日语，10人会英语、日语和法语。问有多少人不会这三种语言？解：令U为全集，E、F、J分别为会英语、法语和日语人的集合|U|=170，|E|=120， |F|=80， |J|=60， |EF|=50 ，|EJ|=25，|FJ|=30， |EFJ|=10|EFJ|=|E|+|F|+|J|-|EF|-|EJ|-|FJ|+|EFJ| = 120806050253010165|U-(EFJ)|=170-165=5 即有5人不会这三种语言44/63大学线性代数课件容斥原理n定理定理4.3.2 设1,2,n是n个有限集，则nnnkjikjinjijiniinAAAAAAAAAA

26、AA.(-1). . |.21211 -11145/63大学线性代数课件4.4 集合的划分集合的划分n定义定义4.4.1 划分给定非空集合A和非空集合族=A1,A2,Am,如果A= A1A2AmAiAj= 或Ai=Aj(i,j=1,2,m)称集合族为集合A的一个划分划分(分割分割 )划分的元素Ai称为划分的块块(Block) 如果划分是有限集合,则不同块的个数即#叫划分的秩秩n定义定义4.4.2 覆盖给定非空集合A和非空集合族=A1,A2,Am,如果A= A1A2Am称集合族为集合A的一个覆盖覆盖46/63大学线性代数课件关于集合的划分的理解n划分中的每一块是非空的n划分中的任意两块没有公共元

27、素(两两互不相交)nA的一个划分耗尽了A中的所有元素n例 设S=1,2,3A= 1,2,2,3B= 1,1,2,1,3C= 1,2,3D= 1,2,3E= 1,2,3F= 1,1,2最小(粗)划分最大(细)划分47/63大学线性代数课件交叉划分n定义定义4.4.3 若11,2,r和21,2,t是集合的两个不同划分，则称所有使ij 者(i=1,2,r；j=1,2,t)组成之集： ij(i1j2ij)为1和2的交叉划分。 48/63大学线性代数课件交叉划分n例例4.4.3 设集合表示某个单位全体具有高级职称的职工之集划分11,2n1集合中的男职工之集n2 集合中的女职工之集划分21,2,3n1集合

28、B中的老年职工之集n2 集合B中的中年职工之集n3 集合B中的青年职工之集A1A2B1B2B3n 定理定理4.4.1 集合的划分1和2的交叉划分是集合的划分。 49/63大学线性代数课件集合的划分n定义定义4.4.4 若11,2,r和21,2,t是集合的两个划分，若对于每一个i1都存在j2使得ij，则称1精分2，或称1是2的加细。若1精分2且存在i1和j2使得ij(即12)，则称1真精分2 。50/63大学线性代数课件集合的划分n定理定理4.4.2 集合的划分1和2的交叉划分精分1和2 证明证明: 设11,2,r,21,2,t ，并设1和2的交叉划分为。 则对任意，必有i 1和j 2使得i j

29、 ，显然i ，j ，即精分1和2 。51/63大学线性代数课件第二类Stirling数 n给定集合的划分并不是唯一的 n有多少种不同的方法将一n元集合划分成若干个块？n定义定义4.4.5 将一n元集划分成k块的方法数称为第二类Stirling数，用S(n,k)表示 对于任意的自然数n，当kn时，有S(n,k)0，且S(n,1)1，S(n,n)1 52/63大学线性代数课件第二类Stirling数n定理定理4.4.3 S(n,2)n-1-1，其中n2 n定理定理4.4.4 S(n,k)S(n-1,k-1)+kS(n-1,k)，其中2kn 证明证明 设a1,a2,an-1,an是一n元集合。注意中

30、元素an在的k划分中的情况，情况1： an单独构成一块，则a1,a2,an-1必须划分成k-1块，其方法数为S(n-1,k-1)；情况2： an与其它元素一起构成一块。则a1,a2,an-1必须划分成k块， an可加入其中的任一块，共有kS(n-1,k)种方法。 总之，S(n,k)S(n-1,k-1)+kS(n-1,k)。 53/63大学线性代数课件4.5 自然数集与数学归纳法自然数集与数学归纳法n自然数的定义公理化方法构造化方法 n应用后继集合的概念归纳定义n定义定义 4.5.1 设A是任意集合, A的后继集合后继集合记为A+, 定义为 A+= AA称A+为A的后继的同时，也常说A是A+的前

31、趋 例例(a) a,b的后继集合：a,ba,b=a,b,a,b(b) 的后继集合： = , 54/63大学线性代数课件n定理定理4.5.1 设是一个集合，则 + ； + , ； +； +； + 。55/63大学线性代数课件自然数n自然数集合1908年Zermelo , , , , Von Neumann的方案0= ， 1=0+= ，2=1+= , n定义定义4.5.2 自然数N是如下集合：(1) (基础) ，这里 0= 。(2) (归纳)如果nN, 那么n+N。(3) (极小性)如果AN且满足条款(1)和(2)，那么A=N。56/63大学线性代数课件n自然数系统满足以下Peano公理(1) 0

32、N, (2) 如果nN, 则恰存在一个n的后继者n+N, (3) 0 不是任何自然数的后继者, ;(4) 如果n+=m+, 那么n=m,(5) 如果A是N的子集, 使, (i) 0A; ;(ii) 如果nA, 那么n+A那么, A=N57/63大学线性代数课件归纳证明归纳证明n定理定理4.5.3 第一数学归纳法原理设P(n)是定义于I上的一项谓词，n0为一给定整数，为了证明n n0 ， P(n)皆为真，只需证明： P(n0)为真； k n0 ，若P(k) 为真，则P(k+)也为真证明证明：令A=n| nN 且 P(n+n0)为真往证在题设(1)和(2)成立时， A=N显然 AN，且由(1)知：

33、0A由(2)知：如果nA, 那么n+A由归纳原理A=N归纳变量58/63大学线性代数课件n第一数学归纳法证明步骤归纳基础：直接验证n=n0时，命题为真归纳步骤：对任意整数k n0 ，设n=k时命题为真（归纳假设），证明当n=k+1时命题也为真n例(1)证明对所有nN ,ninni02) 1(证明：证明：(1) n=0时0002) 10(00ii(2) 设n=k时，kikki02) 1(则n=k+1时，2)2)(1(12)1(1010kkkkkkiikiki59/63大学线性代数课件n例：设i0是一整数，令S=i| iI 且 i i0，证明：对于S的任一非空子集J，皆存在j0 J使得对于任意的j J有j0 j（称j0为J的最小元）注意注意：由于J可能是无限集合，因此不能直接对| J |进行归纳证明：任取m J ，令A=j| jJ 且 j m，则A J ， | A | m- i0 +1，又m A知A ，且