数理逻辑的一项重要任务是回答“什么是证明?” 并试图将“证明”这一概念(与之相关有可计算性概念)精确化。基于这个目的,数理逻辑需要设计适当的语言用于对计算机科学领域中遇到的情景建模,以便于对它们作形式推理,得到我们想要的结论。
为了将证明精确化,所用的方法是什么呢?数理逻辑在研究推理时要建立数学模型(我们称这个数学模型为形式系统)ß对形式系统进行研究,必须用普通的自然语言(元语言)ß研究推理时不可避免要用到逻辑ß逻辑是由演算组成的ß在进行推理时需要用到精确的演算规则ß推理过程中所使用的语言必须无二义性,以便于构造有效的推理论证。
在计算机应用中,这就要求我们构造的论证必须是有效的且能在计算机上执行。因此,为了达到这样的目的,通常的方法是引进一种符号语言,它能够精确表达其意义。
先来看第一个例子:
例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)
为此,对于上述联结符约定邦定的优先级:
﹁ 优先于∨和∧, ∨和∧优先于→。
→是右结合的。
很熟悉是不是,仿佛回到了遥远的高中。
这一节比较简单,下一节我们说自然演算。
相关推荐
### 数理逻辑之命题逻辑知识点详解 #### 一、数理逻辑概述 数理逻辑是逻辑学的一个分支,它利用数学方法研究思维规律。数理逻辑的特点在于它使用一套符号系统来简洁地表达各种推理的逻辑关系,因此也被称为符号...
从给定的文件中,我们可以提炼出数理逻辑中的几个关键知识点,尤其是关于命题逻辑的基础概念和应用。 ### 命题逻辑基本概念 在数理逻辑中,命题逻辑是最基础的部分,它关注的是命题的真假值及其逻辑关系。命题是...
数理逻辑的研究范围非常广泛,包括命题逻辑、一阶谓词逻辑、高阶逻辑、证明理论、模型论、递归论和集合论等。通过研究这些领域,数学家和逻辑学家们尝试揭示数学理论中的基本结构,以及这些结构如何影响我们对数学...
3. **第一章 数理逻辑**:这一章深入探讨了命题逻辑,包括命题的定义、真值表、逻辑等值(如德摩根定律、分配律等)、命题公式及其简化方法,以及逻辑推理规则(如蕴涵引理、零蕴涵引理等)。 4. **第二章**:虽然...
离散数学是计算机学科的经典核心基础课程。课程内容主要包括集合论,数理逻辑,关系...离散数学 教学课件(配方世昌《离散数学(第三版)》) 第1章 数理逻辑(命题逻辑部分)文档作者:中南大学计算机学院 郑瑾副教授
最后,虽然不是数理逻辑的直接部分,但计算复杂性理论与之密切相关。这个领域的习题通常涉及计算问题的分类,比如P、NP、NPC类问题,以及算法的时间和空间复杂性分析。 通过这两份习题解答,学生不仅可以检验自己对...
数理逻辑的核心概念包括命题逻辑、谓词逻辑、模态逻辑等。命题逻辑是逻辑的基础,处理的是简单命题的真假关系和复合命题的构造。在计算机科学中,命题逻辑用于验证程序的正确性,比如布尔代数在电路设计中的应用。...
国防科大王兵山主编数理逻辑教材,有点看着了,如果想考博可以下载。 逻辑和代数是计算机科学的两大理论基础。数理逻辑各个分支中的许多方面和计算机科学有着密切的联系。本书是作者在多年给硬士研究生讲授《数理...
计算机科学的基础之一是数字电路的布尔代数,而布尔代数正是数理逻辑的一个分支。此外,计算机程序设计语言、编译方法、人工智能、知识库和关系数据库等领域,都深受数理逻辑的影响。数理逻辑的理论在计算机科学中...
哈工大的数理逻辑课程可能涵盖了命题逻辑、一阶逻辑、模型论、证明论和计算理论等核心主题。课后答案对于学习者来说是一个宝贵的资源,能够帮助他们检查自己的理解,加深对概念的掌握。 在提供的压缩包文件"9705...
这种处理方式类似于代数中的方程理论,即通过一套系统化的方法来验证逻辑命题的真假。 - **希尔伯特纲领**:大卫·希尔伯特提出了一个著名的纲领,旨在为数学建立坚实的基础。他的目标之一是希望通过有限的过程证明...
1. **命题逻辑**:这是数理逻辑的基础,涉及命题、联接词(如与、或、非)、蕴含和等价关系。通过学习命题逻辑,我们可以理解和构造逻辑推理的基本步骤,这对于程序设计和验证至关重要。 2. **谓词逻辑**:相比于...
- **数理逻辑**:作为计算机科学的重要基础之一,数理逻辑要求学生能够将日常生活中的逻辑条件转化为数学公式,并进行有效的推理。这对于程序设计等后续课程的学习至关重要。 - **集合论**:被视为数学的基石之一,...
数理逻辑是数学的一个分支,它研究的是逻辑系统的数学性质,包括但不限于命题逻辑、谓词逻辑、模型论、递归论、证明论等。这些理论不仅对于理解数学本身非常重要,同时也是计算机科学、人工智能等领域不可或缺的基础...
数理逻辑命题逻辑等值演算
1. **命题逻辑**:这是数理逻辑的起点,涉及基本的逻辑联接词(如与、或、非),命题的真值表,以及蕴含和等价关系。学生会学习如何通过推理规则进行命题证明,理解量词(全称量词和存在量词)的概念。 2. **一阶...
1. **命题逻辑**:这是数理逻辑的起点,涉及到简单的真值命题和逻辑运算。例如,学习如何使用逻辑联接词构造复合命题,并理解真值表的概念,用于确定命题的真假。 2. **一阶逻辑(一阶谓词逻辑)**:比命题逻辑更...
在数理逻辑中,命题逻辑是最基础的内容,它主要关注命题、命题公式以及它们之间的关系。 1.1 命题和命题联结词 命题是能够判断真假的陈述句。例如,"空气是人生存所必需的"、"南京是中国的首都"等是命题,它们可以...