离散数学集合自然数与自然数集省公共课一等奖全国赛课获奖课件.pptx

第六章 集合6.1 集合基本概念集合基本概念6.2 集合基本运算集合基本运算6.3 全集和集合补全集和集合补 6.4 自然数与自然数集自然数与自然数集6.5 包含与排斥原理包含与排斥原理第1页后继：后继：A+=A A 定义定义1 A是一个给定集合，存在一个集合叫做是一个给定集合，存在一个集合叫做A后继后继，记为，记为A+。例例 设设A=a,则则 A+=a a=a,a 例例 设设B=a,b,则则 B+=a,b a,b=a,b,a,b第2页自然数(冯诺伊曼 John von Neumann,1912月28日生于匈牙利,1957年2月8日卒于美国)0=1=2=，3=，4=，1=02=0，1=1+3=0，1，2=2+4=0，1，2，3=3+第3页自然数定义定义定义2 对于一个集合对于一个集合S，假如它是空集假如它是空集（亦即（亦即0），），或者有一个自然数或者有一个自然数n，使得，使得S=n+，则称则称S为一个自然数。为一个自然数。0=1=0=0+2=0，1=1+3=0，1，2=2+4=0，1，2，3=3+第4页后继、前驱后继、前驱 对于任意两个自然数对于任意两个自然数m和和n，假如假如m=n+，即，即 m=n n，称称m为为n后继后继，能够记为，能够记为 m=n+1，也称也称n为为m前驱前驱，也能够记为，也能够记为 n=m-1。第5页自然数集 N定义定义3 存在一个由全部自然数组成集合叫存在一个由全部自然数组成集合叫自然数集自然数集，记为，记为 N第6页皮亚诺公设(Peanos Axioms)设设N表示自然数集。则：表示自然数集。则：10 N2假如假如n N，那么，那么n+N，30不是任何自然数集后继，即不存在自然数不是任何自然数集后继，即不存在自然数m N，使得使得0=m+。4n和和m均是自然数，假如均是自然数，假如n+=m+，那么，那么n=m。5如如S是是N子集，有性质子集，有性质 (1)0 S,(2)假如假如n S，那么，那么n+S，则有则有 S=N。第7页数学归纳法数学归纳法皮亚诺公设第皮亚诺公设第5条条设设n是一个自然数，是一个自然数，P(n)表示一个与表示一个与n相关公式或命题，相关公式或命题，令令 S=n NP(n)为真为真。若证实了若证实了lP(0)为真，也即为真，也即0 S(归纳基础归纳基础)；l若若P(n)为真，则为真，则P(n+)也为真，也为真，即若即若n S，则，则n+S(归纳步骤归纳步骤)。则由皮亚诺公设第则由皮亚诺公设第5条条,得得S=N。第8页第二归纳法第二归纳法l若若 n=0时命题成立时命题成立，l假定当假定当n 小于等于小于等于k 时命题成立，能够证实时命题成立，能够证实 n等于等于k+1 时命题也成立。时命题也成立。则对于一切自然数命题成立。则对于一切自然数命题成立。这种归纳方法又叫这种归纳方法又叫第二归纳法第二归纳法。第9页性质 设设n1,n2和和n3是三个任意自然数，若是三个任意自然数，若n1 n2,n2 n3，则，则n1 n3。设设n1和和n2是两个任意自然数，则下述三个式是两个任意自然数，则下述三个式中有一个成立：中有一个成立：n1 n2,n1=n2,n2 n1设设S是自然数集任意非空子集，则存在是自然数集任意非空子集，则存在n0 S，使得，使得n0S=。第10页例1 (传递性)设设n是一个自然数，求证：是一个自然数，求证：若若n1和和n2为两个集合，且为两个集合，且n1 n2，n2 n，则，则n1 n。设设 S=n N若有若有n1,n2,且且n1 n2，n2 n，则，则n1 n，要证要证S=N。证实思绪：证实思绪：0 S?若若n S，n+=n+1 S?第11页例1证（续）证（续）若若n S，要证，要证n+=n+1 S。设有两个集合设有两个集合n1和和n2，且，且 n1 n2，n2 n+=nn。因因n2 n n，所以，所以n2 n或者或者n2 n。若若n2 n，因为，因为n S，所以，所以n1 n。若若n2 n，则，则n2=n，即，即n1 n2=n。总而言之总而言之n1 n n n=n+,故故 n+=n+1 S。所以归纳得证所以归纳得证S=N。第12页19Zermelo(蔡梅罗)定义自然数 0=1=2=3=4=显然，显然，012341234 但但“”不不满满足足传递传递性性，未能准确刻画出自然，未能准确刻画出自然数本身所固有良好性数本身所固有良好性质质。第13页例例 求证：对于任意自然数求证：对于任意自然数m和和n，若若n m,则则n+m或者或者n+=m之一之一成立成立.证实：对证实：对m用归纳法。用归纳法。若若m=n+，则则 nmm成立成立,此时有此时有n+=m。归纳假设对任意归纳假设对任意m，若若n m，则，则n+=m，或者，或者n+m之一成立。之一成立。考查考查m+=m m,若若n m+=mm，n m mn mn=mn+=m+n+mn+m+n+=m第14页例例 求证：对于任意自然数求证：对于任意自然数m和和n，若若n m,则则n+m或者或者n+=m之一之一成立成立.证实：对证实：对m用归纳法。用归纳法。若若m=n+，则则 nmm成立成立,此时有此时有n+=m。归纳假设对任意归纳假设对任意m，若若n m，则，则n+=m，或者，或者n+m之一成立。之一成立。考查考查m+=m m,若若n m+=mm，则则n n=m，或者或者n m。于是有于是有n+=m+,或者或者n+=m，或者，或者n+m之一成立。之一成立。从而分别有从而分别有n+=m+，或者n+=m m+,或者n+m m+之一成立之一成立,即有即有n+=m+或者或者n+m+之一成立。之一成立。所以归纳得证结论成立。所以归纳得证结论成立。第15页例例2(p69)证实：对于任意自然数证实：对于任意自然数m和和n，都有，都有 m n或者或者m=n或者或者n m之之一成立。一成立。证实：对证实：对n用归纳法。用归纳法。当当n=0时，时，n=.显然显然,对于任意自然数对于任意自然数m,只有两种情况：只有两种情况：m=,或者或者 m(对于非对于非0自然数自然数)即有即有 m=n,或者或者n m之一成立之一成立.能够对m利用数学归纳法证实(详见教材)第16页例例2(p69)证实：对于任意自然数证实：对于任意自然数m和和n，都有，都有 m n或者或者m=n或者或者n m之之一成立。一成立。当当n=0时时，已经证实了结论成立。，已经证实了结论成立。对对n作归纳假设作归纳假设，假设对任意自然数，假设对任意自然数m,有有n m,或者或者n=m，或者，或者m n三者之一成立。三者之一成立。现在考查对于现在考查对于n+=n+1情况。情况。n mn=mm nn+mn+=mm n+第17页例例2(p69)证实：对于任意自然数证实：对于任意自然数m和和n，都有，都有 m n或者或者m=n或者或者n m之之一成立。一成立。当当n=0时时，已经证实了结论成立。，已经证实了结论成立。对对n作归纳假设作归纳假设，假设对任意自然数，假设对任意自然数m,有有n m,或者或者n=m，或者，或者m n三者之一成立。三者之一成立。现在考查对于现在考查对于n+=n+1情况。情况。n+=n n，对于任意自然数，对于任意自然数m，若若n m,则由对则由对m用归纳法能够证实用归纳法能够证实 n+m或者或者n+=m之一成立之一成立(见前页见前页)。若若n=m，则，则m m=n，即，即m n n=n+。若若m n，则，则m n n=n+。即对即对n+满足满足:对于任意自然数对于任意自然数m,有有m n+,或者或者m=n+，或者，或者n+m三者之一成立。三者之一成立。第18页例3(p70)设有数目相等两堆棋子，两人轮番从任一设有数目相等两堆棋子，两人轮番从任一堆里取出任意颗棋子，但不能不取，也不能堆里取出任意颗棋子，但不能不取，也不能同时在两堆里取。要求谁最终取完，谁胜利。同时在两堆里取。要求谁最终取完，谁胜利。求证能够确保让后取者必胜。求证能够确保让后取者必胜。第19页例3(p70)求证能够确保让后取者必胜。求证能够确保让后取者必胜。证实证实：对每堆棋子数目：对每堆棋子数目n 作归纳。作归纳。当当n=1时时，先取者必须取走二堆各一颗中一粒，且，先取者必须取走二堆各一颗中一粒，且仅能取一粒，后者取剩下一粒。后取者胜。仅能取一粒，后者取剩下一粒。后取者胜。若若nkk时时，命题成立。，命题成立。当当n=k+1时时，先取者只能在一堆中取，若全部取完，先取者只能在一堆中取，若全部取完一堆，那么后取者取完另一堆，后取者胜。若先取一堆，那么后取者取完另一堆，后取者胜。若先取者取者取r 粒粒(0rk+1)，则后取者在另一堆也取，则后取者在另一堆也取r 粒。粒。此时该先取者取，而二堆数目依旧相等，但数目个此时该先取者取，而二堆数目依旧相等，但数目个数为数为k+1-rkk，由归纳假定先取者不论怎样取，后取，由归纳假定先取者不论怎样取，后取者一定能够胜。者一定能够胜。第20页集合归纳定义（递归定义）基础条款基础条款 指出一些事物属于集合，给集指出一些事物属于集合，给集合以基本元素，使所定义集合非空。合以基本元素，使所定义集合非空。归纳条款归纳条款指出由集合已经有元素结构新指出由集合已经有元素结构新元素方法。元素方法。最小性条款最小性条款断言一个事物除非能有限次断言一个事物除非能有限次应用基础条款和归纳条款组成外，那么这个应用基础条款和归纳条款组成外，那么这个事物不是集合组员。事物不是集合组员。注：最小性条款形式可能不一样，结果可能是等价，全部服务于一个目标，既指明所定义集合是满足基础条款与归纳条款最小集合。第21页例例4(p70)用归纳定义集合用归纳定义集合S=n N3整除整除n 设设S是一个集合，它满足以下三条：是一个集合，它满足以下三条：3 S,且且0 S；假如假如x S，y S，那么，那么x+y S；S中元素均是有限次地利用中元素均是有限次地利用和和得到。得到。注：第注：第条也可改为：条也可改为：A是一个任意集合，是一个任意集合，若若3 A，且，且0 A，且若，且若x,y A，则，则x+y A，那么那么SA。N满足 第22页例例4(补)求证：T=S,这里 T=3n|n N.证实：先证TSS。记P(n)表示3n属于S。当n=1时，3*1=3属于S，故P(1)显然成立。归纳假设P(k)成立，则 3*(k+1)=3*k+3也属于S。即有P(k+1)成立。由归纳法，TSS得证。再证实STT。由基础条款，0、3属于S，显然，0、3都是3倍数，故0、3都属于T。假定x与y都属于S，而且都属于T，则 x+y也属于S，同时也是3倍数，即属于T。即有归纳条款得到新元素也属于T，故STT得得证证。第23页例例 用归纳定义集合用归纳定义集合D=n N6整除整除n 设设D是一个集合，它满足以下三条：是一个集合，它满足以下三条：6 D,且且0 D；假如假如x D，y D，那么，那么x+y D；D中元素均是有限次地利用中元素均是有限次地利用和和得到。得到。N与S都满足定义D 第24页例5(p70)设设 是一个字母表。是一个字母表。*是包含空字是包含空字全部全部中中字母组成字符串为元素集合。给出字母组成字符串为元素集合。给出*归纳定义。归纳定义。*是有以下三条一个集合：是有以下三条一个集合：*；若若x *，且，且 a，则，则 ax*；*中元素均是有限次地利用条款中元素均是有限次地利用条款所得。所得。第25页第六章 集合6.1 集合基本概念集合基本概念6.2 集合基本运算集合基本运算6.3 全集和集合补全集和集合补 6.4 自然数与自然数集自然数与自然数集6.5 包含与排斥原理包含与排斥原理第26页