离散数学课件第2章.ppt

2.1集合论的基本概念2.2集合上的运算2.3归纳法和自然数*2.4语言上的运算2.5集合的笛卡尔乘积,第2章 集合,2.1 集合论的基本概念2.1.1 集合的概念集合在某些场合又称为类、族或搜集，它是数学中最基本的概念之一，如同几何中的“点”、“线”等概念一样，不可精确定义，现描述如下:一个集合是能作为整体论述的事物的集体。,例如,(1)“高二(1)班的学生”是一集合。(2)硬币有两面正面和反面，“正面，反面”构成一集合。(3)计算机内存之全体单元构成一集合。(4)1，2，3，n，构成正整数集合。(5)所有三角形构成三角形集合。(6)坐标满足方程x2+y2R2的全部点构成图 2.1-1所示的点集。,图 2.1-1,组成集合的每个事物叫做这个集合的元素或成员。通常用大写字母A，B，C，代表集合;用小写字母a，b，c，代表元素。如果a是集合A的一个元素，则记为aA读做“a属于A”，或说“a在A中”。如果a不是集合A的一个元素，则记为a A读做“a不属于A”，或说“a不在A中”。,任一元素，对某一集合而言，或属于该集合，或不属于该集合，二者必居其一，不可兼得。通常采用3种方法表示集合。第一种是列举法。就是把集合中的元素一一列举出来。例如“所有小于5的正整数”这个集合的元素为1，2，3，4，除这4个元素外，再没有别的元素了。如果把这个集合命名为A，就可记为A=1，2，3，4 在能清楚表示集合成员的情况下可使用省略号，例如，从1 到50 的整数集合可记为1，2，3，50，偶数集合可记为,-4,-2,0,2,4,。,第二种是描述法。就是用谓词描述出集合元素的公共特征来表示这个集合。例如，上述各例可分别写成A=a|aI0aa5和 a|aI1a50，x|y(yIx=2y)这里I表示整数集合。一般地S=a|P(a)表示aS当且仅当P(a)是真。,比较这两种表示方法可以看出，列举法的好处是可以具体看清集合的元素;描述法的好处是刻画出了集合元素的共同特征。应用时可根据方便任意选用，不受限制。第三种是归纳定义法。该法我们将留待2.3节讨论。集合的元素可以是一个集合，例如A=a,b,c,D，而 D=0,1。仅含有一个元素的集合称为单元素集合。应把单元素集合与这个元素区别开来。例如A与A不同，A表示仅以A为元素的集合，而A对A而言仅是一个元素，当然这个元素也可以是一个集合，如A=1,2。,称含有有限个元素的集合为有限集合。称不是有限集合的集合为无限集合或无穷集。有限集合的元素个数称为该集合的基数或势。集合A的基数记为|A|，例如若 A=a，b，则|A|=2，又|A|=1两个集合怎样才算相等呢?以下外延公理给出了它的规定。外延公理 两个集合A和B相等，即A=B，当且仅当它们有相同的成员(也就是，A的每一元素是B的一个元素而B的每一元素也是A的一个元素)。,外延公理用逻辑符号可表达为 A=B x(xA xB)或 A=B x(xAxB)x(xBxA)外延公理断言:如果两个集合有相同的元素，那么不管集合是如何表示的，它们都相等。,因此,(1)列举法中，元素的次序是无关紧要的。例如x,y,z与z,x,y相等。(2)元素的重复出现无足轻重。例如，x,y,x、x,y、x,x,x,y是相同的集合。(3)集合的表示不是唯一的。例如，x|x2-3x+2=0、x|xI1x2和1，2均表示同一集合。,2.1.2 罗素悖论正如本章前言中所指出的，朴素集合论由于在定义集合的方法上缺乏限制会导致悖论，现在让我们考察一下这种悖论是如何产生的。我们通常遇到的集合，集合本身不能成为它自己的元素。例如a a，但有些集合，集合本身可以成为它自己的元素，例如考察概念的集合，因为它本身是一个概念，因此这个集合可以是它自己的一个元素。因此，断言AA和A A都是谓词，可以用来定义集合。,1901年罗素(Bertrand Russell)提出以下悖论:设论述域是所有集合的集合，并定义S为下述集合:S=A|A A 这样，S是不以自身为元素的全体集合的集合，我们现在问“S是不是它自己的元素?”假设S不是它自己的元素，那么S满足谓词A A，而该谓词定义了集合S，所以SS。另一方面，如果SS，那么S必须满足定义S的谓词，所以S S。这样，我们导致了一个类似于谎言悖论的矛盾:既非SS也非S S是真。一个“集合”，诸如S，它能导致矛盾，称为非良定的。,罗素悖论起因于不受限制的定义集合的方法，特别是集合可以是自己的元素的概念值得怀疑。康脱以后创立的许多公理化集合论都直接地或间接地限制集合成为它自己的元素，因而避免了罗素悖论。公理化集合论用某个方法避免了罗素悖论，但怎能确信没有其它悖论潜伏在这些形式结构中呢?回答是悲观的，业已证明，应用现今有效的数学技术，没有方法能证明新的悖论不会产生。关于悖论问题就简单地叙述至此。,2.1.3 集合间的包含关系两集合的相等关系已用外延公理定义，现在介绍两集合间的另一种关系包含。集合的包含定义如下:定义2.1-1 设A和B是集合，如果A的每一元素是B的一个元素，那么A是B的子集合，记为A B，读做“B包含A”或“A包含于B中”。用逻辑符表示为 A B xxAxB)A B有时也记作B A，称B是A的扩集。,定义2.1-2 如果A B且AB，那么称A是B的真子集，记作A B，读做“B真包含A”。用逻辑符表示为 要注意区分从属关系“”及包含关系“”。从属关系是集合元素与集合本身的关系，包含关系是集合与集合之间的关系。在前言中我们已指出:我们所讨论的全部集合和元素是限于某一论述域中的。因此，虽然这个论述域有时并没有明晰地指出，但表示集合元素的变元只能在该域中取值。论述域在本章常用U表示，有的书上称论述域为全集合。,定理 2.1-1 对任意集合A有A U。证 对任意元素x，xU是真，所以xAxU是真。由全称推广规则得x(xAxU)所以A U这是一个平凡证明的例子。,定理 2.1-2 设A和B是集合，A=B当且仅当A B和B A。证,推论 2.1-2 对任何集合A，恒有A A。定理 2.1-3 设A、B、C是集合，若A B且B C，则A C。证 设x是论述域中任意元素，因为所以xAxBxBxC,由前提三段论得xAxC由全称推广规则得 x(xAxC)即A C,定义 2.1-3 没有元素的集合叫空集或零集，记为。定理 2.1-4 对任意集合A有 证 设x是论述域中任意元素，则 x 常假，所以 无义地真，由全称推广规则得即,定理 2.1-5 空集是唯一的。证 设 和 都是空集，由定理2.1-4得 和，根据定理2.1-2得=。注意 与 不同，后者是以空集为元素的一个集合，前者没有元素。能用空集构造不同集合的无限序列。在序列中，每一集合除第一个外都确实有一元素，即序列中前面的集合。,在序列中，如果我们从0开始计算，则第i项有i个元素。这一序列的每一集合，以序列中在它之前的所有集合作为它的元素。,例 2.1-1(1)集合p,q有4个不同子集:p,q、p、q和，注意p p,q但pp,q，pp,q但p p,q。再者 p,q，但 p,q。(2)集合q是单元素集合，它的唯一元素是集合q。每一单元素集合恰有两个子集，q的子集是q和。一般地，n个元素的集合有2n个不同的子集合，我们在下一节将证明这一点。,习 题1.用列举法表示下列集合:(1)小于20的质数集合(2)构成词evening的字母集合(3)x|x2+x-6=0(4)真值构成的集合,2.用描述法表示下列集合:(1)1，2，3，79(2)奇整数集合(3)能被5 整除的整数集合(4)重言式集合3.列出下列集合的成员:(1)x|x是36的因子(2)x|x=ax=b(3)1，3，a,4.论述域是I，确定下列哪些集合是相等的:A=x|x2-1=15x3=1 B=0 C=x|y(yIx=2y)D=x|x2-6x+8=0 E=2x|xI F=4，2，4，2 G=x|x2+1=0 H=0，2，-2，4，-4，6，-6，,5.证明:若a，b，c和d是任意客体，则a，a,b=c，c,d当且仅当a=c和b=d。*6.小镇上唯一的理发师公开宣布:他仅给自己不刮脸的人刮脸，问谁给这位理发师刮脸?为什么这是一个悖论?7.列出下列集合的全部子集合:,8.证明推论2.1-2。9.设A、B和C是集合，如果AB和BC，AC可能吗?AC常真吗?试举例说明之。10.设A、B和C是集合，证明或否定以下断言:,11.指出下列各组集合中的集合有何不同，列出每一集合的元素和全部子集。12.A B且AB，这可能吗?证明你的断言。,13.确定下列各命题的真和假:,14.对任意集合A、B、C确定下列各命题是真或假:(1)如果AB及B C，则AC。(2)如果AB及B C，则A C。(3)如果A B及BC，则AC。(4)如果A B及BC，则A C。,2.2 集合上的运算集合上的运算是用给定的集合(叫运算对象)去指定一新的集合(叫运算结果)。我们将依次介绍常见的集合运算。如同前节一样，我们假定所有集合都是用(非明晰指定的)论述域U的元素构造的。,2.2.1 并、交和差运算定义 2.2-1 设A和B是集合。(1)A和B的并记为AB，是集合。AB=x|xAxB(2)A和B的交记为AB，是集合。AB=x|xAxB(3)A和B的差，或B关于A的相对补，记为A-B，是集合。A-B=x|xAx B,例 2.2-1 设A=a,b,c,d)和B=b,c,e，那么AB=a，b，c，d，e AB=b，cA-B=a，dB-A=e,定义 2.2-2 如果A和B是集合，AB=，那么称A和B是不相交的。如果C是一个集合的族，使C的任意两个不同元素都不相交，那么C是(两两)不相交集合的族。例 2.2-2 如果C=0，1，2，=i|iN，那么C是不相交集合的族。定理 2.2-1 集合的并和交运算是可交换和可结合的。也就是对任意A、B和C。(1)AB=BA(2)AB=BA(3)(AB)C=A(BC)(4)(AB)C=A(BC),我们仅证明(1)和(3)，(2)和(4)是类似的。证(1)设x是论述域U的任意元素，那么 xAB xAxB 的定义 xBxA的可交换性 xBA的定义因为x是任意的，得 x(xAB xBA)即AB=BA,(3)设x是任意元素，那么因为x是任意的，得出 x(xA(BC)x(AB)C)因此A(BC)=(AB)C,定理 2.2-2 对任意集合A、B和C有:(1)A(BC)=(AB)(AC)(2)A(BC)=(AB)(AC)即集合运算和，在上可分配，在上可分配。,证(1)设x是任意元素，那么因此，A(BC)=(AB)(AC)。,(2)部分的证明留作练习。定理 2.2-3 设A、B、C和D是论述域U的任意子集合，那么下列断言是真:,证(1)xAA xAxA xA，因此，AA=A。(3)xA xAx，因x 常假，于是xAx xA因此，xA xA。所以，A=A。(5)A-=x|xAx。但x 常真，因此，xAx xA，所以A-=x|xA=A，即A-=A。(6)xA-B xAx BxA。因此，xA-BxA，得A-B A。(7)设x是AC的任意元素，那么xAxC。现在分情况证明。,情况1:设xA，因为A B，得xB，所以xBxD，因此xBD。情况2:设xC，用与情况1相似的论证得xBD。因此，xAC，那么xBD。所以AC BD。(11)因A B，又B B根据(7)得AB BB，但BB=B，因此AB B。另一方面由(9)得B AB。所以，AB=B。其余部分的证明留作练习。,推论2.2-3(1)AU=U;(2)AU=A。本推论可由定理2.2-3的(11)、(12)部分得出。,2.2.2 补运算定义2.2-3 设U是论述域而A是U的子集。A的(绝对)补，记作，是集合=U-A=x|xUx A=x|x A。例 2.2-3(1)如果U=p,q,r,s和A=p,q，那么=r,s。(2)如果U=N和A=x|x0，那么=0。(3)如果U=I和A=2x+1|xI，那么=2x|xI。,定理 2.2-4 设A是某论述域U的任意子集，那么证,定理 2.2-5(补的唯一性)设A和B 是论述域U的子集，那么B=当且仅当AB=U和AB=。证 必要性从定理 2.2-4 直接得到。现证明充分性。设AB=和AB=U，那么,推论2.2-5(1)=U;(2)=。证 因U=U和U=，所以，=U和=。定理 2.2-6 设A是U的任意子集，那么=A。也就是说，A的补的补是A。证 因为 A=U和 A=，根据上一定理A是 的补，但 也是 的补，而补是唯一的，所以，=A。,定理2.2-7(德摩根定律)设A和B是U的任意子集，那么证 根据定理2.2-5，()是AB的补，但AB也是AB的补，而补是唯一的，所以AB=。(2)的证明是类似的，故略。,定理 2.2-8 设A、B是U的任意子集，若A B，则。证 由A B x(xAxB)知xAxB根据逆反律得x Bx A即x x x是任意的，所以 x(x x)即,当集合数目不多时，集合运算的结果能用文氏图表达出来。参看图2.2-1，图中长方形表示论述域，而以一定区域表示任意集合A、B和C，每一图形的阴影部分分别代表出现在各自下边的表达式。上边给出的定理和公式，都可联系文氏图形象地理解。,图 2.2-1,另外，根据并、交、补等定义，亦知命题演算中的、T、F等分别与集合论中的、U、等有对应关系，因此，有关它们的公式也有相似性。例如命题演算中有公式 集合论中有对应公式,又如命题演算中有范式等概念 PQR(PQR)(P QR)(PQR)如果需要，在集合论中也可引入范式等概念，使ABC=(ABC)(A C)(BC)注意到它们的相似性，有利于理解、记忆和引用。,2.2.3 并和交运算的扩展扩展后并和交运算都定义在集合的搜集上。定义 2.2-4 设C是某论述域子集的搜集。(1)C的成员的并，记为，是由下式指定的集合(2)如果C，C的成员的交，记为，是下式指定的集合:,定义说明如果x，那么x至少是一个子集SC的元素;如果x，那么x是每一个子集SC的元素。注意对的定义来说，C必须非空，否则，由于C=，蕴含式SCxS对每一S将是无义地真。这样,谓词 s(SCxS)对每一x是真。因此，所定义的集合就是全集合U。要求C，这个可能消除。,设D是一集合，如果给定D的任一元素d，就能确定一个集合Ad，那么d叫做Ad的索引，搜集C=Ad|dD叫做集合的加索引搜集;而D叫做搜集的索引集合。当D是一个搜集C的索引集合时，符号表示，而表示。如果加索引搜集C的索引集合是前n+1个自然数0，1，2，n，或全体自然数0，1，2，那么C的成员的并和交能用类似于和式概念的符号表示。,例如 一般地，索引集合不必是N的子集，可以是任意集合，例如R+。,例 2.2-4 设论述域是实数R。(1)如果C=1，2，4，3，4，5，4，6，那么,(2)我们用0，a)表示集合x|0 xa。,(3)设C=Ai|ip,q,r，其中Ap=2,3，Aq=3,4，Ar=4,6;a,b表示x|axb，那么,2.2.4 环和与环积定义 2.2-5 A、B两集合的环和记为AB，是集合 参看图 2.2-2。环和又叫对称差(Symmetric Difference)。,定理 2.2-9 证 因为,但所以，,推论 2.2-9(a)=AB，(b)AB=BA，(c)AA=。定理 2.2-10(AB)C=A(BC)。定理 2.2-11 C(AB)=(CA)(CB)。,以上两个定理留给读者自证。但注意并在环和上不可分配，环和在交上不可分配。即，通常 定义 2.2-6A、B两集合的环积记为AB，是集合。参看图 2.2-2。由定义即得出下述两定理。,图 2.2-2,定理 2.2-12(1)=AB，(2)AB=BA，(3)AA=U。定理 2.2-13 证 所以，,根据定理2.2-10 得两边取补，即得 定理 2.2-14 留给读者自证。,2.2.5 幂集合我们常常涉及以某个集合的子集为元素的集合，因此需要以下定义。定义 2.2-7 设A是一集合，A的幂集(A)是A的所有子集的集合，即(A)=B|B A 一个给定集合的幂集是唯一的，因此求一个集合的幂集是以集合为运算对象的一元运算。,例 2.2-5(1)如果A=，那么(A)=。(2)如果A=a,b，那么(A)=，a，b，a，b。(3)如果A是任意自然数集合，那么A(A)，(A)。,下面说明子集的二进制数表示和幂集合的个数。在集合的定义里，没有规定集合中元素的次序，但为了便于在计算机上表示集合，亦可给集合元素编定次序。例如，A=a,b,c，不妨认为a、b、c分别是第一、二、三个元素。于是可用三位二进制数做足标表示A的任意子集:二进制数的第i位表示第i个元素是否属于该子集，1表示属于，0 表示否。例如可用S101表示a,c，S011 表示b,c，三位二进制数可与其子集一一对应。因而(A)=Si|iJ，这里J=000,001,111。为了书写方便，可用十进制数代替二进制数，于是J=0,1，2，7。一般地，n个元素的集合A，可用n位二进制数与其子集一一对应。,因而(A)=Si|iJ，J=0，1，2，2n-1由此可知，n个元素的集合A，其幂集的元素个数是 2n。如果A是无限集，则(A)的元素个数也是无限的。,*2.2.6 有限集的计数定理 2.2-15 设A和B都是有限集合，则以下公式成立:,我们仅证明，其它都是明显的。证 A和B之间可能有公共元素，公共元素个数是|AB|，在计算|AB|时每个元素只计算一次，但在计算|A|+|B|时，公共元素计算了两次，一次是在计算|A|时，一次是在计算|B|时，因此，右边减去|AB|才能相等。证毕。,公式可以推广，三个集合时为如图 2.2-3所示。,图 2.2-3,一般地成立以下公式:,证 用归纳法证明(未学过归纳法的同学可在学完下节后，再看此证明)。n=2时，已证明成立，即|A1A2|=|A1|+|A2|-|A1A2|设n-1(n3)时公式成立，现证明n时也成立。,根据归纳假设得,例 2.2-6(1)在一个班级50个学生中，有 26 人在第一次考试中得到A，21人在第二次考试中得到A，假如有17 人两次考试都没有得到A，问有多少学生在两次考试中都得到A?解 设第一次考试得A的是集合A1，第二次考试得A的是集合A2，则|A1A2|=50-17=33但|A1A2|=|A1|+|A2|-|A1A2|所以|A1A2|=|A1|+|A2|-|A1A2|=26+21-33=14故两次考试都得A的有 14 人。,(2)某教研室有 30 名老师，可供他们选修的第二外语是日语、法语、德语。已知有 15 人进修日语，8 人选修法语，6 人选修德语，而且其中 3 人选修三门外语，我们希望知道至少有多少人一门也没有选修。解 设A1、A2、A3分别表示选修日语、法语和德语的人，因此,因为|A1A2|A1A2A3|A1A3|A1A2A3|A2A3|A1A2A3|我们得|A1A2A3|32-3-3-3=23即至多有 23 人在进修第二外语，因此至少有 7 人没有进修第二外语。,习 题1.给定自然数集合N的下列子集:,求出下列集合:,2.考察正整数集合I+的下列子集:,试用A、B、C、D和E表达下列集合:,3.设x和y是实数，定义运算xy是xy(x的y次幂)。(1)证明运算既非可交换的也非可结合的。(2)设*代表乘法运算，确定下列分配律哪些是成立的:,4.(1)对下列各式构造文氏图:(2)给出一公式，它表示图 2.2-4中各文氏图中的阴影部分。,图 2.2-4,5.设A、B、C是任意集合，把ABC表示为不相交集合之并。6.设A、B和C是集合。(1)证明如果C A且C B，那么C AB(也就是AB是包含A和B的最小集合)。(2)证明如果C A且C B，那么C AB(也就是AB是包含在A和B中的最大集合)。7.证明定理2.2-2的(2)。8.假定A 和AB=AC，证明这不能得出B=C，假设中增加AB=AC，你能得出B=C吗?,9.(1)证明“相对补”不是一个可交换运算，即证明存在一个论述域包含集合A和B，使A-BB-A。(2)A-B=B-A可能吗?刻画此式出现的全部条件。(3)“相对补”是一个可结合的运算吗?证明你的断言。10.证明定理2.2-3的其余部分。11.设A、B和C是论述域U的任意子集，证明下列各式:,16.设C是一非空的某论述域U的子集的搜集，证明下列德摩根定律的推广:17.设C是一非空的某论述域U的子集的搜集，B是U的子集，证明下列分配律的推广:,18.指出下列集合的幂集合:(1)a，b，c(2)a，b，c(3)设A=a，求A和(A)的幂集合。19.设Sn=a0，a1，an和Sn+1=a0，a1，an，an+1，试用(Sn)和an+1表达出(Sn+1)。,20.证明下列各式:*21.试决定在1 到 250 之间能被2、3、5、7任何一数整除的整数个数。*22.某班学生 50 人，会FORTRAN语言的40人，会ALGOL60语言的35人。会PL/1语言的10人，以上三门都会的5人，都不会的没有，问仅会两门的有几人?,2.3 归纳法和自然数2.3.1 集合的归纳定义我们在2.1节介绍了指定集合的两种最常用方法列举法和描述法。但仍然有许多集合难以用这两种方法表示出来，诸如算术表达式集合，命题演算公式集合，ALGOL程序集合等等，这些集合用归纳定义来指定较为方便。归纳定义习惯上称为递归定义。,一个集合的归纳定义由 3 部分组成:(1)基础条款(简称基础)。它指出某些事物属于集合。它的功能是给集合以基本元素，使所定义的集合非空。(2)归纳条款(简称归纳)。它指出由集合的已有元素构造新元素的方法。归纳条款的形式总是断言:如果事物 x,y,，z是集合的元素，那么用某种方法组合它们而成的一种新事物也在集合中。它的功能是指出为了构造集合的新元素，能够在事物上进行的运算。(3)极小性条款(简称极小性)。它断言一个事物除非能有限次应用基础和归纳条款构成外，那么这个事物不是集合的成员。,集合S的归纳定义的极小性条款还有其它形式，常见的有:(i)“集合S是满足基础和归纳条款的最小集合”。(ii)“如果T是S的子集，使T满足基础和归纳条款，那么T=S”。其意义是:S满足基础和归纳条款，但没有S的真子集满足它们。这些极小性条款虽然形式不同，结果是等价的，全部服务于一个目的，即指明所定义的集合是满足基础和归纳条款的最小集合，即通常所谓极小性。,例 2.3-1 如果论述域是整数I，那么能为3 整除的正整数集合S的谓词定义如下:S=x|x0 y(x=3y)同样集合能归纳地定义如下:(1)(基础)3S,(2)(归纳)如果xS和yS，那么x+yS,(3)(极小性)没有一个整数是S的元素，除非它是有限次应用条款(1)和(2)得出的。,为了得出更多的利用归纳定义指定的集合的例子，我们现在介绍一些关于符号串方面的术语和记号。设表示一个有限的非空的符号(字符)集合，我们称为字母表。由字母表中有限个字符拼接起来的符号串叫做字母表上的一个字(或叫串)。,例 2.3-2(1)如果=a，b，z，那么is，then都是上的字。(2)如果=你，我，人，工，是，那么“你是工人”是上的串。(3)如果=a，b，z，这里是代表空白。那么thatwaslongago是上的串，习惯上写成that was long ago。,设x是上的一个字，如果x=a1a2an，这里nN，对每一1in，ai，那么x中的符号个数n称为x的长度，记为x。长度为0的串表示为，叫做空串。注意空串不是空白符，前者长度为 0，后者长度是1。如果x和y都是在上的符号串，x=a1a2an和y=b1b2bm，这里，对所有i和j，ai和bj，那么x连结(或叫并置，毗连)y，记为xy，是串。xy=a1a2anb1b2bm,如果x=，那么xy=y;如果y=，那么xy=x。如果z=xy，那么x是z的词头，y是z的词尾。如果xz，那么x是真词头;如果yz，那么y是真词尾。如果w=xyz，那么y是w的子串;如果yw，那么y是真子串。显然，串的连结运算满足结合律，但不可交换。现在转回到归纳定义。下述两个定义描述的集合对从事计算机工作的人是极为重要的。,定义2.3-1 设是一个字母表，上的非空串的集合+定义如下:(1)(基础)如果a，那么a+。(2)(归纳)如果x+且a，那么ax+。(ax表示串，它由符号a和串x连结组成。)(3)(极小性)集合+仅包含这些元素:它能由有限次应用条款(1)和(2)构成。集合+包含长度为1，2，3，的串，所以是无限集合。然而，在+中没有一个串包含无限数目的符号，这是极小性条款限制的结果。,例 2.3-3 如果=a,b，那么+=a，b，aa，ab，ba，bb，aaa，aab，。上的所有有限符号串的集合记为*。集合*包含空串，其归纳定义如下:定义2.3-2 设是字母表，那么*定义如下:(1)(基础)*。(2)(归纳)如果x*和a，那么ax*。(3)(极小性)没有一个串可以是集合*的元素，除非它能有限次应用条款(1)和条款(2)构成。当然，*也可这样定义:*=+,例 2.3-4(1)如果=a,b，那么*=,a,b,aa,ab,。(2)如果=0,1，那么*是有限二进制序列的集合，包括空序列。归纳定义常用来刻画数学中的合式公式，或叫成形公式(Well-Formed Formula)。这方面我们已见过一些例子。如第1章的命题公式定义和谓词公式定义等。现在我们再举一个算术表达式集合的例子。,例 2.3-5 为简明起见，我们将算术表达式集合限制于仅包含整数，一元运算+和-，二元运算+、-、*和/。(1)(基础)如果D=0，1，2，3，4，5，6，7，8，9和xD+，那么x是一算术表达式。(2)(归纳)如果x和y都是算术表达式，那么(+x)是一算术表达式,(-x)是一算术表达式,(x+y)是一算术表达式,(x-y)是一算术表达式,(x*y)是一算术表达式,(x/y)是一算术表达式。,(3)(极小性)一个符号序列是一算术表达式当且仅当它能得自有限次应用条款(1)和(2)。用这个定义刻画的算术表达式集合包括45,000,(-321),(3+7),(3*(-35)和(+(-(+(7/2)等，不包括诸如+)和+6+之类的符号串。有些归纳定义是以其它归纳定义的集合作基础建立起来的，我们称这样的归纳定义为“二次归纳定义”，二次归纳定义不需要极小性条款，因为基础集合的极小性条款保证了所定义的集合的极小性。作为基础集合最常见的是自然数集合N(下一小节即将说明N是归纳定义的集合)。因此，以自然数集合为基础集合的归纳定义常不需极小性条款。,例 2.3-6 设aR+且nN。an的归纳定义如下:(1)(基础)a0=1(2)(归纳)an+1=ana这个归纳定义的基础集合是N，所以不需要极小性条款。程序设计语言，诸如ALGOL，它们的语法也常用归纳定义(以巴科斯范式形式给出)描述，有了上述知识作基础，相信读者可以自己看懂，我们不举这方面的例子了。,2.3.2 自然数自然数可应用后继集合的概念归纳地定义。定义 2.3-3 设A是任意集合，A的后继集合记为A，定义为A=AA 例 2.3-7(1)a,b的后继集合是a,ba,b=a,b,a,b。(2)的后继集合是=,。,定义 2.3-4 自然数N是如下集合:(1)(基础)N。(2)(归纳)如果nN，那么nnN。(3)(极小性)如果S N且满足条款(1)和(2)，那么S=N。按照这个定义，自然数集合的元素是:,为了书写方便依次记为0，1，2，3，。其结构如图2.3-1所示。可能有人会想出这样的定义:(1)(基础)0N，(2)(归纳)如果nN，那么n+1N,(3)(极小性)如果S N且满足条款(1)和(2)，那么S=N。,图 2.3-1,以上3条一般称为归纳特征，下面可以看到它将帮助我们对论述域N讨论归纳证明，但作为定义则是不完善的。因为自然数的加法定义是建立在集合N上，现在又用加法定义自然数，这就犯了循环定义的错误，所以定义自然数必须不用加法。可能有人会想:用n来表示自然数n的“后继者”，把第(2)条改为:(2)(归纳)如果nN，那么nN。这样总是可以了吧!其实这样也不行，例如，规定0=0，即模型(图2.3-2)也符合这个定义，显然不是自然数。,图 2.3-2,这些想法也不是完全错的，只要再补上一些条款，也可定义出自然数集合N。可这样定义:(1)0N,(2)如果nN，则恰存在一个n的后继者nN,(3)0 不是任何自然数的后继者,(4)如果n=m，那么n=m,(5)如果S是N的子集，使 0S;如果nS，那么nS那么，S=N。,这就是有名的皮亚诺(Peano)公设。其中(2)保证后继者是唯一的，(3)保证0只作开端，(4)保证除0外的每一个自然数只有一个直接前趋。常用(2)和(4)来检查一个序列有没有自然数性质。例如，序列0，2，4，1，3，5，不具有自然数性质，因为其中1没有直接前趋。,2.3.3 归纳证明归纳定义不仅提供了定义无限集合的一种方法，也为证明定理形成某些有效技术的基础。对于 xP(x)形式的命题，如果其论述域S是归纳定义的集合，则归纳法往往是有效的证明方法。归纳法证明通常由基础步骤和归纳步骤两部分组成，它们分别对应于S的定义的基础和归纳条款。,(1)基础步骤。这一步证明S的定义中基础条款指定的每一元素xS，P(x)是真。(2)归纳步骤。这一步证明如果事物x,y,z,有性质P，那么用归纳条款指定的方法，组合它们所得的新元素也具有性质P。归纳定义的极小性条款保证S的所有元素仅仅应用基础和归纳条款才能构成，因此证明了以上两步，就足以推出 xP(x)。,现在举例说明这一方法。回顾定理1.2-1:设A和A*是对偶式。P1，P2，Pn是出现于A和A*中的所有命题变元，于是因为根据对偶式定义，公式A中仅含有联结词、，因此公式A可归纳定义如下:(1)Pi(1in)是公式;T是公式;F是公式。(2)若A和B是公式，则 A、(AB)、(AB)是公式。(3)只有有限次运用条款(1)和(2)生成的才是公式。,定理1.2-1是建立在归纳定义的公式集合上，因此可以用上述一般的归纳法证明。(1)(基础步骤)Pi Pi(1in)，T F，F T，所以当A是由一个变元或常元构成时，公式成立。(2)(归纳步骤)设A1(P1,P2,Pn)、A2(P1,P2,Pn)对公式成立，即,现证明下述三种情况时公式也成立。情况一:(A1A2)记(A1A2)为A。,情况二:(A1A2)方法与情况一类似，留给读者自证。情况三:A1记 A1为A。故对n个命题变元的一切公式，公式成立。,以上证明就是以最一般的归纳法给出的。但通常的归纳证明是涉及自然数的，自然数具有以下归纳特征:(1)(基础)0N。(2)(归纳)如果nN，那么n+1N。(3)(极小性)如果S N，且S有以下性质:(i)0S，(ii)对每一nN，如果nS，那么(n+1)S。那么，S=N。这里，极小性条款是习惯上用于自然数定义中的形式，它叫做数学归纳法第一原理。我们适当地改变一下这个条款的形式，就可得到以自然数为论述域的 xP(x)形式的断言的归纳证明过程。,令S=n|P(n)是N的子集，于是极小性条款可改为“如果P(0)为真，n(P(n)P(n+1)为真，那么，对一切n，P(n)为真。”根据这一条款，立即得出归纳证明的过程如下:(1)(基础)先证明P(0)是真。可用任意证明技术。(2)(归纳)再证明 n(P(n)P(n+1)是真。为此，一般先假设“P(n)对任意nN是真”，这叫归纳假设(或归纳前提)，由此再推出P(n+1)也真，一旦证明了P(n)P(n+1)对任意n是真，用全称推广规则得 n(P(n)P(n+1)。再根据数学归纳法第一原理得出 xP(x)。,例 2.3-8 证明对所有nN，。这里的定理是 nP(n)的形式。P(n)是断言,假设对一切nN，P(n)是真，即，我们希望证明P(n+1)，也就是因为,而n是任意的，得出 n(P(n)P(n+1)，应用归纳法第一原理得 xP(x)，即对一切自然数n，成立。数学归纳法第一原理，事实上是自然数域上的一个推理规则。用1.5节的符号，规则的形式如下:,规则可以有各种变形，例如，我们通常希望证明对某整数k，谓词P对所有xk成立。这时，基础步骤必须换为证明P(k)。于是推理规则是:容易证明这两种形式的推理规则是等价的。,例 2.3-9证明n4 时，2nn2。证(1)(基础)n=5 时，2552，显然成立。(2)(归纳)设n时，2nn2成立，现证n+1 时命题也成立，这里n5。因为 2n+1=22n2n2(根据归纳假设)n2+5nn2+2n+1=(n+1)2所以，对一切n4，2nn2。证毕。,如果令n=m+5，上题就成为“证明对一切自然数m，2m+5(m+5)2”，这样，本题就成为基本形式了。有时命题中含有自然数域上的两个变元，对于这种命题也可用归纳法证明。,例 2.3-10 设an如例2.3-6所定义，试证明 m n(aman=am+n)。证 设m是任意的，对n作归纳，证明断言 n(aman=am+n)。(1)(基础)如果n=0，那么aman=ama0=am1=am=am+0=am+n(2)(归纳)设aman=am+n对任意n成立，那么 aman+1=am(ana)an的定义=(aman)a乘法结合律=(am+n)a归纳假设=a(m+n)+1an的定义=am+(n+1)加法结合律所以，naman=am+n。,因为m是任意的，由全称推广规则得 m naman=am+n证毕自然数域上的归纳法证明还有另一形式，称为数学归纳法第二原理，第二原理作为推理规则的形式如下:,应用这一推理规则的证明的归纳假设是 kknP(k)即对一切kn，P(k)是真。从这一假设出发，我们必须证明P(n)。一旦在归纳假设的前提下证明了P(n)，就可得出 xP(x)。应用第二原理仅需我们证明单一的前提，但它通常需要分情况证明。首先证明n=0的情况。n=0时，k0 对一切kN常假，所以 kk0P(k)常真。所以，证明 kk0P(k)P(0)是真，等价于证明P(0)是真。,其次证明:对任意n0，如果P(k)对一切kn成立，那么P(n)是真。这样，用第二原理证明和用第一原理证明的唯一不同是:用“对一切kn，P(k)是真”的归纳假设代替“P(n-1)是真”的归纳假设。虽然两个数学归纳法原理是不同的，但如果论述域是自然数集N，则它们的前提是逻辑等价的，因此它们也是等效的。但有其它论述域存在，那里第二原理更有效。第3章会看到这方面的例子。,通常，如果证明P(n+1)为真，即证明元素n+1具有性质P，不仅可能依赖于元素n的性质，还可能依赖于n以前各元素的性质时，应选用第二原理。第二原理和第一原理一样，也有各种变形。,例 2.3-11 有数目相等的两堆棋子，两人轮流从任一堆里取几颗棋子，但不能不取也不能同时在两堆里取。规定凡取得最后一颗者胜。求证后取者可以必胜。证 对每堆棋子数目n作归纳证明。为了便于叙述，设甲为先取者，乙为后取者。n=1时，甲必须在某堆中取一颗。于是另一堆中的一颗必为乙所得，乙胜。设nk时，后取者胜。现证n=k时也是后取者胜。设第一轮甲在某堆先取r颗，0rk。乙的对策是在另一堆中也取r颗。这里有两种可能。,(1)若rk，经过两人各取一次之后，两堆都只有kr颗，krk，现在又是甲先取，根据归纳假设乙胜。(2)若r=k，显然是乙胜。证毕。本例不仅说明了归纳法第二原理的应用，还说明有些问题虽然与自然数无直接关系，也可引入自然数作参数，利用有关自然数的归纳法证明。,习 题1.对下列集合给出归纳定义:(1)十进制无符号整数集合，定义的集合将包含6，235，0045等等。(2)十进制的以小数部分为结束的实数集合，定义的集合将包含5.3，453.，01.2700，0.480等等。,(3)二进制形式的不以0开头的正偶数和0所组成的集合，定义的集合包含0，110，1010等等。(4)把算术表达式中的运算符和运算对象全删去，所得的括号叫成形括号串。例如、等都是成形括号串(例中用 代()是为了明晰)，试定义成形括号串集合。,*2.将皮亚诺公设交替地删去其中第(5)条、第(4)条或第(2