| Let me try another attempt for explaining the issue. To make things simpler, let's leave aside the issue of refinement mapping, that is, consider just the identity refinement mapping. We want to prove (0) InitL /\ [][NextL]_varsL => InitH /\ [][NextH]_varsH Obviously, this can be reduced to proving (1) InitL => InitH (2) NextL \/ varsL' = varsL => NextH \/ varsH' = varsH However, the obligation (2) is very likely going to be unprovable because really, we only have to prove that implication for all reachable states (i.e., reachable in runs of the low-level spec) rather than for completely arbitrary states, and that's where the invariant comes in. Let's look at a stupid example: our high-level specification has one variable initialized to zero and that keeps growing while remaining an even number: Even == {n \in Int : n % 2 = 0} InitH == x = 0 NextH == x' > x /\ x' \in Even Our low-level specification has two variables x and y that evolve as follows: InitL == x = 0 /\ y = 0 NextL == x' = x+y /\ y' = y+2 Condition (2) now requires us to show (x' = x+y /\ y'=y+2) \/ (x'=x /\ y'=y) => (x' > x /\ x' \in Even) \/ x' = x but this implication is not true and therefore cannot be proved: we have no information about the "types" of x and y, so they could be strings for example. Even if they are integers, we could have x=42 and y=7, x' = 49 and y'=9, and the right-hand side will be false. And indeed, such a state cannot be reached because the low-level spec ensures that x and y are always even. Therefore we define Inv == x \in Even /\ y \in Even and relax our proof obligations to be (1') InitL => InitH /\ Inv (2') Inv /\ (NextL \/ varsL' = varsL) => Inv' /\ (NextH \/ varsH' = varsH) which still implies our high-level goal (0). I leave proving (1') and (2') for our example as an exercise to you. Indeed, Inv can be an arbitrary state predicate and has to be "invented" by the system designer / verifier. But it must be an invariant of the low-level specification, and FALSE is unlikely to be one. You may also want to read section 6.8 of the Hyperbook. Hope this helps, Stephan
You received this message because you are subscribed to the Google Groups "tlaplus" group. To unsubscribe from this group and stop receiving emails from it, send an email to tlaplus+unsubscribe@xxxxxxxxxxxxxxxx. To view this discussion on the web visit https://groups.google.com/d/msgid/tlaplus/D3586299-C7D2-44B5-8A7A-8B8EAC5AAAE0%40gmail.com. |