第一部分 数理逻辑.ppt

第一部分 数理逻辑.ppt1
离散数学
面向21世纪课程教材
高等教育出版社
耿素云屈婉玲编著
2
离散数学是研究离散量的结构及其相互关系的数学学科,是现代数学的一个重要分支。它在各学科领域,特别在计算机科学与技术领域有着广泛的应用。
学****离散数学的目的在于培养学生的抽象推理、逻辑思维和归拉构造等能力,提高学生利用数学方法解决问题的技能,以及为后续课程作必要的准备,为学生的进一步学****奠定计算机数学的基础。它所涉及的概念、方法和理论,大量地应用在数字电路,编译原理,数据结构,操作系统,数据库,算法等。
3
第一部分数理逻辑
第二部分集合论
第三部分代数结构
第四部分图论
4
第一章命题逻辑基本概念
第二章命题逻辑等值演算
第三章命题逻辑的推理理论
第四章一阶逻辑基本概念
第五章一阶逻辑等值演算与推理
第一部分数理逻辑
5
命题与联结词
一、基本概念
命题:能够判断真假的陈述句。
陈述句
能够判断真假
真值:命题的真假,只取两个值:真1假0。
例如:
4是素数。
x大于y。
2009年元旦是晴天。
请不要吸烟!
我正在说假话。
(是命题)
(不是命题)
(是命题)
(不是命题)
(不是命题,“悖论”)
6
二、命题的表示
符号化:本书中,命题通常用小写字母或带下标的小写字母表示。完全由符号构成的语言为形式语言。
例如:
p:4是素数。
q: 是无理数。
r1:我是一名大学生。
7
三、原子命题与命题联结词
原子命题(简单命题):不能被分解为更简单的陈述句的命题。
例如:
(1)2和3是素数。
(2)6或8是素数。
复合命题:由原子命题通过联结词联结而成的命题。
常用命题联结词:
8
否定联结词﹁: ﹁p为真 iff p为假
P
﹁P
0
1
1
0
p
q
p∧ q
0
0
0
0
1
0
1
0
0
1
1
1
合取联结词∧: p∧ q为真 iff p、q 同时为真
例:
p:我是大学生。
﹁p:我不是大学生。
例:
p:张林是大学生。
q:李响是大学生。
p∧ q:张林和李响都是大学生。
(两点注意如书P3页)
9
p
q
p ∨ q
0
0
0
0
1
1
1
0
1
1
1
1
析取联结词∨:p ∨ q为假 iff p、q全为假
注:“相容或”和“排斥或”
:
(1)张晓静爱唱歌或爱听音乐。
(2)张晓静是江西人或安徽人。
(3)张晓静只能挑选202或203房间。
10
p
q
p → q
0
0
1
0
1
1
1
0
0
1
1
1
蕴涵联结词→: p → q为假 iff p为真q为假
q → p
0
1
注1:“只要p,就q”、”因为p,所以q”、”只有q才p”、”除非q才p”、”除非q,否则非p”;
注2:p和q可以无任何关系。(形式蕴涵,实质蕴涵)
注3:蕴涵式前件为假时,蕴涵式为真
p:蕴涵式的前件
q:蕴涵式的后件