数学符号化的扩充:数理逻辑的兴起

2011-10-19  敦行斋

   数学的主要内容是计算和证明。在十七世纪,算术因符号化促使了代数学的产生,代数使计算变得精确和方便,也使计算方法系统化。费尔马和笛卡儿的解析几何 把几何学代数化,大大扩展了几何的领域,而且使得少数天才的推理变成机械化的步骤。这反映了代数学作为普遍科学方法的效力,于是笛卡儿尝试也把逻辑代数 化。与笛卡儿同时代的英国哲学家霍布斯也认为推理带有计算性质,不过他并没有系统地发展这种思想。

    现 在公认的数理逻辑创始人是莱布尼兹。他的目的是选出一种“通用代数”,其中把一切推理都化归为计算。实际上这正是数理逻辑的总纲领。他希望建立一套普遍的 符号语言,其中的符号是表义的,这样就可以象数字一样进行演算,他的确将某些命题形式表达为符号形式,但他的工作只是一个开头,大部分没有发表,因此影响 不大。

    真正使逻辑代数化的是英国数学家布尔,他在1847年出版了《逻辑的数学分析》,给出了现代所谓的“布尔代数”的原型。布尔确信符号化会使逻辑变得严密。他的对象是事物的类,1表示全类,0表示空类;xy表示xy的共同分子所组成的类,运算是逻辑乘法;xy表示xy两类所合成的类,运算是逻辑加法。

    所以逻辑命题可以表示如下:凡xy可以表示成x(1y)0;没有xy可以表示成xy0。它还可以表示矛盾律 x(1x)0;排中律x(1x)1

    布尔看出类的演算也可解释为命题的演算。当xy不是类而是命题,则x1表示的是命题 x为真,x0表示命题x为假,1x表示x的否定等等。显然布尔的演算构成一个代数系统,遵守着某些规律,这就是布尔代数。特别是它遵从德·莫尔根定律。

    美国哲学家、数学家小皮尔斯推进了命题演算,他区别了命题和命题函数。一个命题总是真的或假的,而一个命题函数包含着变元,随着变元值选取的不同,它可以是真也可以是假。皮尔斯还引进了两个变元的命题函数以及量词和谓词的演算。

    对现代数理逻辑贡献最大的是德国耶拿大学教授、数学家弗雷格。弗雷格在1879年出版的《概念文字》一书中不仅完备地发展了命题演算,而且引进了量词概念以及实质蕴涵的概念,他还给出一个一阶谓词演算的公理系统,这可以说是历史上第一个符号逻辑的公理系统。因此在这本只有88页的小册子中,包含着现代数理逻辑的一个颇为完备的基础。

    1884年,弗雷格的《算术基础》出版,后来又扩展成《算术的基本规律》。不过由于他的符号系统烦琐复杂,从而限制了它的普及,因此在十九世纪时,他的著作流传不广。后来由于罗素的独立工作,才使得弗雷格的工作受到重视。

    用符号语言对数学进行公理化的是意大利数学家皮亚诺,他在1889年用拉丁文写了一本小册子《用新方法陈述的算术原理》。在这之前,皮亚诺已经把布尔和施罗德的逻辑用在数学研究上,并且引进了一系列对于他前人工作的更新。例如对逻辑运算和数学运算使用不同的符号,区别范畴命题和条件命题,这引导他得出量词理论。

    这些改进都是对于布尔和施罗德理论的改进,而不是对弗雷格理论的改进,因为当时皮亚诺还不知道弗雷格的工作。在《算术原理》中,他在引进逻辑概念相公式之后,开始用符号的记法来重写算术,在这本书中他讨论了分数、实数、甚至极限和点集论中的概念。

  皮亚诺引进最原始的算术概念是“数”“1”“后继”和“等于”,并且陈述了关于这些概念的九条公理。今天我们认为其中公理2345都是讨论恒等的,应该属于逻辑公理,所以就剩下了五条公理。这就是现在众所周知的皮亚诺公理。最后一条公理即公理9,就是所谓数学归纳法原理,他用类的词句来表述,其中包含一个类变元。皮亚诺承认他的公理化来自戴德金。

    1开始,皮亚诺用x1来表示后继函数。然后作为定义引进了加法和乘法。这些定义是递归的定义。虽然在他的系统中,皮亚诺没有象戴德金那样有力的定理可资利用,但皮亚诺并没有公开地宣称这些定义可以去掉。

    这 本书的逻辑部分还列出命题演算的公式,类演算的公式,还有一部分量词的理论。皮亚诺的符号要比布尔和施罗德的符号高明得多,标志着向近代逻辑的重要转变。 他还对于命题的演算和类演算做了某些区别。这就是我们现在的两种不同演算,而不是同一种演算的两种不同解释。它的普遍量词记号是新的,而且是便利的。

    不过书里还是存在缺点,如公式只是列出来的,而不是推导出来的;因为没有给出推导规则,皮亚诺引进了代入规则的概念,但是也没有给出任何规则;更严重的是他没有给出任何分离规则,结果尽管他的系统有许多优点,但他没有可供使用的逻辑。一直到后来,他才在一系列文章,特别是1895年发表的《数学论集》中,对这些逻辑公式进行了证明。然而他这些证明还是缺少推演规则,在这方面他受到了弗雷格的批评。后来皮亚诺尽力想比弗雷格的《概念文字》有更多的内容,但是他做得并不够。不过他的这些著作在数学界仍有很大影响,得到广泛的传播。

    2.1.1 命题演算

    逻 辑演算是数理逻辑的基础,命题演算是逻辑演算最基本的组成部分。命题演算研究命题之间的关系,比如简单命题和复杂命题之间的关系,简单命题如何构成复杂命 题,由简单命题的真假如何推出复杂命题的真假等等。对于具体命题,我们不难通过机械运算来达到我们的目的,这就是命题的算术。

    对于命题演算最早是由美国逻辑学家波斯特在1921年给出证明的,他的证明方法是把命题化为标准形式—合取范式。教科书中常见的证明是匈牙利数学家卡尔马给出的。除了这些构造性证明之外,还有用布尔代数的非构造性证明。

    2.1.2 一阶谓词演算

    在命题演算中,形式化的对象及演算的对象都是语句。但是,在数学乃至一般推理过程中,许多常见的逻辑推理并不能建立在命题演算的基础上。例如:1.张三的每位朋友都是李四的朋友,王五不是李四的朋友,所以王五不是张三的朋友。因此,我们必须深入到语句的内部,也就是要把语句分解为主语和谓语。

    谓 词演算要比命题演算范围宽广得多,这由变元也可以反映出来。命题演算的变元只是语句或命题,而谓词演算的变元有三类:个体变元、命题变元、谓词变元。由于 谓词演算中有全称量词和存在量词,在这些量词后面的变化称为约束变元,其他变元称为自由变元。最简单的谓词演算是狭义谓词演算,现在通称一阶谓词演算。

