离散数学——数理逻辑new

《离散数学——数理逻辑new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一篇数理逻辑逻辑学是研究推理的科学，具有十分悠久的历史，早在两千多年前的古希腊时代就已经很发达了。数理逻辑是数学化的逻辑学，是用数学方法研究推理的科学，其历史只有三百多年。德国哲学家和数学家莱布尼兹（Leibniz）被认为是数理逻辑的创始人，他于17世纪中期明确提出了建立通用的符号语言和通用代数的思想。他认为数学之所以能迅速发展，数学知识之所以能行之有效，就是因为数学使用了特制的符号语言。这种符号为表达思想和进行推理提供了良好的条件。他希望能够建立一个普遍的符号语言，这种语言的符号应该是表意的，每个符号表达一个概念，如同数学的符号一样。一个完善的符号语言同时又应该是一个思维的演算。他希望

2、根据这种演算，思维和推理就可以用计算来代替。这样当遇有争论的时候，大家只要拿起笔来计算一下，问题就解决了。表意的符号语言和思维的演算是他提出来的重要思想。数理逻辑最近几十年发展迅速，研究范围不断扩大，应用领域日益广泛。不少成果已应用于计算机科学领域。如PROLOG语言就以一阶逻辑为基础。在程序验证、程序变换、软件形式说明、程序设计语言的形式语义学、人工智能等方面，都大量地应用数理逻辑的概念、方法和理论。概括起来，数理逻辑可以分为五大分支：逻辑演算、公理集合论、证明论、递归论和模型论。逻辑演算是数理逻辑中的最基础部分。本篇介绍逻辑演算中最基本、最成熟的两个部分：命题逻辑和谓词逻辑。这也是学习

3、和研究各种非标准逻辑的基础，在计算机科学中应用最为广泛。1第1章命题逻辑1.1命题与联结词1.1.1命题及其表示所谓命题，是指具有真假意义的陈述句。也就是说能够确定或能够分辨其真假的陈述句，且真或假二者必居其一，也只能居其一。简言之，命题就是非真即假的陈述句。下面给出一些实例，判断是否为命题？（1）离散数学好学吗？（2）我真开心！（3）禁止吸烟！（4）我是学生。（5）6不是自然数。（6）火星上有生物。（7）现在是八点钟。（8）2012年奥林匹克运动会将在英国举行。（9）如果天气好，那么我去散步。（10）本命题为假。在上面的例子中，（1）、（2）、（3）不是陈述句，因而不是命题。（4）、（5

4、）、（6）、（7）、（8）、（9）是命题。其中（4）的真假意义要根据具体的“我”而定；（7）要根据“现在”具体的时间而定；（5）是假命题；（6）在目前可能无法判定真假，但从事物的本质而言，它本身是有明确真假意义的，只不过我们现在还不知道，所以我们承认这也是一个命题；（8）是真命题；（9）由两句话组成，有明确的真假意义，因而是命题；（10）无法确定它的真假，当“本命题”假时，它便真，当“本命题”真时它便假，这种断言叫悖论。一些不能分解为更简单的陈述句的命题，称为原子命题。如上面的（4）、（5）、（6）、（7）、（8）都是原子命题。反之，称为复合命题，即由联结词，标点符号和原子命题复合而成的命

5、题。如上面的（9）为复合命题。联结词的概念将在下一小节给出。一个命题的真或假称为命题的真值，简称值，真用T或1表示；假用F或0表示。由于命题只有真、假二个真值，所以命题逻辑也称二值逻辑。一个原子命题，一般用大写字母或带下标的大写字母，如P，Q，R，…，或Pi，Qi，Ri，…，等表示，把表示原子命题的符号，称为命题标识符，简称命题符。例如P：北京是中国的首都。其中“:”代表表示的意思，下同。一个命题标识符P，如果表示一个确定的命题，则称P为原子命题常元，简称命题常元；若P只表示任意命题的位置标志，或表示不确定的命题，或以原子命题为值的变元P，就称P为原子命题变元，简称命题变元。可见，命题变元

6、是以命题的真值为值的变元。显然，命题变元不是命题。将一个命题变元P用一个特定命题去代替，才能确定它的真值，这时也称为对P进行指派或对P进行解释。21.1.2联结词联结词是逻辑联结词或命题联结词的简称，用它和原子命题构成复合命题。常用联结词有以下五种。定义如下：(1)否定联结词设P是一个命题，由联结词┐和命题P构成┐P，┐P为命题P的否定式复合命题。┐P读做“非P”。联结词┐是自然语言中的“非”、“不”和“没有”等的逻辑抽象。否定联结词是一个一元运算。例如；P：离散数学是计算机及相关专业的基础课。┐P：离散数学不是计算机及相关专业的基础课。(2)合取联结词令P和Q是两个命题，由联结词∧把P，

7、Q连接成P∧Q，称P∧Q为P和Q的合取式复合命题，P∧Q读做“P与Q”，或“P合取Q”。联结词∧是自然语言中的“和”，“与”，“并且”，“既…又…”等的逻辑抽象。合取联结词是一个二元运算。例如：P：今天下雨。Q：明天下雨。P∧Q：今天与明天都下雨。(3)析取联结词设P和Q是两个命题，由联结词∨把P，Q连接成P∨Q，称P∨Q为P和Q的析取式复合命题，P∨Q读做“P或Q”，或“P析取Q”。析取联结词∨是自然语言中的“或”的逻