(3) 若A和B是合式公式,则(A B)是合式公式;
(4) 只有通过有限次使用(1): (3)得到的符号串才是合式公式。
.
武汉大学国际软件学院唐存琛 刘峰
36
3、公理集：
(L1) ( A (B A)) (L2 ) (( A (B C)) (( A B) ( A C)) (L3) (((A) (B)) (B A)
m0 m2 m3
这不是一个永真式，01是该公式成假的赋值，
所以推理不正确。
.
武汉大学国际软件学院唐存琛 刘峰
7
三、推理规则
1、推理规则的定义
A1, A2 , , An 是一个推理规则，当且仅当 B
A1 A2 An B，其中, A1, A2, … , An 称 为推理规则的前提，B 称为推理规则的结论。
推理的形式结构为 ( p q) p q
证明 用等值演算法
( p q) p q ((p q) p) q (( p q) p) q (( p q) p) q ( p p) (q p) q q p q T
所以，原推理正确。
.
武汉大学国际软件学院唐存琛 刘峰
4、推理规则：假言推理规则（MP规则）。
.
武汉大学国际软件学院唐存琛 刘峰
37
例9 证明
├L (P1 P2 ) (P1 P1)
L2
L1
[证] (1) (P1 (P2 P1)) ((P1 P2 ) (P1 P1()1))、L2(2)，MP
(2) P1 (P2 P1) (3) (P1 P2 ) (P1 P1)
定义2.20 称（A1 A2 … Ak ） B为由前提 A1, A2, … , Ak推结论 B 的推理的形式结构。
推理的形式结构一般有以下三种：
形式(1) A1 A2 … Ak B 形式(2) 前提: A1, A2, … , Ak
结论: B 形式(3) A1， A2 ， … ， Ak B
2.4 命题逻辑推理理论
2.4.1 推理的形式结构 推理及其形式结构 推理定律
2.4.2 自然推理系统P 自然推理系统的定义 证明方法
.
武汉大学国际软件学院
唐存琛 刘峰
1
2.4.1 推理的形式结构
一、什么是推理
定义2.19 设A1，A2 ， … ，Ak ，B都是命题公式，若对于 每组赋值, A1A2 … Ak为假, 或者当A1 A2 … Ak 为真时，B也为真, 则称由前提A1，A2，…, Ak推B的推 理有效或推理正确, 并称B是有效的结论。
31
⑨p
前提引入
⑩ pp
⑧⑨合取
推理正确, q是有效结论
.
武汉大学国际软件学院
唐存琛 刘峰
32
课堂实训
应用实例1 分析下列事实“如果我有很高的收 入，那么我就能资助许多贫困学生；如果我能资 助许多贫困学生，那么我很高兴；但我不高兴， 所以我没有很高的收入。”试指明前提和结论， 并给予证明。
.
武汉大学国际软件学院
⑤置换
结论有效, 即明天不是星期一和星期三.
.
武汉大学国际软件学院
唐存琛 刘峰
27
附加前提证明法举例
欲证明
前提: A1, A2, …, Ak 结论: CB
等价地证明
前提: A1, A2, …, Ak, C 结论: B
.
武汉大学国际软件学院
唐存琛 刘峰
28
例7 构造下面推理的证明: 前提: pq, qr, rs 结论: ps
22
例4 证明 (P Q), (Q R), (R S) P
ቤተ መጻሕፍቲ ባይዱ
[证]①
② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨
(P) P P Q Q Q R R R S R R R
假设前提 ①，E1 前提 ②、③，假言推理 前提 ④、⑤，析取三段论 前提 ⑦，化简 ⑥、⑧，合取引入
⑨ 是一个永假式，因此，原推理正确。
唐存琛 刘峰
17
附加前提证明法的说明：
欲证明
前提: A1, A2, …, Ak 结论: CB
等价地证明
前提: A1, A2, …, Ak, C 结论: B
理由: (A1A2…Ak)(CB) ( A1A2…Ak)(CB) ( A1A2…AkC)B (A1A2…AkC)B
.
武汉大学国际软件学院
唐存琛 刘峰
武汉大学国际软件学院唐存琛 刘峰
24
(6)q r
前提
(7)r
(5)、(6)假言推理
(8)r ( p q) (7)、(4)合取
.
武汉大学国际软件学院唐存琛 刘峰
25
例6 构造推理的证明: 若明天是星期一或星期三, 我就有课. 若有课, 今天必需备课. 我今天下午 没备课. 所以, 明天不是星期一和星期三.
.
武汉大学国际软件学院
唐存琛 刘峰
16
（5）分情况证明法
为了证明 A1 A2 An B , 只需证明对任意的 i (1 i n) ，均有 Ai B 。
（6）附加前提证明法
为了证明 A1 A2 An A B ,
只需证明 A1 A2 An A B
.
武汉大学国际软件学院
证明： ① p
附加前提引入
② pq
前提引入
③q
①②析取三段论
④ qr
前提引入
⑤r
③④析取三段论
⑥ rs
前提引入
⑦s
⑤⑥假言推理
推理正确, ps是有效结论
.
武汉大学国际软件学院
唐存琛 刘峰
29
归谬法(反证法)举例
欲证明 前提：A1, A2, … , Ak 结论：B 将B加入前提, 若推出矛盾, 则得证推理正确.
12
一、自然推理系统P的定义（续）
3. 推理规则 (1) 前提引入规则 (2) 结论引入规则 (3) 置换规则 (4) 假言推理规则 (5) 附加规则 (6) 化简规则
(7) 拒取式规则 (8) 假言三段论规则 (9) 析取三段论规则 (10)构造性二难推理
规则 (11) 破坏性二难推理
规则 (12) 合取引入规则
.
武汉大学国际软件学院
唐存琛 刘峰
30
例8 构造下面推理的证明
前提: (pq)r, rs, s, p ；结论: q
证明：用归缪法
①q
结论否定引入
② rs
前提引入
③ s
前提引入
④ r
②③拒取式
⑤ (pq)r 前提引入
⑥ (pq)
④⑤析取三段论
⑦ pq
⑥置换
⑧ p
①⑦析取三段论
.
武汉大学国际软件学院
唐存琛 刘峰
.
武汉大学国际软件学院
唐存琛 刘峰
20
归谬法(反证法)的说明
欲证明
前提：A1, A2, … , Ak 结论：B
将B加入前提, 若推出矛盾, 则得证推理正确.
理由: A1A2…AkB (A1A2…Ak)B (A1A2…AkB)
括号内部为矛盾式当且仅当 (A1A2…AkB)为重言式
.
武汉大学国际软件学院
AC
7）合取引入
A, B A B
8）构造性二难 A B,C D, A C
B D
.
武汉大学国际软件学院
唐存琛 刘峰
10
注意：
（1）推理规则中出现的A、B、C 等是元语言符号； （2）直接引用而不需证明，只要说明所引用规则的名称； （3）24个永真公式每个都可以等效为2个推理规则。
.
武汉大学国际软件学院
.
武汉大学国际软件学院
唐存琛 刘峰
2
定理2.8 由前提A1, A2, …, Ak 推出B 的推理正确当且仅当 A1 A2 … Ak B为重言式.
如果把（A1 A2 … Ak ） B为永真式记为：
A1 A2 L Ak B
上式的含义？？？
.
武汉大学国际软件学院
唐存琛 刘峰
3
二、推理的形式结构
唐存琛 刘峰
11
2.4.2 自然推理系统P
一、自然推理系统P的定义
自然推理系统P由下述3部分组成: 1. 字母表
(1) 命题变项符号: p,q,r,…, pi,qi,ri,… (2) 联结词: , , , , (3) 括号与逗号: ( ), , 2. 合式公式
.
武汉大学国际软件学院
唐存琛 刘峰
解 设 p:明天是星期一, q:明天是星期三，
r:我有课，
s:我备课
前提: (pq)r, rs, s
结论: pq
pqr
.
武汉大学国际软件学院唐存琛 刘峰
26
前提: (pq)r, rs, s
结论: pq
证明：
① rs
前提引入
② s
前提引入
③ r
①②拒取式
④ (pq)r
前提引入
⑤ (pq)
③④拒取式
⑥ pq
.
武汉大学国际软件学院
唐存琛 刘峰
23
直接证明法举例
例5 在自然推理系统P中构造下面推理的证明:
前提: p q, q r, p s, s 结论: r ( p q)
证明： (1) p s 前提
(2)s
前提
(3)p
(1)、(2)拒取式
(4) p q 前提
(5)q
(3)、(4)析取三段论
.
6
例1 (2) 若今天是1号, 则明天是5号. 明天是5号. 所以, 今天是1号。
解 设 p: 今天是1号, q: 明天是5号
推理的形式结构为 ( p q) q p
证明 用主析取范式法
( p q) q p ((p q) q) p