《初等子框架》word版

1、.補充1 初等子框架定義1.1 子框架 F = <W, R>是框架，W¢ Í W，R¢ = R | W¢框架F¢ = <W¢, R¢>稱為由W¢生成的F的子框架。任給x, yÎW¢，都有xRy 當且僅當 xR¢y。為了表示R和R¢之間的聯(lián)系，可以將<W¢, R¢>記為<W¢, R>，對x, yÎW¢，可以將xR¢y記為xRy。一般的子框架和原框架沒有什么聯(lián)系，我們考慮一

2、種特殊的子框架。如果從xÎW¢且xRy能夠得到y(tǒng)ÎW¢，則稱W¢對R封閉。定義1.2 初等子框架 F = <W, R>是框架，W¢ Í W，如果W¢對R封閉，則稱子框架<W¢, R¢>是F的初等子框架。定理1.3 F = <W, R>是框架，F¢ = <W¢, R¢>是F的初等子框架。任給F¢上的賦值V¢，存在F上的賦值V，使得任給xÎW¢，任給公式a，都有V(a, x) = V

3、¢(a, x)。證 任給F¢上的賦值V¢，取V如下：任給命題變項p，V(p, x) = V¢(p, x)如果xÎW¢ 1否則歸納證明：任給xÎW¢，任給公式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)

4、 = 0當且僅當 V¢(Øb, x) = 1 當且僅當 V¢(a, x) = 1。因此，V(a, x) = V¢(a, x)。(3) a = bÙg，由歸納假設V(b, x) = V¢(b, x), V(g, x) = V¢(g, x)，所以V(a, x) = 1 當且僅當 V(bÙg, x) = 1當且僅當 (V(b, x) = 1且V(g, x) = 1)當且僅當 (V¢(b, x) = 1且V¢(g, x) = 1)當且僅當 V¢(bÙg, x) = 1 當且僅當 V&

5、#162;(a, x) = 1。因此，V(a, x) = V¢(a, x)。(4) a =b，由歸納假設任給yÎW¢，都有V(b,y) = V¢(b, y)。因為W¢對R封閉，所以任給xÎW¢，都有(yÎW¢且xR¢y) 當且僅當 (yÎW且xRy)。所以V(a, x) = 1 當且僅當 V(b, x) = 1當且僅當 "y(如果yÎW且xRy則V(b, y) = 1)當且僅當 "y(如果yÎW¢且xR¢y則V(b, y) =

6、 1)當且僅當 "y(如果yÎW¢且xR¢y則V¢(b, y) = 1)當且僅當 V¢(b, x) = 1 當且僅當 V¢(a, x) = 1。因此，V(a, x) = V¢(a, x)。定理1.4 F¢ = <W¢, R¢>是F = <W, R>的初等子框架。任給公式a，如果任給F |= a，則F¢ |= a。證 任給F¢上的賦值V¢，任給xÎW¢，由定理1.3得存在F上的賦值V，使得V(a, x) = V&#

7、162;(a, x)，由F |= a得V(a, x) = 1，所以V¢ (a, x) = 1，因此F¢ |= a。定理1.5 F = <W, R>是框架，F¢ = <W¢, R¢>是F的初等子框架。任給F上的賦值V，存在F¢上的賦值V¢，使得任給xÎW¢，任給公式a，都有V¢(a, x) = V(a, x)。證 任給F上的賦值V，取V¢如下：任給命題變項p，V¢(p, x) = V(p, x)。歸納證明同定理1.3。F = <W, R>是框

8、架，G = Fi = <Wi, Ri> | iÎI是F的初等子框架類（即任給iÎI，Fi都是F的初等子框架）。如果W =Wi | iÎI，則稱G是F的完備的初等子框架類。定理1.6 F = <W, R>是框架，G = Fi = <Wi, Ri> | iÎI是F的完備的初等子框架類，則F等價G（即任給公式a，都有F |= a 當且僅當 G |= a）。證 證明如果F |= a，則G |= a。任給FiÎG，Fi都是F的初等子框架，由定理1.4得Fi |= a，因此G |= a。證明如果G |= a，則F |=

9、a。任給F上的賦值V，任給xÎW，由W =Wi | iÎI得存在iÎI，使得xÎWi，由定理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 = <Wi, Ri> | iÎI是框架類，G稱為相容的，如果G滿足以下條件：(1) 任給i, jÎI，任給x, yÎWi&#

10、199;Wj，都有xRiy 當且僅當 xRjy。(2) 任給xÎWiÇWj，任給yÎWj，如果xRjy，則yÎWiÇWj。定理1.8 G = Fi = <Wi, Ri> | iÎI是相容的框架類，令W =Wi | iÎI，R =Ri | iÎI，構造框架F = <W, R>，則G是完備的初等子框架類。證 證明任給iÎI，Fi是F的初等子框架。1. 證明<Wi, Ri>是<W, R>的子框架，即證明R | Wi = Ri，也就是證明任給x, yÎWi

