离散数学课件第2章.ppt

1 1第2章 集合2.1　集合论的基本概念　集合论的基本概念2.2　集合上的运算　集合上的运算2.3　归纳法和自然数　归纳法和自然数*2.4　语言上的运算　语言上的运算2.5　集合的笛卡尔乘积　集合的笛卡尔乘积第第2章章 集合集合2 2第2章 集合 2.1 集合论的基本概念2.1.1 集合的概念　　集合在某些场合又称为类、族或搜集，它是数学中最基本的概念之一，如同几何中的“点”、“线”等概念一样，不可精确定义，现描述如下:　　一个集合是能作为整体论述的事物的集体3 3第2章 集合　　例如,　　(1) “高二(1)班的学生”是一集合　　(2) 硬币有两面——正面和反面，“正面， 反面”构成一集合　　(3) 计算机内存之全体单元构成一集合　　(4) 1，2，3，…，n，…构成正整数集合　　(5) 所有三角形构成三角形集合　　(6) 坐标满足方程x2+y2≤R2的全部点构成图 2.1-1所示的点集4 4第2章 集合图 2.1-15 5第2章 集合　　组成集合的每个事物叫做这个集合的元素元素或成员成员　　通常用大写字母A，B，C，…代表集合; 用小写字母a，b，c，…代表元素。

　　如果a是集合A的一个元素，则记为　　　　　　　　　　a∈A　　读做“a属于A”，或说“a在A中”　　如果a不是集合A的一个元素，则记为　　　　　　　　　　a　 A　　读做“a不属于A”，或说“a不在A中”6 6第2章 集合　　任一元素，对某一集合而言，或属于该集合，或不属于该集合，二者必居其一，不可兼得　　通常采用3种方法表示集合　　第一种是列举法就是把集合中的元素一一列举出来例如“所有小于5的正整数”这个集合的元素为1，2，3，4，除这4个元素外，再没有别的元素了如果把这个集合命名为A，就可记为　　　　　　　　　　A={1，2，3，4} 在能清楚表示集合成员的情况下可使用省略号，例如，从1 到50 的整数集合可记为{1，2，3，…，50}，偶数集合可记为{…,-4,-2,0,2,4,…}7 7第2章 集合　　第二种是描述法就是用谓词描述出集合元素的公共特征来表示这个集合　　例如，上述各例可分别写成　　　　　　　　A={a|a∈I∧0＜a∧a＜5}和　　　 {a|a∈I∧1≤a≤50}，{x|　 y(y∈I∧x=2y)}这里I表示整数集合一般地　　　　　　　　　　S={a|P(a)}表示a∈S当且仅当P(a)是真。

8 8第2章 集合　　比较这两种表示方法可以看出，列举法的好处是可以具体看清集合的元素; 描述法的好处是刻画出了集合元素的共同特征应用时可根据方便任意选用，不受限制　　第三种是归纳定义法该法我们将留待2.3节讨论　　集合的元素可以是一个集合，例如A={a,b,c,D}，而 D={0,1}　　仅含有一个元素的集合称为单元素集合单元素集合　　应把单元素集合与这个元素区别开来例如{A}与A不同，{A}表示仅以A为元素的集合，而A对{A}而言仅是一个元素，当然这个元素也可以是一个集合，如A={1,2}9 9第2章 集合　　称含有有限个元素的集合为有限集合有限集合称不是有限集合的集合为无限集合无限集合或无穷集无穷集有限集合的元素个数称为该集合的基数基数或势势集合A的基数记为|A|，例如　　　　　　若 A={a，b}，则 |A|=2，又|{A}|=1　　两个集合怎样才算相等呢? 以下外延公理给出了它的规定　　外延公理 两个集合A和B相等，即A=B，当且仅当它们有相同的成员(也就是，A的每一元素是B的一个元素而B的每一元素也是A的一个元素)1010第2章 集合　　外延公理用逻辑符号可表达为　 A=B　 x(x∈A　 x∈B)或 A=B x(x∈A→x∈B)∧ x(x∈B→x∈A) 外延公理断言: 如果两个集合有相同的元素，那么不管集合是如何表示的，它们都相等。

1111第2章 集合　　因此,　　(1) 列举法中，元素的次序是无关紧要的例如{x,y,z}与{z,x,y}相等　　(2) 元素的重复出现无足轻重例如，{x,y,x}、{x,y}、{x,x,x,y}是相同的集合　　(3) 集合的表示不是唯一的例如，{x|x2-3x+2=0}、{x|x∈I∧1≤x≤2}和{1，2}均表示同一集合1212第2章 集合2.1.2 罗素悖论　　正如本章前言中所指出的，朴素集合论由于在定义集合的方法上缺乏限制会导致悖论，现在让我们考察一下这种悖论是如何产生的　　我们通常遇到的集合，集合本身不能成为它自己的元素例如{a}　 {a}，但有些集合，集合本身可以成为它自己的元素，例如考察概念的集合，因为它本身是一个概念，因此这个集合可以是它自己的一个元素因此，断言A∈A和A　 A都是谓词，可以用来定义集合1313第2章 集合　　1901年罗素(Bertrand Russell)提出以下悖论: 设论述域是所有集合的集合，并定义S为下述集合:　　　　　　　　　S={A|A　 A} 　这样，S是不以自身为元素的全体集合的集合，我们现在问“S是不是它自己的元素?”　　假设S不是它自己的元素，那么S满足谓词A　 A，而该谓词定义了集合S，所以S∈S。

另一方面，如果S∈S，那么S必须满足定义S的谓词，所以S　 S　　这样，我们导致了一个类似于谎言悖论的矛盾: 既非S∈S也非S　 S是真一个“集合”，诸如S，它能导致矛盾，称为非良定的非良定的1414第2章 集合　　罗素悖论起因于不受限制的定义集合的方法，特别是集合可以是自己的元素的概念值得怀疑 康脱以后创立的许多公理化集合论都直接地或间接地限制集合成为它自己的元素，因而避免了罗素悖论　　公理化集合论用某个方法避免了罗素悖论，但怎能确信没有其它悖论潜伏在这些形式结构中呢? 回答是悲观的，业已证明，应用现今有效的数学技术，没有方法能证明新的悖论不会产生　　关于悖论问题就简单地叙述至此1515第2章 集合2.1.3 集合间的包含关系　　两集合的相等关系已用外延公理定义，现在介绍两集合间的另一种关系——包含集合的包含定义如下:　　定义2.1-1 设A和B是集合，如果A的每一元素是B的一个元素，那么A是B的子集合，记为A 　B，读做“B包含A”或“A包含于B中”　　用逻辑符表示为　　 A　 B 　　x{x∈A→x∈B)A　 B有时也记作B　 A，称B是A的扩集扩集。

1616第2章 集合　　定义2.1-2 如果A　 B且A≠B，那么称A是B的真子集，记作A　 B，读做“B真包含A”　　用逻辑符表示为 要注意区分从属关系“∈”及包含关系“　 ”从属关系是集合元素与集合本身的关系，包含关系是集合与集合之间的关系　　在前言中我们已指出: 我们所讨论的全部集合和元素是限于某一论述域中的因此，虽然这个论述域有时并没有明晰地指出，但表示集合元素的变元只能在该域中取值论述域在本章常用U表示，有的书上称论述域为全集合1717第2章 集合　　定理 2.1-1 对任意集合A有A　 U　　证 对任意元素x，x∈U是真，所以　　　　　　　　　x∈A→x∈U是真由全称推广规则得　　　　　　　　　x(x∈A→x∈U)所以　　　　　　　　　　A　 U这是一个平凡证明的例子1818第2章 集合　　定理 2.1-2 设A和B是集合，A=B当且仅当A　 B和B　 A　　证1919第2章 集合　　推论 2.1-2 对任何集合A，恒有A　 A　　定理 2.1-3 设A、B、C是集合，若A　 B且B　 C，则A　 C　　证 设x是论述域中任意元素，因为所以　　　　　　　　　　　x∈A→x∈B　　　　　　　　　　　x∈B→x∈C2020第2章 集合　　由前提三段论得　　　　　　　　　　　x∈A→x∈C　　由全称推广规则得　　　　　　　　　　　 x(x∈A→x∈C)即　　　　　　　　　　　　　A　 C2121第2章 集合　　定义 2.1-3 没有元素的集合叫空集或零集，记为　 。

