重言式——推理规则
6/66
三段论
已知的一般原理
P Q P
大前提 小前提
所研究的特殊情况
Q
结 论
对特殊情况作 出判断
三段论推理的有效性由永真公式： ((PQ)P)Q 所保证。
7/66
前提和结论间具有可推导性的形式关系
大前提：如果 1+1=3，则雪是黑的。
小前提：1+1=3。
结 论 ：雪是黑的。
3条公理模式 分离规则 15条公理 代入规则, 分 离规则
离散数学
11/70 11/66
2.1 命题演算的公理系统
给出若干条永真公式(称为公理)，
再给出若干条由永真公式推出永真公式 的推理规则， 由它们出发推出一切永真公式。
要求：了解公理系统的构成规则和推理形式。
12/66
公理系统的组成部分
A1，A2, A3, …，An=B，
把待证明的公式结论变成永真蕴涵式的后件 ，再证明前件永真，最后利用分离规则得到 结论。
20/66
定理1(p20) ├
从前提出发，通过推导即“演绎”，得出 结论的过程。前提和结论之间有可推导性 关系：前提的真蕴涵结论的真。
•归纳推理（科学家使用） 从真的前提出发，得到的结论只能够要求 它与前提是协调的，但不一定是真的。
• 溯因推理（侦探使用） 生成假设来解释观察或结论。
2/66
第二章 命题演算的推理理论
例 判断下面两个推理是否正确: (1) 如果今天是星期二, 今天有数学课。 今天是星期二， 所以今天有数学课。
一、语法部分 ㈠ 基本符号
公理系统所允许出现的全体符号的集合
㈡ 公理
㈢ 规则
二、语义部分
13/66
㈠基本符号
命题变元 联结词 括号 合式公式 推出符 ┣ P，Q，R，…… , , , , (， )
14/66
㈡ 公理
公理1 PP 公理2 (P(QR))(Q(PR)) 调头
该推理过程正确, 但不意味着前提 与结论正确
8/66
莫绍揆教授（1917.8-2011.4）
数理逻辑教育和研究的开拓 者之一。编著有： 《数理逻辑导论》 《递归数论》 《递归论》 《算法论》 • 1939年毕业于中央大学教学系 • 1948年，瑞士苏黎世高级工业大学留学，师从 希尔伯特的继承人贝尔奈斯 • 1950年4月回国，任职南京大学，创建数理逻 辑专业
((PQ)P)Q
4/66
从真值表看推理是否正确：
P T T F F Q T F T F ((PQ)P)Q T T T T ((PQ)P)Q T T F T
永真公式 三段论
非永真
5/66
有效推理
若有重言式
(A1 A2 … An) B
则称由前提A1，…， An 推出结论B的 推理有效， 并称B是 A1，A2， …， An 的逻辑结论，记为： A1，A2， …， An ┣ B 或 A1，A2， …， An B
公理3 (PQ)((QR)(PR))
公理4 (P(PQ))(PQ)
传递
凝缩 与有关
公理5 (PQ)(PQ)
公理6 (PQ)(QP)
公理7 (PQ)((QP)(PQ))
1P
公理9 (PQ)Q
与∧有关
公理10 P(Q(PQ))
(2) 如果今天是星期二, 今天有数学课。
今天不是星期二， 所以今天没有数学课。
3/66
推理是否正确？
记： P表示今天是星期二， Q表示今天有数学课。 (1) 如果今天是星期二, 今天有数学课。
今天是星期二，所以今天有数学课。
((PQ)P)Q
(2) 如果今天是星期二, 今天有数学课。 今天不是星期二，所以今天没有数学课。
前提引入规则（P规则） 结论引入规则（T规则） 置换规则, 11个重言式,22个等价公式
10/70 10/66
关于推理理论的学习
公理化 离散数学导论 离散数学 基础教程 离散数学及其 在计算机中的 应用 离散数学导论 南京大学 徐洁磐 南京大学 徐洁磐 南京大学 徐洁磐 解放军理 工大学 王元元 南京理工 大学 朱保平 ✔ ✔ 演绎推理 应用公理系统 ✔ 等式推理 蕴涵推理 推理定理 ✔ 自然推理系统 ✔ ✔ 消解原理 ✔ ✔ 归结推理 自动定理证明 ✔
9/70 9/66
关于推理理论的学习
公理化 演绎推理 归结推理
离散 数学
北京大学 耿素云
前提引入规则 结论引入规则 置换规则 8条推理定律
前提引入规则 结论引入规则 置换规则 9条推理定律,24个等值式 9条推理规则
离散 数学 及其 应用 离散 数学 离散 数学
北京大学 屈婉玲
解放军通信 工程学院 方世昌 朱怀宏， 南京大学出 版社
上堂课的内容、重点与难点
联结词的完备集合 合取式、析取式 合取范式、析取范式 极小项、极大项 主合取范式、主析取范式 • 合(析)取式与成真(假)解释 • 求解范式、主范式 等价公式的熟练运用 等价变换法、解释法、真值表法的灵活运用
1/66
逻辑推理
•演绎推理（数学家使用）
MP规则
17/66
二、语义部分
(1) 公理是永真公式。
(2) 规则规定如何从永真公式推出永真公式。
分离规则指明: 如果AB永真且A永真，则B也为 永真公式。 (3) 代入规则指明如果为永真公式，则某一个公式 正确代入公式后所得的公式也为永真公式。 (4) 定理为永真公式。
18/66
公理系统的推理过程 ├B
定义 如果能够作出一系列合式公式序列 A1，A2, A3, …，An， 它们满足下列性质： (1) 诸Ai或为公理/定理之一(可以使用代入规则)； (2) 或由前面的Ag、Ah利用分离规则而得；
(3) An=B。
称序列A1，A2, …，An为B的永真证明过程。
19/66
公理推理证明的方法
├B
构造合式公式序列
公理11 P(PQ)
公理12 Q(PQ)
公理13 (PR)((QR)((PQ)R))
与∨有关
公理14 (PQ)(QP)
公理15 PP
与有关
16/66
㈢ 规则
(1)代入规则：将公式中出现的某一符号 B 每处均代以某一公式C， 所到的公式D 称为C 对 的 代入。 (2)分离规则：如果AB，且A，则B。