第三章 命题演算
判定有效推理形式的方法：真值表法、归谬赋值法。 生成有效推理形式的方法：公理系统、自然推演系统。 3.1 公理系统
公理系统的构成：
（1）符号库（初始符号） （2）形成规则（符号的使用） （3）公理（推演的起点） （4）变形规则（推演规则） 3.2 命题演算的公理系统 L （1）初始符号：p1 ,p2 ,?；? ,→；( ,) （2）形成规则：
(i) p1 ，p2 ，?是合式公式；
(ii) 若A ，B 是任意合式公式，则( ? A ), ( A →B ) 是合式公式； (iii）所有合式公式由（i）,（ii）生成。 合式公式（well-formed formula）（wf.）：合于形成规则的式子（相当于合乎语
法的句子）。 （3）公理模式：（设A，B，C 是任意合式公式） L1 (( A →( B →A )))
L2 (( A →( B →C ))→(( A →B )→( A →C ))) L3 ((( ? A )→( ? B ))→( B →A )) （4）推演规则：（分离规则，MP ） 从( A →B )和 A 可得 B . L 中的证明：
L 的合式公式序列，其中每个合式公式满足下列条件之一： （i）L 的公理，
（ii）由在先的两个合式公式用 MP 得出。
这一序列中的最后一个合式公式称为L中的定理。
例1 证（ p1 → p1 ） 例2 证（（? p1 ）→（ p1 → 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）初始符号：p1 ,p2 ,?；? ,→ ；（,） （2）形成规则：
(i)p1，p2，?是合式公式；
(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 ）→（ p1 → p2 ））
命题演算的自然推演系统C与命题演算的公理系统L等价。
第三章提纲
