逻辑和计算，对许多置身其外的人来说，似乎是两门不相干的学问，学逻辑的，大部分在哲学系，少部分在数学系，对他们来讲，逻辑就是关于“思维”的，是形而上的；从数学角度来说，就是数学的一个分支；而学计算机的，因为程序语言和离散数学的关系，了解多一些，但大多也是技术层面的知识，例如一个程序代码中的判断表达式之间的关系，布尔类型的使用。很少有人真正从本质上探究逻辑和计算的关系。因此本文想就这个问题做一点探讨和尝试，从命题逻辑出发，一路走下去，走到λ-演算和函数式编程。当然，这些讨论还是比较浅层次的，没有深入到理论问题，如类型论、证明论和范畴论等，只是力争让不太了解的人不必付出过大的阅读努力就可以了解逻辑到计算的大致路径。在本文最后，想探讨一下对这种研究的更一般的哲学性思考，超越了各种技术细节的深层思想。
为此，在开始这个话题之前，我想先引用一段《计算机程序的构造与解释》(Structure and Interpretation of Computer Programs，简称SICP)的第一作者Abelson1986在MIT开讲第一课的头一段话：

“欢迎大家到这里来上这门计算机科学的课程。不过‘计算机科学’这个名称是个很糟糕的名称：首先，它不是科学，你可以叫它工程、叫它艺术，不过我们后面会讲到，它更像巫师手里的魔法，一种带有灵性的魔法。第二，计算机科学和计算机无关。这种无关就像物理学并不是研究加速器，生物学不是研究显微镜，几何学不是关于土地测量的学问一样。不过，计算机科学确实在许多方面和几何学相像。因为几何学的起源确实来自于土地测量，几千年前因为尼罗河水的泛滥，人们个人所拥有的土地边界被冲毁，隔几年就需要重新丈量土地界定边界，这就造成了土地测量学的发达。因此对古埃及人来说，几何学就是土地测量学的技术。我们现在把计算机科学看做是关于计算机的学问，理由和当年埃及人把几何学看做是土地测量学完全一样。因此当人们刚刚开始认识一个新学科的时候，往往会把手头进行的工作和该学科的本质搞混，往往会把使用的工具当做研究对象。目前的现实情况(1986年)，我们对计算机科学的认识可能还不如当年埃及人对几何学的认识。现在回过头来审视发展了2000多年的几何学，就会认识到：真正的几何学，是关于形式化空间概念的学问，是关于数学真理性质的学科，是对数学对象的建模。这种科学的本质就是：它是一种陈述性知识，用定义、定理等语言手段陈述属于这个学科真理的知识，这种知识的本质就是：什么是关于这个学科真理？
而计算机科学，未来的人们会认识到它的实质实际上是形式化“过程”(process)的知识：概念创建、实现和完成的过程，这种知识的本质就是：如何“证实”(verify)真理？计算机科学的任务就是精确阐述某个知识的实现方法。”

我们要真正理解逻辑和计算的本质，基本上就像Abelson教授所述，一种是陈述性知识，一种是过程性知识，这两种知识的关联，就在于如何将陈述性知识转换为过程性知识。这是我们理解逻辑和计算关系本质的核心思想。
我们今天所有的讨论都是以这个观点作为基础。因此我们的出发点就是一阶逻辑，具体地说就是一阶命题逻辑和少数关于量词和量化表达式的谓词逻辑。

1. 命题和命题逻辑
命题的概念大部分人都熟悉，就是以肯定陈述句形式出现可以回答对还是不对的句子。我们来看几个例子：
(1)
a. 张晓华很聪明
b. 李建很聪明
c. 王立波很聪明
这三个句子看上去平淡无奇，在可以把这些句子的主语和现实世界中的具体人物联系起来之前我们无法知道说的“对不对”、是真是假。不过目前我们只关心这些句子的形式。这些句子形式上的共同点就是：在“很聪明”这个谓语之前有三个不同的人名做主语。这很像我们在学外语时做的句型替换练习。这种关联，在语言学中称作“聚合关系”、或者“排比关系”(paradigmatic)，因为很像修辞学中的排比句。如果做成网页上的表格，我们可以在主语位置建一个下拉框，后面是谓语文本的内容，用户可在下拉框中任选一人然后计算机可以决定这个句子是真是假。
如果用文本的形式表示，或者说有点数学味的表示，我们可以用提取公因式法：
很聪明 {张晓华、李建、王立波}
如果数学味再强一点，我们可以建立一个函数，这个函数的定义域就是花括号里的人名，值域就是真值集合{真、假}。如果用ƒ表示谓词“很聪明”，那么：
ƒ：{张晓华、李建、王立波} → {真、假}
如果我们假定只有“张晓华”一人“很聪明”的话，我们就会得到三个命题：
(2)
a. ƒ(张晓华) = 真
b. ƒ(李建) = 假
c. ƒ(王立波) = 假
这三个命题，我们可以形式化为：
(3)
ƒ：{z, l, w} → {T, F}
这样，我们就达到了目的——从命题的概念走到了函数的概念，这个历程，我们这里仅仅用了几分钟，而人类却花了2000多年，从亚里士多德到布尔和弗雷格。