11、，都有xRy 當且僅當 xRiy。如果xRiy，由R的定義得xRy。如果xRy，由R的定義得存在jÎI，使得xRjy。由xRjy得x, yÎWj，所以xÎWiÇWj，yÎWj，由相容條件(2)得yÎWiÇWj，由相容條件(1)得xRiy 當且僅當 xRjy，因此xRiy。2. 證明<Wi, Ri>是<W, R>的初等子框架，即證明Wi對R是封閉的。任給xÎWi，yÎW，如果xRy，則存在jÎI，使得xRjy。由xRjy得x, yÎWj，所以xÎWi&#

12、199;Wj，yÎWj，由相容條件(2)得yÎWiÇWj，因此yÎWi。完備性顯然。定理1.8中的框架稱為相容的框架類G的并框架,記為FG。由定理1.6和定理1.8得：定理1.9 G是相容的框架類，則存在框架F，使得G和F等價。G = Fi = <Wi, Ri> | iÎI是框架類，如果Wi | iÎI是不交的，則稱G的不交的框架類。定理1.10 G是不交的框架類，則存在框架F，使得G和F等價。證 不交的框架類是相容的框架類。定義1.11 同構 F = <W, R>和F¢ = <W¢,

13、 R¢>是兩個框架。(1) f是W到W¢的雙射，如果f保持關系不變（即xRy 當且僅當 f(x)R¢f(y)），則稱f是F到F¢的同構映射。(2) 如果存在F到F¢的同構映射，則稱F和F¢同構，記為FF¢。定理1.12 同構是等價關系，即(1) <W, R><W, R>。(2) 如果<W, R><W¢, R¢>，則<W¢, R¢><W, R>。(3) 如果<W, R><W¢, R&

14、#162;>，<W¢, R¢><W², R²>，則<W, R><W², R²>。證 (1) 恒等映射iW是<W, R>到<W, R>的同構映射。(2) 如果f是<W, R>到<W¢, R¢>的同構映射，則f -1是<W¢, R¢>到<W, R>的同構映射。(3) 如果f是<W, R>到<W¢, R¢>的同構映射，g是<W&

15、#162;, R¢>到<W², R²>的同構映射，則gf 是<W, R>到<W², R²>的同構映射。定理1.13 F = <W, R>和F¢ = <W¢, R>是兩個框架，如果F同構F¢，則F等價F¢。證 取f是<W, R>到<W¢, R¢>，證明F |= a，則F¢ |= a。任給F¢上賦值V¢，取F上賦值V如下：V(p, x) = 1 當且僅當 V¢(

16、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

17、)。(3) a = bÙg，由歸納假設V(b, x) = V¢(b, f(x), V(g, x) = V¢(g, f(x)，所以V(a, x) = 1 當且僅當 V(bÙg, x) = 1當且僅當 (V(b, x) = 1且V(g, x) = 1)當且僅當 (V¢(b, f(x) = 1且V¢(g, f(x) = 1)當且僅當 V¢(bÙg, f(x) = 1 當且僅當 V¢(a, f(x) = 1。因此，V(a, x) = V¢(a, x)。(4) a =b，由歸納假設任給yÎW&#

18、162;，都有V(b,y) = V¢(b, y)，所以V(a, x) = 1 當且僅當 V(b, x) = 1當且僅當 "y(如果yÎW且xRy則V(b, y) = 1)當且僅當 "y(如果yÎW且xRy則V(b, f(y) = 1)當且僅當 "y(如果f(y)ÎW¢且f(x)R¢f(y)則V(b,f(y) = 1)當且僅當 "u(如果uÎW¢且f(x)R¢u則V¢(b, u) = 1)當且僅當 V¢(b, f(x) = 1 當且僅當 V

19、2;(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, R>是框架，令W(a) = <x, a> | xÎW，<x, a>R(a)<y, a> 當且僅當 xRy，構造框架F(a) = <W(a), R(a)>，則F和F(a)同構。證 取W到W(a)的雙射f：W到

20、74;W(a) f(x) = <x, a>，則xRy 當且僅當 <x, a>R(a)<y, a> 當且僅當 f(x)R¢f(y)，因此f是F到F(a)的同構映射。定理1.15 S是框架類，存在不交的框架類G，使得S等價G。證 設S = Fi = <Wi, Ri> | iÎI，取G = Fi(i) = <Wi(i), Ri(i)> | iÎI，任給iÎI，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是模態(tài)可定義的。定義1.18 f是一個關于框架的