　　定理 2.1-4 对任意集合A有 　 　　证 设x是论述域中任意元素，则 x∈　 常假，所以 无义地真，由全称推广规则得即2222第2章 集合　　定理 2.1-5 空集是唯一的　　证 设　 和　 ′都是空集，由定理2.1-4得　 　 　 ′和　 ′　 　 ，根据定理2.1-2得　 =　 ′　　注意　 与{　 }不同，后者是以空集为元素的一个集合，前者没有元素　　能用空集构造不同集合的无限序列在序列中，每一集合除第一个外都确实有一元素，即序列中前面的集合2323第2章 集合　　在序列中，如果我们从0开始计算，则第i项有i个元素这一序列的每一集合，以序列中在它之前的所有集合作为它的元素2424第2章 集合　　例 2.1-1　　(1) 集合{p,q}有4个不同子集: {p,q}、{p}、{q}和　 ，注意{p}　 {p,q}但p{p,q}，p∈{p,q}但{p}　 {p,q}再者　 　 {p,q}，但　 　 {p,q}　　(2) 集合{{q}}是单元素集合，它的唯一元素是集合{q}。

每一单元素集合恰有两个子集，{{q}}的子集是{{q}}和　 　　一般地，n个元素的集合有2n个不同的子集合，我们在下一节将证明这一点2525第2章 集合　　　　　　　习 题　　1. 用列举法表示下列集合:　　(1) 小于20的质数集合　　(2) 构成词evening的字母集合　　(3) {x|x2+x-6=0}　　(4) 真值构成的集合2626第2章 集合　　2. 用描述法表示下列集合:　　(1) {1，2，3，…，79}　　(2) 奇整数集合　　(3) 能被5 整除的整数集合　　(4) 重言式集合　　3. 列出下列集合的成员:　　(1) {x|x是36的因子}　　(2) {x|x=a∨x=b}　　(3) {1，{3}，{{a}}}2727第2章 集合　　4. 论述域是I，确定下列哪些集合是相等的:　　 A={x|x2-1=15∧x3=1}　　 B={0}　　 C={x|　 y(y∈I∧x=2y)}　　 D={x|x2-6x+8=0}　　 E={2x|x∈I}　　 F={4，2，4，2}　　 G={x|x2+1=0}　　 H={0，2，-2，4，-4，6，-6，…}2828第2章 集合　　5. 证明: 若a，b，c和d是任意客体，则{{a}，{a,b}}={{c}，{c,d}}当且仅当a=c和b=d。

　　 *6. 小镇上唯一的理发师公开宣布: 他仅给自己不刮脸的人刮脸，问谁给这位理发师刮脸? 为什么这是一个悖论?　　7. 列出下列集合的全部子集合:2929第2章 集合　　8. 证明推论2.1-2　　9. 设A、B和C是集合，如果A∈B和B∈C，A∈C可能吗? A∈C常真吗? 试举例说明之　　10. 设A、B和C是集合，证明或否定以下断言:3030第2章 集合　　11. 指出下列各组集合中的集合有何不同，列出每一集合的元素和全部子集　　12. A　 B且A∈B，这可能吗? 证明你的断言3131第2章 集合　　13. 确定下列各命题的真和假:3232第2章 集合　　14. 对任意集合A、B、C确定下列各命题是真或假:　　(1) 如果A∈B及B　 C，则A∈C　　(2) 如果A∈B及B　 C，则A　 C　　(3) 如果A　 B及B∈C，则A∈C　　(4) 如果A　 B及B∈C，则A　 C3333第2章 集合　　　　 2.2 集合上的运算　　集合上的运算是用给定的集合(叫运算对象)去指定一新的集合(叫运算结果)我们将依次介绍常见的集合运算如同前节一样，我们假定所有集合都是用(非明晰指定的)论述域U的元素构造的。

3434第2章 集合2.2.1 并、交和差运算　　定义 2.2-1 设A和B是集合　　(1) A和B的并记为A∪B，是集合　　　　　　　A∪B={x|x∈A∨x∈B}　　(2) A和B的交记为A∩B，是集合　　　　　　　A∩B={x|x∈A∧x∈B}　　(3) A和B的差，或B关于A的相对补，记为A-B，是集合　　　　　　　A-B={x|x∈A∧x　 B}3535第2章 集合　　例 2.2-1 设A={a,b,c,d)和B={b,c,e}，那么　　　　　　A∪B={a，b，c，d，e} 　　　　　　A∩B={b，c}　　　　　　A-B={a，d}　　　　　　B-A={e}3636第2章 集合　　定义 2.2-2 如果A和B是集合，A∩B=　 ，那么称A和B是不相交的不相交的如果C是一个集合的族，使C的任意两个不同元素都不相交，那么C是(两两)不相交集合的族　　例 2.2-2 如果C={{0}，{1}，{2}，…}={{i}|i∈N}，那么C是不相交集合的族　　定理 2.2-1 集合的并和交运算是可交换和可结合的也就是对任意A、B和C　　(1) A∪B=B∪A　　(2) A∩B=B∩A　　(3) (A∪B)∪C=A∪(B∪C)　　(4) (A∩B)∩C=A∩(B∩C)3737第2章 集合　　我们仅证明(1)和(3)，(2)和(4)是类似的。

　　证　　(1) 设x是论述域U的任意元素，那么　　　　 x∈A∪B　 x∈A∨x∈B ∪的定义 　　　　　　　　　 x∈B∨x∈A∨的可交换性　　　　　　　　　 x∈B∪A∪的定义因为x是任意的，得　　　　　　　　 x(x∈A∪B　 x∈B∪A)即　　　　　　　　　　A∪B=B∪A3838第2章 集合　　(3) 设x是任意元素，那么因为x是任意的，得出　　　　　　 x(x∈A∪(B∪C)　 x∈(A∪B)∪C)因此　　　　　　　　　　A∪(B∪C)=(A∪B)∪C3939第2章 集合　　定理 2.2-2 对任意集合A、B和C有:　　(1) A∪(B∩C)=(A∪B)∩(A∪C)　　(2) A∩(B∪C)=(A∩B)∪(A∩C)即集合运算∩和∪， ∪在∩上可分配，∩在∪上可分配4040第2章 集合　　证 (1) 设x是任意元素，那么因此，A∪(B∩C)=(A∪B)∩(A∪C)4141第2章 集合　　(2)部分的证明留作练习　　定理 2.2-3 设A、B、C和D是论述域U的任意子集合，那么下列断言是真:4242第2章 集合4343第2章 集合　　证　　(1) x∈A∪A　 x∈A∨x∈A　 x∈A，因此，A∪A=A。

　　(3) x∈A∪　 　 x∈A∨x∈　 ，因x∈　 常假，于是x∈A∨x∈　 　 x∈A因此，x∈A∪　 　 x∈A所以，A∪　 =A　　(5) A-　 ={x|x∈A∧x　 　 }但x　 　 常真，因此，x∈A∧x　 　 　 x∈A，所以A-　 ={x|x∈A}=A，即A-　 =A　　(6) x∈A-B　 x∈A∧x　 Bx∈A因此，x∈A-Bx∈A，得A-B　 A　　(7) 设x是A∪C的任意元素，那么x∈A∨x∈C现在分情况证明4444第2章 集合　　情况1: 设x∈A，因为A　 B，得x∈B，所以x∈B∨x∈D，因此x∈B∪D　　情况2: 设x∈C，用与情况1相似的论证得x∈B∪D因此，x∈A∪C，那么x∈B∪D所以A∪C　 B∪D　　(11) 因A　 B，又B　 B根据(7)得A∪B　 B∪B，但B∪B=B，因此A∪B　 B另一方面由(9)得B　 A∪B所以，A∪B=B　　其余部分的证明留作练习4545第2章 集合　　推论2.2-3 　　(1) A∪U=U;　　(2) A∩U=A　　本推论可由定理2.2-3的(11)、(12)部分得出4646第2章 集合2.2.2 补运算　　定义2.2-3 设U是论述域而A是U的子集。

