14
(2)证明：
①┐p∨q ②p→q ③r∨┐q ④q→r ⑤p→r ⑥r→s ⑦p→s
前提引入 ①置换 前提引入 ③置换 ②④假言三段论 前提引入 ⑤⑥假言三段论
从最后一步可知推理正确，p→s是有效结论。
15
可以在自然推理系统p中构造数学和日常生活中的 一些推理，所得结论都是有效的，即当各前提的 合取式为真时，结论必为真。
解:将简单命题符号化： 设p:小张去看电影；q:小王去看电影； r:小李去看电影；s:小赵去看电影。
前提：(p∧q)→r,┐s∨p,q 结论：s→r
21
证明：用附加前提证明法。
①s
附加前提引入②┐s∨p前提引入源自③p①②析取三段论
④(p∧q)→r 前提引入
⑤q
前提引入
⑥p∧q
③⑤合取
⑦r
④⑥假言推理
9
（4）假言推理 用图示表示如下：
A→B A ∴B
（5）附加规则
A ∴A∨B
（6）化简规则
A∧B ∴A
10
（7）拒取式规则
A→B
┐B
∴ ┐A
（8）假言三段论规则
A→B B→C
（9）析取三段论规则
∴ A→C
A∨B ┐B
∴A
11
（10）构造性二难推理规则 A→B
C→D
A∨C
∴ B∨D
（11）破坏性二难推理规则
结论也为蕴涵式。此时可将结论中的前件也作为推理的前提，使结论
只为B。即化为下述形式:
(A1∧A2∧…∧Ak∧A)→B
（3.11）
使用等值演算法可证（ 3.10 ）式与（ 3.11 ）式是等值的，因而若能
证明（ 3.11 ）式是正确的，则（ 3.10 ）式也是正确的。
采用形式结构（ 3.11 ）式证明（ 3.10 ），将A称为附加前提，并称 此证明法为附加前提证明法。
19
2）归谬法。 在构造形式结构为(A1∧A2∧…∧Ak)→B的推理证明中，
如果将┐B作为前提能推出矛盾来，比如说得出 (A∧┐A)，则说明推理正确。
20
例3.5 在自然推理系统P中构造下面推理的证明。 如果小张和小王去看电影，则小李也去看电影；小赵不去 看电影或小张去看电影；小王去看电影。所以，当小赵去 看电影时，小李也去看电影。
即结论：s→r得证。
22
例3.6 在自然推理系统P2中构造下面推理的证明。 如果小张守第一垒并且小李向B队投球，则A队将取胜；或 者A队未取胜，或者A队获得联赛第一名；A队没有获得联 赛的第一名；小张守第一垒。因此，小李没有向B队投球。
解：先将简单命题符号化。 设p:小张守第一垒；q:小李向B队投球； r:A队取胜；s:A队获得联赛第一名。
6
形式系统分为： （1）自然推理系统：从任意给定的前提出发，应
用系统中的推理规则进行推理演算，最后得到结 论。 （2）公理推理系统：从若干条给定的公理出发， 应用系统中的推理规则进行推理演算，最后得到 系统中的重言式，称为定理。
本书只介绍自然推理系统P，它的定义中无公理部 分。
7
定义3.3 自然推理系统P定义如下： 1．字母表 （1）命题变项符号：p，q，r，…,pi，qi，ri，… （2）联结词符号：┐,∧,∨,→, （3）括号和逗号：(,)，， 2．合式公式参见定义1.6。 3．推理规则 （1）前提引入规则：在证明的任何步骤上都可以引入前提。 （2）结论引入规则：在证明的任何步骤上所得到的结论都 可以作为后继证明的前提。
8
（3）置换规则：在证明的任何步骤上，命题公式 中的子公式都可以用与之等值的公式置换，得到 公式序列中的又一个公式。 由九条推理定律和结论引入规则还可以导出以下 各条推理定律。
（4）假言推理规则（或称分离规则）：由A→B 和A，可得B.
若证明的公式序列中已出现过A→B和A，则由假言推理定律(A→B)∧AB可知，B 是A→B和A的有效结论。由结论引入规则可知，可将B引入到命题序列中来。
3.2 自然推理系统
1
§1.8 命题逻辑的推理理论
数理逻辑的主要任务是用数学的方法来研究推理。 所谓推理是指从前提出发推出结论的思维过程，而前提 是已知命题公式集合，结论是从前提出发应用推理规则 推出的命题公式。
2
一、有效推理
定义 设α1，α2，…，αn，β都是命题公式，
称推理“α1，α2，…，αn推出β”是有效的（或正确的）， 如果对α1，α2，…，αn，β中出现的命题变项的任一指派， 若α1，α2，…，αn都真，则β亦真，并称β是有效结论。 否则，称“由α1，α2，…，αn推出β”是无效的或不合理的。
A→B
C→D
┐B∨┐D
（12）合取引入规则
∴ ┐A∨┐C
A
B
∴ A ∧B
12
例子
例3.3 在自然推理系统P中构造下面推理的证明： (1)前提：p∨q, q→r, p→s, ┐s 结论：r∧(p∨q) (2)前提：┐p∨q,r∨┐q,r→s 结论：p→s
13
解(1)证明：
①p→s 前提引入 ②┐s 前提引入 ③┐p ①②拒取式 ④p∨q 前提引入 ⑤q ③④析取三段论 ⑥q→r 前提引入 ⑦r ⑤⑥假言推理 ⑧r∧(p∨q) ⑦④合取 此证明的序列长为8，最后一步为推理的结论，所 以推理正确，r∧(p∨q)是有效结论。
24
AX(I)。 （4）推理规则集，记作R(I)。 可以将I记为<A(I),E(I),AX(I),R(I)>.
其中<A(I),E(I)>是I的形式语言系统， <AX(I),R(I)>为I的形式演算系统。
5
形式系统
符号库（字母表） （形式）公式 （形式）公理 （形式）推理规则
符号库和形式公式统称为形式语言系统。 形式公理和形式推理规则统称为形式演算系统。
17
证明：
①p∧┐s 前提引入
②p
①化简
③┐s
①化简
④p→(q∨r) 前提引入
⑤q∨r
②④假言推理
⑥┐s→┐q 前提引入
⑦┐q
③⑥假言推理
⑧r
⑤⑦析取三段论
（完毕）
18
P中证明的两个常用技巧：
1）附加前提证明法；
有时推理的形式结构具有如下形式:
（A1∧A2∧…∧Ak）→(A→B)
（3.10）
注意：在推理形式中，推理形式的有效与否与前提中命题公式 的排列次序无关。
3
我们将前述推理用更严谨的形式推理系统描述出 来。
怎样在计算机上实现如下的有效推理： {pq, qr} ├ pr
识别符号p,q,r 识别公式pq, qr, …… 推理方法
4
定义
定义3.2 一个形式系统I由下面四个部分组成： （1）非空的字符表集，记作A(I)。 （2）A(I)中符号构造的合式公式集，记作E(I)。 （3）E(I)中一些特殊的公式组成的公理集，记作
前提：(p∧q)→r,┐r∨s,┐s,p 结论：┐q
23
证明：用归谬法
①q
结论的否定引入
②┐r∨s 前提引入
③┐s 前提引入
④┐r ②③析取三段论
⑤(p∧q)→r 前提引入
⑥┐(p∧q) ④⑤拒取式
⑦┐p∨┐q ⑥置换
⑧p
前提引入
⑨┐q
⑦⑧析取三段论
⑩q∧┐q ①⑨合取
由于最后一步q∧┐q0，即 (((p∧q)→r)∧(┐r∨s)∧┐s∧p)∧q0，所以推理正确。
16
例子
例3.4 在自然推理系统P中构造下面推理的证明： 若数a是实数，则它不是有理数就是无理数；若a不能表示 成分数，则它不是有理数；a是实数且它不能表示成分数。 所以a是无理数。
解：首先将简单命题符号化： 设p：a是实数。
q：a是有理数。 r：a是无理数。 s：a能表示成分数。
前提：p→(q∨r),┐s→┐q,p∧┐s 结论：r