2. 真值函数
函数和关系的引进，是弗雷格创立一阶谓词逻辑的最大贡献，它使得对命题句的分析更加细化，因为关系可以是二项的，R1(a, b)，也可以是多于二项的，R2(a, b, c)，这在亚氏逻辑中是无法表示和处理的。
如果说关系是为了处理更复杂的句子，侧重于句法层面，那么函数就是描述命题逻辑语义的工具。有了这个工具，弗雷格就可以把复合命题句的真值描述为：
(4)
复合命题的真值是这个命题下各个子句真值的函数
写成式子：
(5)
a. 𝝋(𝑝, 𝑞) = ~(𝑝 ∧ 𝑞) → 𝑞
b. 𝝍(𝑝, 𝑞) = (𝑞 → ~p) ∨ ~ 𝑞
翻译成中文就是𝝋和𝝍的真值，分别是由𝑝和𝑞的真值决定的。这里，𝑝和𝑞的真值是自变量，而是𝝋和𝝍的真值是因变量。这种变量，不再是数学中的实数集合，而是布尔数集合，在这样的集合上定义的运算叫做逻辑运算或者布尔运算（严格说布尔运算不包括蕴含和等价），这种由弗雷格发明的函数叫做真值函数(truth function)，以这种运算作为基础的逻辑框架叫做真值函数式逻辑(truth functional logic)。
既然谈到了函数，就不得不讨论变量。我们知道，符号逻辑学的开篇大致都是从逻辑常量和变量开始。有了常量、变量的概念我们就可以理解量词和量化表达式了。现在我们有了函数的概念，那么量化表达式中的变量和函数中的变量是怎样一种关系，就是我们下面讨论的话题。

