next up previous
Next: OddCounter Up: Proving an Invariant Previous: B. Show that your

C. Use a proof rule using pre-/post-condition specifications.

Technique A requires that we reason in terms of first principles-- using structural induction (over states in executions)--which can sometimes be cumbersome. And, usually, of course, we are not so lucky as in Technique B. Technique C is an alternative inductive proof strategy that is usually more manageable than Technique A: we do a case analysis of all actions, which indirectly proves the same thing as in Technique A.

At the bottom of p. 1 when I argued that the Counter's invariant holds, we need to show that the invariant holds in each initial state and then for each actiongif show that if the invariant holds in its pre-state, it holds in the post-state. In general, we have a proof rule that looks like:

tex2html_wrap_inline390
tex2html_wrap_inline392
tex2html_wrap_inline354

where I is the set of initial states and A is the set of actions. tex2html_wrap_inline400 and tex2html_wrap_inline402 are the pre- and post-conditions of a, respectively. Or, said in English:

  1. Show that tex2html_wrap_inline342 is true for each initial state.
  2. For each action,
  3. Conclude that tex2html_wrap_inline342 is an invariant.

The two main proof steps are sometimes called (1) establishing the invariant (true in initial states) and (2) preserving the invariant (assuming it's true in a pre-state and showing that each action's the post-state preserves it).

What's the rationale for this proof rule? First, notice I care only about reachable states (that's why the tex2html_wrap_inline418 appears above). Second, consider any execution of my state machine:

tex2html_wrap_inline420

As in Technique A I need to make sure that tex2html_wrap_inline342 holds in tex2html_wrap_inline374 (establishing the invariant). Also, for any pair of successive states, tex2html_wrap_inline426 , in the execution, if I assume tex2html_wrap_inline342 holds in tex2html_wrap_inline376 then I need to show it holds in tex2html_wrap_inline378 . Since the only way I can get from any tex2html_wrap_inline376 to the next state tex2html_wrap_inline378 is by one of the actions a in A, then if I show the invariant if preserved for each a, I've shown for each reachable state the invariant holds.


next up previous
Next: OddCounter Up: Proving an Invariant Previous: B. Show that your

Norman Papernick
Mon Mar 18 14:28:12 EST 1996