命题逻辑再进阶.PDF

回顾 演绎定理 可靠性 公理独立性 紧致性 完全性 命题逻辑再进阶 哲学数学计算机中的逻辑课程(2016 年秋) 王彦晶 北大哲学系 2016 年11 月3 日 王彦晶 北大哲学系: 命题逻辑再进阶 回顾 演绎定理 可靠性 公理独立性 紧致性 完全性 回顾 演绎定理 可靠性 公理独立性 紧致性 完全性 王彦晶 北大哲学系: 命题逻辑再进阶 回顾 回顾 演绎定理 可靠性 公理独立性 紧致性 完全性 给定命题变元的集合pv=p p p , 命题逻辑的语言与语义: 1 2 3 命题逻辑(PropositionalLogic) 的语言: φ p φ φ φ 这 里p PV. 我们省略外层的括号及不会误读的括号. 令φ , φ , ′′ φ , , ⊤ 分别为φ , φ , φ φ , ′′ ′′ p p 及 p p 的简写(引号里要进一步把缩写的符号去掉). i 1 1 1 一个模型V 是从PV (定义域) 到0 1 (值域) 的函数, 告诉我们哪些 命题变元(最简单的公式) 是真, 哪些是假. 语义规定什么样的公式 (包括复杂的) 在什么样的模型上为真或假, 由可满足关系⊨ 给出. V ⊨ p Vp 1 V ⊨ φ V⊭ φ V ⊨ φ V⊭ φ 或者V ⊨ 王彦晶 北大哲学系: 命题逻辑再进阶 回顾 演绎定理 可靠性 公理独立性 紧致性 完全性 一些记法和术语 V ⊨ φ 读作“φ 在V 上为真” 或“V 满足φ”, 在所有模型上都为真的公 式称为有效的(valid)(记为⊨ φ). 命题逻辑的有效公式也称重言式(Tautology). 重言式是永远真的句 子, 那他们是“废话” 吗? 给定命题逻辑语言的公式集, 我们用V ⊨ 表示V 满足 里面 的所有公式. 如果每个满足 的模型也都满足φ, 我们就称φ 是 的语义后承(SemanticConsequence)(记为 ⊨ φ), 显然有效式是空 集的语义后承. 王彦晶 北大哲学系: 命题逻辑再进阶 回顾 演绎定理 可靠性 公理独立性 紧致性 完全性 命题逻辑的(一个) 公理系统(公理+ 推理规则) 我们想只用很少的几条公理和规则推出所有重言式. 公理(模式): A1 φ φ A2 φ φ φ A3 φ φ φ (反证法) 规则: 分离规则(ModusPonens): 从φ 以及φ 可得 有各种各样(在推理能力意义上) 等价的公理系统. 还有其他的证明 系统多用规则少用公理, 更容易做证明(SequentCalculus 等). 王彦晶 北大哲学系: