第 3章 命题逻辑的推理理论离 散 数 学哈尔滨理工大学本科生课程计算机系本章说明
本章的主要内容
– 推理的形式结构
– 自然推理系统 P
本章与后续各章的关系
– 本章是第五章的特殊情况和先行准备
3.1 推理的形式结构
3.2 自然推理系统 P
本章小结
习题
作业
3.1 推理的形式结构
数理逻辑的主要任务是 用数学的方法来研究数学中的推理 。
推理 是指从前提出发推出结论的思维过程。
前提 是已知命题公式集合。
结论 是从前提出发应用推理规则推出的命题公式。
证明 是描述推理正确或错误的过程。
要研究推理，首先应该明确什么样的推理是有效的或正确的。
定义 3.1 设 A1,A2,…,Ak和 B都是命题公式，若对于
A1,A2,…,Ak和 B中出现的命题变项的任意一组赋值，
（ 1）或者 A1∧A 2 ∧ … ∧A k为假 ;
（ 2）或者当 A1∧A 2 ∧ … ∧A k为真时,B也为真 ;
则称由前提 A1,A2,…,Ak推出 B的 推理是有效的或正确的,并称 B是 有效结论 。
有效推理的定义关于有效推理的说明
＝ {A1,A2,…,Ak}
由?推 B的推理记为 ┣ B
若推理是正确的，记为? ╞ B
若推理是不正确的，记为? B
由前提 A1,A2,…,Ak推结论 B的推理是否正确与诸前提的排列次序无关。
关于有效推理的说明
设 A1,A2,…,Ak,B中共出现 n个命题变项，对于任何一组赋值 α 1α 2… α n(α i=0或者 1,i=1,2,…,n),前提和结论的取值情况有以下四种：
(1) A1∧A 2 ∧ … ∧A k为 0,B为 0。
(2) A1∧A 2 ∧ … ∧A k为 0,B为 1。
(3) A1∧A 2 ∧ … ∧A k为 1,B为 0。
(4) A1∧A 2 ∧ … ∧A k为 1,B为 1。
只要不出现 (3)中的情况，推理就是正确的，因而判断推理是否正确，就是判断是否会出现 (3)中的情况。
推理正确，并不能保证结论 B一定为真 。
(1) {p,p→q}├ q
(2) {p,q→p}├ q
例 3.1 判断下列推理是否正确。（真值表法）
p q p?(p→ q) q p?(q→ p) q
0 0 0 0 0 0
0 1 0 1 0 1
1 0 0 0 1 0
1 1 1 1 1 1
例题正确不正确定理 3.1 命题公式 A1,A2,…,Ak推 B的推理正确当且仅当
(A1∧A 2∧ … ∧A k )→B 为重言式。
该定理是判断推理是否正确的另一种方法。说明有效推理的等价定理定理 3.1的证明
(1)证明必要性。若 A1,A2,…,Ak推 B的推理正确，
则对于 A1,A2,…,Ak,B中所含命题变项的任意一组赋值，不会出现 A1∧A 2∧ … ∧A k为真，而 B为假的情况，
因而在任何赋值下，蕴涵式 (A1∧A 2∧ … ∧A k )→B 均为真，故它为重言式。
(2)证明充分性。若蕴涵式 (A1∧A 2∧ … ∧A k)→B 为重言式，
则对于任何赋值此蕴涵式均为真，因而不会出现前件为真后件为假的情况，
即在任何赋值下，或者 A1∧A 2∧ … ∧A k为假，
或者 A1∧A 2∧ … ∧A k和 B同时为真，这正符合推理正确的定义。
当推理正确时，
形式（ 1）记为?╞ B。
形式（ 2）记为 A1?A2?…?Ak?B。
表示蕴涵式为重言式。
(1) 设?={ A1,A2,…,A k},记为?┣ B。
(2) A1?A2?…?Ak?B
(3) 前提,A1,A2,…,A k
结论,B
说明推理的形式结构
真值表法
等值演算法
主析取范式法判断推理是否正确的方法
是否有其他的证明方法？思考
当命题变项较少时,这三种方法比较方便 。说明
（ 1） 下午马芳或去看电影或去游泳。她没去看电影，所以，她去游泳了。
例 3.2 判断下列推理是否正确。（等值演算法）
解：设 p:马芳下午去看电影,q:马芳下午去游泳。
前提,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? 1
由定理 3.1可知，
推理正确。
例题
（ 2） 若今天是 1号，则明天是 5号。明天是 5号，所以今天是 1号。
例 3.2 判断下列推理是否正确。（主析取范式法 ）
(p?q)?q?p
(?p?q)?q?p
((?p?q)?q)?p
q?p
(?pq)?(pq)?(pq)?(p?q)
m0?m2?m3
主析取范式不含 m1,故不是重言式 （ 01是成假赋值 ）,所以推理不正确 。
解：设 p,今天是 1号,q,明天是 5号。
前提,p?q,q
结论,p
推理的形式结构,(p?q)?q?p
例题
(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)∧(A∨┐A)? B 构造性二难
(特殊形式 )
(9)(A→B)∧(C→D)∧(┐B∨┐D)?(┐A∨┐C) 破坏性二难推理定律 --重言蕴含式小节结束关于推理定律的几点说明
A,B,C为元语言符号，代表任意的命题公式。
若一个推理的形式结构与某条推理定律对应的蕴涵式一致，则不用证明就可断定这个推理是正确的。
2.1节给出的 24个等值式中的每一个都派生出两条推理定律。例如双重否定律 AA产生两条推理定律 AA和A?A。
由九条推理定律可以产生九条推理规则,它们构成了推理系统中的推理规则 。
3.2 自然推理系统 P
判断推理是否正确的三种方法：真值表法、等值演算法和主析取范式法。
当推理中包含的命题变项较多时，上述三种方法演算量太大。
对于由前提 A1,A2,…,Ak推 B的正确推理应该给出严谨的证明 。
证明是一个描述推理过程的命题公式序列，其中的每个公式或者是前提，或者是由某些前提应用推理规则得到的结论（中间结论或推理中的结论）。
要构造出严谨的证明就必须在形式系统中进行。
形式系统的定义定义 3.2 一个 形式系统 I由下面四个部分组成：
（ 1） 非空的字母表,记作 A(I)。
（ 2） A(I)中符号构造的合式公式集,记作 E(I)。
（ 3） E(I)中一些特殊的公式组成的公理集,记作 AX(I)。
（ 4） 推理规则集,记作 R(I)。
可以将 I记为 4元组 <A(I),E(I),AX(I),R(I)>
<A(I),E(I)> 是 I的 形式语言系统
<AX(I),R(I) > 是 I的 形式演算系统形式系统的分类
（ 1） 自然推理系统从任意给定的前提出发,应用系统中的推理规则进行推理演算,得到的最后命题公式是推理的结论
（ 有时称为有效的结论 ） 。
（ 2） 公理系统从若干给定的公理出发,应用系统中推理规则进行推理演算,得到的结论是系统中的定理 。
本书只介绍自然推理系统 P。说明自然推理系统的定义定义 3.3 自然推理系统 P的定义
1,字母表
（ 1） 命题变项符号,p,q,r,…,pi,qi,ri,…
（ 2） 联结词符号,┐,?,?,?,?
（ 3） 括号与逗号,( )，，
2,合式公式 （ 同定义 1.6）
自然推理系统的定义
3,推理规则
（ 1）前提引入规则在证明的任何步骤上都可以引入前提。
（ 2）结论引入规则在证明的任何步骤上所得到的结论都可以作为后继证明的前提。
（ 3）置换规则在证明的任何步骤上，命题公式中的子公式都可以用与之等值的公式置换，得到公式序列中的又一个公式。
自然推理系统的定义
（ 4）假言推理规则
A?B
A
B
（ 5）附加规则
A
A?B
（ 6）化简规则
A?B
A
（ 4）若今天下雪,则将去滑雪。今天下雪，所以去滑雪。
（ 5）现在气温在冰点以下。
因此，要么现在气温在冰点以下，要么现在下雨。
（ 6）现在气温在冰点以下并且正在下雨。因此，现在气温在冰点以下。
自然推理系统的定义
（ 7）拒取式规则
A?B
B
A
（ 8） 假言三段论规则
A?B
B?C
A?C
（ 9）析取三段论规则
A?B
B
A
自然推理系统的定义
（ 10）构造性二难推理规则
A?B
C?D
A?C
B?D
（ 11）破坏性二难推理规则
A?B
C?D
BD
AC
（ 12） 合取引入规则
A
B
A?B
在自然推理系统 P中构造证明
P中构造证明就是由一组 P中公式作为前提，利用
P中的规则，推出结论。
构造形式结构 A1?A2?…?Ak? B 的推理的 书写方法：
前提,A1,A2,…,Ak
结论,B
证明方法：
– 直接证明法
– 附加前提法
– 归谬法（或称反证法）
例题例 3.3 在自然推理系统 P中构造下面推理的证明：
前提,┐ p∨q,r∨┐q,r→s
结论,p→s
① ┐ p∨q 前提引入
② p→q ① 置换
③ r∨┐q 前提引入
④ q→r ③ 置换
⑤ p→r ②④ 假言三段论
⑥ r→s 前提引入
⑦ p→s ⑤⑥ 假言三段论例题例 3.3 在自然推理系统 P中构造下面推理的证明：
前提,p→ （ q→r ）,p∧q
结论,┐r→s
① p→ （ q→r ） 前提引入
② p∧q 前提引入
③ p ②化简
④ q ②化简
⑤ q→r ① ③ 假言推理
⑥ r ④⑤假言推理
⑦ r∨s ⑥ 附加
⑧ ┐r→s ⑦置换例题例 3.4 在自然 推理系统 P中构造下面推理的证明：
若数 a是实数,则它不是有理数就是无理数；若 a不能表示成分数,则它不是有理数； a是实数且它不能表示成分数 。
所以 a是无理数 。
构造证明：
（ 1）将简单命题符号化：
设 p,a是实数。 q,a是有理数。
r,a是无理数。 s,a能表示成分数。
（ 2）形式结构：
前提,p→(q∨r),┐s→┐q,p∧┐s
结论,r
① p∧┐s 前提引入
② p ① 化简
③ ┐ s ① 化简
④ p→(q∨r) 前提引入
⑤ q∨r ②④ 假言推理
⑥ ┐ s→┐q 前提引入
⑦ ┐ q ③⑥ 假言推理
⑧ r ⑤⑦ 析取三段论例题附加前提法
有时推理的形式结构具有如下形式,
前提,A1,A2,…,Ak
结论,C?B
可将结论中的前件也作为推理的前提，使结论只为 B。
前提,A1,A2,…,Ak,C
结论,B
理由,(A1?A2?…?Ak)?(C?B)
( A1?A2?…?Ak)?(?C?B)
( A1?A2?…?Ak?C)?B
(A1?A2?…?Ak?C)?B
例题例 3.5 在自然推理系统 P中构造下面推理的证明。
如果小张和小王去看电影，则小李也去看电影；小赵不去看电影或小张去看电影；小王去看电影。所以，当小赵去看电影时，小李也去看电影。
构造证明：
（ 1）将简单命题符号化：
设 p:小张去看电影。
q:小王去看电影。
r:小李去看电影。
s:小赵去看电影。
例题
（ 2） 形式结构：
前提,(p∧q)→r,┐s∨p,q
结论,s→r
（ 3）证明：用附加前提证明法
① s 附加前提引入
② ┐ s∨p 前提引入
③ p ①② 析取三段论
④ (p∧q)→r 前提引入
⑤ q 前提引入
⑥ p∧q ③⑤ 合取
⑦ r ④⑥ 假言推理归谬法（反证法）
有时推理的形式结构具有如下形式：
前提,A1,A2,…,Ak
结论,B
如果将 ┐ B作为前提能推出矛盾来，则说明推理正确。
前提,A1,A2,…,Ak,?B
结论：矛盾
理由,A1?A2?…?Ak?B
(A1?A2?…?Ak)?B
(A1?A2?…?AkB)
若 A1?A2?…?AkB为矛盾式，则说明 (A1?A2?…?Ak?B)
为重言式。
例题例 3.6 在自然推理系统 P中构造下面推理的证明。
如果小张守第一垒并且小李向 B队投球，则 A队将取胜；或者 A
队未取胜，或者 A队获得联赛第一名； A队没有获得联赛的第一名；小张守第一垒。因此，小李没有向 B队投球。
构造证明：
（ 1）将简单命题符号化：
设 p:小张守第一垒。 q:小李向 B队投球。
r:A队取胜。 s:A队获得联赛第一名。
（ 2）形式结构：
前提,(p∧q)→r,┐r∨s,┐s,p
结论,┐ q
例题
（ 3）证明：用归谬法
① q 结论的否定引入
② ┐ r∨s 前提引入
③ ┐ s 前提引入
④ ┐ r ②③ 析取三段论
⑤ (p∧q)→r 前提引人
⑥ ┐( p∧q) ④⑤ 拒取式
⑦ ┐ p∨┐q ⑥ 置换
⑧ p 前提引入
⑨ ┐ q ⑦⑧ 析取三段论
⑩ q∧┐q ①⑨ 合取由于最后一步为矛盾式，所以推理正确。 小节结束本章主要内容
推理的形式结构：
推理的前提
推理的结论
推理正确
判断推理是否正确的方法：
真值表法
等值演算法
主析取范式法
对于正确的推理，在自然推理系统 P中构造证明,
自然推理系统 P的定义
自然推理系统 P的推理规则：
附加前提证明法
归谬法本章学习要求
理解并记住推理的形式结构的三种等价形式，即
① {A1,A2,…,A k}├B
② A1∧ A2∧ … ∧ Ak→B
③ 前提,A1,A2,…,A k
结论,B
在判断推理是否正确时，用②；在 P系统中构造证明时用③。
熟练掌握判断推理是否正确的三种方法（真值表法，等值演算法，主析取范式法）。
牢记 P系统中的各条推理规则。
对于给定的正确推理，要求在 P系统中给出严谨的证明序列。
会用附加前提证明法和归谬法。 小节结束习题
1,用不同的方法验证下面推理是否正确 。 对于正确的推理还要在 P系统中给出证明 。
（ 1） 前提,?p?q,?q
结论,?p
（ 2） 前提,q?r,pr
结论,qp
（ 1） 不正确 。
验证答案，只需证明 (?p?q)qp不是重言式。
方法一 等值演算
(?p?q)qp
((p?q)q)p
(?pq)?qp
((?p?q)?(?q?q))p
p?q
易知 10是成假赋值,故 (?p?q)qp不是重言式,所以推理不正确 。
方法二 主析取范式法经过演算后可知
(?p?q)qp?m0?m1?m3
未含 m2,故 (?p?q)qp不是重言式。
方法三 直接观察出 10是成假赋值。
方法四 真值表法
(?p?q)qp的真值表为
p q (?p?q)qp
0 0 1
1 0 1
0 1 0
1 1 1
结论 （ 不正确 ） 是对的 。
（ 2） 推理正确方法一 真值表法 （ 自己做 ）
方法二 等值演算法 （ 自己做 ）
方法三 主析取范式法 （ 自己做 ）
方法四 P系统中构造证明证明,（ 直接证明法 ）
① pr （ 前提引入 ）
② rp （ ① 置换 ）
③ q?r （ 前提引入 ）
④ qp （ ③② 假言三段论 ）
2,在 P系统中构造下面推理的证明：
如果今天是周六，我们就到颐和园或圆明园玩。 如果颐和园游人太多，就不去颐和园。 今天是周六，并且颐和园游人太多。 所以我们去圆明园或动物园玩。
构造证明：
（ 1） 设 p,今天是周六。 q,到颐和园玩。
r,到圆明园玩。 s,颐和园游人太多。
t,到动物园玩。
（ 2）前提,p?(q?r),sq,p,s
结论,r?t
（ 3） 证明：
① p?(q?r) 前提引入
② p 前提引入
③ q?r ①② 假言推理
④ sq 前提引入
⑤ s 前提引入
⑥?q ④⑤ 假言推理
⑦ r ③⑥ 析取三段论
⑧ r?t ⑦ 附加小节结束作业习题三,6,14,15,16,18
结束
本章的主要内容
– 推理的形式结构
– 自然推理系统 P
本章与后续各章的关系
– 本章是第五章的特殊情况和先行准备
3.1 推理的形式结构
3.2 自然推理系统 P
本章小结
习题
作业
3.1 推理的形式结构
数理逻辑的主要任务是 用数学的方法来研究数学中的推理 。
推理 是指从前提出发推出结论的思维过程。
前提 是已知命题公式集合。
结论 是从前提出发应用推理规则推出的命题公式。
证明 是描述推理正确或错误的过程。
要研究推理，首先应该明确什么样的推理是有效的或正确的。
定义 3.1 设 A1,A2,…,Ak和 B都是命题公式，若对于
A1,A2,…,Ak和 B中出现的命题变项的任意一组赋值，
（ 1）或者 A1∧A 2 ∧ … ∧A k为假 ;
（ 2）或者当 A1∧A 2 ∧ … ∧A k为真时,B也为真 ;
则称由前提 A1,A2,…,Ak推出 B的 推理是有效的或正确的,并称 B是 有效结论 。
有效推理的定义关于有效推理的说明
＝ {A1,A2,…,Ak}
由?推 B的推理记为 ┣ B
若推理是正确的，记为? ╞ B
若推理是不正确的，记为? B
由前提 A1,A2,…,Ak推结论 B的推理是否正确与诸前提的排列次序无关。
关于有效推理的说明
设 A1,A2,…,Ak,B中共出现 n个命题变项，对于任何一组赋值 α 1α 2… α n(α i=0或者 1,i=1,2,…,n),前提和结论的取值情况有以下四种：
(1) A1∧A 2 ∧ … ∧A k为 0,B为 0。
(2) A1∧A 2 ∧ … ∧A k为 0,B为 1。
(3) A1∧A 2 ∧ … ∧A k为 1,B为 0。
(4) A1∧A 2 ∧ … ∧A k为 1,B为 1。
只要不出现 (3)中的情况，推理就是正确的，因而判断推理是否正确，就是判断是否会出现 (3)中的情况。
推理正确，并不能保证结论 B一定为真 。
(1) {p,p→q}├ q
(2) {p,q→p}├ q
例 3.1 判断下列推理是否正确。（真值表法）
p q p?(p→ q) q p?(q→ p) q
0 0 0 0 0 0
0 1 0 1 0 1
1 0 0 0 1 0
1 1 1 1 1 1
例题正确不正确定理 3.1 命题公式 A1,A2,…,Ak推 B的推理正确当且仅当
(A1∧A 2∧ … ∧A k )→B 为重言式。
该定理是判断推理是否正确的另一种方法。说明有效推理的等价定理定理 3.1的证明
(1)证明必要性。若 A1,A2,…,Ak推 B的推理正确，
则对于 A1,A2,…,Ak,B中所含命题变项的任意一组赋值，不会出现 A1∧A 2∧ … ∧A k为真，而 B为假的情况，
因而在任何赋值下，蕴涵式 (A1∧A 2∧ … ∧A k )→B 均为真，故它为重言式。
(2)证明充分性。若蕴涵式 (A1∧A 2∧ … ∧A k)→B 为重言式，
则对于任何赋值此蕴涵式均为真，因而不会出现前件为真后件为假的情况，
即在任何赋值下，或者 A1∧A 2∧ … ∧A k为假，
或者 A1∧A 2∧ … ∧A k和 B同时为真，这正符合推理正确的定义。
当推理正确时，
形式（ 1）记为?╞ B。
形式（ 2）记为 A1?A2?…?Ak?B。
表示蕴涵式为重言式。
(1) 设?={ A1,A2,…,A k},记为?┣ B。
(2) A1?A2?…?Ak?B
(3) 前提,A1,A2,…,A k
结论,B
说明推理的形式结构
真值表法
等值演算法
主析取范式法判断推理是否正确的方法
是否有其他的证明方法？思考
当命题变项较少时,这三种方法比较方便 。说明
（ 1） 下午马芳或去看电影或去游泳。她没去看电影，所以，她去游泳了。
例 3.2 判断下列推理是否正确。（等值演算法）
解：设 p:马芳下午去看电影,q:马芳下午去游泳。
前提,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? 1
由定理 3.1可知，
推理正确。
例题
（ 2） 若今天是 1号，则明天是 5号。明天是 5号，所以今天是 1号。
例 3.2 判断下列推理是否正确。（主析取范式法 ）
(p?q)?q?p
(?p?q)?q?p
((?p?q)?q)?p
q?p
(?pq)?(pq)?(pq)?(p?q)
m0?m2?m3
主析取范式不含 m1,故不是重言式 （ 01是成假赋值 ）,所以推理不正确 。
解：设 p,今天是 1号,q,明天是 5号。
前提,p?q,q
结论,p
推理的形式结构,(p?q)?q?p
例题
(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)∧(A∨┐A)? B 构造性二难
(特殊形式 )
(9)(A→B)∧(C→D)∧(┐B∨┐D)?(┐A∨┐C) 破坏性二难推理定律 --重言蕴含式小节结束关于推理定律的几点说明
A,B,C为元语言符号，代表任意的命题公式。
若一个推理的形式结构与某条推理定律对应的蕴涵式一致，则不用证明就可断定这个推理是正确的。
2.1节给出的 24个等值式中的每一个都派生出两条推理定律。例如双重否定律 AA产生两条推理定律 AA和A?A。
由九条推理定律可以产生九条推理规则,它们构成了推理系统中的推理规则 。
3.2 自然推理系统 P
判断推理是否正确的三种方法：真值表法、等值演算法和主析取范式法。
当推理中包含的命题变项较多时，上述三种方法演算量太大。
对于由前提 A1,A2,…,Ak推 B的正确推理应该给出严谨的证明 。
证明是一个描述推理过程的命题公式序列，其中的每个公式或者是前提，或者是由某些前提应用推理规则得到的结论（中间结论或推理中的结论）。
要构造出严谨的证明就必须在形式系统中进行。
形式系统的定义定义 3.2 一个 形式系统 I由下面四个部分组成：
（ 1） 非空的字母表,记作 A(I)。
（ 2） A(I)中符号构造的合式公式集,记作 E(I)。
（ 3） E(I)中一些特殊的公式组成的公理集,记作 AX(I)。
（ 4） 推理规则集,记作 R(I)。
可以将 I记为 4元组 <A(I),E(I),AX(I),R(I)>
<A(I),E(I)> 是 I的 形式语言系统
<AX(I),R(I) > 是 I的 形式演算系统形式系统的分类
（ 1） 自然推理系统从任意给定的前提出发,应用系统中的推理规则进行推理演算,得到的最后命题公式是推理的结论
（ 有时称为有效的结论 ） 。
（ 2） 公理系统从若干给定的公理出发,应用系统中推理规则进行推理演算,得到的结论是系统中的定理 。
本书只介绍自然推理系统 P。说明自然推理系统的定义定义 3.3 自然推理系统 P的定义
1,字母表
（ 1） 命题变项符号,p,q,r,…,pi,qi,ri,…
（ 2） 联结词符号,┐,?,?,?,?
（ 3） 括号与逗号,( )，，
2,合式公式 （ 同定义 1.6）
自然推理系统的定义
3,推理规则
（ 1）前提引入规则在证明的任何步骤上都可以引入前提。
（ 2）结论引入规则在证明的任何步骤上所得到的结论都可以作为后继证明的前提。
（ 3）置换规则在证明的任何步骤上，命题公式中的子公式都可以用与之等值的公式置换，得到公式序列中的又一个公式。
自然推理系统的定义
（ 4）假言推理规则
A?B
A
B
（ 5）附加规则
A
A?B
（ 6）化简规则
A?B
A
（ 4）若今天下雪,则将去滑雪。今天下雪，所以去滑雪。
（ 5）现在气温在冰点以下。
因此，要么现在气温在冰点以下，要么现在下雨。
（ 6）现在气温在冰点以下并且正在下雨。因此，现在气温在冰点以下。
自然推理系统的定义
（ 7）拒取式规则
A?B
B
A
（ 8） 假言三段论规则
A?B
B?C
A?C
（ 9）析取三段论规则
A?B
B
A
自然推理系统的定义
（ 10）构造性二难推理规则
A?B
C?D
A?C
B?D
（ 11）破坏性二难推理规则
A?B
C?D
BD
AC
（ 12） 合取引入规则
A
B
A?B
在自然推理系统 P中构造证明
P中构造证明就是由一组 P中公式作为前提，利用
P中的规则，推出结论。
构造形式结构 A1?A2?…?Ak? B 的推理的 书写方法：
前提,A1,A2,…,Ak
结论,B
证明方法：
– 直接证明法
– 附加前提法
– 归谬法（或称反证法）
例题例 3.3 在自然推理系统 P中构造下面推理的证明：
前提,┐ p∨q,r∨┐q,r→s
结论,p→s
① ┐ p∨q 前提引入
② p→q ① 置换
③ r∨┐q 前提引入
④ q→r ③ 置换
⑤ p→r ②④ 假言三段论
⑥ r→s 前提引入
⑦ p→s ⑤⑥ 假言三段论例题例 3.3 在自然推理系统 P中构造下面推理的证明：
前提,p→ （ q→r ）,p∧q
结论,┐r→s
① p→ （ q→r ） 前提引入
② p∧q 前提引入
③ p ②化简
④ q ②化简
⑤ q→r ① ③ 假言推理
⑥ r ④⑤假言推理
⑦ r∨s ⑥ 附加
⑧ ┐r→s ⑦置换例题例 3.4 在自然 推理系统 P中构造下面推理的证明：
若数 a是实数,则它不是有理数就是无理数；若 a不能表示成分数,则它不是有理数； a是实数且它不能表示成分数 。
所以 a是无理数 。
构造证明：
（ 1）将简单命题符号化：
设 p,a是实数。 q,a是有理数。
r,a是无理数。 s,a能表示成分数。
（ 2）形式结构：
前提,p→(q∨r),┐s→┐q,p∧┐s
结论,r
① p∧┐s 前提引入
② p ① 化简
③ ┐ s ① 化简
④ p→(q∨r) 前提引入
⑤ q∨r ②④ 假言推理
⑥ ┐ s→┐q 前提引入
⑦ ┐ q ③⑥ 假言推理
⑧ r ⑤⑦ 析取三段论例题附加前提法
有时推理的形式结构具有如下形式,
前提,A1,A2,…,Ak
结论,C?B
可将结论中的前件也作为推理的前提，使结论只为 B。
前提,A1,A2,…,Ak,C
结论,B
理由,(A1?A2?…?Ak)?(C?B)
( A1?A2?…?Ak)?(?C?B)
( A1?A2?…?Ak?C)?B
(A1?A2?…?Ak?C)?B
例题例 3.5 在自然推理系统 P中构造下面推理的证明。
如果小张和小王去看电影，则小李也去看电影；小赵不去看电影或小张去看电影；小王去看电影。所以，当小赵去看电影时，小李也去看电影。
构造证明：
（ 1）将简单命题符号化：
设 p:小张去看电影。
q:小王去看电影。
r:小李去看电影。
s:小赵去看电影。
例题
（ 2） 形式结构：
前提,(p∧q)→r,┐s∨p,q
结论,s→r
（ 3）证明：用附加前提证明法
① s 附加前提引入
② ┐ s∨p 前提引入
③ p ①② 析取三段论
④ (p∧q)→r 前提引入
⑤ q 前提引入
⑥ p∧q ③⑤ 合取
⑦ r ④⑥ 假言推理归谬法（反证法）
有时推理的形式结构具有如下形式：
前提,A1,A2,…,Ak
结论,B
如果将 ┐ B作为前提能推出矛盾来，则说明推理正确。
前提,A1,A2,…,Ak,?B
结论：矛盾
理由,A1?A2?…?Ak?B
(A1?A2?…?Ak)?B
(A1?A2?…?AkB)
若 A1?A2?…?AkB为矛盾式，则说明 (A1?A2?…?Ak?B)
为重言式。
例题例 3.6 在自然推理系统 P中构造下面推理的证明。
如果小张守第一垒并且小李向 B队投球，则 A队将取胜；或者 A
队未取胜，或者 A队获得联赛第一名； A队没有获得联赛的第一名；小张守第一垒。因此，小李没有向 B队投球。
构造证明：
（ 1）将简单命题符号化：
设 p:小张守第一垒。 q:小李向 B队投球。
r:A队取胜。 s:A队获得联赛第一名。
（ 2）形式结构：
前提,(p∧q)→r,┐r∨s,┐s,p
结论,┐ q
例题
（ 3）证明：用归谬法
① q 结论的否定引入
② ┐ r∨s 前提引入
③ ┐ s 前提引入
④ ┐ r ②③ 析取三段论
⑤ (p∧q)→r 前提引人
⑥ ┐( p∧q) ④⑤ 拒取式
⑦ ┐ p∨┐q ⑥ 置换
⑧ p 前提引入
⑨ ┐ q ⑦⑧ 析取三段论
⑩ q∧┐q ①⑨ 合取由于最后一步为矛盾式，所以推理正确。 小节结束本章主要内容
推理的形式结构：
推理的前提
推理的结论
推理正确
判断推理是否正确的方法：
真值表法
等值演算法
主析取范式法
对于正确的推理，在自然推理系统 P中构造证明,
自然推理系统 P的定义
自然推理系统 P的推理规则：
附加前提证明法
归谬法本章学习要求
理解并记住推理的形式结构的三种等价形式，即
① {A1,A2,…,A k}├B
② A1∧ A2∧ … ∧ Ak→B
③ 前提,A1,A2,…,A k
结论,B
在判断推理是否正确时，用②；在 P系统中构造证明时用③。
熟练掌握判断推理是否正确的三种方法（真值表法，等值演算法，主析取范式法）。
牢记 P系统中的各条推理规则。
对于给定的正确推理，要求在 P系统中给出严谨的证明序列。
会用附加前提证明法和归谬法。 小节结束习题
1,用不同的方法验证下面推理是否正确 。 对于正确的推理还要在 P系统中给出证明 。
（ 1） 前提,?p?q,?q
结论,?p
（ 2） 前提,q?r,pr
结论,qp
（ 1） 不正确 。
验证答案，只需证明 (?p?q)qp不是重言式。
方法一 等值演算
(?p?q)qp
((p?q)q)p
(?pq)?qp
((?p?q)?(?q?q))p
p?q
易知 10是成假赋值,故 (?p?q)qp不是重言式,所以推理不正确 。
方法二 主析取范式法经过演算后可知
(?p?q)qp?m0?m1?m3
未含 m2,故 (?p?q)qp不是重言式。
方法三 直接观察出 10是成假赋值。
方法四 真值表法
(?p?q)qp的真值表为
p q (?p?q)qp
0 0 1
1 0 1
0 1 0
1 1 1
结论 （ 不正确 ） 是对的 。
（ 2） 推理正确方法一 真值表法 （ 自己做 ）
方法二 等值演算法 （ 自己做 ）
方法三 主析取范式法 （ 自己做 ）
方法四 P系统中构造证明证明,（ 直接证明法 ）
① pr （ 前提引入 ）
② rp （ ① 置换 ）
③ q?r （ 前提引入 ）
④ qp （ ③② 假言三段论 ）
2,在 P系统中构造下面推理的证明：
如果今天是周六，我们就到颐和园或圆明园玩。 如果颐和园游人太多，就不去颐和园。 今天是周六，并且颐和园游人太多。 所以我们去圆明园或动物园玩。
构造证明：
（ 1） 设 p,今天是周六。 q,到颐和园玩。
r,到圆明园玩。 s,颐和园游人太多。
t,到动物园玩。
（ 2）前提,p?(q?r),sq,p,s
结论,r?t
（ 3） 证明：
① p?(q?r) 前提引入
② p 前提引入
③ q?r ①② 假言推理
④ sq 前提引入
⑤ s 前提引入
⑥?q ④⑤ 假言推理
⑦ r ③⑥ 析取三段论
⑧ r?t ⑦ 附加小节结束作业习题三,6,14,15,16,18
结束
