编程的实践理论 第三章 函数理论

第三章 函数理论

如果我们解释规则的使用，我们总是允许发明新的语法。新的语法的
一个好的来源是名称（标识符），通过公理给出了规则是如何使用的。
通常，当我们介绍名称和公理时，我们要它们实现当前的目的。读者
被假定理解它们的作用域，就是它们的应用范围，在它的范围外不使用。
尽管名称和公理是形式化的（在我们的形式化中的表达式），到现在
为止，我们已经用自然语言非形式化地介绍了它们。但是非形式化地
介绍名称和公理的作用域并不总是很清楚的。在这一章中，我们使用
了一个形式化的记号，来介绍本地化的名称和公理。

一个变量是一个名称，它的引用是为了替换它的值。例如定律 x*1=x
使用了变量x来告诉我们任何一个数乘以1等于同一个数。一个常量也是
一个名称，它的值不能被替换。例如，我们引入了一个名称pi,公理是
3.14<pi<3.15,但是我们不是说每个数都在3.14和3.15之间。相似的是，
我们引入了i 和公理 i*i=-1 并且，我们没有想要替换i。

函数的记号是引入了局部变量结合上局部的公理的形式化的方式，它说明
什么样的表达式能被用来替换变量。

3.0  函数

让v是一个名字，让D是一个项的束，让b是任意的表达式。那么，
<v:D→b>                    "在D中把v映射成b","在D中，本地的
v映射成b"  是变量v的函数在域D中，有函数体b.   包含关系
v:D 是一个本地的公理，带着函数体b. 方括号<> 显示出了
变量和公理的作用域。例如，
<n:nat → n+1> 是在自然数中，加一的自增函数。这有它的图
            0
0  →     1
1 →      2
2 →      3
3 →      4
.           .
.           .
.           .

如果 f是一个函数，那么，
口f                “f的域”
是它的域 ，域的公理是
口<v:D→b> = D
我们说D是函数<v:D→b>的域，也是变量v的域。一个函数的范围
包括在函数体中的变量的域中，通过替换每个元素，得到元素的范围。
我们的增量函数的范围是 nat+1。

一个函数引入了一个变量，或者说是一个参数。变量的目的是为了帮助
表达从域的元素到范围的元素的映射。只要名称是新的，没有已经被
用于其它目的，名称的选择是无关紧要的。重命名的公理说如果v和w
都是名称，并且它们都没有出现在域Dk ,并且w没有出现在b中，那么，

<v:D→b> = <w:D→(在b中所有的v替换成w)>
这种替换必须是每一处出现v的地方都替换成w。

如果f是一个函数 并且x是它的域中的一个元素，那么
fx       "函数f 参数是x"
对应的是范围的元素。这是函数应用，x是形式参数。当然了，
括号能用在任何表达式的周围，所以我们可以写成f(x)。如果函数
或者是参数不是简单的，我们将不得不把它用括号括起来。当没有
混淆的危险时，我们可以写fx,而不用写空格，但是当我们写多个字符
的名称时，我们必须在函数和它的参数之间加上空格。作为一个应用
的例子， 如果 suc=<n:nat→n+1> ,那么
suc 3 = <n:nat→n+1> 3 = 3+1 =4

这里有应用的公理。如果元素x在域D内，那么，
<v:D→b> x = (在b中所有的v替换成w)

操作符与函数是相似的，正如我们把操作符-
应用于x,就得到了-x。我们应用了函数f到形式
参数x上，得到了fx。

超过一个变量的函数是一个函数，它的函数体
是一个函数。这里有两个例子。

max = <x:xrat→<y:xrat→if x≥y then x else y fi>>
min = <x:xrat→<y:xrat→if x≤y then x else y fi>>

如果我们应用max到一个形式参数，我们得到了一个函数，
还带有一个变量。

max 3 =<y:xrat→if 3≥y then 3 else y fi>
当我再应用一个参数时，得到了一个结果值。
max 3 5 = 5

一个预测语句是一个函数，它的函数体是一个二进制的表达式。
两个例子是
even  = <i:int→i/2:int>
odd   = <i:int→¬i/2:int>

