离散数学——数理逻辑.pdfVIP

第一篇 数理逻辑 逻辑学是研究推理的科学，具有十分悠久的历史，早在两千多年前的古希腊时代就已经 很发达了。数理逻辑是数学化的逻辑学，是用数学方法研究推理的科学，其历史只有三百多 年。德国哲学家和数学家莱布尼兹（Leibniz ）被认为是数理逻辑的创始人，他于 17 世纪中 期明确提出了建立通用的符号语言和通用代数的思想。他认为数学之所以能迅速发展，数学 知识之所以能行之有效，就是因为数学使用了特制的符号语言。这种符号为表达思想和进行 推理提供了良好的条件。他希望能够建立一个普遍的符号语言，这种语言的符号应该是表意 的，每个符号表达一个概念，如同数学的符号一样。一个完善的符号语言同时又应该是一个 思维的演算。他希望根据这种演算，思维和推理就可以用计算来代替。这样当遇有争论的时 候，大家只要拿起笔来计算一下，问题就解决了。表意的符号语言和思维的演算是他提出来 的重要思想。 数理逻辑最近几十年发展迅速，研究范围不断扩大，应用领域日益广泛。不少成果已应 用于计算机科学领域。如 PROLOG 语言就以一阶逻辑为基础。在程序验证、程序变换、软 件形式说明、程序设计语言的形式语义学、人工智能等方面，都大量地应用数理逻辑的概念、 方法和理论。 概括起来，数理逻辑可以分为五大分支：逻辑演算、公理集合论、证明论、递归论和模 型论。逻辑演算是数理逻辑中的最基础部分。本篇介绍逻辑演算中最基本、最成熟的两个部 分：命题逻辑和谓词逻辑。这也是学习和研究各种非标准逻辑的基础，在计算机科学中应用 最为广泛。 1 第 1 章 命题逻辑 1.1 命题与联结词 1.1.1 命题及其表示 所谓命题，是指具有真假意义的陈述句。也就是说能够确定或能够分辨其真假的陈述句， 且真或假二者必居其一，也只能居其一。简言之，命题就是非真即假的陈述句。下面给出一 些实例，判断是否为命题？ （1）离散数学好学吗？ （2 ）我真开心！ （3 ）禁止吸烟！ （4 ）我是学生。 （5 ）6 不是自然数。 （6 ）火星上有生物。 （7 ）现在是八点钟。 （8 ）2012 年奥林匹克运动会将在英国举行。 （9 ）如果天气好，那么我去散步。 （10）本命题为假。 在上面的例子中，（1）、（2 ）、（3 ）不是陈述句，因而不是命题。（4 ）、（5 ）、（6 ）、（7 ）、 （8 ）、（9 ）是命题。其中（4 ）的真假意义要根据具体的“我”而定；（7 ）要根据“现在” 具体的时间而定；（5 ）是假命题；（6 ）在目前可能无法判定真假，但从事物的本质而言，它 本身是有明确真假意义的，只不过我们现在还不知道，所以我们承认这也是一个命题；（8 ） 是真命题；（9 ）由两句话组成，有明确的真假意义，因而是命题；（10）无法确定它的真假， 当“本命题”假时，它便真，当“本命题”真时它便假，这种断言叫悖论。 一些不能分解为更简单的陈述句的命题，称为原子命题。如上面的（4 ）、（5 ）、（6 ）、（7 ）、 （8 ）都是原子命题。反之，称为复合命题，即由联结词，标点符号和原子命题复合而成的 命题。如上面的（9 ）为复合命题。联结词的概念将在下一小节给出。 一个命题的真或假称为命题的真值，简称值，真用 T 或 1 表示；假用 F 或 0 表示。由 于命题只有真、假二个真值，所以命题逻辑也称二值逻辑。 一个原子命题，一般用大写字母或带下标的大写字母，如P ，Q，R ，…，或P ，Q ，R ，…， i i i 等表示，把表示原子命题的符号，称为命题标识符，简称命题符。例如 P ：北京是中国的首都。其中“:”代表表示的意思，下同。 一个命题标识符 P ，如果表示一个确定的命题，则称P 为原子命题常元，简称命题常元； 若 P 只表示任意命题的位置标志，或表示不确定的命题，或以原子命题为值的变元 P ，就称 P 为原子命题变元，简称命题变元。可见，命题变元是以命题的真值为值的变元。显然