文档介绍：1
离散数学
Discrete Mathematics
曾庆田
Email:qtzeng@
山东科技大学
信息科学与工程学院
二零一零年三月
2
上次课内容回顾
析取范式
主析取范式
合取范式
主合取范式
小项
大项
第一章 第5讲§1—8 推理理论
在数学和其它自然科学中,经常要考虑从某些前提A1,A2,…,An能够推导出什么结论。
例如:
从分子学说,原子学说,能够得到什么结论;
从光的波动学说,能得到什么结论。
我们一般地要对“假设”的内容作深入分析,并推究其间的关系,从而得到结论。
但也有一些推理,只需分析假设中的真值和联结词,便可获得结论。
在数理逻辑中,集中注意的是研究和提供用来从前提导出结论的推理规则和论证原理,这些规则有关的理论称为推理理论。
在实际应用的推理中,我们常常把本门学科的一些定律、定理和条件,作为假设前提,尽管这些前提在数理逻辑中实非永真,但在推理过程中,却总是假设这些命题为T,并使用一些公认的规则,得到另外的命题,形成结论,这种过程就是论证。
注意,必须把推理的有效性和结论的真实性区别开。
一、有效结论
1. 定义
定义1- 设A和C是两个命题公式,当且仅当A→C为一重言式,即A C,称C是A的有效结论。或C可由A逻辑地推出。
3 . 论证过程
判别有效结论的过程就是论证过程。
2. 推广
有效结论定义可以推广到有n个前提的情况。
设H1,H2,……,Hn,C是命题公式,当且仅当
H1∧H2∧…∧Hn C (A)
称C是一组前提H1,H2,……,Hn的有效结论。
二、证明方法
1. 真值表法
2. 直接证法
3. 间接证法
7
二、证明方法
1. 真值表法
2. 直接证法
3. 间接证法
1. 真值表法
设P1,P2,…,Pn是出现于前提H1,H2,…,Hn和结论C中的全部命题变元,假定对P1,P2,…,Pn作了全部的真值指派,这样就能对应地确定H1,H2,…,Hn和C的所有真值,列出这个真值表,即可看出(A)式是否成立。
H1,H2,…,Hn真值均为T的行,对于每一个这样的行,若C也有真值T,则(A)式成立;
或者看C的真值为F的行,在每一个这样的行中,H1,H2,…,Hn的真值至少有一个为F,则(A)式也成立。
例题1 一份统计表格的错误或者是由于材料不可靠,或者是由于计算有错误;这份统计表格的错误不是由于材料不可靠,所以这份统计表格是由于计算有错误。
解设各命题变元为
P:统计表格的错误是由于材料不可靠。
Q:统计表格的错误是由于计算有错误。
本例可译为:Q是前提P∨Q,┐P的有效结论,即
┐P∧(P∨Q) Q
我们列出真值表1-
P
Q
P∨Q
┐P
T
T
T
F
T
F
T
F
F
T
T
T
F
F
F
T
从表上看到只有在第三行P∨Q和┐P的真值都为T,这时Q的真值亦为T。故(P∨Q)∧(┐P) Q 成立。
或者考察Q的真值为F的情况,在第二行和第四行,其相应的P∨Q或┐P中至少有一真值为F,故亦说明(P∨Q)∧(┐P) Q成立。