A的(绝对)补，记作　 ，是集合 　=U-A={x|x∈U∧x　 A}={x|x　 A}　　例 2.2-3　　(1) 如果U={p,q,r,s}和A={p,q}，那么　 ={r,s}　　(2) 如果U=N和A={x|x＞0}，那么 　={0}　　(3) 如果U=I和A={2x+1|x∈I}，那么　 ={2x|x∈I}4747第2章 集合　　定理 2.2-4 设A是某论述域U的任意子集，那么　　证4848第2章 集合　　定理 2.2-5 (补的唯一性)设A和B 是论述域U的子集，那么B= 　当且仅当A∪B=U和A∩B=　 　　证 必要性从定理 2.2-4 直接得到现证明充分性设A∩B=　 和A∪B=U，那么4949第2章 集合　　推论2.2-5 　　(1) 　 =U; 　　(2) 　 =　 　　证 因U∪　 =U和U∩　 =　 ，所以，　 =U和 　 =　 　　定理 2.2-6 设A是U的任意子集，那么 　 =A也就是说，A的补的补是A　　证 因为 　∪A=U和 　∩A=　 ，根据上一定理A是 　的补，但 　也是 　的补，而补是唯一的，所以，　 =A。

5050第2章 集合　　定理2.2-7 (德·摩根定律)设A和B是U的任意子集，那么　　证 　　根据定理2.2-5，( 　∩　 )是A∪B的补，但A∪B也是A∪B的补，而补是唯一的，所以A∪B= 　∩ 　　　(2)的证明是类似的，故略5151第2章 集合　　定理 2.2-8 设A、B是U的任意子集，若A　 B，则 　　 　　　证 由A　 B　　 x(x∈A→x∈B)知　　　　　　　　　　　x∈A→x∈B根据逆反律得　　　　　　　　　　　x　 B→x　 A即　　　　　　　　　　　x∈ 　→x∈ 　x是任意的，所以　　　　　　　　　　 x(x∈ 　→x∈ 　)即5252第2章 集合　　当集合数目不多时，集合运算的结果能用文氏图表达出来参看图2.2-1，图中长方形表示论述域，而以一定区域表示任意集合A、B和C，每一图形的阴影部分分别代表出现在各自下边的表达式上边给出的定理和公式，都可联系文氏图形象地理解5353第2章 集合图 2.2-15454第2章 集合　　另外，根据并、交、补等定义，亦知命题演算中的∨、∧、　 、→、T、F等分别与集合论中的∪、∩、－、　 、U、　 等有对应关系，因此，有关它们的公式也有相似性。

例如命题演算中有公式　　　　　 集合论中有对应公式5555第2章 集合　　又如命题演算中有范式等概念　 P∧Q∨R　 (P∨Q∨R)∧(P∨　 Q∨R)∧(　 P∨Q∨R)　　如果需要，在集合论中也可引入范式等概念，使　　　A∩B∪C=(A∪B∪C)∩(A∪ 　∪C)∩( 　∪B∪C)注意到它们的相似性，有利于理解、记忆和引用5656第2章 集合2.2.3 并和交运算的扩展　　扩展后并和交运算都定义在集合的搜集上　　定义 2.2-4 设C是某论述域子集的搜集　　(1) C的成员的并，记为　　　，是由下式指定的集合 　　(2) 如果C≠　 ，C的成员的交，记为　　　，是下式指定的集合:5757第2章 集合　　定义说明如果x∈　　　，那么x至少是一个子集S∈C的元素; 如果x∈　　　，那么x是每一个子集S∈C的元素注意对　　　的定义来说，C必须非空，否则，由于C=　 ，蕴含式S∈C→x∈S对每一S将是无义地真这样,谓词 s(S∈C→x∈S)对每一x是真因此，所定义的集合就是全集合U要求C≠　 ，这个可能消除5858第2章 集合　　设D是一集合，如果给定D的任一元素d，就能确定一个集合Ad，那么d叫做Ad的索引，搜集C={Ad|d∈D}叫做集合的加索加索引搜集引搜集; 而D叫做搜集的索引集合搜集的索引集合。

当D是一个搜集C的索引集合时， 符号　　　表示　　　，而　　　表示　　　　　如果加索引搜集C的索引集合是前n+1个自然数{0，1，2，…，n}，或全体自然数{0，1，2，…}，那么C的成员的并和交能用类似于和式概念的符号表示 5959第2章 集合　　例如 一般地，索引集合不必是N的子集，可以是任意集合，例如R+6060第2章 集合　　例 2.2-4 设论述域是实数R　　(1) 如果C={{1，2，4}，{3，4，5}，{4，6}}，那么6161第2章 集合　(2) 我们用［0，a)表示集合{x|0≤x＜a}6262第2章 集合　　(3) 设C={Ai|i∈{p,q,r}}，其中Ap=［2,3］，Aq=［3,4］，Ar=［4,6］; ［a,b］表示{x|a≤x≤b}， 那么6363第2章 集合2.2.4 环和与环积　　定义 2.2-5 A、B两集合的环和记为AB，是集合 参看图 2.2-2环和又叫对称差(Symmetric Difference)6464第2章 集合　　定理 2.2-9 　　证 因为6565第2章 集合但所以， 6666第2章 集合　　推论 2.2-9 (a) 　 　=AB，(b) AB=BA，(c) AA=　 。

　　定理 2.2-10 (AB)C=A(BC)　　定理 2.2-11 C∩(AB)=(C∩A)(C∩B)6767第2章 集合　　以上两个定理留给读者自证但注意并在环和上不可分配，环和在交上不可分配即，通常 　　定义 2.2-6　A、B两集合的环积记为AB，是集合　　参看图 2.2-2由定义即得出下述两定理6868第2章 集合图 2.2-26969第2章 集合　　定理 2.2-12 (1) 　 　=AB，(2) AB=BA，(3) AA=U　　定理 2.2-13 　　证 所以，7070第2章 集合　　根据定理2.2-10 得两边取补，即得 　　定理 2.2-14 　　留给读者自证7171第2章 集合2.2.5 幂集合　　我们常常涉及以某个集合的子集为元素的集合，因此需要以下定义　　定义 2.2-7 设A是一集合，A的幂集幂集ρ(A)是A的所有子集的集合，即　　　　　　　　　ρ(A)={B|B　 A} 一个给定集合的幂集是唯一的，因此求一个集合的幂集是以集合为运算对象的一元运算。

7272第2章 集合　　例 2.2-5　　(1) 如果A=　 ，那么ρ(A)={　 }　　(2) 如果A={a,b}，那么ρ(A)={　 ，{a}，{b}，{a，b}}　　(3) 如果A是任意自然数集合，那么A∈ρ(A)，　 ∈ρ(A)7373第2章 集合　　下面说明子集的二进制数表示和幂集合的个数　　在集合的定义里，没有规定集合中元素的次序，但为了便于在计算机上表示集合，亦可给集合元素编定次序例如，A={a,b,c}，不妨认为a、b、c分别是第一、二、三个元素于是可用三位二进制数做足标表示A的任意子集: 二进制数的第i位表示第i个元素是否属于该子集，1表示属于，0 表示否例如可用S101表示{a,c}，S011 表示{b,c}，三位二进制数可与其子集一一对应因而ρ(A)={Si|i∈J}，这里J={000,001,…,111}为了书写方便，可用十进制数代替二进制数，于是J={0,1，2，…，7}一般地，n个元素的集合A，可用n位二进制数与其子集一一对应 7474第2章 集合　　因而　　　　ρ(A)={Si|i∈J}，J={0，1，2，…，2n-1}　　由此可知，n个元素的集合A，其幂集的元素个数是 2n。

　　如果A是无限集，则ρ(A)的元素个数也是无限的7575第2章 集合*2.2.6 有限集的计数　　定理 2.2-15 设A和B都是有限集合，则以下公式成立:7676第2章 集合　　我们仅证明①，其它都是明显的　　证 A和B之间可能有公共元素，公共元素个数是|A∩B|，在计算|A∪B|时每个元素只计算一次，但在计算|A|+|B|时，公共元素计算了两次， 一次是在计算|A|时，一次是在计算|B|时，因此，右边减去|A∩B|才能相等7777第2章 集合　　公式①可以推广，三个集合时为　　如图 2.2-3所示7878第2章 集合图 2.2-37979第2章 集合一般地成立以下公式:8080第2章 集合　　证 用归纳法证明(未学过归纳法的同学可在学完下节后，再看此证明)　　n=2时，已证明成立，即　　　　　　　　|A1∪A2|=|A1|+|A2|-|A1∩A2| 设n-1(n≥3)时公式成立，现证明n时也成立8181第2章 集合　根据归纳假设得8282第2章 集合　　例 2.2-6　　(1) 在一个班级50个学生中，有 26 人在第一次考试中得到A，21人在第二次考试中得到A，假如有17 人两次考试都没有得到A，问有多少学生在两次考试中都得到A?　　解 设第一次考试得A的是集合A1，第二次考试得A的是集合A2，则　　　　　　　　　　|A1∪A2|=50-17=33但　　　　　　　　|A1∪A2|=|A1|+|A2|-|A1∩A2|所以　　 　　　 |A1∩A2|=|A1|+|A2|-|A1∪A2|=26+21-33=14故两次考试都得A的有 14 人。

