《中南大学线性代数课件.ppt》由会员分享，可在线阅读，更多相关《中南大学线性代数课件.ppt（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,b,a,d集合中的元素不计重度x,y
2、,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的非空有限集称为n元(或n阶)集合,空集与全集,显然，空集是不含有任何元素的有限集，常用符号
3、 表示定义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,读做“B包含A”或“A包含于B”,即 ABx(xAxB),集合的比较运算,定理4.1.1设A和B是集合,
4、A=B当且仅当A B和BA（的反对称性）证明：ABBA x(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),集合的表示列举法将集合中的元素一一列出，写在大括号内A=1,2,3,4，B=a,b,c,d，C=,-4,-2,0,2,4,谓词描述法(指定原理)用谓词公式描
5、述元素的共同属性一般形式：S=a|P(a)表示aS当且仅当P(a)是真A=a|aI0aa5,a|aI1a50A=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的基础，并保证非空。递归项 给出一组规则，从A中(已获得的)元素出发，依照这些规则所获得的元素，仍然是A中的元素。这是构造A的关键部分。极小化 如果集合S A也满足和，
6、则S=A。这说明，A中的每个元素都可以通过有限次使用和来获得(或称A是满足条款(1)和(2)的最小集合)，它保证所构造出的集合A是唯一的。,同样集合S能归纳地定义如下：(1)(基础)3S;(2)(归纳)如果xS和yS,那么x+yS;(3)(极小性)S的元素都是由有限次应用条款(1)和(2)得出的。,例,如果全集是整数集合I,那么能为3 整除的正整数集合S的谓词定义如下:,字母表与串,设表示一个有限的非空的符号(字符)集合、我们称为字母表。由字母表中有限个字符拼接起来的符号串叫做字母表上的一个字(或叫串)例(a)如果=a,b,z,那么is,then都是上的字(b)如果=你,我,人,工,是,那么“
7、你是工人”是上的串(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的串叫做空串，记为(或)x和y都是在上的符号串，x连结(或叫并置,毗连)y,记为xyx=a1a2an，y=b1b2bm 则 xy=a1a2anb1b2bmx=则 xy=yz=xyx是z的词头,y是z的词尾如果xz,称x为真词头如果yz,称y为真词尾如果w=xyz,
8、则y是w的子串,如果yw,称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)构成。*=+例=
9、a,b,*=,a,b,aa,ab,例:算术表达式集合设集合仅包含整数，一元运算+和-，二元运算+、-、*、/(1)(基础)如果D=0,1,2,3,4,5,6,7,8,9和xD+,那么x是一算术表达式。(2)(归纳)如果x和y都是算术表达式,那么(i)(+x)是一算术表达式(ii)(-x)是一算术表达式(iii)(x+y)是一算术表达式(iv)(x-y)是一算术表达式(v)(x*y)是一算术表达式(vi)(x/y)是一算术表达式(3)(极小性)一个符号序列是一算术表达式当且仅当它能由有限次应用条款(1)和(2)得到,小结,递归定义(1)基础条款(简称基础)已知哪些元素属于集合(2)归纳条款(简称
10、归纳)一般为一些递推规则(3)极小性条款(简称极小性)断言一个事物仅能有限次应用基础和归纳条款构成其它形式(i)集合S是满足基础和归纳条款的最小集合(ii)如果T是S的子集,使T满足基础和归纳条款,那么T=S,集合比较运算的基本事实,定理4.1.2 设A、B和C是任意三个集合，则有 A AE AA（的自反性）若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,判
11、断下面命题的真值 aA A A aa,b,c aA a,ba,b,c a,bA a,ba,b,c ca,b,c(cA)(a),幂集,定义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是任意集合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
12、|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 c b b,c a a,c a,b a,b,c S000 S001 S010 S011 S100 S101 S110 S111若a,b,c,d，则：S9=？S9=a,da,c,d=S？a,c,d=S1011=S11,练习,1.设A=，B=P(P(A)，则以下哪些是真命题？(1)B(2)B(3)B(4)B(5)B(6)B解：P(A)=,B=
13、,对一般集合A，有：aAaAaP(A)2.证明：AB iff P(A)P(B),运算共性的研究(如何理解一个新的运算),运算,基本概念,基本性质,一元运算：对合律等,二元运算：交换律、结合律等,与比较运算的关系,与其他运算的关系,对性质的封闭性,证明：AB iff P(A)P(B),必要性：AB时 根据指定原理，为了证明P(A)P(B)，只需证明：S SP(A)SP(B)P(A)P(B),充分性：P(A)P(B)时 x xA xB AB,SA,SB,(A)的成员都是(B)的成员,A的子集都是B的子集,xA,或证：因为A P(A)所以A P(B),自己补充完整,罗素悖论,1901年罗素(Bert
14、rand Russell)提出不存在集合S=A|A是集合，且AA证明：假设S是一个集合，则以下两种情况有且仅有一种出现：(1)SS，这时由S的定义知SS(2)SS，这时由S的定义知SS总之，恒有 SS iff SS矛盾，所以S不可能是一个集合一个“集合”,如S,它能导致矛盾，称为非良定的,4.2 集合的运算,定义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|xAxBx
15、AB xA xB,绝对补:E-A,例,例4.2.1 若取E0,1,2,3,4,5，A1,2,4及B2,5，则有：AB 1,2,4,5，AB 2，A-B 1,4，A B 1,4,5，A c0,3,5，B c0,1,3,4。例4.2.2 设是一个字母表，用n表示上全体长度为n的串组成的集合(n)，则：*012+*12,定义4.2.2 如果A和B是集合,AB=,那么称A和B是不相交的。如果C是一个集合的族,使C的任意两个不同元素都不相交,那么C是(两两)不相交集合的族。例：四个集合：1,2,3、4、5,6和7,8,9,10是两两互不相交的定理4.2.1 设A、B和C是三个集合，则有 A A B，B
16、A B；A B A，A B B；A-B A；若A B，则B c A c；若A C且B C，则A B C；若A B且A C，则A B C。,特别重要,定理4.2.2 设A、B、C和D是四个集合，且A B，C D，则 A C B D；A C B D。定理4.2.3 设A和B是两个集合，则下面三个关系式互相等价。A B；A B B；A B A。集合运算的基本恒等式(集合运算基本律)P98-P99,集合等式与不等式证明的一般方法(1),试证明：A(AB)=A 方法1：A(AB)=(AE)(AB)=A(EB)=AE=A,不足：强调技巧，不规范 死记公式 难以推广应用,方法2：显然，AA(AB)；另一方面
17、，AA且ABA 故A(AB)A。总之，A(AB)=A。,适用于子集之并为子集、母集之交为母集的问题,引用集合运算基本律,集合等式与不等式证明的一般方法(2),依据指定原理,根据指定原理，为了证明A=B(A、B为集合表达式)，只需证明：x xA xB 为了证明AB，只需证明：x xA xB这样集合等式与不等式的证明转变成谓词公式等价与蕴含的证明了。证明谓词公式等价与蕴含可采用等价变换或逻辑推证。一般而言，等价变换比逻辑推证有明显优点。但等价变换也有缺点。,集合等式与不等式证明的一般方法(3),证明：P(AB)=P(A)P(B)证：(等价变换)S SP(AB)SP(A)P(B),依据指定原理,SA
18、B,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),(逻辑推证),思考:P(AB)=P(A)P(B)？,集合等式与不等式证明的一般方法(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的定义相矛盾,
19、总结(集合等式与不等式证明的一般方法),引用集合运算基本律子集之并仍为子集扩集之交仍为扩集指定原理等价变换(例4.2.5，定理5.1.3、5.4.5的证明)逻辑推证(例4.2.4)反证法主要适用于证明某集合表达式为空集的情形,文氏图(Venn diagram),AB,AB,A-B,=A-AB,4.3 Venn氏图及容斥原理,容斥原理,|AB|=|M1|+|M2|+|M3|=|B|-|AB|+|A|-|AB|+|AB|=|A|+|B|-|AB|,由A和B生成的最小集合,容斥原理,定理 4.3.1 设A和B都是有限集合,例,在20名青年有10名是公司职员,12名是学生,其中5名既是职员又是学生,问
20、有几名既不是职员,又不是学生？解 设职员和学生的集合分别是A和B。由已知条件A=10,B=12,AB=5AB=A+B-AB=10+12-5=17则,有3名既不是职员又不是学生,三个集合的容斥定理|ABC|=|A|+|B|+|C|-|AB|-|AC|-|BC|+|ABC|例：某研究所有170名职工，其中120人会英语，80人会法语，60人会日语，50人会英语和法语，25人会英语和日语，30人会法语和日语，10人会英语、日语和法语。问有多少人不会这三种语言？解：令U为全集，E、F、J分别为会英语、法语和日语人的集合|U|=170，|E|=120，|F|=80，|J|=60，|EF|=50，|EJ|
21、=25，|FJ|=30，|EFJ|=10|EFJ|=|E|+|F|+|J|-|EF|-|EJ|-|FJ|+|EFJ|=120806050253010165|U-(EFJ)|=170-165=5 即有5人不会这三种语言,容斥原理,定理4.3.2 设1,2,n是n个有限集，则,4.4 集合的划分,定义4.4.1 划分给定非空集合A和非空集合族=A1,A2,Am,如果A=A1A2AmAiAj=或Ai=Aj(i,j=1,2,m)称集合族为集合A的一个划分(分割)划分的元素Ai称为划分的块(Block)如果划分是有限集合,则不同块的个数即#叫划分的秩定义4.4.2 覆盖给定非空集合A和非空集合族=A1,
22、A2,Am,如果A=A1A2Am称集合族为集合A的一个覆盖,关于集合的划分的理解,划分中的每一块是非空的划分中的任意两块没有公共元素(两两互不相交)A的一个划分耗尽了A中的所有元素例 设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,最小(粗)划分,最大(细)划分,交叉划分,定义4.4.3 若11,2,r和21,2,t是集合的两个不同划分，则称所有使ij 者(i=1,2,r；j=1,2,t)组成之集：ij(i1j2ij)为1和2的交叉划分。,交叉划分,例4.4.3 设集合表示某个单位全体具有高级职称的职工之集划分11,21集合中的
23、男职工之集2 集合中的女职工之集划分21,2,31集合B中的老年职工之集2 集合B中的中年职工之集3 集合B中的青年职工之集,A1,A2,B1,B2,B3,定理4.4.1 集合的划分1和2的交叉划分是集合的划分。,集合的划分,定义4.4.4 若11,2,r和21,2,t是集合的两个划分，若对于每一个i1都存在j2使得ij，则称1精分2，或称1是2的加细。若1精分2且存在i1和j2使得ij(即12)，则称1真精分2。,集合的划分,定理4.4.2 集合的划分1和2的交叉划分精分1和2 证明:设11,2,r,21,2,t，并设1和2的交叉划分为。则对任意，必有i 1和j 2使得i j，显然i，j，即
24、精分1和2。,第二类Stirling数,给定集合的划分并不是唯一的 有多少种不同的方法将一n元集合划分成若干个块？定义4.4.5 将一n元集划分成k块的方法数称为第二类Stirling数，用S(n,k)表示 对于任意的自然数n，当kn时，有S(n,k)0，且S(n,1)1，S(n,n)1,第二类Stirling数,定理4.4.3 S(n,2)n-1-1，其中n2 定理4.4.4 S(n,k)S(n-1,k-1)+kS(n-1,k)，其中2kn 证明 设a1,a2,an-1,an是一n元集合。注意中元素an在的k划分中的情况，情况1：an单独构成一块，则a1,a2,an-1必须划分成k-1块，其
25、方法数为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)。,4.5 自然数集与数学归纳法,自然数的定义公理化方法构造化方法 应用后继集合的概念归纳定义定义 4.5.1 设A是任意集合,A的后继集合记为A+,定义为 A+=AA称A+为A的后继的同时，也常说A是A+的前趋 例(a)a,b的后继集合：a,ba,b=a,b,a,b(b)的后继集合：=,定理4.5.1 设是一个集合，则+；+,；+；+；+。,自然数,自然数集合1908年Zerme
26、lo,Von Neumann的方案0=，1=0+=，2=1+=,定义4.5.2 自然数N是如下集合：(1)(基础)，这里 0=。(2)(归纳)如果nN,那么n+N。(3)(极小性)如果AN且满足条款(1)和(2)，那么A=N。,自然数系统满足以下Peano公理(1)0N,(2)如果nN,则恰存在一个n的后继者n+N,(3)0 不是任何自然数的后继者,;(4)如果n+=m+,那么n=m,(5)如果A是N的子集,使,(i)0A;(ii)如果nA,那么n+A那么,A=N,归纳证明,定理4.5.3 第一数学归纳法原理设P(n)是定义于I上的一项谓词，n0为一给定整数，为了证明n n0，P(n)皆为真，
27、只需证明：P(n0)为真；k n0，若P(k)为真，则P(k+)也为真证明：令A=n|nN 且 P(n+n0)为真往证在题设(1)和(2)成立时，A=N显然 AN，且由(1)知：0A由(2)知：如果nA,那么n+A由归纳原理A=N,第一数学归纳法证明步骤归纳基础：直接验证n=n0时，命题为真归纳步骤：对任意整数k n0，设n=k时命题为真（归纳假设），证明当n=k+1时命题也为真例证明对所有nN,证明：(1)n=0时,(2)设n=k时，,则n=k+1时，,例：设i0是一整数，令S=i|iI 且 i i0，证明：对于S的任一非空子集J，皆存在j0 J使得对于任意的j J有j0 j（称j0为J的最
28、小元）注意：由于J可能是无限集合，因此不能直接对|J|进行归纳证明：任取m J，令A=j|jJ 且 j m，则A J，|A|m-i0+1，又m A知A，且若A有最小元a，显然a必是J的最小元，故只需证A有最小元。(1)当|A|=1时，A中仅一个元素m，它就是A的最小元(2)设|A|=k时(k1)，命题成立，考虑|A|=k+1时的情况，设A=j1,j2,jk,jk+!，由于j1,j2,jk是k元集合，由归纳假设得它有最小元，设为j，则当j jk+!时，j是最小元，否则 jk+!是最小元。总之，A存在最小元。命题得证。,考虑下面的证明过程并指出问题证明：若n为自然数，则n+1=n.“证明”：对任意
29、的kN，假定n=k时命题为真，即k+1=k.从而(k+1)+1=k+1，即当n=k+1时命题也真.由第一数学归纳法，命题得证.证明世界上所有的人都同岁.“证明”：设世界上有n个人.(1)当n=1时，因为只有一个人，他和自己同岁，所以命题为真(2)因为n=1的情况已经证明过了，所以假定对任意的自然数k1，当n=k时命题为真，现考虑k+1个人，不妨设为a1,a2,ak,ak+1.根据假定，a1,a2,ak同岁，a2,ak,ak+1同岁，所以a1,a2,ak,ak+1都与a2同岁.即n=k+1时命题也真.由第一数学归纳法，命题得证,定理4.5.4 第二数学归纳法原理设P(n)是定义于I上的一项谓词，
30、n0为一给定整数，为了证明n n0，P(n)皆为真，只需证明：P(n0)为真；n n0，若k=n0,n0+1,n时P(k)皆为真，则P(n+)也为真证明：令J=n|nI，n n0 且 P(n)为假往证在题设(1)和(2)成立时，J=假若不然，已证J必有最小元j0.由(1)知：n0 J.故j0 n0,从而当k=n0,n0+1,j0-1时P(k)皆为真，由(2)知，P(j0)为真，与j0 J矛盾.,例：有数目相等的两堆棋子,两人轮流从任一堆里取几颗棋子,但不能不取也不能同时在两堆里取。规定凡取得最后一颗者胜。求证后取者可以必胜。证明 对每堆棋子数目n作归纳证明。为了便于叙述,设甲为先取者,乙为后取者。n=1时,甲必须在某堆中取一颗。于是另一堆中的一颗必为乙所得,乙胜。设nk时,后取者胜。现证n=k时也是后取者胜。设第一轮甲在某堆先取r颗,0rk。乙在另一堆中也取r颗。则：(1)若rk,经过两人各取一次之后,两堆都只有k-r颗,k-rk,现在又是甲先取,根据归纳假设乙胜。(2)若r=k,显然是乙胜。证毕,练习,证明：对于任意n8，必存在非负整数s和t，使得n=3s+5t Fibonacci数列定义为F0=0,F1=1,Fn+2=Fn+1+Fn(nN)证明：若n1，则,