一个关系是一个函数，它的函数体是一个预测语句。
这是一个例子：
divides = <n:nat+1→<i:int→i/n:int>>
divides 2 = even
divides 2 3 = ⊥

在函数中一个更常见的操作是选择性的并。如果 f 和 g
是函数，那么 f|g  "f或者g" "f和g的选择性并"
是一个函数，如果把参数应用于f的域，它的行为f,否则
像g. 公理是
口(f|g)= 口f,口g
(f|g) x = if x:口f then fx else gx fi

证明的所有的规则应用于函数的函数体，附加的本地公理是
新的变量是域的元素。

    3.0.0  缩写的函数的标记

部分为了便利，部分为了传统，我们允许在函数的记号上有
一些改变。第一个改变是对变量的引入的分组。例如，
<x,y:xrat→if x≥y then x else y fi>    
是之前看到的最大值函数的一个缩写。

如果有额外的解释，我们可能忽略一个函数的域。例如，
自增函数可能写成<n→n+1>。这是在一个上下文中，能
理解到它的域是nat时的简写。

当函数体没有使用变量时，我们可以忽略到变量。
在这个方面，我们也能忽略掉方括号。例如 当我们
写着<n:2→3>,这里的n是没有用上的，于是可以缩写为，
2→3是一个函数，它把2映射成3.

一些人倾向于用任何的表达式来作为一个有变量的函数。
例如 他们可能写x+3,并且说它是x的一个函数。他们
忽略了形式变量，和域的引入，这是非形式化的提供内容。
这是缩写的问题。一个问题是可能有变量没有出现在表达式中。
例如，<x:int→<y:int→ x+3>> 它有两个变量，与下面的缩写
表达的内容是一样的。
<x:int→ x+3>
另一个问题是，没有精确地引入变量的作用域。还有
我们也不知道变量引入的顺序，所以我们无法把这个缩写
的函数应用于形式参数。我们认为缩写太过了，我们
将不使用它。我们仅指出它，因为它是一个共同的术语，
展示了在之前的章节中我们非形式化地引入了变量，这个
变量在函数部分中，我们形式化地引入了它。

    3.0.1  作用域和替换

如果一个变量在表达式的内部，这个变量对于这个
表达式来说是本地的（因而是形式化的）。如果一
个变量在表达式的外部，这个变量对于这个对于这个
表达式而言是非本地的（是形式化的或者是非形式化的）
单词本地化和非本地化的使用都是相对于一个特别的表
达式或者是一个子表达式的。

对于我们的本地的变量，如果我们总是使用名称，那么
一个替换就是要替换一个变量出现的每一处地方。但是
如果我们要重用一个名称，我们需要更加小心。这是一
个例子，使用了空格来表示不感兴趣的部分。
<x→ x <x→  x > x > 3
变量x被引入了两次：在内部的域中被引入了一次，
即使在外部的域中也引入了一次。在内部的作用域中，
x被引入了。在外部的作用域中，是一个函数，它被
应用于3. 假定3在它的作用域中，应用公理说，这个
表达式等价于用3替换了x后的表达式。这个意图是
用3代替函数中的x,而不是内部的作用域。这个结果如下：
= （3 <x→  x > 3 ）

这里有一个更差的例子。假定x是一个非本地化的变量，并且，
我们在内部的作用域中重新的引入了它。

<y→ x y <x→  x y> x y  >x

应用公理说，对于所有的y出现的地方统统换成x.
外部的作用域引入了y变量，它出现了三次，所以三次
都被替换成了非本地化的x，作为形式参数用。但是，
内部的x,看起来是一个本地化的变量。在我们替换之前，
我们必须对内部的作用域使用重命名公理。选择一个新名z,
我们得到了：
<y→ x y <z→  z y> x y  >x
通过重命名和替换，得到了如下的表达式：
(x x <z→  z y> x x)

