数理逻辑 第26章§9 赋值 王捍贫 北京大学信息科学技术学院软件研究所
26 §9 ✁✂ ✄☎✆✝✞✟✠✝✡☛✝☞✌✍✎✏✑
复习 ●命题演算推理形式系统N和P. ●N和P的核心是推理。 但在N或P中,符号、公式本身是没有含义的。 在推理过程中并不看公式的真假,而只看是否 为公理或规则。 ●形式系统是否具有预计的性质? 内定理是否一定是正确的? 什么叫“公式是正确的”?
• N P. • N P ✒ • N P , ✓✒ — ✔ ✒ • ? — ✕✖ ✗ • ✘✙✗ 1
89赋值 对形式系统P(等价地,N)进行赋值,就是对P的 每个公式分配一个值 首先要对每个命题符号分配一个值
§9 • P( , N) , P ✖ . • ✖ . 2
指派 定义17:形式系统P的一个指派是指如下的映射G {p0,p1,p2,…}→{0,1} σ()(i∈N)称为命题符号γ在指派σ下的值
17: P ✖ σ: σ : {p0, p1, p2, · · · }→{0, 1} σ(pi) (i ∈ N) pi σ . 3
赋值 定义18:设σ是形式系统P的一个指派,如下归纳定 义P中公式a在指派a下的值a: 若a是命题变元p,则a=a(2) ·若a是(),则a=1-60 ·若a是(→),则a=max{1-/,}
18: σ P ✖ , P α σ ασ: • α pi, ασ = σ(pi). • α (¬ β), ασ = 1 − βσ. • α (β→γ), ασ = max{1 − βσ, γσ}. 4