第3章命题逻辑的推理理论主要内容1. 推理的形式结构：①推理的前提②推理的结论③推理正确④有效结论2. 判断推理是否正确的方法：①真值表法②等值演算法③主析取范式法3. 对于正确的推理，在自然推理系统P中构造证明4. ①自然推理系统P的定义②自然推理系统P的推理规则：前提引入规则、结论引入规则、置换规则、假言推理规则、附加规则、化简规则、拒取式规则、假言三段式规则、构造性二难规则、合取引入规则。

③附加前提证明法④归谬法学习要求1. 理解并记住推理的形式结构的三种等价形式，即①{A1,A2,…,A k}├B②A1∧A2∧…∧A k→B③前提与结论分开写：前提：A1,A2,…,A k结论：B在判断推理是否正确时，用②；在P系统中构造证明时用③。

2. 熟练掌握判断推理是否正确的三种方法（真值表法，等值演算法，主析取范式法）。

3. 牢记P系统中的各条推理规则。

4. 对于给定的正确推理，要求在P系统中给出严谨的证明序列。

5. 会用附加前提证明法和归谬法。

3.1 推理的形式结构定义3.1设A1,A2,…,A k和B都是命题公式，若对于A1,A2,…,A k和B中出现的命题变项的任意一组赋值，或者A1∧A2∧…∧A k为假，或者当A1∧A2∧…∧A k为真时，B也为真，则称由前提A1,A2,…,A k推出B的推理是有效的或正确的，并称B是有效结论。

二、有效推理的等价定理定理3.1命题公式A1,A2,…,A k推B的推理正确当且仅当(A1∧A2∧…∧A k )→B为重言式。

A k为假，或者A1∧A2∧…∧A k和B同时为真，这正符合定义3.1中推理正确的定义。

由此定理知，推理形式：前提：A1,A2,…,A k结论：B是有效的当且仅当(A1∧A2∧…∧A k)→B为重言式。

(A1∧A2∧…∧A k)→B称为上述推理的形式结构。

从而推理的有效性等价于它的形式结构为永真式。

于是，推理正确{A1,A2,…,A k} B可记为A1∧A2∧…∧A k B其中同一样是一种元语言符号，用来表示蕴涵式为重言式。

而判断命题公式永真性有三个方法：1．真值表法2．等值演算法3．主析取范式法三、重言蕴涵式由上一个小节可以看出：形如A→B的重言式在推理中十分重要。

若A→B为重言式，则称B为A的推论，记为A B，下面是几个重要的重言蕴涵式及其名称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) 破坏性二难这几个蕴涵式在下节中将起重要的作用。

3.2 自然推理系统P一、形式推理系统我们将前述推理用更严谨的形式推理系统描述出来。

定义3.2一个形式系统I由下面四个部分组成：（1）非空的字符表集，记作A(I)。

（2）A(I)中符号构造的合式公式集，记作E(I)。

（3）E(I)中一些特殊的公式组成的公理集，记作A X(I)。

（4）推理规则集，记作R(I)。

可以将I记为<A(I),E(I),A X(I),R(I)>.其中<A(I),E(I)>是I的形式语言系统，<A X(I),R(I)>为I的形式演算系统。

形式系统一般分为两类。

一类是自然推理系统，它的特点是从任意给定的前提出发，应用系统中的推理规则进行推理演算，得到的最后命题公式是推理的结论（有时称为有效的结论，它可能是重言式，也可能不是）。

另一类是公理推理系统，它只能从若干给定的公理出发，应用系统中推理规则进行推理演算，得到的结论是系统中的重言式，称为系统中的定理。

二、自然推理系统PP是一个自然推理系统，因而没有公理。

故P只有三个部分。

定义3.3自然推理系统P定义如下：1．字母表（1）命题变项符号：p，q，r，…,p i，q i，r i，…（2）联结词符号：┐,∧,∨,→,（3）括号和逗号：( , )，，2．合式公式同定义1.63．推理规则（1）前提引入规则：在证明的任何步骤上都可以引入前提。

（2）结论引入规则：在证明的任何步骤上所得到的结论都可以作为后继证明的前提。

（3）置换规则：在证明的任何步骤上，命题公式中的子公式都可以用与之等值的公式置换，得到公式序列中的又一个公式。

由九条推理定律和结论引入规则还可以导出以下各条推理定律。

（4）假言推理规则（或称分离规则）：若证明的公式序列中已出现过A→B和A，则由假言推理定律(A→B)∧A B可知，B是A→B和A的有效结论。

由结论引入规则可知，可将B引入到命题序列中来。

用图式表示为如下形式：以下各条推理定律直接以图式给出，不再加以说明。

