35108
|
1 |
(* Title: HOL/TLA/Stfun.thy
|
|
2 |
Author: Stephan Merz
|
|
3 |
Copyright: 1998 University of Munich
|
21624
|
4 |
*)
|
3807
|
5 |
|
21624
|
6 |
header {* States and state functions for TLA as an "intensional" logic *}
|
3807
|
7 |
|
17309
|
8 |
theory Stfun
|
|
9 |
imports Intensional
|
|
10 |
begin
|
|
11 |
|
|
12 |
typedecl state
|
|
13 |
|
|
14 |
instance state :: world ..
|
3807
|
15 |
|
|
16 |
types
|
17309
|
17 |
'a stfun = "state => 'a"
|
|
18 |
stpred = "bool stfun"
|
3807
|
19 |
|
|
20 |
|
|
21 |
consts
|
6255
|
22 |
(* Formalizing type "state" would require formulas to be tagged with
|
|
23 |
their underlying state space and would result in a system that is
|
|
24 |
much harder to use. (Unlike Hoare logic or Unity, TLA has quantification
|
|
25 |
over state variables, and therefore one usually works with different
|
|
26 |
state spaces within a single specification.) Instead, "state" is just
|
|
27 |
an anonymous type whose only purpose is to provide "Skolem" constants.
|
|
28 |
Moreover, we do not define a type of state variables separate from that
|
|
29 |
of arbitrary state functions, again in order to simplify the definition
|
|
30 |
of flexible quantification later on. Nevertheless, we need to distinguish
|
|
31 |
state variables, mainly to define the enabledness of actions. The user
|
|
32 |
identifies (tuples of) "base" state variables in a specification via the
|
12607
|
33 |
"meta predicate" basevars, which is defined here.
|
3807
|
34 |
*)
|
6255
|
35 |
stvars :: "'a stfun => bool"
|
3807
|
36 |
|
|
37 |
syntax
|
17309
|
38 |
"PRED" :: "lift => 'a" ("PRED _")
|
|
39 |
"_stvars" :: "lift => bool" ("basevars _")
|
3807
|
40 |
|
|
41 |
translations
|
6255
|
42 |
"PRED P" => "(P::state => _)"
|
35108
|
43 |
"_stvars" == "CONST stvars"
|
3807
|
44 |
|
12607
|
45 |
defs
|
17309
|
46 |
(* Base variables may be assigned arbitrary (type-correct) values.
|
12607
|
47 |
Note that vs may be a tuple of variables. The correct identification
|
|
48 |
of base variables is up to the user who must take care not to
|
|
49 |
introduce an inconsistency. For example, "basevars (x,x)" would
|
|
50 |
definitely be inconsistent.
|
6255
|
51 |
*)
|
17309
|
52 |
basevars_def: "stvars vs == range vs = UNIV"
|
|
53 |
|
21624
|
54 |
|
|
55 |
lemma basevars: "!!vs. basevars vs ==> EX u. vs u = c"
|
|
56 |
apply (unfold basevars_def)
|
|
57 |
apply (rule_tac b = c and f = vs in rangeE)
|
|
58 |
apply auto
|
|
59 |
done
|
|
60 |
|
|
61 |
lemma base_pair1: "!!x y. basevars (x,y) ==> basevars x"
|
|
62 |
apply (simp (no_asm) add: basevars_def)
|
|
63 |
apply (rule equalityI)
|
|
64 |
apply (rule subset_UNIV)
|
|
65 |
apply (rule subsetI)
|
|
66 |
apply (drule_tac c = "(xa, arbitrary) " in basevars)
|
|
67 |
apply auto
|
|
68 |
done
|
|
69 |
|
|
70 |
lemma base_pair2: "!!x y. basevars (x,y) ==> basevars y"
|
|
71 |
apply (simp (no_asm) add: basevars_def)
|
|
72 |
apply (rule equalityI)
|
|
73 |
apply (rule subset_UNIV)
|
|
74 |
apply (rule subsetI)
|
|
75 |
apply (drule_tac c = "(arbitrary, xa) " in basevars)
|
|
76 |
apply auto
|
|
77 |
done
|
|
78 |
|
|
79 |
lemma base_pair: "!!x y. basevars (x,y) ==> basevars x & basevars y"
|
|
80 |
apply (rule conjI)
|
|
81 |
apply (erule base_pair1)
|
|
82 |
apply (erule base_pair2)
|
|
83 |
done
|
|
84 |
|
|
85 |
(* Since the unit type has just one value, any state function can be
|
|
86 |
regarded as "base". The following axiom can sometimes be useful
|
|
87 |
because it gives a trivial solution for "basevars" premises.
|
|
88 |
*)
|
|
89 |
lemma unit_base: "basevars (v::unit stfun)"
|
|
90 |
apply (unfold basevars_def)
|
|
91 |
apply auto
|
|
92 |
done
|
|
93 |
|
|
94 |
lemma baseE: "[| basevars v; !!x. v x = c ==> Q |] ==> Q"
|
|
95 |
apply (erule basevars [THEN exE])
|
|
96 |
apply blast
|
|
97 |
done
|
|
98 |
|
|
99 |
|
|
100 |
(* -------------------------------------------------------------------------------
|
|
101 |
The following shows that there should not be duplicates in a "stvars" tuple:
|
|
102 |
*)
|
|
103 |
|
|
104 |
lemma "!!v. basevars (v::bool stfun, v) ==> False"
|
|
105 |
apply (erule baseE)
|
|
106 |
apply (subgoal_tac "(LIFT (v,v)) x = (True, False)")
|
|
107 |
prefer 2
|
|
108 |
apply assumption
|
|
109 |
apply simp
|
|
110 |
done
|
3807
|
111 |
|
|
112 |
end
|