数理逻辑举例

《数理逻辑》教案

许道云

(2011.8)

教 材：《面向计算机科学的数理逻辑》(第二版)

(陆钟万著)

出版社：科学出版社

版 本：2006年6月第8次印刷

绪言（课程介绍）

什么是逻辑？命题（判断）对象、以及对象间的（推理）关系。 数理逻辑：用数学的方法研究逻辑。

数理逻辑研究分支：模型论、集合论、递归论、证明论。 数理逻辑研究什么？

逻辑推理：当前提为真时，保证结论为真。

逻辑研究这样的可推理关系。即，前提和结论之间的推理关系是否正确。演绎推理---演绎逻辑。

它不同于归纳逻辑。归纳逻辑是从前提出发，使用归纳推理，得到的结论与自身协调，或与前提协调。

数理逻辑属于演绎逻辑范围。只研究推理及可推理关系，不关心前提与结论中各个命题的真假。

例1. 前提：所有大于2不被自身整除的自然数为素数。 7不被自身整除。 结论：7不是素数。 例2. 前提：所有中学生打网球。 王君不打网球。 结论：王君不是中学生。

命题有内容和形式：内容决定命题的真或假。决定前提和结论之间的可推导关系，是命题逻辑形式。如：

前提：集合S中的所有元素具有R性质。 a不具有R性质。

结论

数理逻辑部分

一、 填空题

1、将几个命题联结起来，形成一个复合命题的逻辑联结词主要有 、 、 、 和 。 2、命题公式G=（P?Q）?R，则G共有 个不同的解释；把G在其所有解释下所

取真值列成一个表，称为G的 ；解释（?P，Q，?R）或（0，1，0）使G的真值为 。 3、 已知命题公式G?(?P?Q)?R，则G的主析取范式是 。

4、 求公式?(P?Q)?(P?Q)的析取范式

合取范式是 。

5、 设命题公式G?P??(Q?R)，则使公式G为假的解释是 、 和

《数理逻辑》教案

许道云

(2011.8)

教 材：《面向计算机科学的数理逻辑》(第二版)

(陆钟万著)

出版社：科学出版社

版 本：2006年6月第8次印刷

绪言（课程介绍）

什么是逻辑？命题（判断）对象、以及对象间的（推理）关系。 数理逻辑：用数学的方法研究逻辑。

数理逻辑研究分支：模型论、集合论、递归论、证明论。 数理逻辑研究什么？

逻辑推理：当前提为真时，保证结论为真。

逻辑研究这样的可推理关系。即，前提和结论之间的推理关系是否正确。演绎推理---演绎逻辑。

它不同于归纳逻辑。归纳逻辑是从前提出发，使用归纳推理，得到的结论与自身协调，或与前提协调。

数理逻辑属于演绎逻辑范围。只研究推理及可推理关系，不关心前提与结论中各个命题的真假。

例1. 前提：所有大于2不被自身整除的自然数为素数。 7不被自身整除。 结论：7不是素数。 例2. 前提：所有中学生打网球。 王君不打网球。 结论：王君不是中学生。

命题有内容和形式：内容决定命题的真或假。决定前提和结论之间的可推导关系，是命题逻辑形式。如：

前提：集合S中的所有元素具有R性质。 a不具有R性质。

结论

数理逻辑部分

一、 填空题

1、将几个命题联结起来，形成一个复合命题的逻辑联结词主要有 、 、 、 和 。 2、命题公式G=（P?Q）?R，则G共有 个不同的解释；把G在其所有解释下所

取真值列成一个表，称为G的 ；解释（?P，Q，?R）或（0，1，0）使G的真值为 。 3、 已知命题公式G?(?P?Q)?R，则G的主析取范式是 。

4、 求公式?(P?Q)?(P?Q)的析取范式

合取范式是 。

5、 设命题公式G?P??(Q?R)，则使公式G为假的解释是 、 和

《数理逻辑》教案

许道云

(2011.8)

教 材：《面向计算机科学的数理逻辑》(第二版)

(陆钟万著)

出版社：科学出版社

版 本：2006年6月第8次印刷

绪言（课程介绍）

什么是逻辑？命题（判断）对象、以及对象间的（推理）关系。 数理逻辑：用数学的方法研究逻辑。

数理逻辑研究分支：模型论、集合论、递归论、证明论。 数理逻辑研究什么？

逻辑推理：当前提为真时，保证结论为真。

逻辑研究这样的可推理关系。即，前提和结论之间的推理关系是否正确。演绎推理---演绎逻辑。

它不同于归纳逻辑。归纳逻辑是从前提出发，使用归纳推理，得到的结论与自身协调，或与前提协调。

数理逻辑属于演绎逻辑范围。只研究推理及可推理关系，不关心前提与结论中各个命题的真假。

例1. 前提：所有大于2不被自身整除的自然数为素数。 7不被自身整除。 结论：7不是素数。 例2. 前提：所有中学生打网球。 王君不打网球。 结论：王君不是中学生。

命题有内容和形式：内容决定命题的真或假。决定前提和结论之间的可推导关系，是命题逻辑形式。如：

前提：集合S中的所有元素具有R性质。 a不具有R性质。

结论

1 离散数学期末复习题 2012-6-16

1.“太阳系以外的星球上有生命。”是命题。 （ T ） 2．?（???）=?（A）? ?（B） （ F ）

?（?∩?）=?（A）∩?（B） （ T ） 3．一个命题的合取范式不是唯一的。 （ T ） 4．等价式?（?x）A（x）?（?x）?A（x）成立。 ( T ) 5．（?x）（P（x）?Q（x））? R（x）是命题。 （ F ）

