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