Page 127 - 《软件学报》2020年第12期

张玉志 等:面向完美回忆的时态认知逻辑 3793

c
c
c
① ¬ϕ.给定公式¬ϕ与任意Γ∈W.首先,M ,ΓB¬ϕ当且仅当 M ,ΓHϕ;其次,由归纳假设得,M ,ΓHϕ当且仅当
c
ϕ∉Γ;最后,由引理 2.3(2)可得,ϕ∉Γ当且仅当¬ϕ∈Γ.所以,M ,ΓB¬ϕ当且仅当¬ϕ∈Γ.
c
c
c
② ϕ∧ψ.首先,M ,ΓBϕ∧ψ当且仅当(M ,ΓBϕ并且 M ,ΓBψ);其次,根据归纳假设上述结论适用于ϕ与ψ可
c
c
得,M ,ΓBϕ∧ψ当且仅当(ϕ∈Γ且ψ∈Γ);最后,由引理 2.3(3)可得,M ,ΓBϕ∧ψ当且仅当(ϕ∧ψ)∈Γ.
t
③ K ϕ :
a
从右到左:假设 K ϕ Γ∈ .任取Φ中的任意极大一致集Δ.假设(Γ,Δ)∈R (a,t).根据对Φ中典范模型的
c
t
a
定义可知 K ϕ Δ∈ .因为 K ϕ →├ t ϕ 且Φ中的Δ是演绎封闭的,所以ϕ∈Δ.根据归纳假设可知:对Φ中任
t
a a
c c c t
意极大一致集Δ,M ,ΔBϕ.因为(Γ,Δ)∈R (a,t),所以根据语义定义可得 M ,Γ B K ϕ ;
a
t
c
c
c
从左到右:假设 M c ,Γ B K ϕ .所以对任意Δ∈W ,若(Γ,Δ)∈R (a,t),则 M ,ΔBϕ.假设集合Λ={¬ϕ}∪
a
t
t
t
{K χ∣ K χ t Γ ∈ } 是一致集.根据引理 2.2 可知,Λ是Φ中某个极大一致集Θ的子集.所以{K χ∣ K χ ∈
a a a a
c
Γ}⊆Θ.根据引理 2.3(7)可知(Γ,Θ)∈R (a,t).因为¬ϕ∈Λ并且Θ是Φ中极大一致集,所以ϕ∉Θ.根据归
c
c
c
t
纳假设可知 M ,ΘHϕ.因为 M c ,Γ B K ϕ 并且(Γ,Θ)∈R (a,t),所以 M ,ΘBϕ,得出矛盾.所以Λ={¬ϕ}∪
a
t
t
t
{K χ∣ K χ a t Γ ∈ } 不是一致集.所以{K χ∣ K χ t a Γ ∈ } ϕ ├ .根据引理 2.3(5)可知 Γ K ϕ ├ a t ,故 K ϕ Γ∈ ;
a
a
a
t
④ C ϕ .假设 C ϕ Γ∈ .由引理 2.3(8)可知, C ϕ Γ∈ 当且仅当从Γ开始的每个 B(t)-路径都是ϕ-路径.
t
t
B
B
B
根据归纳假设可知,从Γ开始的每个 B(t)-路径都是ϕ-路径,等价于是说从Γ开始的每个 B(t)-路径的Φ
t
t
中极大一致集上都成立ϕ是真的.根据语义定义可得, C ϕ Γ∈ 当且仅当 M c ,Γ B C ϕ .
B
B
综上情形(1)、情形(2),结论得证.
c
c
c
引理 2.5(典范模型性). 令Φ是某公式的闭包, K ϕ ,K ψ a n Φ ∈ ,m<n,M =〈W ,R ,V 〉是Φ的典范模型,Γ与Δ是Φ
c
m
a
c
中极大一致集.则 R (a,t)满足等价关系和单调递减.
c
证明:分别证明 R 满足如下两种情况.
c
(1) 等价关系:根据定义 2.3 中对 R 的定义容易得到;
c
c
(2) 单调递减:对任意 a∈A,m<n,都有 R (a,m)⊇R (a,n).
不妨假设 K ϕ Γ∈ 且 K ϕ Δ∉ ,即(Γ,Δ)∉R (a,m).由 Ax3,Ax4,Ax5 结合定义 2.1 和引理 2.3 容易得到:
m
m
c
a
a
m
n
m
n
KK ϕ Γ∈ 且 K ¬ K ϕ Δ∈ .
a a a a
c
所以,(Γ,Δ)∉R (a,n).证毕. □
t
t
引理 2.5 表明,定义 2.3 给出的典范模型是 S5 C 模型.
命题 2.1(完全性). 对任意公式ϕ,若Bϕ,则Aϕ.
证明:假设Gϕ.所以{¬ϕ}是一致集.由引理 2.2 可知,{¬ϕ}是闭包 cl(¬ϕ)中某个极大一致集Γ的子集.由引理
c
c
2.4 可知 M ,ΓB¬ϕ,即 M ,ΓHϕ.所以,Hϕ.
3 应 用
t
t
S5 C 系统能够刻画哪些认知变化规律?我们以分析如下情景作答.
• 情景
a 与 b 进入一个内设远程控制投掷硬币机器的大房间里.有人按下按钮,硬币随之旋转落下,进入桌上的一
个小盒子里,盒子关闭.而 a,b 二人都离硬币太远,以致于二人都没有看清楚硬币究竟哪面朝上.假定如下两点是
主体 a,b 之间的公共知识:① 落入盒子中的硬币要么正面朝上,要么反面朝上;② a,b 二人都不知道盒中硬币究
竟是正面朝上还是反面朝上.
然后,a 独自打开盒子,发现硬币正面朝上.b 看到 a 打开盒子,但 b 看不到盒子中的硬币.而且,a 也没有告诉
b 盒中硬币究竟是哪面朝上.
最后,b 在 a 面前打开盒子,两人都看到硬币正面朝上.