应用公理（对于元素 x:D） 在b中代替所有的v为x.
这给我们提供了一个形式化的代替记号。这是我们
非形式化表达的两个公理之一。（一个是变量引入，
另一个是在第5章中，关注的变量削除）因为形式化
等于写一个程序来执行代替。重命名公理写成了如
下的形式化的样子：
<v:D→b> = <w:D→ <v:D→ b>w>
并且它不需要一个公理，因为它是一个扩展的公理的实例。
f=<w:口f→ fw>
当一个域是明显的，或者当一个我们要包括x的域是明显的，
我们写<v→b>x 来表示在b中用x来代替v.例如，对形式参数x
来应用重命名公理。
<v→b>x = <w→<v→b>w>x
说的是用x代替v 与先用w代替v,再用x代替w是一样的。

3.1 量词

一个量词是一个前缀的操作符它带有一个操作数，并且应用于函数。
任何一个有两个操作数的有对称性的有结合律的操作符能够被用来
定义一个量词。这里有四个例子：操作符∧ ∨ +  ×  用来定义量词 
∀  ∃ Σ Π。如果p是一个判断命题，那么，通用量词 ∀p 是把p应用于
域的所有的元素之后的二进制的结果，然后析取所有的结果。相似的是
存在性测试的量词 ∃p 是把p应用于域的所有的元素之后的二进制的结果，
然后合取所有的结果。如果f 是一个有数值结果的函数，那么， Σf 是把f
应用于域的所有的元素之后的数值的结果，然后加总所有的结果;  Πf是
把f应用于域的所有的元素之后的数值的结果，然后相乘所有的结果 。
这里有四个例子。
∀〈r : rat→r<0 ∨ r=0 ∨ r>0〉          对于所有的r 在rat中....
∃〈n: nat→n=0〉                              存在n 在nat 中，使得 ...
Σ〈n: nat+1→1/2n〉                        对于 n 在nat+1中，对... 求和
Π〈n: nat+1→(4×n2)/(4×n2–1)〉   对于 n 在nat+1中，对... 求乘积

为了适合传统与便利，我们允许两个缩写的量词记号。首先是我们允许量词
后的表示作用域的方括号省略；现在我们为了歧义，我们不得不把箭头改为
一个位置升高一点的句点。例如我们写
∀r: rat· r<0 ∨ r=0 ∨ r>0
Σn: nat+1· 1/2n

缩写过的量词记号 让变量的作用域变得不清晰了，它让优先级的规则复杂化了，
但是数学方面的传统是强大的，所以我们将使用它。第二，我们能够在重复性
的量词中对变量进行分组。代替了
∀x: rat· ∀y: rat· x = y+1  ⇒  x > y
我们能写
∀x, y: rat· x = y+1  ⇒  x > y

还有代替了
Σn: 0,..10· Σm: 0,..10· n×m
我们能写
Σn, m: 0,..10· n×m

对于这些量词的这些公理分成了两个模式，这依赖于操作符的基是否是幂等的。
公理如下（v是名称，A和B是束，b是一个二进制的表达式，n是一个数值
的表达式，x是一个元素）。
∀v: null· b   =   T
∀v: x· b   =   〈v: x→b〉 x
∀v: A,B· b   =   (∀v: A· b) ∧ (∀v: B· b)
∃v: null· b   =   ⊥ ⊥ ⊥ ⊥
∃v: x· b   =   〈v: x→b〉 x
∃v: A,B· b   =   (∃v: A· b) ∨ (∃v: B· b)
Σv: null· n   =   0
Σv: x· n   =   〈v: x→n〉 x
(Σv: A,B· n) + (Σv: A‘B· n)   =   (Σv: A· n) + (Σv: B· n)
Πv: null· n   =   1
Πv: x· n   =   〈v: x→n〉x
(Πv: A,B· n) × (Πv: A‘B· n)   =   (Πv: A· n) × (Πv: B· n)

当把英语单词的所有和一些 翻译成形式化的记号  ∀  和   ∃ 时，要注意的。
例如，语句 “所有的都不丢”不应该译成∀x· ¬ lost x ,  而是要译成  
  ∃x· ¬ lost x  或者   ¬∀x· lost x   或者是  ¬∀lost 。注意的是，当一个