（5）附加规则：（6）化简规则：（7）拒取式规则：（8）假言三段论规则：（9）析取三段论规则：（10）构造性二难推理：（11）破坏性二难推理规则：（12）合取引入规则：本条规则说明，若证明的公式序列中已出现A和B ，则可将A∧B引入序列中。

这就完成了P的定义。

三、P中的证明P中的证明就是由一组P中公式作为前提，利用P中的规则，推出结论。

当然此结论也为P中公式。

例在自然推理系统P中构造下面推理的证明：(1)前提：p∨q,q→r,p→s,┐s结论：r∧(p∨q)(2)前提：┐p∨q, r∨┐q ,r→s结论：p→s解 (1)证明：①p→s 前提引入②┐s 前提引入③┐p ①②拒取式④p∨q 前提引入⑤q ③④析取三段论⑥q→r 前提引入⑦r ⑤⑥假言推理⑧r∧(p∨q) ⑦④合取此证明的序列长为8，最后一步为推理的结论，所以推理正确，r∧(p∨q)是有效结论。

(2)证明：①┐p∨q 前提引入②p→q ①置换③r∨┐q 前提引入④q→r ③置换⑤p→r ②④假言三段论⑥r→s 前提引入⑦p→s ⑤⑥假言三段论从最后一步可知推理正确，p→s是有效结论。

可以在自然推理系统P中构造数学和日常生活中的一些推理，所得结论都是有效的，即当各前提的合取式为真时，结论必为真。

例在自然推理系统P中构造下面推理的证明：若数a是实数，则它不是有理数就是无理数；若a不能表示成分数，则它不是有理数；a是实数且它不能表示成分数。

所以a是无理数。

解首先将简单命题符号化：设p：a是实数。

q：a是有理数。

r：a是无理数。

s：a能表示成分数。

前提：p→(q∨r), ┐s→┐q, p∧┐s结论：r证明：①p∧┐s 前提引入②p ①化简③┐s ①化简④p→(q∨r) 前提引入⑤q∨r ②④假言推理⑥┐s→┐q 前提引入⑦┐q ③⑥假言推理⑧r ⑤⑦析取三段论P中证明的两个常用技巧：1．附加前提证明法2．归谬法四、附加前提法有时推理的形式结构具有如下形式（A1∧A2∧…∧A k)→(A→B) （3.5）（3.5）式中结论也为蕴涵式。

此时可将结论中的前件也作为推理的前提，使结论只为B。

即，将（3.5）化为下述形式(A1∧A2∧…∧A k∧A)→B （3.6）其正确性证明如下：（A1∧A2∧…∧A k)→(A→B)）┐(A1∧A2∧…∧A k)∨(┐A∨B）┐(A1∧A2∧…∧A k∨┐A)∨B┐(A1∧A2∧…∧A k∧A)∨B(A1∧A2∧…∧A k∧A)→B因为（3.5）式与（3.6）式是等值的，因而若能证明（3.6）式是正确的，则（3.5）式也是正确的。

用形式结构（3.6）式证明，将A称为附加前提，并称此证明法为附加前提证明法。

例在自然推理系统P中构造下面推理的证明。

如果小张和小王去看电影，则小李也去看电影；小赵不去看电影或小张去看电影；小王去看电影。

所以，当小赵去看电影时，小李也去看电影。

解将简单命题符号化：设p:小张去看电影。

q:小王去看电影。

r:小李去看电影。

s:小赵去看电影。

前提：(p∧q)→r,┐s∨p,q结论：s→r证明：用附加前提证明法。

①s 附加前提引入②┐s∨p 前提引入③p ①②析取三段论④(p∧q)→r 前提引入⑤q 前提引入⑥p∧q ③⑤合取⑦r ④⑥假言推理思考：不用附加前提证明法构造例3.5的证明。

五、归谬法在构造形式结构为(A1∧A2∧…∧A k)→B的推理证明中，如果将┐B作为前提能推出矛盾来，比如说得出(A∧┐A)，则说明推理正确。

其原因如下：(A1∧A2∧…∧A k)→B┐(A1∧A2∧…∧A k)∨B┐(A1∧A2∧…∧A k∧┐B)若(A1∧A2∧…∧A k∧┐B)为矛盾式，正说明(A1∧A2∧…∧A k)→B为重言式，即(A1∧A2∧…∧A k)B,故推理正确。

例在自然推理系统P中构造下面推理的证明。

如果小张守第一垒并且小李向B队投球，则A队将取胜；或者A队未取胜，或者A 队获得联赛第一名；A队没有获得联赛的第一名；小张守第一垒。

因此，小李没有向B 队投球。

解先将简单命题符号化。

设p:小张守第一垒。

q:小李向B队投球。

r:A队取胜。

s:A队获得联赛第一名。

前提：(p∧q)→r,┐r∨s,┐s ,p结论：┐q证明：用归谬法①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，所以推理正确。