离散第2讲-广义并交、笛卡尔、归纳定义-PPT.ppt

离散第2 讲 广义并交、笛卡尔、归纳定义vvPowerPoint Template_Sub PowerPoint Template_Sub 1.1 集合的概念与表示1.2 集合运算1.3 集合的归纳定义第第22讲讲 集合的运算与归纳定义集合的运算与归纳定义vv集合运算与归纳定义集合运算与归纳定义 Page 7 to 13 Page 7 to 13离散数学离散数学第第22讲讲v内容提要 集合的运算广义并、广义交运算序偶和n 元有序组笛卡尔积 集合的归纳定义集合的归纳定义方法集合定义的自然数第第22讲讲 集合的运算与归纳定义集合的运算与归纳定义v集合族的概念 定义1.7：称每个元素都是集合的集合为集合族（collection）。若集合族C 可表示为C=Sd|d D，则称D 为集合族C 的标志集（index set）。C=0,0,1,0,1,2,C=Nd|d I+第第22讲讲 集合的运算与归纳定义集合的运算与归纳定义v集合的广义并和广义交 定义1.8：设C 为非空集合族（1）C=x|存在某个S，满足S C 并且xS C 称为C 的广义并(C中所有集合的并)（2）C=x|对任意的S，如果S C 则一定有xS C 称为C 的广义交(C中所有集合的交)例如 C=0,0,1,0,1,2,C=N,C=0 C=Nd|d I+，C=,C=第第22讲讲 集合的运算与归纳定义集合的运算与归纳定义v广义并、交运算实例A,B=A BA,B=A BA,B,C=A B CA,B,C=A B C=,=,=,A=A,A=第第22讲讲 集合的运算与归纳定义集合的运算与归纳定义大家应该也有点累了，稍作休息大家有疑问的，可以询问和交流 大家有疑问的，可以询问和交流88v序偶(ordered pairs)如何在集合的基础上定义出次序的概念？定义1.9：设a,b 为任意对象，称集合a,a,b为二元有序组，或序偶，简记作。其中a称为序偶 的第一分量，b 称为序偶的 第二分量。定理1.17：对任意序偶,，=当且仅当a=c 且b=d。可以是单个客体，集合，甚至序偶第第22讲讲 集合的运算与归纳定义集合的运算与归纳定义vn元有序组 定义1.10：n 元有序组 可以从二元有序组（序偶）出发，递归地定义如下=a1,a1,a2=,a3=,an其中ai称为n 元有序组的第i 分量 本质上，n 元有序组依然是序偶 定理1.18：对任意对象a1,a2,an，b1,b2,bn，=当且仅当a1=b1，a2=b2，an=bn第第22讲讲 集合的运算与归纳定义集合的运算与归纳定义v集合的笛卡尔积 定义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第第22讲讲 集合的运算与归纳定义集合的运算与归纳定义v笛卡尔积运算举例 例1.10 A=1,2,B=a,b,c,C=,R 为实数集AB，BAABC，A(BC)A，AR2，R3第第22讲讲 集合的运算与归纳定义集合的运算与归纳定义v笛卡儿积的性质 定理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|第第22讲讲 集合的运算与归纳定义集合的运算与归纳定义vvPowerPoint Template_Sub PowerPoint Template_Sub 1.1 集合的概念与表示1.2 集合运算1.3 集合的归纳定义第第22讲讲 集合的运算与归纳定义集合的运算与归纳定义v集合的表示方法 列举法 描述法 试定义算术表达式的集合SS=123,55,1+2,100，(993)10,?S=x|x 是一算术表达式?(1)如果x是整数，则xS（是算术表达式）(2)如果x,y S，则(+x)、(x)、(x+y)、(x y)、(x y)、(x y)均S（均是算术表达式）(3)只有有限次应用条款1、2所得的符号序列S 以上第三种定义方法称为归纳法第第22讲讲 集合的运算与归纳定义集合的运算与归纳定义v集合的归纳定义(inductive definition)一个集合的归纳定义由三部分组成：1、基础条款：指出某些元素属于欲定义之集合；奠基，确定集合的基本成员，其他成员可以此为基础逐步确定。一般来讲要求基础集合尽可能的小。2、归纳条款：指出由已确定元素构造新元素的规则；从基本元素出发，反复运用这些规则，可得到欲定义之集合的所有成员。3、终极条款：断定只有有限次应用条款1、2所得元素才是欲定义之集合的元素。保证整个定义过程所规定的集合只包括满足要求的那些对象。完备性条款纯粹性条款第第22讲讲 集合的运算与归纳定义集合的运算与归纳定义v归纳定义举例 例1.11 归纳定义偶数集合E+基础条款：0E+归纳条款：如果xE+，那么x+2 E+如果xE+，那么x-2 E+终极条款：只有有限次应用条款1、2所得元素才是E+的元素 第第22讲讲 集合的运算与归纳定义集合的运算与归纳定义v与形式语言有关的一些概念 字母表：指有限非空的符号的集合，一般用 表示二进制基数的集合=0，126个英文字母定义的集合=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第第22讲讲 集合的运算与归纳定义集合的运算与归纳定义v归纳定义字的概念 是一个字母表，+是 上字的集合。+的归纳定义：1、基础条款：如果a，则a+（或+）2、归纳条款：如果x+且，则x+3、终极条款：只有有限次应用条款1、2所得之元素才是+之元素 例如=0，1+=0，1，00，01，10，11，000，001，010，011，第第22讲讲 集合的运算与归纳定义集合的运算与归纳定义v归纳定义*=+*可归纳定义如下：1、基础条款：*2、归纳条款：如果x*且，则 x*3、终极条款：只有有限次应用条款1、2所得之元素才是*之元素 对于某个字母表，如果L*，则L 称为 上的一个形式语言(formal language)第第22讲讲 集合的运算与归纳定义集合的运算与归纳定义v归纳定义字头和字尾 字w 的字头w 可以归纳定义如下：1、基础条款：是w 的字头2、归纳条款：如果w 为w 的字头，且w=w w”（其中，w、w”*），则w 也是w 的字头3、终极条款：只有有限次应用条款1、2所得之元素才是w 的字头 若字w=0100011，则w 的字头有哪些？若w 为w 的字头，且w=ww，则w 称为w 的字尾 请归纳定义字尾的概念第第22讲讲 集合的运算与归纳定义集合的运算与归纳定义v自然数 从本质上看自然数是满足下列特性的一列符号：它们中有一个为首的符号每个符号都有且仅有一个直接后继符号为首的符号不是任何符号的直接后继符号没有两个符号具有相同的直接后继符号自然数仅指这列符号中的符号第第22讲讲 集合的运算与归纳定义集合的运算与归纳定义v皮亚诺五公理 皮亚诺（Peano）用五条公理刻画自然数的概念P1.至少有一个客体是自然数，记为0P2.如果n 是自然数，那么n 必定恰有一个直接后继，记为nP3.0 不是任何自然数的直接后继P4.如果自然数m，n 的直接后继m，n 相同，则m=nP5.没有不满足上述条件的客体是自然数第第22讲讲 集合的运算与归纳定义集合的运算与归纳定义v归纳定义自然数 归纳定义条款0N如果xN，则x+1 N除有限次应用上述条款得到的元素外，N 中无其它元素 能否作为自然数的定义？0是什么？+又是什么？第第22讲讲 集合的运算与归纳定义集合的运算与归纳定义v用集合定义自然数 为在集合论中定义自然数，首先要选择一个集合作为为首的那个自然数，然后要确定一种集合运算作为求直接后继的运算 用 作为起始自然数，用如下定义的运算作为求直接后继运算 定义6：设A 是任意集合，称集合 A 为A 的直接后继集合，如果 A=A A=,=,=,第第22讲讲 集合的运算与归纳定义集合的运算与归纳定义v用集合定义自然数 自然数的归纳定义基础条款：N归纳条款：如果xN，则x=x x N终极条款（略）N=,把 记作0，则N=0,0,0,0,可以证明，如此定义的自然数满足皮亚诺5公理 有了自然数，便可进一步定义自然数集合上的运算第第22讲讲 集合的运算与归纳定义集合的运算与归纳定义