离散-1-5-命题逻辑(1).ppt

主要内容:
§ 推理理论
推理规则
常用推理方法
直接证法
附加前提证法
反证法
应用:逻辑电路设计
1
实例:
下午小王去看电影或去游泳。他没去看电影,所以他去游泳了。
解: 设 P:小王下午去看电影;
Q:小王下午去游泳;
前提: P ∨ Q,┐P;
结论: Q;
推理形式: (P ∨ Q) ┐P  Q
2
实例2:
在《四签名》开头,谈到逻辑推理时认为,即令一件日常用品,也可以根据找到的痕迹推出使用者的特征,于是华生拿出一只旧怀表,让福尔摩斯推断,我们看作者的一联串推理:表背面刻写姓名缩写, 表系五十年前制造, 表背刻字与制表时间相近推出其父为表的主人;已知其父已去世多年,又根据背景知识:珠宝一类多传给长子、又推出表后归其兄所有;表价值贵重推出其兄所获遗产丰厚;然而表背有无数划痕, 推出其兄生话不检点;表四次送去典当推出其兄景况常潦倒;当而能换回推出有时景况很好;表钥匙孔伤痕累累推出其兄酗酒,生活不检点。
这类推理属条件推理,知道前件,推出后件,
3
§ 推理理论
推理(也称论证):由已知命题得到新的命题的思维过程.
逻辑学中,把从前题(公理或假设)出发,依据公认的推理规则,推导出结论,
这一过程称为有效推理或形式证明, 所得结论叫做有效结论.
关心的不是结论的真实性, 而是推理的有效性。
数理逻辑中,注重的是研究用来从前提导出结论的推理规则和论证原理,
与这些规则和原理有关的理论称为推理理论。
如果 H1H2 …HnC, 则称C是一组前提H1,H2,…,Hn的有效结论,
或称C是从前提H1,H2,…,Hn逻辑推出的结论。
§ 推理理论
B称为推理规则的结论。
常用演绎证明方法: 直接证法、附加前提法和反证法。
在数理逻辑中,从前提推导出结论,要依据事先提供的公认的推理规则。
推理规则:
规则P(前提引入规则): 在推导的任何步骤上都可引入前提。
规则T(结论引入规则): 在推导的任何步骤上所得到的结论都可在
其后的任何步骤中引入使用。
由基本蕴涵式/基本恒等式得出推理规则»
当且仅当 A1∧A2∧…∧An  B 时,称
5
§ 推理理论
直接证法: 从前提(一组命题公式)出发,应用推理规则(蕴涵式恒等式),
推导出结论(一个公式).
例1 证明下列推理有效:如果今天下大雨,则这里难通行;如果这里难通行,
则他们不能准时达到。他们准时达到,所以今天没下大雨。
证明:设 P: 今天下大雨. Q: 这里难通行. R: 他们准时达到.
(P→Q)∧(Q→┐R)∧R ┐P
证法1:
P→Q 前提
Q→┐R 前提
P→┐R (1)(2)假言三段论
R 前提
┐P (3)(4)拒取式
»
证法2:
P→Q 前提
Q→┐R 前提
R 前提
┐Q (2)(3)拒取式
┐P (1)(4)拒取式
6
§ 推理理论 (CP规则)
如果欲推出的结论为条件式R→C时,只需将其前件R加入到前提中,
作为附加前提,再去推出后件C即可。
要证 A1∧A2∧…∧An  A→B, 只需证 A1∧A2∧…∧An∧A  B
∵(A1∧A2∧…∧An)→(A→B) ┐(A1∧A2∧…∧An)∨(┐A∨B)
┐(A1∧A2∧…∧An∧A)∨B (A1∧A2∧…∧An∧A)→B
例2:证明:P→(Q∨R), Q→┐P, S→┐R  P→┐S
P 附加前提
P→(Q∨R) 前提
Q∨R (1)(2)假言推论
Q→┐P 前提
┐Q (1)(4)拒取式
»
(6) R (3)(5)析取三段论
(7) S→┐R 前提
(8) ┐S (6)(7)拒取式
(9) P→┐S CP规则
7
§ 推理理论 (归谬法)
把结论的否定作为附加前提,与给定前提一起推证,若能引出矛盾,
则说明结论是有效的。
要证 A1∧A2∧…∧AnB,只需证A1∧A2∧…∧An∧┐B是永假式。
»蕴涵式
»恒等式
{A1,A2,…,An,┐B}不相容
例3:用反证法证明例1的(P→Q)∧(Q→┐R)∧R ┐P。
证明:(1) ┐(┐P) 附加前提
(2) P (1)双重否定律
(3) (P→Q) 前提
(4) Q (2)(3)假言推论
(5) (Q→┐R) 前提
(6) ┐R (4)(5)假言推论
(7) R 前提
(8) R∧┐R (6)(7)
8
应用: 逻辑电路设计(1)
。
命题变元--- 二值器件,如开关,电灯,电子管、晶体管等
┐--- 非门、