离散数学-3 命题逻辑的推理理论

定义3.1 设A₁, A₂, …, A_k, B为命题公式. 若对于每组赋值，A₁A₂…A_k为假，或当A₁A₂…A_k为真时，B也为真，则称由前提A₁, A₂, …, A_k推出结论B的推理是有效的或正确的, 并称B是有效结论.

推理正确并不能保证结论一定成立；前提不正确，不论结论是否成立，都说推理正确。

定理3.1 由命题公式A₁, A₂, …, A_k推B的推理正确当且仅当A₁A₂…A_kB为重言式

定理说明：

. {A₁, A₂, …, A_k} ├ B 等同于蕴含式A₁A₂…A_kB

{A₁, A₂, …, A_k} ╞ B 等同于 A₁A₂…A_kB

推理的形式结构

1、 {A₁, A₂, …, A_k}├ B；若推理正确, 记为{A₁,A₂,,A_n}╞ B

2、A₁A₂…A_kB；若推理正确, 记为A₁A₂ … A_kB

3、前提： A₁, A₂, … , A_k结论： 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) B 构造性二难(特殊形式)

9. (AB)(CD)( BD)  (AC) 破坏性二难

另外，每个等值式可产生两个推理定律

定义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 的形式演算系统.

自然推理系统：无公理, 即A_X(I)=

公理推理系统：推出的结论是系统中的重言式, 称作定理

定义3.3 自然推理系统 P 定义如下:

1. 字母表

(1) 命题变项符号：p, q, r, …, p_i, q_i, r_i, …

(2) 联结词符号：, , , , 

(3) 括号与逗号：( ), ，

2. 合式公式（同定义1.6）

3. 推理规则

(1) 前提引入规则(P) ：在证明的任何步骤都可以引入前提。

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

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

（4）附加前提规则（CP规则）：若从A和B能有效地推出C，则从A可有效地推出B C。（通常在结论为蕴涵式时使用）

题型

1、用等值演算法判断推理是否正确

将简单语句符号化，找出前提与结论，写成推理的型式结构2，用等值演算法进行判断。

推理的型式结构2、A₁A₂…A_kB

理解并记住推理形式结构的两种形式：

1. (A₁A₂…A_k)B

2. 前提：A₁, A₂, … , A_k

结论：B

2、用主析取范式法判断推理是否正确

一般，对不知是否正确的推理，可先用等值演算法，若推理形式结构为*1，则推理正确；否则，对化简的结果观察其成假赋值，从而判断推理不正确，或者进一步求出主析取范式来进行判断。另外如果所含命题变项比较少，用真值表法不易出错。

3、在自然推理系统中证明推理

用直接证明法

用附加前提证明法：适用于结论为蕴涵式欲证：前提：A₁, A₂, …, A_k结论：CB；等价地证明前提：A₁, A₂, …, A_k, C 结论：B

用反证法（归谬法）：将结论的否定式作为附加前提引入并推出矛盾式的证明方法称做归谬法。

4、在自然推理系统中构造用自然语言描述的推理

解题的步骤一般是：

（1）将简单陈述句符号化

（2）写出前提和结论

（3）在自然推理系统中给出证明

5、用消解序列（消解证明法）构造推理证明