离散数学与组合数学汇总

推理的形式结构

自然推理系统P

定义3.1 设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为重言式

注意: 推理正确不能保证结论一定正确

判断推理是否正确的方法:

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) 破坏性二难

每个等值式可产生两个推理定律。如，由 A ⇔ ¬¬A可产生 A ⇒ ¬¬A和 ¬¬A ⇒ A

定义3.2 一个形式系统 I 由下面四个部分组成： (1) 非空的字母表，记作 A(I). (2) A(I) 中符号构造的合式公式集，记作 E(I). (3) E(I) 中一些特殊的公式组成的公理集，记作 AX(I). (4) 推理规则集，记作 R(I). 记I=, 其中是 I 的 形式语言系统, 是 I 的形式演算系统.

自然推理系统: 无公理, 即AX(I)=Ø 公理推理系统 推出的结论是系统中的重言式, 称作定理

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

设前提A1, A2,…, Ak,结论B及公式序列C1, C2,…, Cl. 如果每 一个Ci(1