第3章 命题逻辑的推理理论
主要内容
1. 推理的形式结构：
①推理的前提 ②推理的结论 ③推理正确 ④有效结论
2. 判断推理是否正确的方法：
①真值表法 ②等值演算法 ③主析取范式法
3. 对于正确的推理，在自然推理系统P中构造证明 4. ①自然推理系统P的定义
②自然推理系统P的推理规则：
前提引入规则、结论引入规则、置换规则、假言推理规则、附加规则、化简规则、拒取式规则、假言三段式规则、构造性二难规则、合取引入规则。 ③附加前提证明法 ④归谬法
学习要求
1. 理解并记住推理的形式结构的三种等价形式，即
①{A1,A2,…,Ak}├B ②A1∧A2∧…∧Ak→B ③前提与结论分开写： 前提：A1,A2,…,Ak 结论：B
在判断推理是否正确时，用②；在P系统中构造证明时用③。
2. 熟练掌握判断推理是否正确的三种方法（真值表法，等值演算法，主析取范式法）。 3. 牢记P系统中的各条推理规则。
4. 对于给定的正确推理，要求在P系统中给出严谨的证明序列。 5. 会用附加前提证明法和归谬法。
3.1 推理的形式结构
定义
3.1 设A1,A2,…,Ak和B都是命题公式，若对于A1,A2,…,Ak和B中出现的命题变
项的任意一组赋值，或者A1∧A2 ∧…∧Ak为假，或者当A1∧A2 ∧…∧Ak为真时，B也为真，则称由前提A1,A2,…,Ak推出B的推理是有效的或正确的，并称B是有效结
论。
二、有效推理的等价定理
定理3.1 命题公式A1,A2,…,Ak推B的推理正确当且仅当 (A1∧A2∧…∧Ak )→B 为重言式。
Ak为假，或者A1∧A2∧…∧Ak和B同时为真，这正符合定义3.1中推理正确的定义。 由此定理知，推理形式：
前提：A1,A2,…,Ak 结论：B
是有效的当且仅当(A1∧A2∧…∧Ak)→B为重言式。(A1∧A2∧…∧Ak)→B称为上述推理的形式结构。从而推理的有效性等价于它的形式结构为永真式。于是，推理正确 {A1,A2,…,Ak}可记为
A1∧A2∧…∧Ak其中
同
B B
一样是一种元语言符号，用来表示蕴涵式为重言式。
而判断命题公式永真性有三个方法： 1． 真值表法
2． 等值演算法
3． 主析取范式法
三、重言蕴涵式
由上一个小节可以看出：形如A→B的重言式在推理中十分重要。
若A→B为重言式，则称B为A的推论，记为A式及其名称
B，下面是几个重要的重言蕴涵
1．A(A∨B) 附加律
2.(A∧B)A 化简律
3.(A→B)∧AB 假言推理
4.(A→B)∧┐B┐A 拒取式
5.(A∨B)∧┐BA 析取三段论
6.(A→B)∧(B→C)(A→C) 假言三段论
7.(AB)∧(BC)(AC) 等价三段论
8.(A→B)∧(C→D)∧(A∨C)(B∨D) 构造性二难 (A→B)∧(┐A→B)∧(A∨┐A)
9.(A→B)∧(C→D)∧(┐B∨┐D)
B 构造性二难 (特殊形式)
(┐A∨┐C) 破坏性二难
这几个蕴涵式在下节中将起重要的作用。
3.2 自然推理系统 P
一、形式推理系统
我们将前述推理用更严谨的形式推理系统描述出来。 定义
3.2 一个形式系统I由下面四个部分组成：
（1） 非空的字符表集，记作A(I)。
（2） A(I)中符号构造的合式公式集，记作E(I)。
（3） E(I)中一些特殊的公式组成的公理集，记作AX(I)。
（4） 推理规则集，记作R(I)。
可以将I记为
形式系统一般分为两类。一类是自然推理系统，它的特点是从任意给定的前提出发，应用系统中的推理规则进行推理演算，得到的最后命题公式是推理的结论（有时称为有效的结论，它可能是重言式，也可能不是）。另一类是公理推理系统，它只能从若干给定的公理出发，应用系统中推理规则进行推理演算，得到的结论是系统中的重言式，称为系统中的定理。
二、自然推理系统 P
P是一个自然推理系统，因而没有公理。故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，
则由假言推理定律(A→B)∧AB可知，B是A→B和A的有效结论。由结论引入规则
可知，可将B引入到命题序列中来。用图式表示为如下形式：
以下各条推理定律直接以图式给出，不再加以说明。
（5） 附加规则：
（6） 化简规则：
（7） 拒取式规则：
（8） 假言三段论规则：
（9） 析取三段论规则：
（10） 构造性二难推理：
（11） 破坏性二难推理规则：
离散数学结构 第3章 命题逻辑的推理理论复习
