文档介绍：离散数学
刘刚
北京邮电大学信息工程学院
简单回顾
等价关系
永真蕴含
对偶
代入
主析取范式(极小项之和)
主合取范式(极大项之积)
命题和联结词
命题公式分类
永真式
永假式
可满足式
判定问题
真值表方法
命题演算
范式
1-4 推理理论
数理逻辑的主要任务
形式逻辑
定义: 研究演绎推理及其规律的科学
研究对象:  形式逻辑研究推理中的前提和结论之间的关系
研究方法: 建立逻辑演算是形式逻辑的主要方法
数理逻辑 
用数学方法研究符号化、形式化的逻辑演绎规律的数学分支,是现代的形式逻辑
数理逻辑的主要任务: 用数学的方法来研究推理的规律
1-4 推理理论
一些基本概念
推理的方法
1-
推理和演绎(形式证明)
推理: 从若干命题(前提)直接得出一个命题(结论)的思维过程
推理分为:演绎推理与非演绎推理(归纳推理)两类
演绎(形式证明): 按照推理规则,从给定的前提出发,推导出结论
特点: 如果前提都为真,则结论必然真
演绎推理常常简称为推理,其前提与结论之间的联系反映了事物情况之间的必然联系。
前提
已知的命题公式
结论
从前提出发,应用推理规则推出的命题公式
1-
论证的合法性和有效性
论证的合法性:
前提正确、推理规则正确,则结论正确
论证的有效性:
不论前提是否正确、推理过程正确,论证有效
有效结论(或逻辑结论)
定义:若H1H2H3....HnC,则称C是命题公式H1,H2,H3.…Hn的有效结论。
特别地,AB称B是A的有效结论,记为:A├ B
论证的具体过程叫证明。
推理的形式结构: H1H2H3....Hn→C
1-
例1:如果天气凉,小王就不去游泳。天气凉。所以小王没去游泳。
P:天气凉; Q:小王去游泳
前提: P→┐Q; P
结论: ┐Q
推理的形式结构:
((P→┐Q)  P) →┐Q
1-
判断推理是否正确的问题
已知: 一个前提集合和一个结论
前例中的前提:(P→┐Q; P)
前例中的结论: ┐Q
问题: 以有限数目的步骤判断,由给定的前
提集合是否可以推导出该结论
即:判断由前提集合和结论构成的条件式是
否是永真蕴涵式
前例中的((P→┐Q)  P) →┐Q是否是永真式
1-
判断推理是否正确的2种方法:
转化为判定问题:
真值表法
命题演算法
范式法
基于推理规则方法
1-:转化为判定问题
例1的证明:
即证明((P→┐Q)  P) →┐Q是永真式
(1)真值表法:(真值表的最后一列全为1)
P
Q
┐Q
P→┐Q
(P→┐Q)  P
((P→┐Q)  P) →┐Q
0
0
1
1
0
1
0
1
0
1
0
1
1
0
1
1
1
1
1
1
0
0
0
1