第三章提纲
第三章 命题演算
判定有效推理形式的方法：真值表法、归谬赋值法。
生成有效推理形式的方法：公理系统、自然推演系统。
3.1 公理系统
公理系统的构成：
（1）符号库（初始符号）
（2）形成规则（符号的使用）
（3）公理（推演的起点）
（4）变形规则（推演规则）
3.2 命题演算的公理系统 L
（1）初始符号：p 1 ,p 2 , „；¬ ,→；( ,)
（2）形成规则：
(i) p1 ，p 2 ，„是合式公式；
(ii) 若A ，B 是任意合式公式，则( ¬ A ), ( A →B ) 是合式公式； (iii）所有合式公式由（i ）, （ii ）生成。
合式公式（well-formed formula）（wf . ）：合于形成规则的式子（相当于合乎语
法的句子）。
（3）公理模式：（设A ，B ，C 是任意合式公式）
L 1 (( A →( B →A )))
L 2 (( A →( B →C )) →(( A →B ) →( A →C )))
L 3 ((( ¬ A ) →( ¬ B )) →( B →A ))
（4）推演规则：（分离规则，MP ）
从( A →B ) 和 A 可得 B .
L 中的证明：
L 的合式公式序列，其中每个合式公式满足下列条件之一：
（i ）L 的公理，
（ii ）由在先的两个合式公式用 MP 得出。
这一序列中的最后一个合式公式称为L 中的定理。
例1 证（ p1 → p1 ）
例2 证（（¬ p1 ）→（ p 1 → p2 ））
其他符号的引入（定义）；已证定理的应用；其他推演规则的导出。
L中的推演：设Γ 是 L 中的合式公式（不必是 L 中的公理）的集合。Γ 中的
合式公式作为临时公理参与 L 中的证明，称为 L 中从Γ的推演，得到的结果 A 称为L 中Γ 的推论。记为 Γ┝ A
L
L 中的定理 A 可记为 Ø┝ A ，或 ┝ A
L L
3.3 公理系统的性质和评价及其意义
L 系统的性质
（1）可靠性：L 的定理都是重言式。
（2）完全性：对应于复合命题有效推理形式的重言式都是 L 的定理。
L 系统的可靠性和完全性使得：L 的定理当且仅当是第二章中的重言式，即：
L 的定理集与第二章中的重言式集完全相同。
（3）公理的独立性：L 的各条公理不能互相推出。
斯宾诺莎（1632—1677）：《用几何学方法作论证的伦理学》。
“凡是想在学识方面超群绝伦的人都一致认为：在研究和传授学问时，数学方
法，即从定义、公设和公理推出结论的方法，乃是发现和传授真理最好的和最可靠的方法。这是千真万确的。” ——路德维希·梅耶尔：斯宾诺莎《笛卡儿哲学原理（依几何学方式证明）》序（1663年）。
3.4 命题演算的自然演绎系统
通过自然演绎系统进行证明和推演的步骤：
（1）引入假设；
（2）使用给定的接近于日常思维的推演规则进行推演；
（3）最后若按照规则消去假设，则得到不依赖于假设的一般定理；若保留假
设，则得到依赖于假设之下的推论。
命题演算的自然演绎系统C
（1）初始符号：p 1 ,p 2 , „；¬ ,→ ；（, ）
（2）形成规则：
(i)p1，p 2，„是合式公式；
(ii)若A ，B 是任意合式公式，则( ¬ A ),( A →B ) 是合式公式；
(iii）所有合式公式由（i ）, （ii ）生成.
（3）推演规则：（设A ，B 是任意合式公式）
（i) 假设引入
〇 A
｜
(ii) 重述
┇
｜ A
｜┇
｜〇 B
｜｜┇
｜｜ A
（ⅲ） 重复
┇
｜ A
｜┇
｜ B
｜┇
｜ A
(ⅳ) →引入
〇 A
｜
｜┇ ｜
｜ B
( A → B )
（ⅴ） ¬ 消去 〇( ¬ A )
｜ ┇
｜ B
｜ ( ¬ B )
A
(ⅵ) → 消去
｜ ┇
｜( A → B ) ｜ A ｜ B
例1 证（ p1 → p1 ） 例2 证（（¬ p1 ）→（ p 1 → p2 ））
命题演算的自然推演系统C 与命题演算的公理系统L 等价。