12.4递归定义与归纳证明 例1-19对有穷集合A,证明2A|=2N。 证明: 设A为一个有穷集合,施归纳于| (1)基础:当A=0时,24={4}=1。 (2)归纳:假设A=n时结论成立,这里m≥0, 往证当A=n+1时结论成立 24=2BU{CU{aHC∈2 2B∩{CU{aC∈2B}=d 2021/2/20
2021/2/20 36 1.2.4 递归定义与归纳证明 例1-19 对有穷集合A，证明|2 A|=2 |A|。 证明： 设A为一个有穷集合, 施归纳于|A|： ⑴ 基础：当|A|=0时,|2 A|=|{Φ}|=1。 ⑵ 归纳：假设|A|=n时结论成立，这里n ≥0， 往证当|A|=n+1时结论成立 2 A=2B∪{C∪{a}|C∈2 B} 2 B∩{C∪{a}|C∈2 B}=Φ
12.4递归定义与归纳证明 24=12BU{CU{a}C∈2B 121+{CU{ayC∈2B =2B+2B1 2 |勹B 2*2|B1 =2|B+1 2A (3)由归纳法原理,结论对任意有穷集合成立。 2021/2/20 37
2021/2/20 37 1.2.4 递归定义与归纳证明 |2 A|=|2 B∪{C∪{a}|C∈2 B}| =|2 B|+|{C∪{a}|C∈2 B}| =|2 B|+|2 B| =2*|2 B| =2*2 |B| =2 |B|+1 =2 |A| ⑶ 由归纳法原理，结论对任意有穷集合成立
12.4递归定义与归纳证明 例1-20表达式的前缀形式是指将运算符 写在前面,后跟相应的运算对象。如:+E1的 前缀形式为+E1,E1+E2的前缀形式为+E1E2, E1*E,的前缀形式为*E1E2,E1*E2的前缀形 式为*E1,FunE1)的前级形式为FunE1 证明例1-18所定义的表达式可以用这里定 义的前缀形式表示。 2021/2/20
2021/2/20 38 1.2.4 递归定义与归纳证明 例1-20 表达式的前缀形式是指将运算符 写在前面，后跟相应的运算对象。如：+E1的 前缀形式为+E1，E1+E2的前缀形式为+E1E2 ， E1 *E2的前缀形式为*E1E2， E1 **E2的前缀形 式为** E1，Fun(E1 ) 的前缀形式为FunE1 。 证明例1-18所定义的表达式可以用这里定 义的前缀形式表示
12.4递归定义与归纳证明 递归定义给出的概念有利于归纳证明。在 计算机科学与技术学科中,有许多问题可 以用递归定义描述或者用归纳方法进行证 明,而且在许多时候,这样做会带来许多 方便。 主要是掌握递归定义与归纳证明的叙述格 式 2021/2/20 39
2021/2/20 39 1.2.4 递归定义与归纳证明 • 递归定义给出的概念有利于归纳证明。在 计算机科学与技术学科中，有许多问题可 以用递归定义描述或者用归纳方法进行证 明，而且在许多时候，这样做会带来许多 方便。 • 主要是掌握递归定义与归纳证明的叙述格 式
1.2.5关系的闭包 闭包 closure) 设P是关于关系的性质的集合,关系R的P闭包 ( closure)是包含R并且具有P中所有性质的最 小关系 正闭包( positive closure) (1)R∈R (2)如果(a,b),(b,c)∈R+则(a,c)∈R+ (3)除(1)、(2)外,R不再含有其他任何元素。 2021/2/20 40
2021/2/20 40 1.2.5 关系的闭包 • 闭包(closure) – 设P是关于关系的性质的集合，关系R的P闭包 (closure)是包含R并且具有P中所有性质的最 小关系。 • 正闭包(positive closure) (1)RR+ 。 (2)如果(a，b)，(b，c)∈R+ 则(a，c)∈R+ 。 (3)除(1)、(2)外，R+不再含有其他任何元素