命题逻辑的推理理论.pptx

离散数学
主要内容
推理的形式结构
推理的正确与错误
推理的形式结构
判断推理正确的方法
推理定律
自然推理系统P
形式系统的定义与分类
自然推理系统P
在P中构造证明:直接证明法、附加前提证明法、归谬法
第三章 命题逻辑的推理理论
2
推理的形式结构
设A1, A2, …, Ak, B为命题公式. 若对于每组赋值，
A1A2… Ak 为假，或当A1A2…Ak为真时，B也为真，
则称由前提A1, A2, …, Ak推出结论B的推理是有效的或正确
的, 并称B是有效结论.
由命题公式A1, A2, …, Ak 推B的推理正确当且仅当
A1A2…AkB为重言式
注意: 推理正确不能保证结论一定正确
3
P Q的
真值表？
推理的形式结构
2. A1A2…AkB
若推理正确, 记为A1  A2  …  Ak  B
3. 前提： A1, A2, … , Ak
结论： B
判断推理是否正确的方法:
真值表法
等值演算法
主析取范式法
4
P  Q、P  Q、P  Q、
P  Q的区别？
推理实例
例1 判断下面推理是否正确
(1) 若今天是1号，则明天星期五. 今天是1号. 所以, 明天星期五.
(2) 若今天是1号，则明天星期五. 明天星期五. 所以, 今天是1号.
解 设 p：今天是1号，q：明天星期五.
(1) 推理的形式结构:
(pq)pq
用等值演算法
(pq)pq
 ((pq)p)q
 pqq  1

5
推理实例
(2) 推理的形式结构:
(pq)qp
用主析取范式法
(pq)qp
 (pq)qp
  ((pq)q)p
 qp
 (pq)(pq) (pq)(pq)
 m0m2m3
结果不含m1, 故01是成假赋值，所以推理不正确
6
推理定律——重言蕴涵式
1. A  (AB) 附加律
2. (AB)  A 化简律
3. (AB)A  B 假言推理
4. (AB)B  A 拒取式
5. (AB)B  A 析取三段论
6. (AB)(BC)  (AC) 假言三段论
7. (AB)(BC)  (AC) 等价三段论
8. (AB)(CD)(AC)  (BD) 构造性二难
(AB)(AB)  B 构造性二难(特殊形式)
9. (AB)(CD)( BD)  (AC) 破坏性二难
每个等值式可产生两个推理定律
如, 由AA可产生 AA 和 AA
7
自然推理系统P
一个形式系统 I 由下面四个部分组成：
(1) 非空的字母表，记作 A(I).
(2) A(I) 中符号构造的合式公式集，记作 E(I).
(3) E(I) 中一些特殊的公式组成的公理集，记作 AX(I).
(4) 推理规则集，记作 R(I).
记I=<A(I),E(I),AX(I),R(I)>, 其中<A(I),E(I),AX(I),R(I)>是 I 的
形式语言系统, <A(I),E(I),AX(I),R(I)> 是 I 的形