数理逻辑 第26章§10 可靠性、和谐性与完备性 王捍贫 北京大学信息科学技术学院软件研究所
26 §10 ✁✂✄ ☎✆✝✞✟✠✡✞☛☞✞✌✍✎✏✑✒
复习 构造逻辑的过程: 命题演算推理形式系统P(和N)一语法. ●语法的核心是推理:}a? P是符号演算。 公式的含义:真、假、永真等一语义 ●语义的核心是公式的永真性. 逻辑=语法+语义
✓ • P( N) — . • : ` α? • P ✔ • : ✕✕— . • . • = + . 1
可靠性、和谐性与完全性 可靠性:P的内定理都是重言式 完全性:所有重言式都是P的内定理 和诸性:P无矛盾,即无a能使-和--o同时成立
✖ : P ✗. : P ✗. : P , α ` α ` ¬α 2
可靠性 定理29若Pa,则a是重言式 证 郾Pa,故存在a在P中的证明序列a1,a2,…,am, 下对(1<<m)归纳证明每个a都是重言式 (1)若=1,a1必为公理,由定理17知a1为重言式 (2)假设a1,Q2,…,Qz-1都是重言式,下证a;也是 (21)若a;是公理,则a为重言式 (22)若a是由a;ak(1≤jk<)用分离规 则(M)得到的.不妨设αk为a;→a;:由归纳假设 知a;ak是重言式.由定理18知a也是重言式
29 `P α, α . : `P α, α P α1, α2, · · · , αn, i (1 ≤ i ≤ n) αi . (1) i = 1, α1 , ✘17 α1 (2) α1, α2, · · · , αi−1 , αi . (2.1) αi , αi . (2.2) αi ✘αj, αk (1 ≤ j, k < i) (M) . αk αj → αi. ✘ αj, αk . ✘18 αi . 3
和谐性 定理30对P的任何公式a,卜pa与hp-a不能同时 成立 证 若不然,则a与_a均为重言式 从而对P的任一个指派σ,a=(a)7=1 但(-a)0=1-a=0≠a,矛盾 注意:P中可能存在某个公式a使得a与-a均不是 内定理. 推论10P中至少有一个公式不是内定理
30 P α, `P α `P ¬α . : , α ¬ α . P ✙ σ, ασ = (¬ α)σ = 1. (¬ α)σ = 1 − ασ = 0 6= ασ, . : P α α ¬ α ✗. 10 P ✙ ✗. 4