数理逻辑 第26章§8 N与P的等价性 王捍贫 北京大学信息科学技术学院软件研究所
26 §8 N P ✁✂ ✄☎✆✝✞✟✠✝✡☛✝☞✌✍✎✏✑
复习 ●命题演算推理形式系统N和P 相同之处: 都由四个组成部分 公式的构成方式相同 都是为了推理 ●不同之处: 符号库不同 一公理与规则不同 推理形式不同:「上a与}a
• N P • ✒ – ✓ – – – · · · • ✒ – – – ✒Γ ` α ` α – · · · 1
8N与P的等价性 「Fpa当且仅当「卜Na
§8 N P Γ `P α Γ `N α 2
「pa→「卜Na 问题:当厂为无限公式集时, 「+pa有可能成立(如当a∈「时) 但「卜Na不可能成立
Γ `P α ⇒ Γ `N α ✔✒Γ ✕ Γ `P α ( α ∈ Γ ). Γ `N α ✖ 3
定理13 设∑,a分别为P中公式集与公式,若∑Fpa,则存 在∑的有限子集Σ0≤∑,使得∑0pa 证明思路:尽管前提Σ可能有无限多个,但由于证明 过程是有限的,故在证明过程中用到的前提必定是 有限的 证:设a1,a2,…,αm(=α)是在前提∑下推 出a的一个证明. 令∑0=∑∩(a1,a2 则a1,a2,…,αn也是在前提Σ0下推出a的一个 证明,故∑0pa.从而∑0即为所求
13 Σ, α P , Σ `P α, Σ Σ0 ⊆ Σ, Σ0 `P α. ✗✘: Σ , ✙ , . : α1, α2, · · · , αn(= α) Σ α ✚ . Σ0 = Σ ∩ {α1, α2, · · · , αn}, α1, α2, · · · , αn Σ0 α ✚ , Σ0 `P α. Σ0 ✖ 4