c语言吧 关注：801,795贴子：4,376,552
不感兴趣
开通SVIP免广告
LZ回来了.
=========================> Chapter 1 <=========================
递归的定义和阐述
1.1. 广义的递归, 其定义/概念/阐述
“Recursion is the process of repeating items in a self-similar way. ”
递归是指以自相似方式重复事物的过程。(请自行抽出key, 递归是过程)
这里唯一要注意的, 广义的递归是一种过程，这种过程，亦是一种刻画/描述/理解现实世界中许多事物的一种方法/方式。它可以是无限无终止的。
有趣的比如说GNU. GNU的定义是 GNU is not Unix.
GNU -> GNU is not Unix, 如果把GNU当成变量(非终结符), 把is, not, Unix都当做终结符, 把GNU -> GNU is not Unix称之为产生式, 产生式左边的GNU作为这个产生式的头部, 产生式右边的GNU is not Unix称之为产生式体, 那么，GUN -> GNU is not Unix 就是一个上下文无关文法(Context-Free Grammar). 对该文法的推导[文法推导即替换]如下：
GNU ==> GNU is not Unix
==> GNU is not Unix is not Unix
==> GNU is not Unix is not Unix is not Unix
....
这是一个无限无终止的左递归(即，该文法产生式体之最左为非终结符/变元)。相应的，非终结符/变元出现在文法最右的文法称之为右递归。这里的“左递归”，“右递归”中的“递归”，是广义的递归。
=========================> Chapter 1 <=========================
递归的定义和阐述
1.1. 广义的递归, 其定义/概念/阐述
“Recursion is the process of repeating items in a self-similar way. ”
递归是指以自相似方式重复事物的过程。(请自行抽出key, 递归是过程)
这里唯一要注意的, 广义的递归是一种过程，这种过程，亦是一种刻画/描述/理解现实世界中许多事物的一种方法/方式。它可以是无限无终止的。
有趣的比如说GNU. GNU的定义是 GNU is not Unix.
GNU -> GNU is not Unix, 如果把GNU当成变量(非终结符), 把is, not, Unix都当做终结符, 把GNU -> GNU is not Unix称之为产生式, 产生式左边的GNU作为这个产生式的头部, 产生式右边的GNU is not Unix称之为产生式体, 那么，GUN -> GNU is not Unix 就是一个上下文无关文法(Context-Free Grammar). 对该文法的推导[文法推导即替换]如下：
GNU ==> GNU is not Unix
==> GNU is not Unix is not Unix
==> GNU is not Unix is not Unix is not Unix
....
这是一个无限无终止的左递归(即，该文法产生式体之最左为非终结符/变元)。相应的，非终结符/变元出现在文法最右的文法称之为右递归。这里的“左递归”，“右递归”中的“递归”，是广义的递归。
=========================> 分割线 <=========================
1.2. Formal definitions of recursion
递归的形式化定义
In mathematics and computer science, a class of objects or methods exhibit recursive behavior when they can be defined by two properties:
1). A simple base case (or cases), and
2). A set of rules which reduce all other cases toward the base case.
数学/计算机科学中, 如果一类对象/方法的定义具有如下两个特性/属性[properties], 那么它就是递归的。
1). 基准情形/简单情形,
2). 一组能够将所有情形规约/递推[reduce]至基准情形的规则. 注意了. 这里的形式化定义，已经不再是广义的递归了。就是说它要求递归是可以终止的。没错，要讲的 C语言的递归函数调用，应该归结为这样的一类递归。
1.2. Formal definitions of recursion
递归的形式化定义
In mathematics and computer science, a class of objects or methods exhibit recursive behavior when they can be defined by two properties:
1). A simple base case (or cases), and
2). A set of rules which reduce all other cases toward the base case.
数学/计算机科学中, 如果一类对象/方法的定义具有如下两个特性/属性[properties], 那么它就是递归的。
1). 基准情形/简单情形,
2). 一组能够将所有情形规约/递推[reduce]至基准情形的规则. 注意了. 这里的形式化定义，已经不再是广义的递归了。就是说它要求递归是可以终止的。没错，要讲的 C语言的递归函数调用，应该归结为这样的一类递归。
不感兴趣
开通SVIP免广告
=========================> 分割线 <=========================
---------------------------------------------------------------------
再扯两句。我们看到了“形式化[Formal]”这个词。请问，什么是形式化的，什么是非形式化[Informal] 的？一般来说, 建立一个系统的方式, 是先有定义和公理, 然后根据定义和公理, 推导各种引理和定理, 然后 -- 一个系统就建立起来了. 比如欧氏几何, 通过有限的公理和公设, 去证明《几何原本》中的所有"真命题". 这估计是人类史上最早的形式化地建立系统的例子, 这个系统的基础是有限的公理和公设, 然后整个系统就是 -- 欧几里得几何, 也即几何原本. 那么欧氏几何就是形式化的.
由于近代符号逻辑的发展, 形式化(formal methods)一般被纳入符号逻辑/命题逻辑/数理逻辑的数学分支中去了. 不过要注意, 形式化只是一种思考方式, 也就是说形式化方法的本质就像前述说欧氏几何的建立一样. 只不过, 由于数学家们认为, 将这种思考方式符号化从某种程度上有助于思考本身(布尔代数奠基人, 其有一本书的名字就是《The Laws of Thought》). 于是, 在数学上看来, 形式化地建立一个系统需要:
Formal systems in mathematics consist of the following elements:
A finite set of symbols (i.e. the alphabet), that can be used for constructing formulas (i.e. finite strings of symbols).
A grammar, which tells how well-formed formulas (abbreviated wff) are constructed out of the symbols in the alphabet. It is usually required that there be a decision procedure for deciding whether a formula is well formed or not.
A set of axioms or axiom schemata: each axiom must be a wff.
A set of inference rules.
即:
1. 一组有限的符号**, **中的符号用来构建公式. [比如, 令命题p表示"3 + 2 = 5", p就是一个符号, 代表一个命题. 比如, 对两个命题的合取一般表示为 p ^ q, 即, p成立而且q也成立, 就像 C语言中, &&对两个表达式取逻辑乘一样. 对两个命题的析取一般表示为p v q, 即p成立, 或者q成立, 或者二者皆成立]
2. 语法规则, 就是根据符号**(亦称字母表)构建合式公式(原文中的well-formed formulas, 一般数理逻辑中译为合式公式)的规则. [合式公式是由命题常项、命题变项、联结词、括号等组成的符号串, 但不是由这些符号任意组成的符号串都是合式公式]. 语法规则用于判断一个公式是不是合式公式.
3. 一组公理或者公设. 公理和公设必须是合式公式.
4. 一组推理规则.[_三-段-论_神马的]. 即, 形式化方法的本质仍然是: 根据基本的公理和公设, 加上一组推理规则, 然后... 建立整个系统. 就是这个意思. 形式化的方式和别的方式的本质区别在于, 是不是具有有限的基本模型抽象, 然后根据这些基本模型抽象推导出/建立整个系统模型. 对于形式化的方式来说, 由于这种形式化的方式保证了逻辑上的严格性, 在系统日益复杂的情况下, 有可能思考需要回到某个定义本身开始. 因此这种方式被广泛地应用.
***************************************
那么非形式化的方式是什么？就是直观地描述. 如果一上来就给人一套数学形式化描述的东西, 然后让人根据这个东西去推导什么的, 谁都会发疯的. 于是一般在介绍一个形式化的定义/概念之前, 都会先给一大段非形式化的描述, 让人建立起直观的理解, 最后将其形式化地定义下来, 最终就是一个形式化了的系统.
---------------------------------------------------------------------
---------------------------------------------------------------------
再扯两句。我们看到了“形式化[Formal]”这个词。请问，什么是形式化的，什么是非形式化[Informal] 的？一般来说, 建立一个系统的方式, 是先有定义和公理, 然后根据定义和公理, 推导各种引理和定理, 然后 -- 一个系统就建立起来了. 比如欧氏几何, 通过有限的公理和公设, 去证明《几何原本》中的所有"真命题". 这估计是人类史上最早的形式化地建立系统的例子, 这个系统的基础是有限的公理和公设, 然后整个系统就是 -- 欧几里得几何, 也即几何原本. 那么欧氏几何就是形式化的.
由于近代符号逻辑的发展, 形式化(formal methods)一般被纳入符号逻辑/命题逻辑/数理逻辑的数学分支中去了. 不过要注意, 形式化只是一种思考方式, 也就是说形式化方法的本质就像前述说欧氏几何的建立一样. 只不过, 由于数学家们认为, 将这种思考方式符号化从某种程度上有助于思考本身(布尔代数奠基人, 其有一本书的名字就是《The Laws of Thought》). 于是, 在数学上看来, 形式化地建立一个系统需要:
Formal systems in mathematics consist of the following elements:
A finite set of symbols (i.e. the alphabet), that can be used for constructing formulas (i.e. finite strings of symbols).
A grammar, which tells how well-formed formulas (abbreviated wff) are constructed out of the symbols in the alphabet. It is usually required that there be a decision procedure for deciding whether a formula is well formed or not.
A set of axioms or axiom schemata: each axiom must be a wff.
A set of inference rules.
即:
1. 一组有限的符号**, **中的符号用来构建公式. [比如, 令命题p表示"3 + 2 = 5", p就是一个符号, 代表一个命题. 比如, 对两个命题的合取一般表示为 p ^ q, 即, p成立而且q也成立, 就像 C语言中, &&对两个表达式取逻辑乘一样. 对两个命题的析取一般表示为p v q, 即p成立, 或者q成立, 或者二者皆成立]
2. 语法规则, 就是根据符号**(亦称字母表)构建合式公式(原文中的well-formed formulas, 一般数理逻辑中译为合式公式)的规则. [合式公式是由命题常项、命题变项、联结词、括号等组成的符号串, 但不是由这些符号任意组成的符号串都是合式公式]. 语法规则用于判断一个公式是不是合式公式.
3. 一组公理或者公设. 公理和公设必须是合式公式.
4. 一组推理规则.[_三-段-论_神马的]. 即, 形式化方法的本质仍然是: 根据基本的公理和公设, 加上一组推理规则, 然后... 建立整个系统. 就是这个意思. 形式化的方式和别的方式的本质区别在于, 是不是具有有限的基本模型抽象, 然后根据这些基本模型抽象推导出/建立整个系统模型. 对于形式化的方式来说, 由于这种形式化的方式保证了逻辑上的严格性, 在系统日益复杂的情况下, 有可能思考需要回到某个定义本身开始. 因此这种方式被广泛地应用.
***************************************
那么非形式化的方式是什么？就是直观地描述. 如果一上来就给人一套数学形式化描述的东西, 然后让人根据这个东西去推导什么的, 谁都会发疯的. 于是一般在介绍一个形式化的定义/概念之前, 都会先给一大段非形式化的描述, 让人建立起直观的理解, 最后将其形式化地定义下来, 最终就是一个形式化了的系统.
---------------------------------------------------------------------
哟西 留名