8．对于一个谓词公式，指定不同的个体域，则其真值不一定相同.T 9. 若命题公式A的主析取范式包含全部的极小项，则A为永真式T 10．命题“他在教室看书或在宿舍看书。”可以符号化为P∨ S。F 11．当个体域S=｛a,b,c｝消去公式(?x) P(x)∨(?x)Q(x)中量词为(P(a)∨Q(a)) ∧ (P(b)) ∨Q(b)) ∧ (P(c)∨Q(c)) F

12. 设P、Q是两个命题，当且仅当P、Q的真值均相同时，P ?

1 离散数学期末复习题 2012-6-16

1.“太阳系以外的星球上有生命。”是命题。 （ T ） 2．?（???）=?（A）? ?（B） （ F ）

?（?∩?）=?（A）∩?（B） （ T ） 3．一个命题的合取范式不是唯一的。 （ T ） 4．等价式?（?x）A（x）?（?x）?A（x）成立。 ( T ) 5．（?x）（P（x）?Q（x））? R（x）是命题。 （ F ）

8．对于一个谓词公式，指定不同的个体域，则其真值不一定相同.T 9. 若命题公式A的主析取范式包含全部的极小项，则A为永真式T 10．命题“他在教室看书或在宿舍看书。”可以符号化为P∨ S。F 11．当个体域S=｛a,b,c｝消去公式(?x) P(x)∨(?x)Q(x)中量词为(P(a)∨Q(a)) ∧ (P(b)) ∨Q(b)) ∧ (P(c)∨Q(c)) F

12. 设P、Q是两个命题，当且仅当P、Q的真值均相同时，P ?

专题二 数理逻辑用语

一、考纲要求：

了解命题的概念常用的逻辑联结词（且、或、非、如果 那么 ）。理解充要条件的含义。

二、复习指导：

数理逻辑用语的知识可以培养学生具有逻辑思维推理、判断能力。涉及这个知识的试题，范围很广，可以是方程、函数、不等式、数列、向量、解析几何等各种数学知识。

数理逻辑用语与集合的知识一样，以容易题为主，题型是选择题和填空题，每年一至二题；在复习过程中要注意三类题型：一是命题的判断；二是判断充分（必要、充要）条件；二是求命题的充分（必要、充要）条件；注意归纳求充分（必要）条件的方法。

三、知识归纳：

1.命题的概念与判断；2.命题的真假判断（或、且、非）；3.充分必要条件判断

四、历届高考题：

（2008 年）14、x R,"x 3"是"|x| 3"的

A.充分必要条件 B .充分不必要条件 C .既不必要也不充分条件 D .必要不充分条件 （2006 年7） 设G和F是两个集合，则“G中的元素都在F中”是“G=F”的（ ）

A 充分条件 B 充要条件 C 必要条件 D 既非充分又非必要条件 （2005年 13） “b2－4ac>0”是方程ax2

课程名称：数理逻辑 （英文名称：Mathematical Logic）

一、课程目的、任务：学习数理逻辑的基本理论，为进一步学习现代西方哲学和逻辑哲学打下基础。

二、课程内容：介绍数理逻辑的基础知识，包括：命题演算和狭谓词演算的构成，定理的推演，范式，语义解释，公理系统的三种一致性和三种完全性，公理的独立性，命题演算和狭谓词演算的一致性和完全性定理，以及判定问题。

三、教学方式、实践环节的特色：注重基本概念和基本方法的讲解，通过课堂教学和课外作业，使学生较扎实地掌握数理逻辑的基础知识。 四、教材及参考书目：

教材：王宪钧著《数理逻辑引论》，北京大学出版社，1998年版。 参考书目：彭漪涟主编《逻辑学导论》，华东师范大学出版社，2000年版。 五、考核方式与评价结构比例：

平时成绩占40％，按照每次课后布置的课外作业来评定。期末闭卷考试，考试成绩占60％。 六、讲授大纲：（两级目录）

序言

第一篇 命题逻辑

第一章 真值联结词 真值函项 重言式 第一节 复合命题 复合命题的真假

第二节 真值联结词 真值形式 第三节 五个基本真值联结词 第四节 命题形式 第五节 真值表方法

第六节 真值函项 重言的真值函

第一篇 数理逻辑

数理逻辑是应用数学方法引进一套符号系统来研究思维的形式结构和规律的学科，它起源于公元十七世纪。十九世纪英国的德·摩根和乔治·布尔发展了逻辑代数，二十世纪三十年代数理逻辑进入了成熟时期，基本内容（命题逻辑和谓词逻辑）有了明确的理论基础，成为数学的一个重要分支，同时也是电子元件设计和性质分析的工具。冯·诺意曼，图灵，克林，? 等人研究了逻辑与计算的关系。基于理论研究和实践，随着1946年第一台通用电子数字计算机的诞生和近代科学的发展，计算技术中提出了大量的逻辑问题，逻辑程序设计语言的研制，更促进了数理逻辑的发展。除古典二值（真，假）逻辑外，还研究了多值逻辑、模态逻辑、概率逻辑、模糊逻辑、非单调逻辑等。不仅有演绎逻辑，也还有归纳逻辑。计算机科学中还专门研究计算逻辑、程序逻辑、时序逻辑等。现代数理逻辑分为四论：证明论，递归论（它们与形式语言语法有关），模型论，公理化集合论（它们与形式语言的语义有关）。

第1-1章 命题逻辑

学习要求: 掌握命题，命题公式，重言式，等价式，蕴涵式等基本概念，能利用逻辑联结词或真值表，等价式与蕴涵式进行命题演算和推理；学习范式时与集合的范式进行对比。

表述客观世界的各种现象，表述人们的思想，表