8383第2章 集合　　(2) 某教研室有 30 名老师，可供他们选修的第二外语是日语、法语、德语已知有 15 人进修日语，8 人选修法语，6 人选修德语，而且其中 3 人选修三门外语，我们希望知道至少有多少人一门也没有选修　　解 设A1、A2、A3分别表示选修日语、法语和德语的人，因此8484第2章 集合　　因为　　　　　　　　|A1∩A2|≥|A1∩A2∩A3|　　　　　　　　|A1∩A3|≥|A1∩A2∩A3|　　　　　　　　|A2∩A3|≥|A1∩A2∩A3|我们得　　　　　　　|A1∪A2∪A3|≤32-3-3-3=23即至多有 23 人在进修第二外语，因此至少有 7 人没有进修第二外语8585第2章 集合　　　　　　　习 题　　1. 给定自然数集合N的下列子集:8686第2章 集合　　求出下列集合:8787第2章 集合　　2. 考察正整数集合I+的下列子集:8888第2章 集合　试用A、B、C、D和E表达下列集合:8989第2章 集合　3. 设x和y是实数，定义运算x△y是xy(x的y次幂)　(1) 证明运算△既非可交换的也非可结合的。

　(2) 设*代表乘法运算，确定下列分配律哪些是成立的:9090第2章 集合　　4. (1) 对下列各式构造文氏图:　　(2) 给出一公式，它表示图 2.2-4中各文氏图中的阴影部分9191第2章 集合图 2.2-49292第2章 集合　　5. 设A、B、C是任意集合，把A∪B∪C表示为不相交集合之并　　6. 设A、B和C是集合　　(1) 证明如果C 　 A且C 　 B，那么C 　 A∪B(也就是A∪B是包含A和B的最小集合)　　(2) 证明如果C　 A且C　 B，那么C　 A∩B(也就是A∩B是包含在A和B中的最大集合)　　7. 证明定理2.2-2的(2)　　8. 假定A≠　 和A∪B=A∪C，证明这不能得出B=C，假设中增加A∩B=A∩C，你能得出B=C吗?9393第2章 集合　　9. (1) 证明“相对补”不是一个可交换运算，即证明存在一个论述域包含集合A和B，使A-B≠B-A　　(2) A-B=B-A可能吗? 刻画此式出现的全部条件　　(3) “相对补”是一个可结合的运算吗? 证明你的断言　　10. 证明定理2.2-3的其余部分　　11. 设A、B和C是论述域U的任意子集，证明下列各式:9494第2章 集合9595第2章 集合9696第2章 集合　　9797第2章 集合　　16. 设C是一非空的某论述域U的子集的搜集，证明下列德·摩根定律的推广:　　17. 设C是一非空的某论述域U的子集的搜集，B是U的子集，证明下列分配律的推广:9898第2章 集合　　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)9999第2章 集合　　20. 证明下列各式:　　　　*21. 试决定在1 到 250 之间能被2、3、5、7任何一数整除的整数个数　　*22. 某班学生 50 人，会FORTRAN—Ⅳ语言的40人，会ALGOL—60语言的35人会PL/1语言的10人，以上三门都会的5人，都不会的没有，问仅会两门的有几人?100100第2章 集合　　　　2.3 归纳法和自然数2.3.1 集合的归纳定义　　我们在2.1节介绍了指定集合的两种最常用方法——列举法和描述法但仍然有许多集合难以用这两种方法表示出来，诸如算术表达式集合，命题演算公式集合，ALGOL程序集合等等，这些集合用归纳定义来指定较为方便归纳定义习惯上称为递归定义101101第2章 集合　　一个集合的归纳定义由 3 部分组成:　　(1) 基础条款(简称基础)它指出某些事物属于集合它的功能是给集合以基本元素，使所定义的集合非空　　(2) 归纳条款(简称归纳)它指出由集合的已有元素构造新元素的方法。

归纳条款的形式总是断言: 如果事物 x,y,…，z是集合的元素，那么用某种方法组合它们而成的一种新事物也在集合中它的功能是指出为了构造集合的新元素，能够在事物上进行的运算　　(3) 极小性条款(简称极小性) 它断言一个事物除非能有限次应用基础和归纳条款构成外，那么这个事物不是集合的成员102102第2章 集合　　集合S的归纳定义的极小性条款还有其它形式，常见的有:　　(i) “集合S是满足基础和归纳条款的最小集合”　　(ii) “如果T是S的子集，使T满足基础和归纳条款，那么T=S”其意义是: S满足基础和归纳条款，但没有S的真子集满足它们　　这些极小性条款虽然形式不同，结果是等价的，全部服务于一个目的，即指明所定义的集合是满足基础和归纳条款的最小集合，即通常所谓极小性103103第2章 集合　　例 2.3-1 如果论述域是整数I，那么能为3 整除的正整数集合S的谓词定义如下:　　　　　　　　S={x|x＞0∧　 y(x=3y)}同样集合能归纳地定义如下:　　(1) (基础)3∈S,　　(2) (归纳)如果x∈S和y∈S，那么x+y∈S,　　(3) (极小性)没有一个整数是S的元素，除非它是有限次应用条款(1)和(2)得出的。

　　104104第2章 集合　　为了得出更多的利用归纳定义指定的集合的例子，我们现在介绍一些关于符号串方面的术语和记号设Σ表示一个有限的非空的符号(字符)集合，我们称Σ为字母表由字母表Σ中有限个字符拼接起来的符号串叫做字母表Σ上的一个字(或叫串)105105第2章 集合　　例 2.3-2　　(1) 如果Σ={a，b，…，z}，那么is，then都是Σ上的字　　(2) 如果Σ={你，我，人，工，…，是}，那么“你是工人”是Σ上的串　　(3) 如果Σ={a，b，…，z，└┘}，这里└┘是代表空白 那么that└┘was└┘long└┘ago是Σ上的串，习惯上写成that was long ago106106第2章 集合　　设x是Σ上的一个字，如果x=a1a2…an，这里n∈N，对每一1≤i≤n，ai∈Σ，那么x中的符号个数n称为x的长度，记为‖x‖长度为0的串表示为Λ，叫做空串空串注意空串不是空白符，前者长度为 0，后者长度是1如果x和y都是在Σ上的符号串，x=a1a2…an和y=b1b2…bm， 这里，对所有i和j，ai∈Σ和bj∈Σ，那么x连结连结(或叫并置并置，毗连毗连)y，记为xy，是串。

　　　　　　　　xy=a1a2…anb1b2…bm107107第2章 集合　　如果x=Λ，那么xy=y; 如果y=Λ，那么xy=x如果z=xy，那么x是z的词头词头，y是z的词尾词尾如果x≠z，那么x是真词头真词头; 如果y≠z，那么y是真词尾真词尾如果w=xyz，那么y是w的子串子串; 如果y≠w，那么y是真子串真子串　　显然，串的连结运算满足结合律，但不可交换　　现在转回到归纳定义下述两个定义描述的集合对从事计算机工作的人是极为重要的108108第2章 集合　　定义2.3-1 设Σ是一个字母表，Σ上的非空串的集合Σ+定义如下:　　(1) (基础)如果a∈Σ，那么a∈Σ+　　(2) (归纳)如果x∈Σ+且a∈Σ，那么ax∈Σ+ax表示串，它由符号a和串x连结组成)　　(3) (极小性)集合Σ+仅包含这些元素: 它能由有限次应用条款(1)和(2)构成　　集合Σ+包含长度为1，2，3，…的串，所以是无限集合然而，在Σ+中没有一个串包含无限数目的符号，这是极小性条款限制的结果109109第2章 集合　　例 2.3-3 如果Σ={a,b}，那么Σ+={a，b， aa，ab，ba，bb，aaa，aab，…}。

