数理逻辑的一项重要任务是回答“什么是证明?” 并试图将“证明”这一概念(与之相关有可计算性概念)精确化。基于这个目的,数理逻辑需要设计适当的语言用于对计算机科学领域中遇到的情景建模,以便于对它们作形式推理,得到我们想要的结论。
为了将证明精确化,所用的方法是什么呢?数理逻辑在研究推理时要建立数学模型(我们称这个数学模型为形式系统)ß对形式系统进行研究,必须用普通的自然语言(元语言)ß研究推理时不可避免要用到逻辑ß逻辑是由演算组成的ß在进行推理时需要用到精确的演算规则ß推理过程中所使用的语言必须无二义性,以便于构造有效的推理论证。
在计算机应用中,这就要求我们构造的论证必须是有效的且能在计算机上执行。因此,为了达到这样的目的,通常的方法是引进一种符号语言,它能够精确表达其意义。
先来看第一个例子:
例1 ①If the train arrives late and there are no taxis at the station, then John is late for his meeting. ②John is not late for his meeting. ③The train did arrive late. ④Therefore, there were taxis at the station.
看完这个例子,直觉告诉我们,这一论证是有效的:
① ③告诉我们,如果车站没有出租车,那么John必迟到;②告诉我们John没有迟到.。
因此车站一定有出租车。
上述的论证有以下结构:
语句序列 前提 therefore 结论
我们说,如果“Therefore” 后的语句逻辑地从前面的语句序列进行推断,这个论证就是有效的。
为了加深印象再看一个同样的例子(刚开始概念可能比较简单,但是我们说的稍微详细一些):
例2 ①If it is raining, and Jane does not have her umbrella with her, then she will get wet. ②Jane is not wet. ③It is raining. ④Therefore, Jane has her umbrella with her.
① ③告诉我们, 如果Jane不带雨伞,那么Jane被雨淋显。②告诉我们 Jane没有被雨淋湿。
因此Jane 一定带了雨伞。
这俩例子有同样的结构(可能你自己总结的结构会不一样):
If p and not q then r Not r p Therefore, q
在进行逻辑推理时,我们仅仅关注这些句子的逻辑结构。即,我们仅考察论证形式。在实际应用这种“论证形式”时,我们会考虑这些句子的实际意义。在上述两个实例中,前提和结论都是简单命题构成。
为了使论证严密,我们需要设计一个语言,利用这一语言,能够表示这些语句并使论证形式突显。我们先讨论命题逻辑语言。命题逻辑语言基于命题或陈述句。原则上,我们约定这些命题或陈述句不是真就是假。
断言是一个陈述句。一个命题是一个或真或假而不能两者都是的陈述句。如果命题是真, 我们说它的真值为真,如果命题是假, 我们说它的真值是假。
例如以下的陈述句都是命题,因为它们不是真就是假:
(1)The sum of the numbers 3 and 5 equals 8. (2)Jane reacted violently to Jack’s accusations. (3)Every even natural number >2 is the sum of two prime numbers. (4)John owes James two pounds. (5)All eggs which are not square are round.
这个我们有几个约定:
①对于那些非陈述句的语句,不在我们的考虑范围内。
例如:下述都不是命题:
(a) x+y>4 (c) 真好啊! (b) x=3 (d) 你去哪里?
(a)和(b)是断言,但不是命题, 因为它的真值取决于x和y的值。 (c)和(d)都不是陈述句, 所以不是命题。
②我们主要考虑涉及计算机系统或计算机程序的精确命题,我们不仅要确切说明这些命题,而且要检验一个给定的程序或系统是否按现有的规范(工程设计书)运行。为此,我们需要设计推理演算。从直觉上说,如果所有的前提是正确的,那么我们推出的结论也是正确的。
给定任一个关于计算机程序的真实性质,在我们的推理演算中是否能找到一个论证,使得该论证的结论就是那个真实性质?这是一个难解问题。比如上述例子中命题3中的情况那样(哥德巴赫猜想)。
我们下面要设计的逻辑是符号化的。我们将所有英语命题构成的某个足够大的子集转化成一系列的符号串。这样做使我们仅关注论证形式。其重要意义是:由于计算机系统或软件的工程设计书都是这样的命题序列。这样做使得对这些工程设计书的自动化处理成为可能。
那么怎么做呢?将某些命题作为原子命题或不可分命题。例如,“6 是偶数”是一个原子命题。对于每个原子命题,用一个不同符号来记它,这些符号可以是:p, q, r, … 或 p1, p2, p3, … 。对于复合命题,我们把它们表示成这些原子命题的组合。比如:
例3 p: I won the lottery last week. q: I purchased a lottery ticket. r: I won last week’s sweepstakes.
为了表示更复杂的命题,我们需要引入表示联结词的符号。最常用的联结词及用于表示它们的符号如下:
非p ﹁p p的否定
I did not win the lottery last week.
It is not true that I won the lottery last week.
p或q p∨q p与q的析取 p与q p∧q p与q的合取 如果p那么q p→q p与q间的蕴含,q是p的逻辑结果。p是p→q 的前提(假设),q是它的结论。
以上每个联结词可以作为规则,利用这些联结词可以构造更为复杂的命题。
比如:
p∧q → ﹁r∨q
这样表示也许存在模糊。在计算机处理时可能要求加上括号。即 (p∧q) → (﹁r∨q)
为此,对于上述联结符约定邦定的优先级:
﹁ 优先于∨和∧, ∨和∧优先于→。
→是右结合的。
很熟悉是不是,仿佛回到了遥远的高中。
这一节比较简单,下一节我们说自然演算。
相关推荐
详细介绍了命题逻辑的基本知识,比课本上的要好些
离散数学是计算机学科的经典核心基础课程。课程内容主要包括集合论,数理逻辑,关系...离散数学 教学课件(配方世昌《离散数学(第三版)》) 第1章 数理逻辑(命题逻辑部分)文档作者:中南大学计算机学院 郑瑾副教授
国防科大王兵山主编数理逻辑教材,有点看着了,如果想考博可以下载。 逻辑和代数是计算机科学的两大理论基础。数理逻辑各个分支中的许多方面和计算机科学有着密切的联系。本书是作者在多年给硬士研究生讲授《数理...
数理逻辑命题逻辑等值演算
数理逻辑部分习题答案:内容包括命题逻辑、一阶逻辑、集合及其运算、等部分的定义、定理、习题与解答
用数学的方法研究关于推理、证明等问题的学科就叫做数理逻辑。也叫做符号逻辑。 数理逻辑的内容: 1、 命题逻辑系统 2、 一阶谓词逻辑系统 命题演算是研究关于命题如何通过一些逻辑连接词构成更复杂的命题以及逻辑...
数理逻辑是用数学方法研究思维规律的一门学科。...本章介绍数理逻辑中最基本的内容命题逻辑。首先引入命题、命题公式等概念。然后,在此基础上研究命题公式间的等值关系和蕴含关系,并给出推理规则,进行命题演绎。
数理逻辑答案 主要包括 命题、谓词、一阶等内容部分答案
希尔柏脱 阿克曼 数理逻辑基础 命题演算 类演算 狭义谓词演算 广义谓词演算
数理逻辑---讲的非常清楚: 形式系统,命题逻辑,谓词逻辑,归结原理, 还有递归论等内容.
离散数学 64讲 1-35讲 含第一二三四章全部 第五章代数系统 视频
离散数学课后答案 数理逻辑学习指导语习题解答
国内最为经典详实的数理逻辑教材。中国科学技术大学出版社1990年出版。包含命题逻辑、谓词逻辑、哥德尔不完备性定理等内容。 下载后可以通过Adobe PDF虚拟打印机打印成PDF文档。
内容提纲: 一、命题逻辑(Propositional Logic) 二、命题演算(Propositional Calculus)
第二章 经典命题逻辑 第三章 经典一阶逻辑 第四章 可靠性和完备性 第五章 公理推演系统 第六章 构造性逻辑 第七章 模态命题逻辑 第八章 模态一阶逻辑 附录 自然推演中形式证明的简明形式 参考文献 符号表 名词表
高级数理逻辑第三章:命题演算,及其在计算机中的应用
在数理逻辑中,要确保推理的正确性,首先应保证写出的前提条件是正确的.在将命题符号化时,逻辑联结词的正确使用最为关键.而其中最容易出错的是蕴涵联结词.本文对蕴涵联结词及其相关的一些符号进行了较为深刻的分析.
离散专业课 数字逻辑课件 专业详细版 由浅入深
数理逻辑的辅助小程序,可以给出任意命题公式的合取范式及析取范式。主要用二叉树实现。压缩包内有比较详细的说明文档
命题逻辑、一阶逻辑、形式证明、一阶语言的结构与真值理论。