Difference between revisions of "Rodin Proving Perspective"
imported>Andy |
imported>Andy |
||
Line 4: | Line 4: | ||
When proof obligations (POs) are not discharged automatically the user can attempt to discharge them interactively using the Proving Perspective. This page provides an overview of the Proving Perspective and its use. If the Proving Perspective is not visible as a tab on the top right-hand corner of the main interface, the user can switch to it via "Window -> Open Perspective". | When proof obligations (POs) are not discharged automatically the user can attempt to discharge them interactively using the Proving Perspective. This page provides an overview of the Proving Perspective and its use. If the Proving Perspective is not visible as a tab on the top right-hand corner of the main interface, the user can switch to it via "Window -> Open Perspective". | ||
− | The Proving Perspective consists of a number of | + | The Proving Perspective consists of a number of views: the Proof Tree, the Goal, the Selected Hypotheses, the Proof Control, the Search Hypotheses, the Cache Hypotheses and the Proof Information. In the discussion that follows we look at each of these views individually. Below is a screenshot of the Proving Perspective: |
[[Image:ProvPers.png|center]] | [[Image:ProvPers.png|center]] |
Revision as of 10:40, 25 March 2010
Overview
When proof obligations (POs) are not discharged automatically the user can attempt to discharge them interactively using the Proving Perspective. This page provides an overview of the Proving Perspective and its use. If the Proving Perspective is not visible as a tab on the top right-hand corner of the main interface, the user can switch to it via "Window -> Open Perspective".
The Proving Perspective consists of a number of views: the Proof Tree, the Goal, the Selected Hypotheses, the Proof Control, the Search Hypotheses, the Cache Hypotheses and the Proof Information. In the discussion that follows we look at each of these views individually. Below is a screenshot of the Proving Perspective:
Loading a Proof
To work on an un-discharged PO it is necessary to load the proof into the Proving Perspective. To do this switch to the Proving Perspective; select the project from the Event-B Explorer; select and expand the component (context or machine); and finally select (double-click) the proof obligation of interest. A number of windows will be updated with details of the corresponding proof.
The Proof Tree
The proof tree describes each individual proof step in the proof. The proof tree can be seen in its corresponding window as seen in the following screenshot:
Each line in the tree corresponds to a node which is a sequent. A line is right shifted when the corresponding node is a direct descendant of the node of the previous line. Each node is labelled with a comment (description) explaining how it has been discharged. By selecting a node in the proof tree, the corresponding sequent is loaded: the hypotheses of the sequent are loaded to the Selected Hypotheses window, and the goal of the sequent is loaded to the Goal window.
Decoration
The leaves of the tree are decorated with three kinds of logos:
- a green logo with a "
" in it means that this leaf is discharged,
- a brown logo with a "?" in it means that this leaf is not discharged,
- a blue logo with a "R" in it means that this leaf has been reviewed.
Internal nodes in the proof tree are decorated in the same (but lighter) way. Note that a "reviewed" leaf is one that is not discharged yet by the prover. Instead, it has been "seen" by the user who decided to have it discharged later. Marking nodes as "reviewed" is very convenient in order to perform an interactive proof in a gradual fashion. In order to discharge a "reviewed" node, select it and prune the tree at that node: the node will become "brown" again (undischarged) and you can now try to discharge it.
On top of the proof tree window, one can see three buttons:
- the "G" buttons allows you to see the goal of the sequent corresponding to each node,
- the "+" button allows you to fully expand the proof tree,
- the "-" allows you to fully collapse the tree: only the root stays visible.
Manipulating the Proof Tree
Hiding
The little triangle (with a "+" or "-" inside) next to each node in the proof tree allows you to expand or collapse the subtree starting at that node.
Pruning
The proof tree can be pruned from a node: it means that the subtree starting at that node is eliminated. The node in question becomes a leaf and is brown decorated. This allows you to resume the proof from that node. After selecting a sequent in the proof tree, pruning can be performed in two ways:
- by right-clicking and then selecting "Prune",
- by pressing the (scissors) button in the proof control window (section 6.4).
Note that after pruning, the post-tactic is not applied to the new current sequent: if needed you have to press the "post-tactic" button in the Proof Control window. This happens in particular when you want to redo a proof from the beginning: you prune the proof tree from the root node and then you can invoke any internal or external prover to proceed.
When you want to redo a proof from a certain node, it might be advisable to do it after copying the tree so that in case your new proof fails you can still resume the previous situation by pasting the copied version (see next section).
Copy/Paste
By selecting a node in the proof tree and then clicking on the right key of the mouse, you can copy the part of the proof tree starting at that sequent: it can later be pasted in the same way. This allows you to reuse part of a proof tree in the same (or even another) proof.
Goal and Selected Hypotheses
The "Goal" and "Selected Hypotheses" windows display the current sequent you have to prove at a given moment in the proof. Here is an example:
A selected hypothesis can be deselected (and as a result becomes hidden) by first clicking in the box (check box) situated next to it (you can click on several boxes) and then by pressing the red (-) button at the top of the selected hypothesis window:
Here is the result:
Notice that the deselected hypotheses are not lost: you can get them back by means of the Search Hypotheses window. The other two buttons next to the red (-) button allow the user (in the order of their appearance from left to right) to select all hypotheses as well as inverse the current selection.
The (ct) button next to the goal allows you to do a proof by contradiction: by pressing it, the negation of the goal becomes a selected hypothesis whereas the goal becomes "⊥".
The (ct) button next to a selected hypothesis allows you to do another kind of proof by contradiction: by pressing it, the negation of the concerned hypothesis becomes the goal whereas the negated goal becomes an hypothesis.
Applying Proof Rules
The red hyperlinks as well as the (ct) buttons (also occasionally other green filled buttons next to it e.g., AND introduction in goal) allows the user to carry out interactive proofs. They are used to invoke proof rules (rewrite rules as well as inference rules).
Rewrite Rules
Rewrite rules are one-directional equalities (and equivalences) that can be used to simplify formulas (the goal or a single hypothesis). A rewrite rule is applied from left to right either in the goal or in one of the selected hypotheses, when its side condition holds.
A rewrite rule is applied either automatically (A) or manually (M):
- automatically, when post tactics are enabled. These rules are equivalence simplification laws.
- manually, through an interactive command. These rules gathers non equivalence laws, definition laws, distributivity laws and derived laws.
Each rule is named after the following elements:
- The law category: simplification law (SIMP), definition law (DEF), distributivity law (DISTRI), or else derived law (DERIV).
- Particularity on terminal elements of the left part of the rule (optional): special element (SPECIAL) such as the empty-set, type expression (TYPE), same element occurring more then once (MULTI), literal (LIT). A type expression is either a basic type (
, any carrier set), or
(type expression), or type expression
type expression.
- One or more elements describing from top to down the left part of the rule, eg. predicate AND, expression BUNION.
- Detail to localize those elements (optional): left (L), right (R).
Rewrite rules having an equivalence operator in their left part may also describe other rules. eg: the rule:
![\True = \False \;\;\defi\;\; \bfalse](/images/math/a/b/3/ab39627f784d1e002390e412f6b39325.png)
should also produce the rule:
![\False = \True \;\;\defi\;\; \bfalse](/images/math/f/e/d/fed85c5f8e4256f05a802b4d07c1eac0.png)
For associative operators in connection with distributive laws as in:
![P \land (Q \lor \ldots \lor R)](/images/math/e/1/0/e10a6b3a1dec6106ca80794ac229595f.png)
it has been decided to put the "button" on the first associative/commutative operator (here ). Pressing that button will generate a menu: the first option of this menu will be to distribute all associative/commutative operators, the second option will be to distribute only the first associative/commutative operator. In the following presentation, to simplify matters, we write associative/commutative operators with two parameters only, but it must always be understood implicitly that we have a sequence of them. For instance, we shall never write
but
instead. Rules are sorted according to their purpose.
Rules marked with a star in the first column are implemented in the current prover. Rules without a star are planned for implementation.
Rewrite rules are split into:
They are also available in a single large page All Rewrite Rules.
Inference Rules
Inference rules (see Proof Rules) are applied either automatically (A) or manually (M).
Inference rules applied automatically are applied at the end of each proof step. They have the following possible effects:
- they discharge the goal,
- they simplify the goal and add a selected hypothesis,
- they simplify the goal by decomposing it into several simpler goals,
- they simplify a selected hypothesis,
- they simplify a selected hypothesis by decomposing it into several simpler selected hypotheses.
Inference rules applied manually are used to perform an interactive proof. They can be invoked by pressing "buttons" which corresponds to emphasized (red) operators in the goal or the hypotheses. A menu is proposed when there are several options.
See Inference Rules list.
The Proof Control Window
The Proof Control window contains the buttons which you can use to perform an interactive proof.
The Proof Control window offers a number of buttons which we succinctly describe from left to right:
- (nPP): the new predicate prover.
- (R) review: in an attempt by the user to carry out proofs in a gradual fashion, they might decide to postpone the task of discharging some interactive proofs for a later stage. In this case they have the possibility to mark these proofs as reviewed by choosing the proof node and pressing this button. This means that by visually checking this proof, the user is convinced that they can discharge it later but they do not want to do it right now.
- (p0): the prover PP and ML can be invoked from the drop-down list.
- (dc) proof by cases: the goal is proved first under the predicate written in the editing area and then under its negation.
- (ah) lemma: the predicate in the editing area is proved and then added as a new selected hypothesis.
- (ae) abstract expression: the expression in the editing area is given a fresh name.
- the robot: the auto-prover attempts to discharge the goal. The auto-prover is the one which is applied automatically on all proof obligations (as generated automatically by the proof obligation generator after a "save") without any intervention of the user. With this button, you can call the auto-prover within an interactive proof.
- the post-tactic is executed (see section 6.8),
- lasoo: load in the Selected Hypotheses window those hidden hypotheses containing identifiers which are common with identifiers in the goal and selected hypotheses,
- backtrack form the current node (i.e., prune its parent),
- scissors: prune the proof tree from the node selected in the proof tree,
- show (in the Search Hypotheses window) hypotheses containing the character string as in the editing area,
- Cache Hypotheses Button: by pressing "Cache Hypotheses" button the tool displays the "Cache Hypotheses" view. This view displays all hypotheses that are related to the current goal.
- load the previous undischarged proof obligation,
- load the next undischarged proof obligation,
- (i) show information corresponding to the current proof obligation in the corresponding window. This information correspond to the elements that directly took part in the proof obligation generation (events, invariant, etc.),
- goto the next pending node of the current proof tree,
- load the next reviewed node of the current proof tree.
- Disable/Enable Post-tactics: allows the user to choose whether post-tactics run after each interactive proof step.
The Smiley
The smiley can take three different colors: (1) red, meaning that the proof tree contains one or more undischarged sequents, (2) blue, meaning that all undischarged sequents of the proof tree have been reviewed, (3) green, meaning that all sequents of the proof tree are discharged.
The Editing Area
The editing area allows the user to supply parameters to certain proof commands. For example, when the user attempts to add a new hypothesis (by pressing the lemma ah button), the new hypothesis should be written by the user in the editing area.
ML/PP and Hypotheses
ML
ML (mono-lemma) prover appears in the drop-down list under the button (pp) as M0, M1, M2, M3, ML. The different configuration (e.g., M0) refer to the proof force of the ML prover. All hypotheses are passed to ML.
PP
PP (predicate prover) appears in the drop-down list under the button (pp) as P0, P1, PP.
- P0 uses all selected hypotheses (the ones in Selected Hypotheses window).
- P1 employs a lasoo operation to the selected hypotheses and the goal, and uses the resulting hypotheses.
- PP uses all hypotheses.
The Search Hypotheses Window
By typing a string in the editing area of the Proof Control window and pressing the Search Hypotheses button, a window is provided which contains the hypotheses having a character string in common with the one entered by the user in the editing area.
In the next step, any of these hypotheses can be selected (box checked), and then by pressing the (+) button, they will be moved to the Selected Hypotheses window. Adding these hypotheses to the set of selected hypotheses means that they will be visible to the prover. This means that they can be used during the next interactive proof phase.
Accordingly by selecting any numbers of hypotheses and pressing the (-) they will be removed from the Search Hypotheses window. The (-) button also appears above the selected hypotheses, and allow the user to remove any hypothesis form the Selected Hypotheses window.
The other button which is situated in the left-hand-side of all hypotheses is the (ct) button. Pressing the (ct) button next to a hypothesis in the Search Hypotheses window achieves proof by contradiction. This has the same effect as selecting (making it part of the Selected Hypothesis window) that hypothesis, and then pressing the (ct) button next to it in the Selected Hypotheses window.
The Cache Hypotheses Window
This window allows the user to keep track of recently manipulated (e.g., used, removed, selected) hypotheses for any PO. For example, when the user applies a rewrite to an hypothesis, a new hypothesis (after the rewriting) is selected, and the original hypothesis is deselected and put in the Cache Hypotheses window.
Similar operations (to that of the Selected Hypotheses and Search Hypotheses windows) such as removing, selecting and proof by contradiction (ct) are also available for the cached hypotheses. Interactive proof steps (e.g., rewriting) can also be carried out from the Cache Hypotheses window as well as the Search Hypotheses window.
Proof Information View
This view displays information that can be used to relate the proof obligation to the model. For example, typical information for an event invariant preservation PO include the event as well as the invariant in question.
Auto-tactic and Post-tactic
Auto-tactic applies a combination of rewrite, inference and external provers to newly generated proof obligations. However, they can also be called upon by the user by pressing the (robot) button in the Proof Control window.
Post-tactic is also a combination of rewrite, inference and external provers, and is applied automatically after each interactive proof step. However, it can also be invoked manually by the user by pressing the (broomstick) button in the Proof Control window. Note that the post-tactic can be disabled by using the "P" button situated on the right of the Proof Control window.
Preferences for the Auto-tactic
The auto-tactic can be configured by means of a preference page which can be obtained as follows: press the "Window" button on the top tooolbar. On the coming menu, press the "Preferences" button. On the coming menu, press the "Event-B" menue, then the "Sequent Prover", and finally the "Auto-Tactic" button. This yilds the following window:
In the left part you can see the ordered sequence of individual tactics composing the auto-tactic, whereas the right part contains further tactics you can incorporate in the left part. By selecting a tactic you can move it from on part to the other or change the order in the left part.
Preferences for the Post-tactic
The post-tactic can be configured by means of a preference page which can be obtained as follows: press the "Window" button on the top tooolbar. On the coming menu, press the "Preferences" button. On the coming menu, press the "Event-B" menue, then the "Sequent Prover", and finally the "Post-Tactic" button. This yilds the following window:
Similarly to the auto-tactic, additional tactics can be added to the post-tactic.