　　Σ上的所有有限符号串的集合记为Σ*集合Σ*包含空串，其归纳定义如下:　　定义2.3-2 设Σ是字母表，那么Σ*定义如下:　　(1) (基础)Λ∈Σ*　　(2) (归纳)如果x∈Σ*和a∈Σ，那么ax∈Σ*　　(3) (极小性)没有一个串可以是集合Σ*的元素，除非它能有限次应用条款(1)和条款(2)构成　　当然，Σ*也可这样定义: 　　　　　　　　　　Σ*=Σ+∪{Λ}110110第2章 集合　　例 2.3-4　　(1) 如果Σ={a,b}，那么Σ*={Λ,a,b,aa,ab,…}　　(2) 如果Σ={0,1}，那么Σ*是有限二进制序列的集合，包括空序列　　归纳定义常用来刻画数学中的合式公式，或叫成形公式(Well-Formed Formula)这方面我们已见过一些例子如第1章的命题公式定义和谓词公式定义等现在我们再举一个算术表达式集合的例子111111第2章 集合　　例 2.3-5 为简明起见，我们将算术表达式集合限制于仅包含整数，一元运算+和-，二元运算+、-、*和/　　(1) (基础)如果D={0，1，2，3，4，5，6，7，8，9}和x∈D+，那么x是一算术表达式。

　　(2) (归纳)如果x和y都是算术表达式，那么　　① (+x)是一算术表达式,　　② (-x)是一算术表达式,　　③ (x+y)是一算术表达式,　　④ (x-y)是一算术表达式,　　⑤ (x*y)是一算术表达式,　　⑥ (x/y)是一算术表达式112112第2章 集合　　(3) (极小性)一个符号序列是一算术表达式当且仅当它能得自有限次应用条款(1)和(2)　　用这个定义刻画的算术表达式集合包括45,000,(-321),(3+7),(3*(-35))和(+(-(+(7/2))))等，不包括诸如+)和+6+之类的符号串　　有些归纳定义是以其它归纳定义的集合作基础建立起来的，我们称这样的归纳定义为“二次归纳定义”，二次归纳定义不需要极小性条款，因为基础集合的极小性条款保证了所定义的集合的极小性作为基础集合最常见的是自然数集合N(下一小节即将说明N是归纳定义的集合)因此，以自然数集合为基础集合的归纳定义常不需极小性条款113113第2章 集合　　例 2.3-6 设a∈R+且n∈Nan的归纳定义如下:　　(1) (基础)a0=1　　(2) (归纳)an+1=an·a　　这个归纳定义的基础集合是N，所以不需要极小性条款。

　　程序设计语言，诸如ALGOL，它们的语法也常用归纳定义(以巴科斯范式形式给出)描述，有了上述知识作基础，相信读者可以自己看懂，我们不举这方面的例子了114114第2章 集合2.3.2 自然数　　自然数可应用后继集合的概念归纳地定义　　定义 2.3-3 设A是任意集合，A的后继集合记为A′，定义为　　　　　　　　　　A′=A∪{A} 例 2.3-7　　(1) {a,b}的后继集合是{a,b}∪{{a,b}}={a,b,{a,b}}　　(2) {　 }的后继集合是{　 }∪{{　 }}={　 ,{　 }}115115第2章 集合　　定义 2.3-4 自然数N是如下集合:　　(1) (基础)　 ∈N　　(2) (归纳)如果n∈N，那么n∪{n}∈N　　(3) (极小性)如果S　 N且满足条款(1)和(2)，那么S=N　　按照这个定义，自然数集合的元素是:116116第2章 集合　　为了书写方便依次记为0，1，2，3，…其结构如图2.3-1所示　　可能有人会想出这样的定义:　　(1) (基础)0∈N，　　(2) (归纳)如果n∈N，那么n+1∈N,　　(3) (极小性)如果S　 N且满足条款(1)和(2)，那么S=N。

117117第2章 集合图 2.3-1118118第2章 集合　　以上3条一般称为归纳特征，下面可以看到它将帮助我们对论述域N讨论归纳证明，但作为定义则是不完善的因为自然数的加法定义是建立在集合N上，现在又用加法定义自然数，这就犯了循环定义的错误，所以定义自然数必须不用加法　　可能有人会想: 用n′来表示自然数n的“后继者”，把第(2)条改为:　　(2) (归纳)如果n∈N，那么n′∈N这样总是可以了吧! 其实这样也不行，例如，规定0′=0，即模型(图2.3-2)也符合这个定义，显然不是自然数119119第2章 集合图 2.3-2120120第2章 集合　　这些想法也不是完全错的，只要再补上一些条款，也可定义出自然数集合N可这样定义:　　(1) 0∈N,　　(2) 如果n∈N，则恰存在一个n的后继者n′∈N,　　(3) 0 不是任何自然数的后继者,　　(4) 如果n′=m′，那么n=m,　　(5) 如果S是N的子集，使　　① 0∈S;　　② 如果n∈S，那么n′∈S那么，S=N121121第2章 集合　　这就是有名的皮亚诺(Peano)公设其中(2)保证后继者是唯一的，(3)保证0只作开端，(4)保证除0外的每一个自然数只有一个直接前趋。

　　常用(2)和(4)来检查一个序列有没有自然数性质例如，序列0，2，4，…，1，3，5，…　　不具有自然数性质，因为其中1没有直接前趋122122第2章 集合2.3.3 归纳证明　　归纳定义不仅提供了定义无限集合的一种方法，也为证明定理形成某些有效技术的基础对于　 xP(x)形式的命题，如果其论述域S是归纳定义的集合，则归纳法往往是有效的证明方法归纳法证明通常由基础步骤和归纳步骤两部分组成，它们分别对应于S的定义的基础和归纳条款123123第2章 集合　　(1) 基础步骤这一步证明S的定义中基础条款指定的每一元素x∈S，P(x)是真　　(2) 归纳步骤这一步证明如果事物x,y,z,…有性质P，那么用归纳条款指定的方法，组合它们所得的新元素也具有性质P　　归纳定义的极小性条款保证S的所有元素仅仅应用基础和归纳条款才能构成，因此证明了以上两步，就足以推出　 xP(x)124124第2章 集合　　现在举例说明这一方法回顾定理1.2-1: 设A和A*是对偶式P1，P2，…，Pn是出现于A和A*中的所有命题变元，于是　　　　　　　　　　　　　　　　　　　　　　　　　　①　　因为根据对偶式定义，公式A中仅含有联结词∧、∨、　 ，因此公式A可归纳定义如下:　　(1) Pi(1≤i≤n)是公式; T是公式; F是公式。

　　(2) 若A和B是公式，则　 A、(A∧B)、 (A∨B)是公式　　(3) 只有有限次运用条款(1)和(2)生成的才是公式125125第2章 集合　　定理1.2-1是建立在归纳定义的公式集合上，因此可以用上述一般的归纳法证明　　(1) (基础步骤)　 Pi　 　 Pi(1≤i≤n)，　 T　 F，　 F　 T，所以当A是由一个变元或常元构成时，公式①成立　　(2) (归纳步骤) 设A1(P1,P2,…,Pn)、A2(P1,P2,…,Pn)对公式①成立，即126126第2章 集合　　现证明下述三种情况时公式①也成立　　情况一: (A1∧A2)　　记(A1∧A2)为A127127第2章 集合　　情况二: (A1∨A2)　　方法与情况一类似，留给读者自证　　情况三: 　 A1　　记　 A1为A故对n个命题变元的一切公式，公式①成立128128第2章 集合　　以上证明就是以最一般的归纳法给出的但通常的归纳证明是涉及自然数的，自然数具有以下归纳特征:　　(1) (基础)0∈N　　(2) (归纳)如果n∈N，那么n+1∈N　　(3) (极小性)如果S　 N，且S有以下性质:　　(i) 0∈S，　　(ii) 对每一n∈N，如果n∈S，那么(n+1)∈S。

那么，S=N　　这里，极小性条款是习惯上用于自然数定义中的形式，它叫做数学归纳法第一原理数学归纳法第一原理我们适当地改变一下这个条款的形式，就可得到以自然数为论述域的　 xP(x)形式的断言的归纳证明过程129129第2章 集合　　令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)对任意n∈N是真”，这叫归纳假设归纳假设(或归纳前提归纳前提)，由此再推出P(n+1)也真，一旦证明了P(n)→P(n+1)对任意n是真，用全称推广规则得　 n(P(n)→P(n+1))　　再根据数学归纳法第一原理得出　 xP(x)130130第2章 集合　　例 2.3-8 证明对所有n∈N，　　　　　　这里的定理是　 nP(n)的形式 P(n)是断言 131131第2章 集合　　假设对一切n∈N，P(n)是真，即　　　　　　　，我们希望证明P(n+1)，也就是因为132132第2章 集合而n是任意的，得出　 n(P(n)→P(n+1))，应用归纳法第一原理得　 xP(x)，即对一切自然数n，　　　　　　　　成立。

