数理逻辑 第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
简单性质 (1)对任意公式a和指派,a∈{0,1} (2)(3)7和(3→)的值如下表: a|0(a→6) 00 01 10 011 0 1101 与、→的真值表相同
(1) α σ, ασ ∈ {0, 1}. (2) (¬β)σ (β→γ)σ : ασ (¬ α)σ 0 1 1 0 ασ βσ (α→β)σ 0 0 1 0 1 1 1 0 0 1 1 1 ¬ ✓→ ✒ 5
aVβ的值 (1)a∨β是(-a)→β的简写 (aV)0 =((-a)→) =maX{1-(-a),} =maX{1-(1-a0),} 10 =maX{Qa,3”}
α ∨ β (1) α ∨ β (¬ α)→β . (2) (α ∨ β)σ = ((¬ α)→β)σ = max{1 − (¬α)σ, βσ} = max{1 − (1 − ασ), βσ} = max{ασ, βσ} ασ βσ (α ∨ β)σ 0 0 0 0 1 1 1 0 1 1 1 1 6
a∧8的值 (1)a∧β是-(a→-)的简写 (2) (aA)0 a0(a∧B) =1-ma×{1-a,()%}000 =1-max{1-a0,1-60} 01 0 =1-(1+max{-a,-6} =-(-min{a",60}) mina, Boj
α ∧ β (1) α ∧ β ¬ (α → ¬ β) . (2) (α ∧ β)σ = 1 − (α → ¬ β)σ = 1 − max{1 − ασ, (¬β)σ} = 1 − max{1 − ασ, 1 − βσ} = 1 − (1 + max{−ασ, −βσ} = −(− min{ασ, βσ}) = min{ασ, βσ} ασ βσ (α ∧ β)σ 0 0 0 0 1 0 1 0 0 1 1 1 7
a←β的值 (1)aφβ是-((a→B)→-()→a)的简写 (2)(a4B) =1-(a→6)→-(→a)0 =1-max{1-(a→),1-(→a)?} =min{(a→),(→a)} min max 1-a, B01, max1-B0a1 min max1,a+30)-ao max{1,a+}-B0} =maX{1,Q+60}+min{-a0,-B} max(1, a+Bo-maxa, Bo)
α ↔ β (1) α ↔ β ¬((α→β) → ¬(β→α)) . (2) (α ↔ β)σ = 1 − ((α→β) → ¬(β→α))σ = 1 − max{1 − (α→β)σ, 1 − (β→α))σ} = min{(α→β)σ, (β→α)σ} = min{max{1 − ασ, βσ}, max{1 − βσασ}} = min{max{1, ασ + βσ} − ασ, max{1, ασ + βσ} − βσ} = max{1, ασ + βσ} + min{−ασ, −βσ} = max{1, ασ + βσ} − max{ασ, βσ} 8
a←B的值表 a/0(a) 0 0101 1001
α ↔ β ασ βσ (α ↔ β)σ 0 0 1 0 1 0 1 0 0 1 1 1 9