数理逻辑 第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
个记号 6(v1,02,…,n)表示P中具有如下条件的公式 (1)v1,02,…,wm是互异的命题符号, (2)6中出现的命题符号都在1,v2,…,n中
✚ β(v1, v2, · · · , vn) P : (1) v1, v2, · · · , vn , (2) β v1, v2, · · · , vn . 5
个引理 设β(v1,02,…,m)为P中一个公式,a为P的一 指派.若a1,Q2,…,am是如下构造的公式序列 2当a(v2)=1时 2当a(v2)=0时 则(1)当((v1,v2,…,wn)=1时, a1,a2,…,anFβ (2)当((v1,02,…,wm)7=0时, C1,a2
✚ β(v1, v2, · · · , vn) P ✙ , σ P ✙ . α1, α2, · · · , αn : αi = vi σ(vi) = 1 ¬vi σ(vi) = 0 (1) (β(v1, v2, · · · , vn))σ = 1 , α1, α2, · · · , αn ` β (2) (β(v1, v2, · · · , vn))σ = 0 , α1, α2, · · · , αn ` ¬ β 6
引理的证明() 证:对β中所含的联结词→,→的个数d进行归纳证明 (1)当d=0时,β为某个命题符号;,B0=a(v;) (1.1)当B0=1时,a(v;)=1,从而a为v2 即a2就是B,故a1,Q2,…,mnF月 (1.2)当B0=0时,a;为v 即a;为B,故a1,a2,……,On+=
(I) : β ¬,→ d . (1) d = 0 , β vi, βσ = σ(vi). (1.1) βσ = 1 , σ(vi) = 1, αi vi. αi β, α1, α2, · · · , αn ` β. (1.2) βσ = 0 , αi ¬ vi. αi ¬ β, α1, α2, · · · , αn ` ¬ β. 7
引理的证明(I (2)假设定理对满足d<k的所有d都成立,下证定 理在d=k+1时也成立 (2.1)若B为(-31),则61中的联结词个d1=k (21.1)当60=1时,=0 由归纳假设知:a1,a2,…,an=月1, a1,a2,…,an (21.2)当=0时,=1. 由归纳假设知:a1,Q2,…,an+1, 由于1=1,故a1,a2,…,am}-61, 1,C2 =6
(II) (2) d ≤ k d , d = k + 1 . (2.1) β (¬ β1), β1 d1 = k. (2.1.1) βσ = 1 , βσ1 = 0. ✘: α1, α2, · · · , αn ` ¬ β1, α1, α2, · · · , αn ` β. (2.1.2) βσ = 0 , βσ1 = 1. ✘: α1, α2, · · · , αn ` β1, ✘β1 ` ¬¬ β1, α1, α2, · · · , αn ` ¬¬ β1, α1, α2, · · · , αn ` ¬ β. 8
引理的证明(ID (22)若为1→2,则1,62中所含联结词的个 数均<k (221)当=0时,=1,且B=0 由归纳假设知:a1,a2,…,am+1 1,2, 由例29知:}1→(2→(1→2) 故61,=2+-(1→2), 从而a1,a2,…,am}=(1→2) 即 C1,O2, 9
(III) (2.2) β β1 → β2, β1, β2 ≤ k. (2.2.1) βσ = 0 , βσ1 = 1, βσ2 = 0. ✘: α1, α2, · · · , αn ` β1 α1, α2, · · · , αn ` ¬ β2 ✘29 : ` β1→¬ β2→¬ (β1→β2, β1, ¬ β2 ` ¬ (β1→β2), α1, α2, · · · , αn ` ¬ (β1→β2), α1, α2, · · · , αn ` ¬ β. 9