DOWNLOADING-课件.ppt

1、离散数学(7)陈斌gischenpku.edu2011.10.29目录数理逻辑集合论图论抽象代数集合论集合代数集合的基本概念集合运算集合的归纳定义关系有序组和集合的笛卡儿积二元关系、等价关系、序关系函数 函数及函数的合成特殊函数类函数的逆集合的归纳定义回顾：列举定义、描述定义归纳定义(inductive definition)基础条款规定某些元素为待定义集合成员，集合其它元素可以从基本元素出发逐步确定归纳条款规定由已确定的集合元素去进一步确定其它元素的规则终极条款规定待定义集合只含有基础条款和归纳条款所确定的成员基础条款和归纳条款称作“完备性条款”，必须保证毫无遗漏产生集合中所有成员终极条款又

2、称“纯粹性条款”，保证集合中仅包含满足完备性条款的那些对象集合的归纳定义归纳定义“圣诞节”基础条款耶稣基督降生的那天是圣诞节归纳条款如果某天是圣诞节，则这一天后的第365天也是圣诞节（不考虑闰年）终极条款除了上面两条所包括的日子，其它日子都不是圣诞节集合的归纳定义设个体域U为整数集，归纳定义偶数集E基础条款：0E归纳条款：若xE，则x+2E，x-2E终极条款：除了有限次使用上述条款确定的元素以外，E中没有别的元素奇数集O的定义？集合的归纳定义归纳定义“程序”基础条款：v:=e是程序（其中v是变元，e是算术表达式）归纳条款：若p1,p2是程序，则if c then p1 else p2 end

3、if也是程序（其中c是条件表达式）；若p是程序，则while c do p end while也是程序；若p1,p2是程序，则p1;p2也是程序终极条款（略）自然数的定义数学中“数”是最基本的原始概念，在集合论创立之后，采用集合来定义自然数，使得数学建立在更为简单的概念“集合”基础之上在算术公理化系统中，皮亚诺(Peano)的5大公理刻画了自然数的概念P1：至少有一个对象是自然数，记做0；P2：如果n是自然数，那么n必定恰有一个直接后继，记做nP3：0不是任何自然数的直接后继P4：如果自然数m,n的直接后继m,n相同，那么m=nP5：没有不满足上述条件的对象是自然数自然数的定义利用集合定义自然

4、数要考虑的几个问题找一个最简单的集合作为0找一种集合运算定义“直接后继”?？这种集合运算不可能得到0对应的那个集合可以通过集合关系反应自然数的顺序性质、自然数的定义自然数集N的归纳定义基础条款：N归纳条款：如果xN，则x=xx N终极条款（略）自然数集的列举定义,实际上有：1=0,2=0,1,3=0,1,20123同时也有03还有012312，410，1010体现了顺序关系，而且子集关系具有传递性自然数的定义如果我们用x=xN作直接后继会如何？,.0123但是没有13递归定义自然数的运算：、x0 xxy(xy)如：3+2=(3+1)=(3+0)=(3)=4=5自然数的定义递归定义自然数的运算：

5、、x00 xy(xy)x例子如：32(31)+3=(30)+3)+3=(0+3)+3=(0+2)+3=(0+1)3=(0+0)+3=(0)+3=3+3=6 归纳原理设集合A是归纳定义的集合，要证明A中所有元素具有性质P，即：x(xAP(x)，可以进行如下的证明：（归纳基础）针对归纳定义的基础条款，证明基础条款中的所有元素均使P(x0)真（归纳推理）证明归纳条款是“保持性质P的”，即在假设归纳条款中已确定元素x使P(x)真的前提下，证明用归纳条款中的操作g所生成的g(x)依然有性质P，即P(g(x)为真归纳原理证明：命题公式中左括号的数量等于右括号的数量设LA,RA分别表示公式A的左括号数量和右

6、括号的数量（归纳基础）：对于命题变元(或常元)p，Lp=Rp=0（归纳推理）：设LA=RA,LB=RB，那么L(A)=LA+1=RA+1=R(A)L(AB)=LA+LB+1=RA+RB+1=R(AB)所以对于一切命题公式，左括号数量等于右括号数量归纳原理既然自然数集合也是归纳定义的，对于自然数的一些性质，也可以通过归纳原理来证明即我们通常用的“数学归纳法”第一数学归纳法归纳基础：证明P(0)为真归纳过程：对于任意k0假设P(k)为真时，推出P(k+1)也为真结论：所有自然数n都使P(n)为真归纳原理证明对任意自然数有(0+1+2+n)2=03+13+23+n3归纳基础：当n=0，02=03归纳

7、过程设当n=k时，(0+1+2+k)2=03+13+23+k3成立，当n=k+1时，(0+1+2+k+(k+1)2=03+13+23+k3+(k+1)2+2(0+1+2+k)(k+1)=03+13+23+k3+(k+1)2+k(k+1)2=03+13+23+k3+(k+1)3归纳完成，命题得证归纳原理起始于任意自然数n0的数学归纳法证明所有大于等于n0的自然数都具有性质P起始于多个自然数的数学归纳法归纳基础：证明P(0),P(1)真归纳过程：对于任意k0假设P(k)为真时，推出P(k+2)也为真结论：所有自然数具有性质P推广到起始于多个自然数归纳原理证明：3分币和5分币可以组成8分以上任何币值

8、8=3+5;9=3+3+3;10=5+5假设k可以用3分和5分币组成，需要证明k+3时命题真，这是显然的，只要再加一个3分币即可允许有参变量的数学归纳法对于二元谓词P(m,n)，证明对于一切自然数m,n都为真，可以只对一个变量进行归纳，另一个作为参数归纳原理数学归纳法的正确性证明假设我们已经完成下面的推理归纳基础：P(0)真；归纳推理：k(P(k)P(k+1)但是还并非所有自然数都有性质P将这些不满足性质P的自然数构成一个非空自然数子集，这样，子集中必定有一个最小的自然数，设为m显然m0，记做n+1，这样n一定具有性质P，即P(n)为真n(P(n)P(n+1)k(P(k)P(k+1)k(P(k)P(k+1)假设推理结果与已经完成的归纳推理矛盾，所以假设错误所有自然数都有性质P关于课程教材O158/75计算机科学中的离散结构王元元,张桂芸编著，机械工业出版社 2019O158/60离散数学导论王元元,张桂芸编著，科学出版社 2019O158/36离散数学王元元,李尚奋编著，科学出版社 1994END特殊符号表,PC,