　　数学归纳法第一原理，事实上是自然数域上的一个推理规则用1.5节的符号，规则的形式如下:133133第2章 集合　　规则可以有各种变形，例如，我们通常希望证明对某整数k，谓词P对所有x≥k成立这时，基础步骤必须换为证明P(k)于是推理规则是:容易证明这两种形式的推理规则是等价的134134第2章 集合　　例 2.3-9　证明n＞4 时，2n＞n2　　证　　(1) (基础)n=5 时，25＞52，显然成立　　(2) (归纳)设n时，2n＞n2成立，现证n+1 时命题也成立，这里n≥5因为　　　　　　　　 2n+1=2·2n　　　　　　　　　　＞2·n2 (根据归纳假设)　　　　　　　　　　≥n2+5n　　　　　　　　　　＞n2+2n+1　　　　　　　　　　=(n+1)2所以，对一切n＞4，2n＞n2135135第2章 集合　　如果令n=m+5，上题就成为“证明对一切自然数m，2m+5＞(m+5)2”，这样，本题就成为基本形式了　　有时命题中含有自然数域上的两个变元，对于这种命题也可用归纳法证明136136第2章 集合　　例 2.3-10 设an如例2.3-6所定义，试证明　 m 　 n(am·an=am+n)。

　　证 设m是任意的，对n作归纳，证明断言　 n(am·an=am+n)　　(1) (基础)如果n=0，那么　　　　　　　am·an=am·a0=am·1=am=am+0=am+n　　(2) (归纳)设am·an=am+n对任意n成立，那么 am·an+1=am·(an·a) an的定义=(am·an)·a乘法结合律=(am+n)·a归纳假设=a(m+n)+1an的定义=am+(n+1)加法结合律所以，　 n［am·an=am+n］137137第2章 集合　　因为m是任意的，由全称推广规则得　　　　　　　 m　 n［am·an=am+n］　　　　　　　　证毕　　自然数域上的归纳法证明还有另一形式，称为数学归纳法第二原理，第二原理作为推理规则的形式如下:138138第2章 集合　　应用这一推理规则的证明的归纳假设是　　　　　　　　　　 k［k＜n→P(k)］即对一切k＜n，P(k)是真从这一假设出发，我们必须证明P(n)一旦在归纳假设的前提下证明了P(n)，就可得出　 xP(x)　　应用第二原理仅需我们证明单一的前提，但它通常需要分情况证明首先证明n=0的情况。

　　n=0时，k＜0 对一切k∈N常假，所以　　　　　　　　　　 k［k＜0→P(k)］常真所以，证明　 k［k＜0→P(k)］→P(0)是真，等价于证明P(0)是真139139第2章 集合　　其次证明: 对任意n＞0，如果P(k)对一切k＜n成立，那么P(n)是真　　这样，用第二原理证明和用第一原理证明的唯一不同是: 用“对一切k＜n，P(k)是真”的归纳假设代替“P(n-1)是真”的归纳假设　　虽然两个数学归纳法原理是不同的，但如果论述域是自然数集N，则它们的前提是逻辑等价的，因此它们也是等效的但有其它论述域存在，那里第二原理更有效第3章会看到这方面的例子　　140140第2章 集合　　通常，如果证明P(n+1)为真，即证明元素n+1具有性质P，不仅可能依赖于元素n的性质，还可能依赖于n以前各元素的性质时，应选用第二原理第二原理和第一原理一样，也有各种变形141141第2章 集合　　例 2.3-11 有数目相等的两堆棋子，两人轮流从任一堆里取几颗棋子，但不能不取也不能同时在两堆里取规定凡取得最后一颗者胜求证后取者可以必胜　　证 对每堆棋子数目n作归纳证明为了便于叙述，设甲为先取者，乙为后取者。

　　n=1时，甲必须在某堆中取一颗于是另一堆中的一颗必为乙所得，乙胜　　设n＜k时，后取者胜现证n=k时也是后取者胜　　设第一轮甲在某堆先取r颗，0＜r≤k乙的对策是在另一堆中也取r颗这里有两种可能142142第2章 集合　　(1) 若r＜k，经过两人各取一次之后，两堆都只有k－r颗，k－r＜k，现在又是甲先取，根据归纳假设乙胜　　(2) 若r=k，显然是乙胜　　本例不仅说明了归纳法第二原理的应用，还说明有些问题虽然与自然数无直接关系，也可引入自然数作参数，利用有关自然数的归纳法证明143143第2章 集合　　　　　　　　习 题　　1. 对下列集合给出归纳定义:　　(1) 十进制无符号整数集合，定义的集合将包含6，235，0045等等　　(2) 十进制的以小数部分为结束的实数集合，定义的集合将包含5.3，453.，01.2700，0.480等等144144第2章 集合　　(3) 二进制形式的不以0开头的正偶数和0所组成的集合，定义的集合包含0，110，1010等等　　(4) 把算术表达式中的运算符和运算对象全删去，所得的括号叫成形括号串例如［ ］、［［ ］］、［ ］［ ］、［［［ ］］［ ］］等都是成形括号串(例中用［ ］代( )是为了明晰)，试定义成形括号串集合。

145145第2章 集合　　 *2. 将皮亚诺公设交替地删去其中第(5)条、第(4)条或第(2)条的唯一性，为这样所得的公理系统分别构造模型，说明它们都不是自然数146146第2章 集合　　*3. 我们已经给出的自然数定义仅仅含有“后继者”的概念自然数论述域上“小于”关系，加和乘等运算可用“后继者”概念的术语加以定义例如，加法运算能归纳地定义如下: ① 对每个自然数m，m+0=m; ② 对每一对自然数m和n，m+n′=(m+n)′　　(1) 证明用以上定义的加法是可结合的　　(2) 用类似方法归纳地定义乘法(可以引用上边定义的加法运算)　　(3) 用乘法运算归纳地定义幂运算　　(4) 给出关于“小于”的一个归纳定义147147第2章 集合　　4. 用{a}代替N的定义中的　 ，但仍用这一定义，可否生成自然数集合? 有何不同?　　5. 证明成形括号串的左右括号个数相等　　6. 我们有 3 分和 5 分两种不同票值的邮票，试证明用这两种邮票就足以组成8 分或更多的任意邮资　　7. 用归纳法证明，对一切n∈I+，有　　　　　　　　(1+2+…+n)2=13+23+…+n3　　8. 设a是一正数，证明　　　　　 m　 n［(am)n=amn］，这里m，n∈N148148第2章 集合　　9. 对所有n∈N，证明下列每一关系式：149149第2章 集合　　10. 如果每根直线连接多边形的两个点，且位于多边形上，那么这个多边形叫凸的，证明对一切n≥3，n边的凸多边形内角之和等于(n－2)·180° 。

提示: 多边形能用连结两个非邻接的顶角划分为两部分)　　11. 找出自然数域上的两个谓词P和Q以证明归纳证明的基础步骤和归纳步骤是独立的，也就是没有一个逻辑地蕴含另一个特别地，要找出一谓词P使P(0)是真而　 n(P(n)→P(n+1))是假，和一谓词Q，使Q(0)是假而　 n(Q(n)→Q(n+1))是真150150第2章 集合　　12. 我们意欲证明，对一切n和一切S，如果S是n个人的集合，那么在S中的所有人都有同样的身材下面“所有人都有同样的身材”的证明错在哪里?　　(1) (基础)设S是一空集合，那么对所有的x和y，如果x∈S和y∈S，那么x和y有同样的身材　　(2) (归纳)假定对所有包含n个人的集合断言是真我们证明对包含n+1个人的集合也真任何由n+1个人组成的集合包含两个n个人组成的不同的但交搭的子集合用S′和S″表示这两个子集合那么根据归纳前提，在S′中的所有人有相同的身材，在S″中的所有人有相同的身材，因为S′和S″是交搭的，所以，所有在S=S′∪S″中的人都有相同的身材151151第2章 集合　　13. 设{A1,A2,…,An}是集合的非空搜集，对n作归纳证明下述推广的德·摩根定律：　　14. 证明所有大于1的整数n都能写成若干个质数之积。

