数理逻辑绪论

1、数理逻辑Mathematical Logic 王书元 讲师e-mail: wsy_生物数学教研室（外语学馆411）绪 论课程之间的联系 离散数学是计算机科学的核心基础课程，它以离散量为研究对象；而数学分析（微积分）以连续函数为主要研究对象，属于连续型数学。 离散数学在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学的理论、方法直接为数据结构、操作系统、编译原理、人工智能、程序设计等课程服务。课程之间的联系离散数学数理逻辑集合论图论代数结构组合数学课程之间的联系什么是数理逻辑？ 逻辑通常指人们思考问题，从某些已知条件出发推出合理的结论的规律。 逻辑学是一门研究思维形式及思维规律

2、的科学。以推理形式为主要研究对象。现代的逻辑学与数学有非常密切的关系。逻辑学现代逻辑古典逻辑传统逻辑数理逻辑什么是数理逻辑？传统逻辑的局限：1. 讨论范围限于主宾式语句，即“S是P” 式的语句。2. 对量词的研究非常有限，只能得出量 词的一些次要性质。3. 表达形式停留在自然语言上，没有专 门的逻辑符号来处理各类思维形式， 所以不够精确。什么是数理逻辑？数理逻辑就是采用数学的方法来研究思维形式的逻辑结构及其规律的一门科学。所谓数学的方法就是用一套符号（即人工符号语言）的方法。什么是数理逻辑？数理逻辑与传统逻辑的区别：1. 使用一整套符号语言，从而简化了推理形式。2. 借助人工符号语言，使整个推

3、理形式化。3. 具有系统性。什么是数理逻辑？数理逻辑的历史 数理逻辑的创始人是17世纪德国数学家和哲学家莱布尼兹，他把数学引入形式逻辑。1847年布尔实现了命题演算，1879年弗雷格建立了第一个谓词演算系统。对建立这门学科做出贡献的，还有美国人皮尔斯，他也在著作中引入了逻辑符号。从而使现代数理逻辑最基本的理论基础逐步形成，成为一门独立的学科。人物简介n莱布尼兹q（Gottfried Wilhelm Leibniz，1646年7月1日1716年11月14日）德意志哲学家、数学家，历史上少见的通才，被誉为17世纪的亚里士多德。q莱布尼兹曾在汉诺威生活和工作了近四十年，为了纪念他和他的学术成就，20

4、06年7月1日，也就是莱布尼兹360周年诞辰之际，汉诺威大学正式改名为汉诺威莱布尼兹大学。人物简介q1646年7月1日莱布尼兹出生于神圣罗马帝国的莱比锡。q他的著书约四成为拉丁文、约三成为法文、约一成五为德文。q现今在微积分领域使用的符号仍是莱布尼兹所提出的。在高等数学和数学分析领域，莱布尼兹判别法是用来判别交错级数的收敛性的。q拓扑学、符号思维、单子论、数理逻辑。q1716年11月14日莱布尼兹于汉诺威孤独地过世。直到去世前几个月，才写完一份关于中国人宗教思想的手稿：论中国人的自然神学。学习数理逻辑要达到的目的首先，培养严谨的逻辑推理能力。其次，培养抽象思维能力。再者，培养解决实际问题的能力

5、。本课程主要内容第一章 逻辑、集合和函数命题逻辑命题逻辑、谓词逻辑谓词逻辑、逻辑等价逻辑等价、集合、集合运算、函数、函数增长函数增长等第二章 算法、整数和矩阵算法算法、搜索算法搜索算法、算法的复杂性算法的复杂性、整数和除法（素数、最大公约数、最小公倍数、模运算等）、整数和算法、矩阵第三章 数学推理证明方法证明方法、数学归纳法数学归纳法、递归算法递归算法等第四章 关系关系及其性质关系及其性质、n元关系及应用元关系及应用、关系的表示关系的表示数理逻辑Mathematical Logic 第一章 逻辑、集合和函数Chapter 1 Logic、set and function逻辑：是所有数学推理的基

6、础，逻辑规则给出数学语句的准确含义。集合：所有离散结构都从集合构造而来。如，表示对象之间相互关联的关系（有序偶的集合），图（顶点的集合、边的集合）等。函数：离散数学中特别重要的概念。如，函数增长、递归函数等。1.1 命题逻辑Propositional Logic命题是一个非真即假（不可兼）的陈述句。 一、命题命题是一个陈述句，祈使句、疑问句和感叹句都不是命题。所表述的内容可决定是真还是假，不能不真又不假，也不能又真又假。 具有两种可能的取值（又称真值），为真或为假，并且只能取其一。 通常用T（True）表示真值为真，用F（False）表示真值为假，有时也用1和0来表示。 因为只有两种取值，所以