谓 词演算中的普遍有效公式与命题演算中的重言式还是有差别的。我们有行之有效的具体方法来判定一个公式是不是重言式。这种方法每一步都有明确的规定,并且可 以在有限步内完成,这种方法我们称为能行的。但是在谓词演算中,并没有一种能行的方法来判定任何一个公式是否普遍有效的。这就需要寻找一种能行的方法来判 定某个具体公式或一类公式是否普遍有效,这就是所谓判定问题。它是数理逻辑中最主要的问题之一。

    一 阶谓词演算的普遍有效公式也有一个公理系统。另外,同样也有代入规则及推理规则。另外,还有约束变元改字规则等变形规则。在谓词演算中也可以将每一个公式 通过变形规则化为标准形式。其中最常用的是所谓前束范式,也就是公式中所有的量词都放在最前面,而且还可以把前束范式进一步化成斯科兰路范式,它不但具有 前束范式的形状,而且每一个存在量词都在所有全称量词之前。

    利用范式可以解决许多问题,最重要的是哥德尔证明的一阶谓词演算的公理系统的完全性定理,即可以证明:公式A在公理系统中可以证明的当且仅当A是普遍有效的。同样,一阶谓词演算的公理系统也是协调(无矛盾)的、相独立的。1936年丘奇和图林独立的证明一阶谓词演算公式的一般判定问题不可解问题,可以变为去解决具有特殊形式的范式公式的判定问题。

    2.1.3 其他逻辑演算

    逻辑演算系统很多,命题演算应该说来源于布尔,布尔的系统是非真即假的二值系统。真值大于2的逻辑系统称为多值逻辑。多值逻辑首先由波兰数学家卢卡西维茨在1920年引进,波斯特在1921年也独立地引进。多值逻辑有着广泛的应用,在二十世纪七十年代,国际上就曾多次召开专门的多值逻辑会议。

    另一种常见的逻辑是模态逻辑,它是美国逻辑学家刘易斯在1918年引进的。他考虑的不是实质蕴涵而是严格蕴涵。另外,他在逻辑中也考虑所谓必要性与可能性等问题,引进著名的模态算子,这是直观可能性的形式化。

    还有一个包括古典逻辑演算的公理系统,即直觉主义公理系统,其中否定排中律,它是荷兰数学家海丁于1930年引进的。它虽因直觉主义而得名,但是可以得到其他的解释,在现代数理逻辑的研究中十分重要。

    在 数理逻辑的研究中,狭义谓词演算是最重要的。狭义谓词演算也称一阶谓词演算,许多人默认数学中所用的逻辑通用为一阶谓词演算。但是,许多涉及数学问题的逻 辑演算必须加进有关等号的谓词,称为具等式的一阶谓词演算。这是现在最常用的一种逻辑系统,在研究算术系统中就要用到它。

    但是,即使象实数的算术系统,一阶谓词演算也是不够的,更何况现代数学中涉及集合的子集,因此一阶谓词演算是不足以表达的。这时需要二阶谓词演算乃至高阶谓词演算,其中首先出现的是谓词变元。

    不 过,在现代数理逻辑的研究中,常常通过其它方式推广一阶谓词演算。比如一种常用的“无穷”逻辑允许无穷公式,即公式中容许可数多合取或析取,不过量词仍限 制为有限多。这种无穷逻辑现在在集合论、递归论、模型论当中是必不可少的。另外一种推广一阶谓词演算的途径是引进新的量词,比如“存在许多……”。

    逻 辑系统比数学系统更不统一,各人用的系统在细节上有许多不同,而且同一概念也用不同的符号来表示。第一套是弗雷格自己系统运用的,但是连他的后继者也不用 这套极不方便的符号系统。第二套是皮亚诺首先在《数学论集》提出的,后经罗素和怀特海在《数学原理》中使用。一般文献通用的都是这种符号系统的改进形式, 如希尔伯特和他的学生们采用的也属于这一套。第三套是卢卡西维茨使用的,后来也有人用,如普瑞尔在《形式逻辑》中就加以来用。

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。如发现有害或侵权内容,请点击这里 或 拨打24小时举报电话:4000070609 与我们联系。

    猜你喜欢

    0条评论

    发表

    请遵守用户 评论公约

    类似文章
    喜欢该文的人也喜欢 更多