量词被用于有空域的函数时，它基于操作符的单位元。不要惊讶地发现
一个数也没有的求和 ，结果是0，但是你可能惊讶地学习到一个数也没有的求
乘积的结果是1 。 你可能同意的是一个元素也没有的空域中，有属性b,
(不管b是什么)  ，并且存在性的量词应用于空域时，得到了你期望的结果。
你可能发现了接受在空域中的所有的元素都有属性b是更加困难的事，但是
以另一个角度去看：否定它，意味着说在空域中有一个元素没有属性b。
因为在空域中没有任何一个元素，也没有一个元素没有属性b,所以所有的
（0个）的元素都有这个属性。

我们能从我们自己定义的函数中形成量词。例如，函数 最小值，最大值是
两个操作数的对称的，有结合律的幂等的函数，所以我们能定义相应的量词
MIN 和MAX 如下：

MIN v: null· n   =   ∞
MIN v: x· n   =   〈v: x→n〉 x
MIN v: A,B· n   =   min (MIN v: A· n) (MIN v: B· n)

MAX v: null· n   =   –∞
MAX v: x· n   =   〈v: x→n〉 x
MAX v: A,B· n   =   max (MAX v: A· n) (MAX v: B· n)

我们最终的量词应用于判断命题。方案量词 § 给出一个判断命题的方案的束。
这里是公理。
§v: null· b   =   null
§v: x· b   =   if 〈v: x→b〉 x then x else null fi
§v: A,B· b   =   (§v: A· b), (§v: B· b)

我们有所有的可实践的解的方程，并且我们知道的是
§i: int· i2 = 4   =   –2, 2      这些i 在int中，使得...

方程仅是二进制表达式中的一个特殊的例子；我们能够讨论的是
任何一个判断命题的方案。例如，
§n: nat· n<3   =   0,..3

话说回来，为了方便与传统，当方案量词被用于一个集合时，
我们能够省略量词。例如，代替写 {§n: nat· n<3} ，我们
可能写  {n: nat· n<3} ，对于集合而言，它是一个标准的记号。

这里有更多的公理，来说明当域是§量词的一个结果时，每个量
词行为是如何的；它们被列在本书的结尾处，包括其它的定律关注
的量词行为。这些定律在编程的过程中不断地使用着；必须研究它们
直到很熟悉。一些定律能够写成更优雅的方式，而不是传统的方式。例如，
本书后面的特别化和通用化的定律说的是 如果 x:D,
∀v: D· b   ⇒   〈v: D→b〉 x
〈v: D→b〉 x   ⇒   ∃v: D· b

如果x:口f,它们能写成如下的方式：
∀f   ⇒   f x   ⇒   ∃f
如果对于域的所有的元素，f是真的，对于域元素x,f是真的。
如果 对于域元素x,f是真的，那么对于ｆ,存在一个域元素是真的。

一点定律说，如果x在D域中，v不在x中，那么
∀v: D· v=x ⇒ b   =   〈v: D→b〉 x
∃v: D· v=x ∧ b   =   〈v: D→b〉 x

例如在通用量词中，  ∀n: nat· n=3 ⇒ n<10 ，我们看到在一个推导之中，
一个前提条件是把一个变量与一个元素相等的判断。一点定律说，通过处理
量词和前提条件，这就能简化了，在后继条件中，通过把变量替换成元素。
所以我们得到了3<10,这进一步简化成真。在一个存在性的量词中，我们需要
合取变量与元素的判断，那么我们能做相同的简化。例如，∃n: nat· n=3 ∧ n<10
变成了3<10,进而能简化为真。如果p是一个判断命题，没有提及非本地化变量x,
元素y 在P的域中，那么如下的都是等价的：
∀x:  P· x=y ⇒ Px
= ∃x:  P· x=y ∧ Px
= 〈x:  P→Px〉 y
= Py

一些定律可能让人吃惊，例如，我们能证明
MIN n: nat· 1/(n+1)  =  0
虽然 0是 函数  〈n: nat→1/(n+1)〉 的一个结果。