7、这样的命题逻辑称为二值逻辑。 一、命题下列语句哪些是命题：华盛顿是美国的首都。1+1=3。好大的雪啊！雪是白的。我学英语，或者我学日语。 一、命题下列语句哪些是命题：几点了？如果刘翔脚没伤，那么他能在奥运会上打破世界纪录。全体起立！ x+1=3. 一、命题下列语句哪些是命题：今天是星期一。严格地说，含有可变时间、地点、人物的语句不是命题，除非假定了一个确定的时间、地点、人物。 一、命题命题表示法：命题常用字母表示，就像用字母表示变量那样。习惯上用来表示命题的字母是p、q、r、s 一、命题简单命题和复合命题：简单命题又称原子命题，不能分解成更简单的命题。如，今天是星期一并且有数理逻辑课。可分解为

8、：今天是星期一。今天有数理逻辑课。复合命题又称分子命题，由原子命题用逻辑运算符组合起来的命题。 一、命题逻辑运算符也称为联结词，它是复合命题中的重要组成部分，体现了复合命题中各个原子命题之间的运算关系，为了便于书写和推演，必须对联结词做出明确的规定并符号化。二、命题联结词及真值表否定（定义）：令p为一命题，则语句“不是p所说的情形。”是另一个命题，称为p的否定。用p表示，读作“非p”。二、命题联结词及真值表否定（例题）：p：今天是星期一。p：今天不是星期一。不能说今天星期二、星期三等。p：昨天张三看球赛了。p：昨天张三没有去看球赛。二、命题联结词及真值表否定（真值表）：ppTFFT二、命题联结

9、词及真值表合取（定义）：令p和q为命题，用pq表示的命题“p而且q”是这样的一个命题：当p和q均为真时它成真，否则为假。命题pq称为p和q的合取。二、命题联结词及真值表合取（例题）：p：今天是星期一。q：今天有数理逻辑课。pq：今天是星期一并且有数理逻辑课。p：1+1=2。 q：雪是白的。pq：1+1=2并且雪是白的。逻辑语言中仅考虑命题与命题之间的形式关系，并不顾及自然语言中是否有此说法。二、命题联结词及真值表合取（真值表）：pqpqTTTTFFFTFFFF二、命题联结词及真值表析取（定义）：令p和q为命题，用pq表示的命题“p或q”是这样的一个命题：它的真值在p和q均为假时为假，否则成真。

10、命题pq称为p和q的析取。二、命题联结词及真值表析取（例题）：选修过微积分或计算机科学的学生可以选修本课程。同或 异或他现在在301房间或302房间。二、命题联结词及真值表析取（真值表）：pqpqTTTTFTFTTFFF二、命题联结词及真值表异或（定义）：令p和q为命题，p和q的异或，用 表示，是这样的一个命题：当p和q中恰有一个成真时它成真，否则它为假。pq二、命题联结词及真值表异或（真值表）：pqTTFTFTFTTFFFpq二、命题联结词及真值表蕴含（定义）：令p和q为命题，蕴含pq是这样一个命题：在p成真而q为假时它为假，否则成真。其中p称为假设（前项、前提），q称为结论（或后果）。二、

11、命题联结词及真值表蕴含（例题）：p：n3（n是整数）。q：n29。pq：如果n3，那么n29。p：刘翔的脚没有受伤。q：刘翔在奥运会上打破了世界纪录。pq：如果刘翔的脚没有受伤，那么刘翔在奥运会上打破了世界纪录。二、命题联结词及真值表蕴含（真值表）：pqpqTTTTFFFTTFFT二、命题联结词及真值表蕴含（术语）：“如果p，那么q”“p是q的充分条件”“ p蕴含q” “q如果p”“如果p，q” “q每当p”“p仅当q” “q是p的必要条件”二、命题联结词及真值表蕴含：逆蕴含：命题qp称为pq的逆蕴含。逆否命题（倒置命题）： pq的逆否命题是命题qp二、命题联结词及真值表双蕴含（定义）：令p和q为命题，双蕴含 是这样一个命题：其真值只有在p和q有同样真值时为真，否则为假。双蕴含恰在pq和qp均为真时为真。pq二、命题联结词及真值表双蕴含：“p当且仅当q”“p是q的充分必要条件”“如果p，那么q；反之亦然。”二、命题联结词及真值表双蕴含（真值表）：pqTTTTFFFTFFFTpq二、命题联结词及真值表运算顺序： 、 pq(p)q二、