152152第2章 集合　　15. 如果a*(b*c)=(a*b)*c，那么二元运算*称为可结合的从它可推得更强的结果，即在任何仅含运算*的表达式中，括号的位置不影响结果，就是，仅仅出现于表达式中的运算对象和次序是重要的为了证明这个“推广的结合律”，我们定义“*表达式集合”如下:153153第2章 集合　　(1) (基础)单个运算对象a是*表达式　　(2) (归纳)设e1和e2是*表达式，那么(e1*e2)是一个*表达式　　(3) (极小性)只有有限次应用(1)和(2)构成的式子才是*表达式　　推广的结合律陈述如下:　　设e是一个表达式，它有a1,a2,…,an个运算对象，且以此次序出现于表达式中，那么　　　　　　e=(a1*(a2*(a3*(…(an-1*an))…)))证明这个推广的结合律提示: 用数学归纳法第二原理)154154第2章 集合　　　　　*2.4 语言上的运算　　语言是某些符号串的集合符号串在计算机科学中扮演着重要角色计算机程序、实录的文本、数学公式、形式系统中的定理都是某些语言中的符号串为了写出处理这些事物的程序，我们必须有处理单个串和语言的工具。

　　本节介绍处理单个串和语言的重要运算，为研究计算模型、形式语言等提供数学基础155155第2章 集合　　前已指出，通常用Σ表示有限字母表，Σ*表示Σ上的有限长的全体符号串集合Σ*元素上的主要运算是连结现在定义串的另一种运算——幂运算，即一个串自身连结n次　　定义2.4-1 设x是Σ*的一个元素，对每一n∈N，串xn定义如下:　　(1) x0=Λ　　(2) xn+1=xn·x156156第2章 集合　　例 2.4-1　　(1) 如果Σ={a,b,c}和x=ac，那么x0=Λ，x1=ac，x2=acac，x3=acacac　　(2) 集合{1n0n|n≥0}表示集合{Λ,10,1100,111000,…}　　在串的运算的基础上可以定义语言上的运算　　定义2.4-2 设Σ是有限字母表，Σ上的语言是Σ*的一个子集157157第2章 集合例 2.4-2　　(1) 集合{b,ab,aab,aaab}是Σ={a，b}上的一个语言　　(2) 一个由1的序列跟随着0的序列组成的串的集合{1n　0m|n，m∈N}是{0，1}上的语言　　(3) FORTRAN程序的集合是FORTRAN字符组成的字母表上的语言。

　　定义2.4-3 设A和B是Σ上语言，A和B的连结积记为A·B或AB，是语言AB={xy|x∈A∧y∈B}， 即语言AB是由A的一个元素连结B的一个元素所形成的所有串组成的集合158158第2章 集合　　例 2.4-3 设Σ={a，b}，A={Λ,a}和B={b,ab}，那么　　　　　　　　　　AB={b,ab,aab} 　　　　　　　　　　BA={b,ba,ab,aba} 从上例可看出，一般地，AB≠BA，也就是说语言的连结积运算是不可交换的但有以下性质159159第2章 集合　定理2.4-1 设A、B、C和D是Σ上的任意语言，那么160160第2章 集合　　证 　　(1) 根据定义，A　 ={xy|x∈A∧y∈　 }，但对每一y∈Σ*，y∈　 常假所以合取式x∈A∧y∈　 对一切x和y是假因为没有元素x和y满足这谓词，集合A　 没有成员，即A　 =　 类似地可证　 A=　 　　(4) 用直接证明设z是AC的任意元素，那么z=xy，这里x∈A和y∈C，因为A　 B 和C　 D，得出x∈B和y∈D因此z=xy∈BD因为z是AC的任意元素，得AC　 BD。

161161第2章 集合　　(2)和(3)的证明留作练习　　因为每一语言是一集合，前边介绍过的集合运算能应用于语言语言的连结积对∪和∩满足以下定理所说的关系式　　定理2.4-2 设A、B、C和D是Σ上的任意语言，那么162162第2章 集合　　证　　(1) 先证AB∪AC　 A(B∪C)　　因为A　 A，B　 B∪C和C　 B∪C，由定理2.4-1的(4)得AB　 A(B∪C)和AC　 A(B∪C) 因此，AB∪AC　 A(B∪C)　　再证A(B∪C)　 AB∪AC　　如果z是A(B∪C)的任一元素，那么z=xy，这里x∈A和y∈B∪C因此，x∈A∧y∈B 或x∈A∧y∈C，得出z∈AB或z∈AC所以，z∈AB∪ACz是任意的，故A(B∪C)　 AB∪AC163163第2章 集合　　(2)、(3)、(4)的证明留作练习　　定理2.4-2(3)和(4)中的包含可能是真包含例如，如果A={Λ,0,01}，B={01,11}和C={101}那么A(B∩C)=　 ，但AB∩AC={0101}　　定义2.4-4 设A是Σ上的一个语言，语言An归纳地定义如下:　　(1) A0={Λ},　　(2) An+1=An·A，对n∈N。

　　语言An是集合A自身连结n次所以，如果z∈An(n≥1)，那么z=x1x2…xn，这里xi∈A，1≤i≤n164164第2章 集合　　例 2.4-4 设Σ={a,b}和A={Λ,b,ab}，那么165165第2章 集合　　定理2.4-3 设A和B是Σ*的子集合，并设m和n是N的任意元素，那么　　(1) Am·An=Am+n　　(2) (Am)n=Amn　　(3) A　 BAn　 Bn　　证 (1)、(2)部分留作练习现用归纳法证明(3)　　(i) (基础)n=0时，A0={Λ}和B0={Λ}，所以An　 Bn　　(ii) (归纳)设对任一n，An　 Bn，现证An+1　 Bn+1根据定理2.4-1(4)，如果An　 Bn和A　 B，那么An·A　 Bn·B，即An+1　 Bn+1　　在语言的幂运算的基础上，我们可以定义语言上的另一种叫闭包的重要运算166166第2章 集合　　定义2.4-5 设A是Σ*的子集，那么集合A*定义为167167第2章 集合　　集合A*通常称为A的星闭包，读做“A星”集合A+定义为集合A+通常叫做A的正闭包正闭包，读做“A正”。

　　闭包运算是语言上的一元运算注意x∈A+当且仅当对某些正的n∈N， x∈An x∈A*， 当且仅当对某些n∈N，x∈An168168第2章 集合　　例 2.4-5　　(1) 如果A={a}，那么(2) 169169第2章 集合　　如果Σ*的子集A取为Σ，那么A*就是Σ*，A+就是Σ+这说明我们把Σ上所有有限长串的集合记为Σ*，把Σ上不含空串的所有有限长串的集合记为Σ+，是因为这样的记法正和闭包运算的定义相一致　　由定义2.4-5即得下列定理170170第2章 集合　　定理2.4-4 设A是Σ上的语言，且n∈N，那么　　(1) A*={Λ}∪A+　　(2) An　 A*，对n≥0　　(3) An　 A+，对n≥1　　由定理2.4-4可推出下列定理　　定理2.4-5 设A和B是Σ上的语言，那么下列关系式成立:　　(1) A　 AB*　　(2) A　 B*A　　(3) (A　 B)(A*　 B*)　　(4) (A　 B)(A+　 B+)171171第2章 集合　　证 　　(1) 根据定理2.4-4(1)，B*={Λ}∪B+所以，AB*=A({Λ}∪B+)=A∪AB+，它含有A。

类似地可证(2)　　(3) 如果x∈A*，那么x∈An，对某些n≥0，但A　 B，所以根据定理2.4-3(3)，An　 Bn， 所以x　 Bn根据定理2.4-4(2)得x∈B*，故A*　 B*，一个类似的论证使(4)成立　　语言的连结积运算和闭包运算间满足以下关系172172第2章 集合　定理2.4-6 设A和B是Σ上的语言，那么下列关系式成立:173173第2章 集合　　证 　　(1) 我们仅证A*A=A+ 所以，A*A=A+174174第2章 集合　　(6) 我们仅证(A*B*)*=(A∪B)*　　先证(A*B*)*　 (A∪B)*　　因为A　 A∪B，所以A*　 (A∪B)*类似地，B*　 (A∪B)*， 这得出　　　　　　　　A*B*　 (A∪B)*(A∪B)*根据本定理(3)得　　　　　　　　　　A*B*　 (A∪B)*　　　　　　　(A*B*)*　 ((A∪B)*)*=(A∪B)*175175第2章 集合　　再证(A∪B)*　 (A*B*)*　　根据定理2.4-4(2)，A　 A*根据定理2.4-5(1)，A*　 A*B*，因此A　 A*B*。