3.2 函数优越点

考虑一个函数，它的函数体是一个束：域中的每一个元素被映射成范围中的
0到多个元素。例如，
〈n: nat→n, n+1〉

映射每一个自然数到两个自然数。

应用是工作正常的：
〈n: nat→n, n+1〉 3 =3,4

一个函数有时没有产生结果，叫做是不完备的。一个函数
总是产生至少一个结果，叫做是完备的。一个函数总是产生
至多一个结果，叫做是确定性的，一个函数有时产生多个结果
叫做非确定性的。函数  〈n: nat→0,..n〉  既是不完备的，又是
非确定性的。

函数的并，应用于参数后，得到结果的并。
(f,g) x = fx,gx

函数应用于参数的并，得到结果的并。
f null  =  null
f (A, B)  =  f A, f B
f (§g)  =  §y: f (口g)· ∃x: 口g· fx=y ∧ gx
换句话说，函数应用对束的并有分配律。函数f的范围是f(口f)

总之，我们不能使用应用定律 来应用一个函数到一个非元素级的束上。
例如，如果我们定义 double = <n:nat→n+n> 我们能说，
double (2, 3) 
= double 2, doub
= 4, 6

但是我们不能说
double (2, 3)     
= (2, 3) + (2, 3)    这一步是错的。
= 4, 5, 6

假定我们真的要把一个函数应用于一个项的集合，例如，报告在一个集合中
是否有太多的项。那么群必须打包成一个集合，使得它作为一个元素级的参数。

如果一个函数的函数体，仅仅使用它的变量一次，在一个分配律的上下文中，
函数能被应用于一个非元素级的参数中，因为在分配律的作用下，结果是一样的。
例如
〈n: nat→n×2〉 (2, 3) 
= (2, 3)×2                这一步是可以的。
= 4, 6

    3.2.0 函数的包含与相等

根据函数的包含定律，一个函数f,被包含在函数g中。
f: g    =》     g:  f  ∧  ∀x:  g· fx: gx
使用两边，我们发现了函数的相等性如下：
f = g    =》     f =  g  ∧  ∀x:  f· fx = gx

我们现在证明  suc:nat→nat. 函数 suc 在 之前被
定义为 suc = <n:nat →n+1> . 函数 nat →nat 是 
<n:nat→nat> 的缩写，它有一个未使用的变量。它
是一个非确定性的函数，对于自然数域中的每一个元素，
它的结果，都是自然数的束。它也是所有的域是自然数，
结果包含在自然数中的函数的束。

suc: nat→nat
= nat:  suc  ∧  ∀n: nat· suc n: nat   使用函数包含定律
= nat: nat  ∧  ∀n: nat· n+1: nat       suc的定义
= T                                                  反身性和nat 的组装定律

我们能证明关于在这一章的第一节中定义的其它的函数的相似的包含。
max: xrat→xrat→xrat
min: xrat→xrat→xrat
even: int→bin
odd: int→bin
divides: (nat+1)→int→bin

进而，
f: A→B    =    A:  f  ∧  fA: B

这之前我们用公理定义了suc
suc  =  〈n: nat→n+1〉

这个等式能替换成如下的式子，
口suc = nat   ∧   ∀n: nat· suc n = n+1

我们能用更弱化的公理来定义suc .
nat:  suc   ∧   ∀n: nat· suc n = n+1

在实践中，它是有用的，并且在如果愿意的话，允许suc 被
扩展到更大的域中。一个相似的解释 还有 最大值，最小值，偶数，
奇数，和除法。

    3.2.1 高阶函数

一个高阶的函数是一个函数，它的输入和输出都是函数。如果 g: A→B
那么 〈f: (A→B)→ ... f ... 〉 g
把一个高阶函数 应用于一个函数。一个参数代表域中的一个元素，
应用定律要求输出结果是域中的一个元素，但是函数不是元素。因此
我们认为一个高阶的函数应用于一个函数，缩写为如下的形式：
〈f: 乡(A→B)→ ... ~f ... 〉 {g}
幂操作符 “乡”和 集合的括号 ｛｝仅是为了让参数和返回值
成为域要求的元素，取内容操作的操作符~ 移除了集合结构。

