《初等子框架》word版.doc

补充1 初等子框架定义1.1 子框架 F = 是框架，W W，R = R | W框架F = 称为由W生成的F的子框架。任给x, yW，都有xRy 当且仅当 xRy。为了表示R和R之间的联系，可以将记为，对x, yW，可以将xRy记为xRy。一般的子框架和原框架没有什么联系，我们考虑一种特殊的子框架。如果从xW且xRy能够得到yW，则称W对R封闭。定义1.2 初等子框架 F = 是框架，W W，如果W对R封闭，则称子框架是F的初等子框架。定理1.3 F = 是框架，F = 是F的初等子框架。任给F上的赋值V，存在F上的赋值V，使得任给xW，任给公式a，都有V(a, x) = V(a, x)。证 任给F上的赋值V，取V如下：任给命题变项p，V(p, x) = V(p, x)如果xW 1否则归纳证明：任给xW，任给公式a，都有V(a, x) = V(a, x)。(1) a是命题变项，按定义V(a, x) = V(a, x)。(2) a = b，由归纳假设V(b, x) = V(b, x)，所以V(a, x) = 1 当且仅当 V(b, x) = 1当且仅当 V(b, x) = 0 当且仅当 V(b, x) = 0当且仅当 V(b, x) = 1 当且仅当 V(a, x) = 1。因此，V(a, x) = V(a, x)。(3) a = bg，由归纳假设V(b, x) = V(b, x), V(g, x) = V(g, x)，所以V(a, x) = 1 当且仅当 V(bg, x) = 1当且仅当 (V(b, x) = 1且V(g, x) = 1)当且仅当 (V(b, x) = 1且V(g, x) = 1)当且仅当 V(bg, x) = 1 当且仅当 V(a, x) = 1。因此，V(a, x) = V(a, x)。(4) a =b，由归纳假设任给yW，都有V(b,y) = V(b, y)。因为W对R封闭，所以任给xW，都有(yW且xRy) 当且仅当 (yW且xRy)。所以V(a, x) = 1 当且仅当 V(b, x) = 1当且仅当 y(如果yW且xRy则V(b, y) = 1)当且仅当 y(如果yW且xRy则V(b, y) = 1)当且仅当 y(如果yW且xRy则V(b, y) = 1)当且仅当 V(b, x) = 1 当且仅当 V(a, x) = 1。因此，V(a, x) = V(a, x)。定理1.4 F = 是F = 的初等子框架。任给公式a，如果任给F |= a，则F |= a。证 任给F上的赋值V，任给xW，由定理1.3得存在F上的赋值V，使得V(a, x) = V(a, x)，由F |= a得V(a, x) = 1，所以V (a, x) = 1，因此F |= a。定理1.5 F = 是框架，F = 是F的初等子框架。任给F上的赋值V，存在F上的赋值V，使得任给xW，任给公式a，都有V(a, x) = V(a, x)。证 任给F上的赋值V，取V如下：任给命题变项p，V(p, x) = V(p, x)。归纳证明同定理1.3。F = 是框架，G = Fi = | iI是F的初等子框架类（即任给iI，Fi都是F的初等子框架）。如果W =Wi | iI，则称G是F的完备的初等子框架类。定理1.6 F = 是框架，G = Fi = | iI是F的完备的初等子框架类，则F等价G（即任给公式a，都有F |= a 当且仅当 G |= a）。证 证明如果F |= a，则G |= a。任给FiG，Fi都是F的初等子框架，由定理1.4得Fi |= a，因此G |= a。证明如果G |= a，则F |= a。任给F上的赋值V，任给xW，由W =Wi | iI得存在iI，使得xWi，由定理1.5得存在Wi上的赋值Vi，使得Vi(a, x) = V(a, x)，由G |= a得Fi |= a，所以Vi(a, x) = 1，由Vi(a, x) = V(a, x)得V(a, x) = 1，因此F |= a。什么样的子框架类可以成为一个框架的完备的初等子框架类？定义1.7 相容 G = Fi = | iI是框架类，G称为相容的，如果G满足以下条件：(1) 任给i, jI，任给x, yWiWj，都有xRiy 当且仅当 xRjy。(2) 任给xWiWj，任给yWj，如果xRjy，则yWiWj。定理1.8 G = Fi = | iI是相容的框架类，令W =Wi | iI，R =Ri | iI，构造框架F = ，则G是完备的初等子框架类。证 证明任给iI，Fi是F的初等子框架。1. 证明是的子框架，即证明R | Wi = Ri，也就是证明任给x, yWi，都有xRy 当且仅当 xRiy。如果xRiy，由R的定义得xRy。如果xRy，由R的定义得存在jI，使得xRjy。由xRjy得x, yWj，所以xWiWj，yWj，由相容条件(2)得yWiWj，由相容条件(1)得xRiy 当且仅当 xRjy，因此xRiy。2. 证明是的初等子框架，即证明Wi对R是封闭的。任给xWi，yW，如果xRy，则存在jI，使得xRjy。由xRjy得x, yWj，所以xWiWj，yWj，由相容条件(2)得yWiWj，因此yWi。完备性显然。定理1.8中的框架称为相容的框架类G的并框架,记为FG。由定理1.6和定理1.8得：定理1.9 G是相容的框架类，则存在框架F，使得G和F等价。G = Fi = | iI是框架类，如果Wi | iI是不交的，则称G的不交的框架类。定理1.10 G是不交的框架类，则存在框架F，使得G和F等价。证 不交的框架类是相容的框架类。定义1.11 同构 F = 和F = 是两个框架。(1) f是W到W的双射，如果f保持关系不变（即xRy 当且仅当 f(x)Rf(y)），则称f是F到F的同构映射。(2) 如果存在F到F的同构映射，则称F和F同构，记为FF。定理1.12 同构是等价关系，即(1) 。(2) 如果，则。(3) 如果，则。证 (1) 恒等映射iW是到的同构映射。(2) 如果f是到的同构映射，则f -1是到的同构映射。(3) 如果f是到的同构映射，g是到的同构映射，则gf 是到的同构映射。定理1.13 F = 和F = 是两个框架，如果F同构F，则F等价F。证 取f是到，证明F |= a，则F |= a。任给F上赋值V，取F上赋值V如下：V(p, x) = 1 当且仅当 V(p, f(x) = 1，归纳证明：任给公式a，都有V(a, x) = V(a, f(x)。(1) a是命题变项，由V的定义得V(a, x) = V(a, f(x)(2) a = b，由归纳假设得V(b, x) = V(b, f(x)，所以V(a, x) = 1 当且仅当 V(b, x) = 1当且仅当 V(b, x) = 0 当且仅当 V(b, f(x) = 0当且仅当 V(b, f(x) = 1当且仅当 V(a, f(x) = 1。因此，V(a, x) = V(a, f(x)。(3) a = bg，由归纳假设V(b, x) = V(b, f(x), V(g, x) = V(g, f(x)，所以V(a, x) = 1 当且仅当 V(bg, x) = 1当且仅当 (V(b, x) = 1且V(g, x) = 1)当且仅当 (V(b, f(x) = 1且V(g, f(x) = 1)当且仅当 V(bg, f(x) = 1 当且仅当 V(a, f(x) = 1。因此，V(a, x) = V(a, x)。(4) a =b，由归纳假设任给yW，都有V(b,y) = V(b, y)，所以V(a, x) = 1 当且仅当 V(b, x) = 1当且仅当 y(如果yW且xRy则V(b, y) = 1)当且仅当 y(如果yW且xRy则V(b, f(y) = 1)当且仅当 y(如果f(y)W且f(x)Rf(y)则V(b,f(y) = 1)当且仅当 u(如果uW且f(x)Ru则V(b, u) = 1)当且仅当 V(b, f(x) = 1 当且仅当 V(a, x) = 1。因此，V(a, x) = V(a, x)。由F |= a得V(a, x) = 1，所以V(a, x) = 1，因此F |= a。从F同构F得F同构F，类似可证：F |= a，则F |= a。定理1.14 F = 是框架，令W(a) = | xW，R(a) 当且仅当 xRy，构造框架F(a) = ，则F和F(a)同构。证 取W到W(a)的双射f：W到W(a) f(x) = ，则xRy 当且仅当 R(a) 当且仅当 f(x)Rf(y)，因此f是F到F(a)的同构映射。定理1.15 S是框架类，存在不交的框架类G，使得S等价G。证 设S = Fi = | iI，取G = Fi(i) = | iI，任给iI，Fi同构Fi(i)，所以Fi等价Fi(i)，因此S等价G。显然G是不交的框架类。由定理1.10和定理1.15得：定理1.16 S是框架类，存在框架F，使得S等价F。定义1.17 f是一个关于框架的性质。如果存在公式a，使得F |= a 当且仅当 F有性质f，则称f是模态可定义的。定义1.18 f是一个关于框架的性质。f满足以下条件：任给相容的框架类G，如果任给FG，F都有性质f，则G的并框架FG也有性质f。就称f对于并框架保持。定理1.19 f是一个关于框架的性质，如果f是模态可定义的，则f对于并框架保持。证 取公式a，使得F |= a 当且仅当 F有性质f。任给相容的框架类G，如果任给FG，F都有性质f，则F |= a，所以G |= a，由定理1.8得FG |= a，所以FG有性质f。因此，f对于并框架保持。定理1.20 全通性不是模态可定义的。证 取a b，取F1 = a, ，F2 = b, ，它们都有全通性。框架类G = F1, F2是相容的，并框架FG = a, b, , ，没有全通性。因