集合函数数列与求和.ppt

离散数学第2章集合、函数、数列与求和,2,2.1集合,定义1：集合是一组无序的对象定义2：集合中的对象也称为该集合的元素，或成员。如果一个集合的元素的数目是有限的并且不是很多，便可以通过列举出它的所有元素来描述它。A=1,2,3,4一个集合由它的元素所决定而与其元素顺序无关.A=1,3,4,2集合中的某些元素可以重复列举多次，但集合中只包含一个这样的元素。A=1,2,2,3,4如果集合是一个包含了很多元素的有限集或是无限集，可以通过列举集合中每个元素必须满足的性质来描述。B=xx是正偶数,3,定义3：两个集合相等当且仅当它们有相同的元素。X与Y相等，记做X=Y。用符号表示，X=Y当且仅当,例：A=xx2+x-6=0B=2,-3A=B,4,子集,定义4：集合A是集合B的子集当且仅当A的每个元素也是B的元素。AB。,任何集合X是其自身的子集，因为X中的每一个元素在X中。,例：C=1,3A=1,2,3,4则C是A的一个子集,A是B的子集，当且仅当x(xAxB)为真,定义5：如果X是一个有限集合，令X是集合X的基数，即集合X中元素的个数如果x在X中，记做xX；如果x不在X中，记做xX。没有元素的集合称为空集（或零集）用符号表示,=,2.1.2幂集,如X是Y的子集但X不等于Y,则X是Y的一个真子集空集是任何集合的子集定义7：集合X的所有子集的集合，称为X的幂集，用P(X)表示,7,例,如A=a,b,cP(A)的成员：,a,b,c,a,b,a,c,b,c,a,b,cA=3，P(A)=23=8,8,定理,如X=n，则P(X)=2n,9,2.1.3笛卡儿积,一个由两个元素组成的有序对(或序偶)，写为(a,b)(a,b)=(c,d)当且仅当a=c,b=d.定义8：有序n元组（a1,a2,an）是以a1为第一个元素，a2为第二个元素，an为第n个元素的有序组定义9：X,Y集合，XY称为X和Y的笛卡儿积，是所有有序对(x,y)的集合，其中xX,yY。即XY=(x,y)|xX,yY,10,例,X=1,2,3Y=a,bXY=1,a,1,b,2,a,2,b,3,a,3,bYX=a,1,a,2,a,3,b,1,b,2,b,3XX=1,1,1,2,1,3,2,1,2,2,2,3,3,1,3,2,3,3YY=a,a,a,b,b,a,b,b,11,XY=1,a,1,b,2,a,2,b,3,a,3,b,12,例,四种餐前开胃菜：r=排骨，n=烤干酪辣味玉米片，s=虾，f=炸干酪；三种主菜：c=鸡肉，b=牛肉，t=鲑鱼。若令A=r,n,s,f，E=c,b,t，则笛卡儿积AE包含了12种可能的由一种开胃菜和一种主菜组成的正餐。,13,n元组,一个n元组记为(a1,a2,.,an)，这同样也是考虑顺序的。如(a1,a2,.,an)=(b1,b2,.,bn)当且仅当a1=b1,a2=b2,.,an=bn集合X1,X2,.,Xn的笛卡儿积定义为所有n元组(x1,x2,.,xn)构成的集合，其中xiXi（i=1,.,n），并记为X1X2Xn。,14,XYZ,X=1,2Y=a,bZ=c,dXYZ=?XYZ=(1,a,c),(1,a,d),(1,b,c),(1,b,d),(2,a,c),(2,a,d),(2,b,c),(2,b,d),2.1.4使用带量词的集合符号,xS(P(x)x(xSP(x)例：语句xR(x20)：任意实数的平方是非负的xZ(x2=1)：有某个整数，其平方等于1,15,2.1.5量词的真值集合,集合理论+谓词逻辑谓词P的论域是D,定义P的真值集合：D中元素x使得P(x)为真的元素组成的集合。记为：xD|P(x)例：论域是整数集合，P(x):|x|=1,Q(x):x2=2R(x):|x|=x，问谓词P(x),Q(x),R(x)的真值集合分别是什么？解：P的真值：xZ|x|=1=1,-1Q的真值：xZ|x2=2=R的真值：xZ|x|=x=N(非负整数集合),16,17,2.2集合运算,并集XY=x|xXyY交集XY=x|xXyY差集X-Y=x|xXxY不相交XY=S两两不相交的,18,例,A=1,3,5,B=4,5,6AB=1,3,4,5,6AB=5AB=1,3BA=4,6,19,例,集合1,4,5和2,6是不相交的S=1,4,5,2,6,3,7,8是两两不相交的,20,全集，补,U：全集X：子集集合UX称为X的补，表示为X,21,例,A=1,3,5如U=1,2,3,4,5则A=2,4如给定U=1,3,5,7,9则A=7,9,22,Venn图：关于集合的形象化表示,1,2,4,3,A,B,1,2,4,3,A,B,2.2.2集合恒等式,U全集,X,Y,ZU结合律(AB)C=A(BC)(AB)C=A(BC)交换律AB=BAAB=BA,分配律A(BC)=(AB)(AC)A(BC)=(AB)(AC)同一律A=A,AU=A互补律A=U,A=,幂等律AA=A,AA=A上下界律AU=U,A=吸收律A(AB)=A,A(AB)=A,对合律A=A零一律=U,U=德摩根律(AB)=AB,AB=AB,24,SandS,S为集族：集合的集合S=x|对于某些XS,xXS=x|对于所有XS,xXS=A1,A2,AnS=Ai,S=Ai,任意集族S的并集是由所有至少属于S的一个集合X的元素构成的集合”任意集族S的交集是由所有属于S的每个集合X的元素x构成的集合,例S1=a,b,c,zS2=1,2,3,4,5,6,7,8,9,0S3=!,#,$,%S4=+,-,*,/S5=A,B,C,ZS=S1,S2,S3,S4,S5S=任何属于S中的一个集合Si的元素构成的集合,25,26,例,Ai=i,i+1,i+2S=A1,A2,S=Ai=1,2,S=Ai=n,n+1,n+2,27,划分,一个由集合X的非空子集的整体组成的S，如X的每个元素都只属于S的某一个元素，S就称为X的一个划分。,例：集合X=1,2,3,4,5,6,7,8S=1,4,5,2,6,3,7,8S是X的一个划分,28,问题求解要点,本节复习1.给出集合的定义。2.集合怎样用符号表示？3.如果X是有限集，|X|表示什么？4.如何表示x是集合X的元素？5.如何表示x不是集合X的元素？6.如何表示空集？7.设X和Y是集合，给出X=Y的定义。8.设X和Y是集合，给出XY的定义。9.给出X是Y的真子集的定义。10.什么是集合X的幂集？怎样表示？,29,11.如果X有n个元素，X的幂集有多少个元素？12.给出X与Y的并的定义。怎样表示X与Y的并集？13.如果是一个集族，的并集的定义是什么？怎样表示的并集？14.给出X与Y的交的定义。怎样表示X与Y的交集？15.如果是一个集族，的交集的定义是什么？怎样表示的交集？16.给出X与Y是不相交的集合的定义。17.什么是两两不相交的集族？18.给出集合X与Y的差集的定义。怎样表示差集？19.什么是全集？20.什么是集合X的余集？如何表示？,2.3函数,距离=速度时间如果以每小时55英里的速度行进t个小时，则D=55t，其中t：时间，D：行进的距离函数将集合X中的每一个元素指派为集合Y中惟一的一个元素。（集合X和集合Y可能相同也可能不同。）上式定义的函数将每一个非负实数t指派为55t。例如，将t=1指派为55；将t=3.45指派为189.75；等等。可以将这种指派表示为有序对：(1,55),(3.45,189.75)。形式化地说，函数是一种特殊的由有序对组成的集合。,定义1,定义：令A和B为非空集合。从A到B的函数f是对元素的一种指派，对A的每个元素恰好指派B的一个元素。f(a)=b表示f指派给A中的元素a的唯一B中的元素是bf:AB，表示f是从A到B的函数f是从A到B的函数，集合A称为f的定义域。集合b|(a,b)f,B的一个子集,称为f的值域,例,集合f=(1,a),(2,b),(3,a)是从X=1,2,3到Y=a,b,c的函数。,例,集合(1,a),(2,a),(3,b)不是从X=1,2,3,4到Y=a,b,c的函数因为X中的元素4没有被指派为Y中的元素。,例,集合(1,a),(2,b),(3,c),(1,b)不是从X=1,2,3到Y=a,b,c的函数因为1没有被指派为Y中惟一的元素。,例,xn=(axn-1+c)modm,例：m=11,a=7,c=5,s=3x1=(ax0+c)modm=(7*3+5)mod11=4x2=(ax1+c)modm=(7*4+5)mod11=0类似地，可以算出x3=5,x4=7,x5=10,x6=9,x7=2,x8=8,x9=6,x10=3,定义3.1.17,x小于等于x的最大整数x大于等于x的最小整数8.3=88.3=9,2.3.2一对一函数和映上函数,单射,满射函数,映上函数,一对一的,定义5,单射(一对一）：从X到Y的函数f称为是一对一的，如果对每个yY，至多有一个xX使得f(x)=y。例2.2.22从X=1,2,3到Y=a,b,c,d的函数f=(1,b),(3,a),(2,c)是一对一的,例,函数f=(1,a),(2,b),(3,a)不是一对一的，因为f(1)=a=f(3)。设X是有社会保障号的人的集合。对每个人xX，指定他或她与其社会保障号SS(x)相对应，这样就得到了一个一对一的函数，因为需要给不同的人指定不同的社会保障号。由于这个对应是一对一的，因此可以把社会保障号用做身份证明。,从X到Y的函数f是一对一的，等价于：对所有的x1，x2X，若f(x1)=f(x2)，则x1=x2。用符号表示为x1x2(f(x1)=f(x2)(x1=x2),例,证明从正整数集合到正整数集合的函数f(n)=2n+1是一对一的。张明：必须证明对所有正整数n1和n2，如果f(n1)=f(n2)，则n1=n2。先假定f(n1)=f(n2)，依据f的定义，将这个等式变形为2n1+1=2n2+1将两边同时减1，然后同除以2，可得n1=n2所以，f是一对一的。,例,如果存在x1和x2使得f(x1)=f(x2)且x1x2，那么一个函数不是一对一的证明从正整数集合到整数集合的函数f(n)=2n-n2不是一对一的。必须找到正整数n1和n2，且n1n2，使得f(n1)=f(n2)f(2)=f(4),定义7,映上函数、满射函数：如果从X到Y的函数f的值域是Y，则称函数f为对Y映上的。例2.2.29从X=1,2,3到Y=a,b,c的函数f=(1,a),(2,c),(3,b)是一对一的，并且是对Y映上的。,例2,函数f=(1,b),(3,a),(2,c)不是对Y=a,b,c,d映上的，而是对a,b,c映上的。例,例,证明从正整数集合X到正整数集合Y的函数f(n)=2n-1不是对Y映上的。必须找到一个元素mY，使得对所有的nX，f(n)m。因为对所有的整数n，f(n)是奇数，所以可以选择一个正偶数y，例如选择y=2，有yY且对于所有的nX，f(n)y,定义8,如果一个函数既是一对一的又是映上的，则称这个函数为双射。例2.2.29从X=1,2,3到Y=a,b,c的函数f=(1,a),(2,c),(3,b)是一对一的，并且是对Y映上的。,2.3.3反函数,设f是从X到Y的一对一的、映上的函数。可以证明(y,x)|(x,y)f也是一个从Y到X的一对一的、映上的函数。将这个新函数记做f-1，称为f的反（逆）函数（inverse）。,例,函数f=(1,a),(2,c),(3,b)的逆函数：f-1=(a,1),(c,2),(b,3),例,函数f(x)=2x是从R到R+上的一对一函数，其中R表示实数集，R+表示正实数集