类似地，B　 A*B*所以，A∪B　 A*B*，再根据定理2.4-5(3)得　　　　　　　　　(A∪B)*　 (A*B*)*　　其余部分的证明留作练习176176第2章 集合　　　　　　习 题　　1. 设A={Λ,a}，B={a,b}，C={ab}，列出下列集合:　　(1) A2　　(2) C3　　(3) CAB　　(4) A+　　(5) C*177177第2章 集合　　2. 证明定理2.4-1的(2)和(3)部分　　3. 证明定理2.4-2的(2)、(3)、(4)部分　　4. 证明定理2.4-3的(1)、(2)部分　　5. 如果A={Λ,a,a2,…,an,…}，B=A－{a2}，能推出A2=B2吗? 一般地，若An=Bn，n＞2，能推出A=B吗?　　6. 虽然A*=A+∪{Λ}，但A+=A*－{Λ}一般不成立设Σ={a}，试找出Σ*的最小子集A，使A+≠A*－{Λ}178178第2章 集合　　7. 设A、B、Bi(i=1,2,…)都是语言，证明　　8. 证明定理2.4-6的(2)、(3)、(4)、(5)及(6)中未证明的部分179179第2章 集合　9. 设A、B、C和D是语言，证明以下等式成立:180180第2章 集合　　10. 设A、B、C是Σ上的语言，举例说明以下等式不成立:181181第2章 集合　　*11. 证明如果A≠　 且A2=A，那么A*=A。

　　12. 用有限集合和集合运算描述Σ={a,b}上的下述语言(例如偶数长度的串的集合是{aa,ab,ba,bb}*):　　(1) 奇数长度的串的集合　　(2) 恰好包含一个a的串的集合　　(3) 或者以一个a开始，或者以两个b结束，或者两者都具备的串的集合　　(4) 至少含有3个连接a的串的集合　　(5) 包含子串“bbab”的串的集合182182第2章 集合　　　　2.5 集合的笛卡尔乘积　　定义2.5-1 　　(1) 两个元素a1、a2组成的序列记作〈a1,a2〉，称为二重二重组组或序偶序偶a1和a2分别称为二重组〈a1,a2〉的第一和第二个分量　　(2) 两个二重组〈a,b〉和〈c,d〉相等当且仅当a=c并且b=d　　(3) 设a1,a2,…,an是n个元素，定义　　　　　　〈a1,a2,…,an〉=〈〈a1,a2,…,an-1〉,an〉为n重组重组，这里n＞2183183第2章 集合　　让我们对定义作些说明:　　(1) 由两个二重组相等的定义可以看出，二重组中元素的次序是重要的，例如〈2,3〉≠〈3,2〉， 这一点和集合相等的定义不同，在集合中元素的次序是无关紧要的，例如{2,3}={3,2}。

　　(2) n重组是一个二重组，其第一分量是n-1重组〈2,3,5〉代表〈〈2,3〉,5〉而不代表〈2,〈3,5〉〉，按定义后者不是三重组，并且〈〈2,3〉,5〉≠〈2,〈3,5〉〉　　(3) 由二重组相等的定义容易推得两个n重组〈a1,a2,…,an〉和〈b1,b2,…,bn〉相等当且仅当ai=bi，1≤i≤n184184第2章 集合　　例如，由二重组相等的定义得〈〈a,b〉,c〉=〈〈d,e〉,f〉当且仅当c=f∧〈a,b〉=〈d,e〉，再由二重组相等的定义得〈a,b〉=〈d,e〉当且仅当a=d∧b=e这样，〈〈a,b〉,c〉=〈〈d,e〉,f〉当且仅当 a=d∧b=e∧c=f　　我们通常需要由集合族A1,A2,…,An的元素生成所有n重组，因而有以下定义185185第2章 集合　　定义2.5-2 　　(1) 集合A和B的叉积记为A×B，是二重组集合{〈a,b〉|a∈A∧b∈B}　　(2) 集合A1,A2,…,An的叉积记为A1×A2×…×An或　　 ，定义为这里n＞2186186第2章 集合　　叉积又叫做集合的笛卡尔乘积　　由定义可看出，　　 是n重组集合另外，对一切i，Ai=A时，　　 可简记为An。

187187第2章 集合　　例2.5-1 设A={a,b}，B={1,2,3}，C={p,q}，D={0}，E=　 　　(1) A×B={〈a,1〉,〈a,2〉,〈a,3〉,〈b,1〉,〈b,2〉,〈b,3〉}　　(2) A×B×C={〈a,1,p〉,〈a,1,q〉,〈a,2,p〉,〈a,2,q〉,〈a,3,p〉,〈a,3,q〉,〈b,1,p〉,〈b,1,q〉,〈b,2,p〉,〈b,2,q〉,〈b,3,p〉,〈b,3,q〉}　　如图2.5-1所示188188第2章 集合图 2.5-1189189第2章 集合　　(3) C×D={〈p,o〉,〈q,o〉}　　(4) D×(C2)=D×{〈p,p〉,〈p,q〉,〈q,p〉,〈q,q〉}　　　　　　 ={〈0,〈p,p〉〉,〈0,〈p,q〉〉,〈0,〈q,p〉〉, 〈0,〈q,q〉〉}　　注意，这里的〈0,〈p,p〉〉等不能写成〈0,p,p〉等，因为按照上述定义，它只是二重组而不是三重组　　(5) A×E= 　　当A和B是实数集合，那么A×B能代表笛卡尔平面的点的集合。

190190第2章 集合　　例2.5-2 设A={x|1≤x≤2}和B={y|0≤y}　　(1) A×B={〈x,y〉|1≤x≤2∧0≤y}　　(2) B×A={〈y,x〉|1≤x≤2∧0≤y}　　(1)和(2)的图像如图2.5-2所示　　由例2.5-2可看出，集合的笛卡尔乘积运算是不可交换的另外，结合律也不成立，因为(A1×A2)×A3和A1×(A2×A3)的元素的形式分别是〈〈a1,a2〉,a3〉和〈a1,〈a2,a3〉〉，按定义2.5-1，二者不可能相等但二元笛卡尔乘积在并与交上可分配191191第2章 集合图 2.5-2192192第2章 集合　定理2.5-1 如果A、B和C都是集合，那么193193第2章 集合　　证 (1) 设〈x,y〉是A×(B∪C)的任一元素，那么所以，A×(B∪C)=(A×B)∪(A×C)　　(2)、(3)、　(4)部分留给读者自证194194第2章 集合　　定理2.5-2 如果所有Ai(i=1,2,…,n)都是有限集合， 则　　　　　|A1×A2×…×An|=|A1|·|A2|…｜An|　　证 n=1时，|A1|=|A1|显然成立。

对n≥2用归纳法证明　　n=2时，设|A1|=p，|A2|=q，A1中的每一个元素与A2中的q个不同元素可构成q个不同序偶，故共可构成pq个不同序偶，所以　　　　　　　　　|A1×A2|=pq=|A1|·|A2|195195第2章 集合　　设对任意n≥2定理成立，现证n+1也成立　　　|A1×A2×…×An×An+1| =|A1×A2×…×An|·|An+1|　　　　　　　　　　　　　 =|A1|·|A2|…|An|·|An+1|这里第一步是根据叉积定义和基础步骤，第二步是根据归纳假设所以，对一切n≥1，定理成立　　最后说明一点: n重组的概念可以推广到n=1的情况，称〈a〉为一重组重组这主要为了在一些场合能方便地与多重组统一叙述，它实质上仍代表一个元素196196第2章 集合　　　　　　　习 题　　1. 证明定理2.5-1中的(2)、(3)、(4)　　2. 如果A={a,b}和B={c}，试确定下列集合:　　(1) A×{0,1}×B　　(2) B2×A　　(3) (A×B)2197197第2章 集合　　3. 设A={0,1}，构成集合ρ(A)×A　　4. 设A、B、C和D是任意集合，试证明:　　　　　　(A∩B)×(C∩D)=(A×C)∩(B×D)　　5. 试证明: A×B=B×A　 A=　 ∨B=　 ∨A=B。

　　*6. 指出下列各式是否成立:。