这是一个判断命题，它的参数是一个函数。
让我们叫这个判断命题为 ‘检查’。‘检查’ 这个函数 的参数
必须是一个函数，参数的域 是0,..10, 因为 ‘检查’这个程序把
它的参数用于 0,..10 中的所有的元素。当 ‘检查’的参数用于
头10个自然数，结果必须包括于 整数域中。因为它们必须被测
试偶数性。‘检查’这个程序的参数可能有一个很大的域（特殊
的域元素被忽略），它可能有一个很小的范围。如果 A: B  和  
f: B→C 和  C: D  那么  f: A→D .  因此  suc: (0,..10)→int . 
我们能应用 ‘检查’到suc ，结果是假。
 

    3.2.2 函数组合

令f和g 是函数，使得 f不在g的域中，（¬  f: 口g）。那么 g f 是g和f
的组合函数，用如下的函数组合公理定义：
口（g f）= §x:口f · fx:口g
(g f) x = g (f x)
例如，因为 suc 不在 even 的域中，
口（even suc）=   §x: 口suc· suc x:口even   =   §x: nat· x+1: int   =   nat
(even suc) 3  =  even (suc 3)  =  even 4  =  T

假定x,y:int 和 f,g:int→  int 和 h:int→ int→ int. 那么
h f x g y                   
=(((h f) x) g) y        在 h f 上使用函数组合
=((h (f x)) g) y        在(h (f x)) g   上使用函数组合
=(h (f x)) (g y)         丢掉多余的括号     
= h (f x) (g y)

组合公理说，我们能够写函数和它的不带括号的参数的复杂的组合。
根据它们的函数性，它们自身进行合适的排序。（这叫做波兰前缀 记号）

