递归定义

定义

  递归定义(Recursive Definition)是一种定义集合的方法,一般包含三个步骤:
1. 指出有一些基本的元素是在集合中的
2. 给出在集合中已有的元素上构造新元素的方法
3. 指明除了可以由第2条所构造的元素外,没有其余任何元素位于该集合中
注意这里只说了分为三个步骤,不代表每个步骤都只包含一条规则

EXAMPLE:
定义一个偶数集合
正常的定义方法为EVEN=\lbrace \text{all positive integers divisible by 2}\rbrace
也可以使用类似EVEN=\lbrace 2n\ for\ n=1,2,3,4,...\rbrace
使用递归定义:
1. 2在集合EVEN
2. 如果xEVEN中,那么x+2也在EVEN
3. EVEN中只包含能从1和2中推导得到的元素
(注:第三条其实是完全多余的,只是写出来更加规范)
或者
1. 2在集合EVEN
2. 如果xy都在EVEN中,那么x+y也在EVEN

当选择一个集合的定义方法的时候,应当顾及到两方面:
1. 这些定义是否易于理解
2. 我们希望通过这个集合证明什么定理
比如在上述例子中,我们想要证明如果xy是偶数,那么x+y也是偶数的话,直接走第二条就可以得到结论了,但是如果按照传统的偶数定义方式,相比之下就要更加复杂。
这种定义方式之所以被称为是"递归的",是因为其中一条用于定义集合的规则涉及到集合本身,比如我们使用已有的EVEN中的元素来定义新的元素,就像在计算机语言中,可以调用自身的例程也被称为是递归的,他们都引用了自身,是自我指涉的(self-referential)

EXAMPLE
Kleene闭包也可以通过递归定义
1. 对于语言\mathcal{S}S的所有单词都属于\mathcal{S}^\ast
2. \varLambda也在\mathcal{S}^\ast
3. 如果xy\mathcal{S}^\ast里,那么他们的拼接xy也在\mathcal{S}^\ast

算术表达式

我们可以用如下的字母表表示算术表达式:

\varSigma=\lbrace0,1,2,3,4,5,6,7,8,9,+,-,*,/,(,)\rbrace

考虑一个问题:我们该如何定义一个合法的算术表达式呢,显然,诸如

(3+5)+6\hspace*{10ex}2(/8+9)\hspace*{10ex}(3+(4-)8)\hspace*{10ex}2)-(4

等都符合对应的字母表,但是他们都不是合法的算术表达式,如果我们使用经典的方法去定义,会存在大量的诸如"两个除号不能连续出现","减号后面不能直接跟括号"这种规则,实际上,我们可以用递归定义的方法来定义算术表达式AE

  1. 所有的数字,包括负数,正数和0都在AE
  2. 如果xAE中,则如下的元素也在AE
    • (x)
    • -x (x并不以-作为前缀)
  3. 如果xyAE中,则如下的元素也在AE
    • x+y (y并不以+或-作为前缀)
    • x-y (y并不以+或-作为前缀)
    • x*y
    • x/y
    • x^y

虽然很难注意到,但这种定义方法的确是我们平时判断一个算术表达式是否合法时候会下意识使用的定义。这个定义可以有助于证明许多定理

定理2

算术表达式不能包含字符$

证明

根据上文中的定义:
1. 该字符本身不属于任何数字,因此不符合第一条
2. 如果x不包含该字符,则(x)-x也不会包含
3. 同理,第3条中的任意表达式也不包含
因此可以得出结论,算术表达式不能包含字符$


乱我心者,今日之日多烦忧