《离散第2讲广义并交笛卡尔归纳定义》由会员分享，可在线阅读，更多相关《离散第2讲广义并交笛卡尔归纳定义（27页珍藏版）》请在金锄头文库上搜索。
1、 计算机专业基础课程计算机专业基础课程计算机专业基础课程计算机专业基础课程授课人：梁妍授课人：梁妍授课人：梁妍授课人：梁妍vvPowerPoint Template_Sub PowerPoint Template_Sub 1.1集合的概念与表示集合的概念与表示1.2集合运算集合运算1.3集合的归纳定义集合的归纳定义22vv集合运算与归纳定义集合运算与归纳定义集合运算与归纳定义集合运算与归纳定义 Page 7 to 13Page 7 to 13Page 7 to 13Page 7 to 13离散数学第离散数学第离散数学第离散数学第2 2 2 2讲讲讲讲v内容提要内容提要集合的运算集合的运算广义并
2、、广义交运算广义并、广义交运算序偶和序偶和n元有序组元有序组笛卡尔积笛卡尔积集合的归纳定义集合的归纳定义集合的归纳定义方法集合的归纳定义方法集合定义的自然数集合定义的自然数44v集合族的概念集合族的概念 定义定义1.7：称每个元素都是集合的集合为称每个元素都是集合的集合为集合族集合族（collection）。）。 若集合族若集合族C可表示为可表示为C = Sd | d D ，则称，则称D为为集合族集合族C的的标志集标志集（index set）。）。C = 0, 0, 1, 0, 1, 2, C = Nd | d I+ 55v集合的广义并和广义交集合的广义并和广义交定义定义1.8：设设C为非空集
3、合族为非空集合族（1）C = x | 存在某个存在某个S，满足，满足S C并且并且x S C称为称为C的的广义并广义并 (C中所有集合的并)（2）C = x | 对任意的对任意的S，如果，如果S C则一定有则一定有x S C称为称为C的的广义交广义交(C中所有集合的交)例如例如C = 0, 0, 1, 0, 1, 2, C = N, C = 0C = Nd | d I+，C = , C = 66v广义并、交运算实例广义并、交运算实例A, B = A BA, B = A BA, B, C = A B CA, B, C = A B C = = , = , = , A =A , A = 77v序偶序
4、偶(ordered pairs)(ordered pairs)如何在集合的基础上定义出如何在集合的基础上定义出次序次序的概念？的概念？定义定义1.9：设设a, b为任意对象，称集合为任意对象，称集合a, a, b为二元有序组，或为二元有序组，或序偶序偶，简记作，简记作。其中。其中a称称为序偶为序偶的的第一分量第一分量，b称为序偶的称为序偶的第二第二分量分量。定理定理1.17：对任意序偶对任意序偶, ， =当且仅当当且仅当a=c且且b=d。可以是单个客体，可以是单个客体，集合，甚至序偶集合，甚至序偶88vn n元有序组元有序组定义定义1.10： n元有序组元有序组可以从二元可以从二元有序组（序偶
5、）出发，递归地定义如下有序组（序偶）出发，递归地定义如下 = a1, a1, a2 = , a3 = , an其中其中ai称为称为n元有序组的元有序组的第第i分量分量本质上，本质上，n元有序组依然是序偶元有序组依然是序偶定理定理1.18：对任意对象对任意对象a1, a2, , an，b1, b2, , bn， = 当且仅当当且仅当a1=b1，a2=b2，an=bn99v集合的笛卡尔积集合的笛卡尔积 定义定义1.11：对任意集合对任意集合A1, A2，A1 A2叫做叫做A1, A2的的笛卡尔积笛卡尔积，定义如下：，定义如下：A1 A2 = | x A1，y A2说明说明 运算是左结合的运算是左结
6、合的A1 A2 An = (A1 A2 An1) An当当A1=A2=An=A时，时，A1 A2 An记作记作An A1 A2 An = | a1 A1，, an An1010v笛卡尔积运算举例笛卡尔积运算举例例例1.10 A=1, 2, B=a, b, c, C=, R为实数集为实数集AB，BAABC， A(BC)A， AR2， R31111v笛卡儿积的性质笛卡儿积的性质 定理定理1.20 设设A、B、C为任意集合，为任意集合， 表示表示，或或运算，那么：运算，那么：A (B C) = (A B) (A C) (B C) A = (B A) (C A) 定理定理1.21 对任意有限集合对任意
7、有限集合A1, A2, , An，有：，有：|A1 A2 An| = |A1|A2|An|1212vvPowerPoint Template_Sub PowerPoint Template_Sub 1.1集合的概念与表示集合的概念与表示1.2集合运算集合运算1.3集合的归纳定义集合的归纳定义1313v集合的表示方法集合的表示方法列举法列举法描述法描述法试定义算术表达式的集合试定义算术表达式的集合SS = 123, 55, 1+2, 100， (993)10, ?S = x | x是一算术表达式是一算术表达式 ?(1) 如果如果x是整数，则是整数，则x S（是算术表达式是算术表达式） (2) 如
8、果如果x, y S ，则，则(+ x) 、( x) 、(x + y) 、(x y) 、(x y) 、(xy) 均均 S （均（均是算术表达式是算术表达式） (3)只有有限次应用条款只有有限次应用条款1、2所得的符号序列所得的符号序列 S以上第三种定义方法称为归纳法以上第三种定义方法称为归纳法1414v集合的归纳定义集合的归纳定义(inductive definition) (inductive definition) 一个集合的一个集合的归纳定义归纳定义由三部分组成：由三部分组成：1、基础条款：基础条款： 指出某些元素属于欲定义之集合；指出某些元素属于欲定义之集合；奠基，确定集合的基本成员，其
9、他成员可以此为基础逐奠基，确定集合的基本成员，其他成员可以此为基础逐步确定。一般来讲要求基础集合尽可能的小。步确定。一般来讲要求基础集合尽可能的小。2、归纳条款：归纳条款： 指出由已确定元素构造新元素的规则；指出由已确定元素构造新元素的规则；从基本元素出发，反复运用这些规则，可得到欲定义之从基本元素出发，反复运用这些规则，可得到欲定义之集合的所有成员。集合的所有成员。3、终极条款：终极条款： 断定只有有限次应用条款断定只有有限次应用条款1、2所得元素所得元素才是欲定义之集合的元素。才是欲定义之集合的元素。保证整个定义过程所规定的集合只包括满足要求的那些保证整个定义过程所规定的集合只包括满足要求
10、的那些对象。对象。完完备备性性条条款款纯纯粹粹性性条条款款1515v归纳定义举例归纳定义举例 例例1.11 归纳定义偶数集合归纳定义偶数集合E+基础条款：基础条款：0 E+归纳条款：如果归纳条款：如果x E+，那么，那么x+2 E+ 如果如果x E+，那么，那么x-2 E+终极条款：只有有限次应用条款终极条款：只有有限次应用条款1、2所得元素才是所得元素才是E+的元素的元素 1616v与形式语言有关的一些概念与形式语言有关的一些概念字母表：字母表：指有限非空的符号的集合，一般用指有限非空的符号的集合，一般用 表示表示二进制基数的集合二进制基数的集合 =0，126个英文字母定义的集合个英文字母定
11、义的集合 =a, b, c, , x, y, z 字：字：指有限数目的符号所组成的串，若每一符号均取自字指有限数目的符号所组成的串，若每一符号均取自字母表母表 之上，则称为字母表之上，则称为字母表 之上的一个字，用之上的一个字，用 表示空字表示空字 01，100，101， a, aa, bike, iwefhweoi, .字的运算：字的运算：毗连毗连（或并置）（或并置） x=01, y=100, x与与y的毗连的毗连xy=01100 x=apple, y= , x与与y的毗连的毗连xy=apple1717v归纳定义归纳定义字的概念字的概念 是一个字母表，是一个字母表， +是是 上字的集合上字的
12、集合。 +的归纳定义：的归纳定义：1、基础条款：如果、基础条款：如果a，则，则a+（或（或+）2、归纳条款：如果、归纳条款：如果x+且且，则，则 x+3、终极条款：只有有限次应用条款、终极条款：只有有限次应用条款1、2所得之元素才所得之元素才是是 +之元素之元素例如例如 = 0，1 +=0，1，00，01，10，11，000，001，010，011， 1818v归纳定义归纳定义 * * *= + *可归纳定义如下：可归纳定义如下：1、基础条款：、基础条款：*2、归纳条款：如果、归纳条款：如果x*且且 ，则，则 x*3、终极条款：只有有限次应用条款、终极条款：只有有限次应用条款1、2所得之元素才
13、所得之元素才是是 *之元素之元素对于某个字母表对于某个字母表 ，如果如果L *，则，则L称为称为 上的上的一个一个形式语言形式语言(formal language)1919v归纳定义字头和字尾归纳定义字头和字尾字字w的的字头字头w可以归纳定义如下：可以归纳定义如下：1、基础条款：、基础条款： 是是w的字头的字头2、归纳条款：如果、归纳条款：如果w为为w的字头，且的字头，且w = w w”（其中（其中 ，w、 w” *），则），则w 也是也是w的字头的字头3、终极条款：只有有限次应用条款、终极条款：只有有限次应用条款1、2所得之元素才是所得之元素才是w的字头的字头若字若字w=0100011，则，
14、则w的字头有哪些？的字头有哪些？若若w为为w的字头，且的字头，且w=ww，则，则w称为称为w的的字尾字尾请归纳定义字尾的概念请归纳定义字尾的概念2020v自然数自然数从本质上看自然数是满足下列特性的一列符号：从本质上看自然数是满足下列特性的一列符号：它们中有一个为首的符号它们中有一个为首的符号每个符号都有且仅有一个直接后继符号每个符号都有且仅有一个直接后继符号为首的符号不是任何符号的直接后继符号为首的符号不是任何符号的直接后继符号没有两个符号具有相同的直接后继符号没有两个符号具有相同的直接后继符号自然数仅指这列符号中的符号自然数仅指这列符号中的符号2121v皮亚诺五公理皮亚诺五公理皮亚诺（皮亚
15、诺（Peano）用）用五条公理五条公理刻画自然数的概念刻画自然数的概念P1. 至少有一个客体是自然数，记为至少有一个客体是自然数，记为0P2. 如果如果n是自然数，那么是自然数，那么n必定恰有一个直接必定恰有一个直接后继，记为后继，记为nP3. 0不是任何自然数的直接后继不是任何自然数的直接后继P4. 如果自然数如果自然数m，n的直接后继的直接后继m，n相同，相同，则则m = nP5. 没有不满足上述条件的客体是自然数没有不满足上述条件的客体是自然数2222v归纳定义自然数归纳定义自然数归纳定义条款归纳定义条款0N如果如果xN，则，则x + 1N除有限次应用上述条款得到的元素外，除有限次应用上
16、述条款得到的元素外，N中无中无其它元素其它元素能否作为自然数的定义？能否作为自然数的定义？0是什么？是什么？+又是什么？又是什么？2323v用集合定义自然数用集合定义自然数为在集合论中定义自然数，首先要选择为在集合论中定义自然数，首先要选择一个集合一个集合作为为首作为为首的那个自然数，然后要确定的那个自然数，然后要确定一种集合运算一种集合运算作为求直接后继作为求直接后继的运算的运算用用作为起始自然数作为起始自然数，用如下定义的运算作为，用如下定义的运算作为求直接后继求直接后继运算运算定义定义6：设设A是任意集合，称集合是任意集合，称集合 A为为A的的直接后继集合直接后继集合，如果如果 A =
17、AA = = = = , , = , , = , , , 2424v用集合定义自然数用集合定义自然数自然数的归纳定义自然数的归纳定义基础条款：基础条款：N归纳条款：如果归纳条款：如果x N，则，则x= xx N终极条款（略）终极条款（略）N=, , , , , , , , 把把记作记作0，则，则N=0, 0, 0, 0, 可以证明，如此定义的自然数可以证明，如此定义的自然数满足皮亚诺满足皮亚诺5公理公理有了自然数，便可进一步定义自然数集合上的运有了自然数，便可进一步定义自然数集合上的运算算2525v本讲小结本讲小结主要内容主要内容广义并、交运算广义并、交运算序偶、序偶、n元有序组、集合的笛卡尔积元有序组、集合的笛卡尔积集合的归纳定义：基础条款、归纳条款、末端条款集合的归纳定义：基础条款、归纳条款、末端条款字母表、语言、字头、字尾字母表、语言、字头、字尾用集合归纳定义自然数用集合归纳定义自然数作业：作业：P15. 11、 15、16(1)(2)P19. 2、62626部分资料从网络收集整理而来，供大家参考，感谢您的关注！
