12.4递归定义与归纳证明 °递归定义( recursive definition) 又称为归纳定义( inductive definition),它来定义 个集合。 集合的递归定义由三部分组成: 基础 basis):用来定义该集合的最基本的元素。 归纳( (induction):指出用集合中的元素来构造集合的 新元素的规则 极小性限定:指出一个对象是所定义集合中的元素 的充要条件是它可以通过有限次的使用基础和归纳 条款中所给的规定构造出来。 2021/2/20
2021/2/20 31 1.2.4 递归定义与归纳证明 • 递归定义(recursive definition) – 又称为归纳定义(inductive definition)，它来定义 一个集合。 – 集合的递归定义由三部分组成： • 基础(basis)：用来定义该集合的最基本的元素。 • 归纳(induction)：指出用集合中的元素来构造集合的 新元素的规则。 • 极小性限定：指出一个对象是所定义集合中的元素 的充要条件是它可以通过有限次的使用基础和归纳 条款中所给的规定构造出来
12.4递归定义与归纳证明 归纳证明 与递归定义相对应。 归纳证明方法包括三大步 基础( basis):证明最基本元素具有相应性质。 归纳 Induction):证明如果某些元素具有相 应性质,则根据这些元素用所规定的方法得 到的新元素也具有相应的性质。 根据归纳法原理,所有的元素具有相应的性 质 2021/2/20
2021/2/20 32 1.2.4 递归定义与归纳证明 • 归纳证明 – 与递归定义相对应。 – 归纳证明方法包括三大步： • 基础(basis)：证明最基本元素具有相应性质。 • 归纳(induction)：证明如果某些元素具有相 应性质，则根据这些元素用所规定的方法得 到的新元素也具有相应的性质。 • 根据归纳法原理，所有的元素具有相应的性 质
12.4递归定义与归纳证明 定义1-17 设R是S上的关系,我们递归地定义R的幂: (1)R={(a,a)la∈S}o (2)R=RHR(i=1,2,3,4,5,)。 2021/2/20 33
2021/2/20 33 1.2.4 递归定义与归纳证明 • 定义 1-17 设R是S上的关系，我们递归地定义Rn的幂： ⑴ R0={(a，a)|a∈S}。 ⑵ Ri=Ri-1R (i=1,2,3,4,5,…)
12.4递归定义与归纳证明 例1-17著名的斐波那契( Fibonacci数的定义 (1)基础:0是第一个斐波那契数,1第二个斐波 那契数; (2)归纳:如果n是第个斐波那契数,m是第i1 个斐波那契数,则nm是第计2个斐波那契数, 这里i为大于等于1的正整数。 (3)只有满足(1)和(2)的数才是斐波那契数 0,1,1,2,3,5,8,13,21,34, 2022720 34
2021/2/20 34 1.2.4 递归定义与归纳证明 例1-17 著名的斐波那契(Fibonacci)数的定义 ⑴ 基础：0是第一个斐波那契数，1第二个斐波 那契数； ⑵ 归纳：如果n是第i个斐波那契数，m是第i+1 个斐波那契数，则n+m是第i+2个斐波那契数， 这里i为大于等于1的正整数。 ⑶ 只有满足(1)和(2)的数才是斐波那契数 0，1，1，2，3，5，8，13，21，34， 55，…
12.4递归定义与归纳证明 例1-18算术表达式 (1)基础:常数是算术表达式,变量是算术表 达式; (2)归纳:如果E1、E2是表达式,则+E1、-E1 E1+E2、E1-E2、E,E /E、E,E 1112 2 Fun(E1)是算术表达式。其中Fun为函数名 (3)只有满足(1)和(2)的才是算术表达式。 2021/2/20
2021/2/20 35 1.2.4 递归定义与归纳证明 例1-18 算术表达式 ⑴ 基础：常数是算术表达式，变量是算术表 达式； ⑵ 归纳：如果E1、E2是表达式，则 +E1、-E1、 E1+E2、 E1 -E2 、E1 *E2 、E1 /E2、E1 **E2、 Fun(E1 )是算术表达式。其中Fun为函数名。 ⑶ 只有满足(1)和(2)的才是算术表达式