3. 变量和函数
谓词逻辑中有两个量词，全称量词和存在量词，分别表达“有、无、盈、亏”这四个概念，现在仍以上面(3)的例子说明：
(3)
ƒ：{z, l, w} → {T, F}
这个函数的一般形式：
ƒ(𝓍）= v（其中 v∈V = {T, F}）
如果在这定义域中所有的命题都为真，亦即：
(6)
ƒ(z）= T
ƒ(l）= T
ƒ(w）= T
我们就可以用全称量化表达式：
∀𝓍 ƒ(𝓍)
意思是在{z, l, w}范围内，任意一个元素x都可以使这个命题为真。有人可能要问：ƒ(𝓍)是函数还是谓词表达式？可以这样认为：如果ƒ(𝓍)施用于{z, l, w} 内某个具体元素得到的结果是真值集合中的元素那么就可以认为是谓词表达式，而谓词表达式的抽象表示——ƒ(𝓍)则称为真值函数。所以，全称量化表达式的真实含义就是：
定义域集合中的任何元素都可以使真值函数ƒ(𝓍)的真值为真。
类似地，存在量化表达式表示定义域集合中至少有一个元素使得真值函数ƒ(𝓍)的真值为真。
这样看来，在真值函数中，变量𝓍并不是绝对任意的，受限于所定义的集合。虽然数学函数也是如此，但由于数学函数的对象是开放集的数系，在定义区间或数系子集合之前一般前提假定似乎是任意的。当然，一旦函数表达式给出，一些关于数的代数性质自然会限制函数的定义域，例如含有有理数的函数其部分表达式的值不能为0。
因此，逻辑学中量化表达式中的变量，或者说在表达“一切”“有些”这些概念时，首先要界定这些变量的范围——定义域。在自然语言中，如果定义域范围较小，表达明确我们也会明确表示：
(7)
z、l、w这三个人都很聪明。
在这个句子中，“z、l、w”表示定义域，而“这三人”，可以用不定复数“这些人”替换，这里的“都”，表达复数概念，特别是表达全称量化的复数概念。

有了上述概念，我们就可以得出结论，谓词表达式命题ƒ(z）= T是特殊的函数——真值函数，它的值域只能是真值集合中的T或F；而一般的函数，其值域可以是任何定义的集合。
在Lisp语言中，如果一个函数的值是真值，通常会在这个函数名后加一个字母p，表示这个函数是谓词，或者真值函数，其值域是真假值集合，其中的p就表示“predicate”。

4. 假言推理
一阶逻辑语言只是工具，逻辑学的最大用途在于形式化推理，论证模式（argument schema）。其中最著名的就是两个假言推理的论证模式：
·假言推理的肯定前件(Modus Ponens)，例如
(8)
如果张晓华很聪明那他一定会做这道题
张晓华很聪明
——————————————
那他一定会做这道题

如果把这个论证模式形式化
𝑝 → 𝑞,  𝑝 ⊢ 𝑞
((𝑝 → 𝑞) ∧ 𝑝) → 𝑞

其中“⊢”后的句子表示推理的结论，相当于上面例子中横线下面的句子。关于假言推理，可以参考网上资源，例如百度百科，我们这里不再详论。讨论这个话题的目的是想要引出另一个重要概念：代入原则和外延公理。

5. 代入原则和外延性（substitutionality and extensionality）
这两个概念在“三聊语义学”系列和“集合论的哲学认知——读《Naive Set Theory》：外延公理”中有详细讨论，有兴趣可以参考。这里只谈函数的外延性和代入原则：
一、外延性：函数的外延是指函数的自变量和因变量的值对集合：
ƒ = {(a, b) | a∈A ∧ b∈B}
换句话说，我们把函数看做是黑盒子，不关心函数本身的内容只关心输入一个值后会得到什么值。例如拿计算器算2的平方根，我们给出函数符号√和数值2，计算器给出结果。至于这个根是如何算出来的我们并不关心。
二、替换性：如果一个函数有一个值对(s, b)，当s被t替换后函数值仍然是b，得到(t, b)，那么就可以确定s=t。
外延性和替换性可以解释为什么一阶逻辑语言对具体原子命题和个体对象的性质不关心而只关心命题间的连接以及量化表达式。

6. 函数的抽象
函数的概念，由弗雷格引入逻辑，上个世纪又经阿伊杜凯维茨、巴希勒尔和兰贝克引入到自然语言研究，产生了范畴语法。范畴语法从逻辑的两个基本概念：个体名词和句子出发，利用函数的概念，定义语言中的其它表达式范畴，而且描述粒度远远超过了短语结构语法，具有更大的灵活性，在新世纪以后的自然语言形式化研究中占有愈来愈重要的位置。对范畴语法的介绍可参考我在“现代形式语法理论”中的范畴语法学习笔记。它的基本概念是这样：
任何语言，都存在表示名称的表达式和表达命题的表达式
设前者为n，后者为s，例如
n = 苏格拉底
s = 苏格拉底是人
n和s被定义为基本范畴，通过n和s各种约分组合，可以生成各种派生范畴。
所谓约分组合，就是
s/n的形式，这种形式表示的就是不及物动词或者形容词
在这里，s/n作为函数，可以生成句子：
例如：
春天来了
s = 春天来了
n = 春天
s/n = 来了
在范畴语法中，除了基本范畴，所有派生范畴都是函数，而且是没有名称只以s/n组合的形式表示函数，因此一个句子的形式表达就是
s/n (n) = s
更详细的解说可参考“Ajdukiewicz《Die syntaktische Konnexität》学习笔记（三）”

我们这里关注的是函数的形式。在范畴语法的形式语言中，n作为自变量，s作为因变量，而s/n的组合表示函数关系，亦即，用函数的外延性——输入和输出表达函数本身，这使得对函数的研究可以在不考虑实际背景，不管是数学函数还是逻辑的真值函数还是范畴语法的派生范畴，我们都可以一个统一视角审视函数：函数的外延性，函数是如何定义的。

对函数的形式化研究早在上世纪1920年代就开始了，经Schönfinkel、Curry和Church，终于发展出两个平行但是又互补的学科——lambda演算和组合子逻辑。因此在我们真正开始学习用编程理解逻辑时，就要对这两个领域有所了解。如果你是程序员，或者在读和信息科学、数学科学有关专业，那这两个学科知识的重要性不言而喻，你可能知道得更多。由于无论lambda演算还是组合子逻辑、再到类型论，其中心思想都是逻辑与计算的关系问题。

（未完待续）