第一节、推理的形式结构

定义:设$A_1$,$A_2$,$\cdots$,$A_k$,B都是命题公式，若对于$A_1$,$A_2$,$\cdots$,$A_k$,B中出现的所有命题变项的任意一组赋值，或者$A_1$ $\wedge$ $A_2$ $\wedge$ $\cdots$ $\wedge$ $A_k$为假，或者当$A_1$ $\wedge$ $A_2$ $\wedge$ $\cdots$ $\wedge$ $A_k$ 为真时，B也为真。则称由前提$A_1$,$A_2$,$\cdots$,$A_k$推出结论B的推理是有效的或正确的。

  • 由前提$A_1$,$A_2$,$\cdots$,$A_k$推B的推理记作{A1， A2，…Ak}|-B ,这称为推理的形式结构。如果推理是正确的，记作{$A_1$,$A_2$,$\cdots$,$A_k$}|=B ，否则记作{$A_1$,$A_2$,$\cdots$,$A_k$}|$\neq$B。
  • 对于任一组赋值，只有前提为1和结论为0的取值才能使推理不是正确的
  • 从上一条可看出，推理正确并不是指结论是重言式。
  • 推理正确与否与诸前提的顺序无关

定理:命题公式$A_1$,$A_2$,$\cdots$,$A_k$推B的推理正确当且仅当($A_1$ $\wedge$ $A_2$ $\wedge$ $\cdots$ $\wedge$ $A_k$) $\to$B为重言式

证明重言式的三种方法：真值表法、等值演算法、主析取式法

九条推理定律(重言蕴含式):

A$\Rightarrow$(A$\vee$B)
(A$\wedge$B) $\Rightarrow$A; 化简
((A$\to$B)$\wedge$A) $\Rightarrow$ B; 假言推理
((A$\to$B)$\wedge\rceil$ B) $\Rightarrow\rceil$ A; 拒取式
((A$\vee$B)$\wedge\rceil$ A) $\Rightarrow$ B; 析取三段论
((A$\to$B)$\wedge$(B$\to$C)) $\Rightarrow$( (A$\to$C); 假言三段论
((A$\leftrightarrow$B)$\wedge$(B $\leftrightarrow$ C)) $\Rightarrow$((A $\leftrightarrow$(C); 等价三段论
(A$\to$B)$wedge$(C$to$D)$\wedge$(A$\vee$C) $\Rightarrow$(B$\vee$D). 构造性二难 (A$\to$B)$\wedge$($\rceil$A$\to$B)$\wedge$(A$\vee\rceil$ A) $\Rightarrow$ B. (特殊形式)
(A$\to$B)$\wedge$(C$\to$D)$\wedge$($\rceil$ B$\vee\rceil$ D) $\Rightarrow$($\rceil$A$\vee\rceil$ C). 破坏性二难

第二节、自然推理系统 P

定义(形式系统): 一个形式系统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 的形式演算系统。

形式系统分两类：

  1. 自然推理系统：特点是从任意给定的前提出发，利用推理规则进行推理演算，得到最后的命题公式是推理的结论，结论可能是重言式，也可能不是
  2. 公理推理系统：特点是从若干给定的公理出发，利用推理规则进行推理演算，得到的结论是系统中的重言式，称为定理。

**定义(自然推理系统 P)**：

  1. 字母表:(1)命题变项符号：p,q,r,…(2)联结词符号： $\rceil$,$\wedge$,$\vee$,$\to$,$\leftrightarrow$ （3）括号与逗号
  2. 合式公式
  3. 12条推理规则