离散数学之数理逻辑

《离散数学之数理逻辑》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第一篇数理逻辑数理逻辑是应用数学方法引进一套符号系统来研究思维的形式结构和规律的学科，它起源于公元十七世纪。十九世纪英国的德·摩根和乔治·布尔发展了逻辑代数，二十世纪三十年代数理逻辑进入了成熟时期，基本内容（命题逻辑和谓词逻辑）有了明确的理论基础，成为数学的一个重要分支，同时也是电子元件设计和性质分析的工具。冯·诺意曼，图灵，克林，…等人研究了逻辑与计算的关系。基于理论研究和实践，随着1946年第一台通用电子数字计算机的诞生和近代科学的发展，计算技术中提出了大量的逻辑问题，逻辑程序设计语言的研制，更促进了数理逻

2、辑的发展。除古典二值（真，假）逻辑外，还研究了多值逻辑、模态逻辑、概率逻辑、模糊逻辑、非单调逻辑等。不仅有演绎逻辑，也还有归纳逻辑。计算机科学中还专门研究计算逻辑、程序逻辑、时序逻辑等。现代数理逻辑分为四论：证明论，递归论（它们与形式语言语法有关），模型论，公理化集合论（它们与形式语言的语义有关）。第1-1章命题逻辑学习要求:掌握命题，命题公式，重言式，等价式，蕴涵式等基本概念，能利用逻辑联结词或真值表，等价式与蕴涵式进行命题演算和推理；学习范式时与集合的范式进行对比。表述客观世界的各种现象，表述人们的思想，表

3、述各门学科的规则、理论等，除使用自然语言（这常常是上有歧异性的）外，还要使用一些特定的术语、符号、规律等“对象语言”，这些是所研究学科的一种特殊的形式化语言，研究思维结构与规律的逻辑学也有其对象语言。本章就是讨论逻辑学中的对象语言—命题及其演算，它相当于自然语言中的语句。§1-1-1命题逻辑联结词与真值表一、命题的基本概念首先我们从下面的例子加以分析。例1-1-1.1人总是要死的。例1-1-1.2苏格拉底是人。73例1-1-1.3苏格拉底是要死的。例1-1-1.4中国人民是勤劳和勇敢的。例1-1-1.5鸵鸟是鸟

4、。例1-1-1.61是质（素）数。例1-1-1.7今天没有下雨。例1-1-1.8公元二千年会出现生物计算机。例1-1-1.9太阳系外的星球上有人。例1-1-1.10他喜欢读书也喜欢运动。例1-1-1.11他在机房里或者在图书馆里。例1-1-1.12电灯不亮是灯泡或线路有毛病，或者是停电所致。例1-1-1.13如果和都是正数，则也是正数。例1-1-1.14当且仅当和都大于零。例1-1-1.15101+1=110。例1-1-1.16天气多好啊？例1-1-1.17他来了吗？例1-1-1.18全体起立！例1-1-1.1

5、9帮帮我吧！例1-1-1.20=0。例1-1-1.21我正在说谎。上述例1-1-1.1~1-1-1.4，例1-1-1.12～1-1-1.13是可以判断为对（真，成立）的陈述句，例1-1-1.5，1-1-1.6，1-1-1.14是能够判断为不对（假，不成立）的陈述句，例1-1-1.7～1-1-1.9在人类历史发展的长河中能够判断它是真或是假的陈述句，例1-1-1.10～1-1-1.11根据“他”当时的情况能够判断出是真或是假的陈述句，例1-1-1.15在二进制计算中为真，在十进制计算中为假，也还是可以判断为真或为

6、假的陈述句，例1-1-1.16是感叹句，例1-1-1.17是疑问句，例1-1-1.18是命令句，例1-1-1.19是祈使句，例1-1-1.20中x是一个未知数（变量），无法判断是真还是假，例1-1-1.21是无法判断真假的悖论。从以上的分析可以看出，表达思想的语句有不同的类别，数理逻辑中研究的是出现较多而又比较规范的语句—可以判断出真或假的陈述句。73定义1-1-1.1凡是能判断是真或是假的陈述句称为命题。如前面的例1-1-1.1～1-1-1.15都是命题，例1-1-1.16～1-1-1.21都不是命题。命题的

7、值为真或假。今后约定用1表示真，0表示假，除T和F以外的大写英文字母或它们后面跟上数字如A，A1，B5，Pi等或[数字]（如[123]，[28]，……）表示命题。如P：M8085芯片有40条引线，或[12]：M8085芯片有40条引线。P或[12]称为命题“M8085芯片有40条引线“的标识符。当命题标识符代表一个确定的命题时（如P或[12]，A：人总是要死的），称为命题常元，当命题标识符代表非确指的命题时，称这样的命题标识符为命题变元。注意：命题变元不是命题，只有对命题变元用一个确定的命题代入后，才能确定其值

8、是1还是0。定义1-1-1.2用一个确定的命题代入一个命题标识符（如P），称为对P进行指派（赋值，或解释）。再看前面的例1-1-1.1～1-1-1.6，这些命题不能再分解为更简单的能判断其值为1或0的陈述句了，这类命题称为原子命题。在例1-1-1.7中，如果表示今天下雨为原子命题P，则今天没有下雨是P的否定；例10可分解为原子命题P：他喜欢读书，Q：他喜欢运动，用联结词“也”联结起来；