组合 和应用是非常相关的。假定：f:A→B 和 g:B→C 和  ¬f:口g
所以 g能够和f组合。尽管 g 不能够应用于f,我们能够改变g为
g':(A→B)→(A→C)，能够被应用于f 得到了相同的结果：
g' f = g f .这是一个例子。定义
double =<n:nat→n+n>
我们能够组合double 和 suc.
(double suc) 3     使用组合
= double (suc 3)  应用double 到 suc 3
= suc 3 + suc 3
从double 我们形成了一个新的函数
double' = <f→<n→f n + f n>>
当它能够应用于suc
(double' suc) 3 = <n→suc n + suc n> 3 = suc 3 +suc 3
得到了相同的结果。这种方法让人们实现了记号上的简捷：
它们进而把double 应用于suc ,即使没有应用，那么把下
一个形式参数分配到suc的每一个出现处。
(double suc) 3       把double应用于 suc
(suc + suc) 3         把 3 分配到 suc出现的每一处
suc 3 + suc 3        得到正确的结果。

正如在这个例子中，快捷方式在工作，但是值得警惕：
它在有的时候能导致不一致性。（应用组合这个词被
认为是应用与组合的混合物，它也完美地描述了记号。）

像应用一样，组合对束的并有分配律。
f(g,h) = fg,fh
(f,g) h =fh,gh

操作符与函数是相似的，每个应用于它的操作数时，都产生了一个结果。
正如我们组合函数，我们能够组合操作符，我们能组合一个操作符和一
个函数。例如，我们能组合 任何的函数f 产生一个数，得到一个新的函数。
(-f) x = -(f x)
特别地，
(- suc) 3 = -(suc 3) = -4

相似的，如果p是一个判断命题，那么
(¬p) x  =  ¬(p x)

我们能组合¬和even  得到  odd
¬even  =  odd

我们写如下的公式：
¬∀f  =  ∃¬f
¬∃f  =  ∀¬f

如果我们写成如下的公式就更好了。
¬∀  =  ∃¬
¬∃  =  ∀¬
 

3.3 列表作为函数

为了一些目的，一个列表能够被视为一个函数：列表L的域是 0,..#L.
与此同时，对于自然数n,一个函数的域是0,..n,它的函数体是一个项，
有时能够被认为是一个列表。索引一个列表与函数应用是相同的，
相同的记号 L n 在使用。列表的组合与函数的组合是相同的，相同的
记号 L M 在使用。在一个组合中，把 操作符，列表和函数混合在一起
是没有什么副作用的。例如：
-[3;5;2] = [-3;-5;-2]
suc [3;5;2] = [4;6;3]

我们也能在一个有选择性的并中，混合列表和函数。函数 1→21 作为
左操作数， 列表[10;11;12]作为右操作数，我们得到了如下的式子
1→21| [10;11;12] = [10;21;12]
正如我们定义它是列表。

我们能够把量词应用于列表，因为列表L，对应于函数 <n:0,..#L → Ln>
那么 ΣL 能够被用来表示 Σn:0,..#L ·  Ln ，这方便地表示了列表的项的求和。

在某一些方面，列表与函数是不同的，联结和求长度被用于列表，
不能用于函数。在列表中定义了顺序，在函数中没有顺序。列表
与函数不是一个硬币的两面。

3.4 极限与实数

让f:nat→rat  使得f0;f1;f2;... 是一个有理数的序列。函数的极限
（序列的极限）被表示为 LIM f. 例如，
LIM n: nat· (1 + 1/n)n
它是自然对数的基，写成 e,近似值是2.718281828459.
我们用如下的极限公理 定义了 LIM量词。
(MAX m· MIN n· f(m+n))  ≤  (LIM f)  ≤  (MIN m· MAX n· f(m+n))
所有的域都是nat.  这个公理给出了 f 极限的上界和下界。当上下界相等时，
极限公理告诉我们 f 的极限 就是这个上界与下界的值。例如，
LIM n· 1/(n+1)  =  0
对于这些函数，极限公理告诉我们这些，例如，
–1 ≤  (LIM n· (–1)n)  ≤  1
总之，
(MIN f) ≤ (LIM f) ≤ (MAX f)
对于单调递增函数 f , LIM f = MAX f . 对于单调递减函数 f, LIM f =MIN f.

现在我们能够定义扩展的实数。
x: xreal   =   ∃f: nat→rat· x = LIM f

我们得到了以自然数为域，或者是说以范围有理数为域的函数的极限。
现在 实数：
r: real   =   r: xreal  ∧  –∞ < r <∞

这个定义的解释是一个大的主题，叫做实分析，我们把这个问题放在其它的书中。

令 p:nat→ bin 使得p 是一个判断命题，p0;p1;p2;... 是一个二进制表达式的序列。
判断命题p的极限 是用如下的公理定义的
∃m· ∀n· p(m+n)   ⇒   LIM p   ⇒   ∀m· ∃n· p(m+n)
所有的域是自然数。 判断命题的极限公理是与数值函数的极限公理非常类似的。
理解它的一个方式 是把它分解成两个独立的部分，再改变如下的第二个变量。
∃m· ∀i· i≥m ⇒ pi   ⇒   LIM p
∃m· ∀i· i≥m ⇒ ¬pi   ⇒   ¬ LIM p

对于任何一个特定的从值到非本地化的变量的赋值，如果在序列p1,p2,p3...中
总是真的，第一个应用是说 LIM p是真的，第二个应用说，如果p的序列上的点
都是真的，p的极限是真的。
例如，
¬ LIM n· 1/(n+1) = 0  即使1/(n+1) 的极限是 0，1/(n+1) = 0 的极限是真的。

如果，对于一些从值到变量的赋值，序列根本没有二进制的值，那么公理不确定
LIM p 的值。

一个函数的目的是引入一个本地化的变量。但是我们必须记住任何一个表达式
都在谈到它的非本地化的变量。例如，
∃n: nat· x = 2×n
说的是 x是一个偶数。本地变量 n,它可以有m 或者是其它的名称，用来说ｘ
是一个偶数. 表达式在讨论的是x,不是n 。

 文章来源地址https://www.toymoban.com/news/detail-466174.html

到了这里，关于编程的实践理论 第三章 函数理论的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！