Difference between pages "Proof Manager" and "Rodin Proving Perspective"

From Event-B
(Difference between pages)
Jump to navigationJump to search
imported>Son
 
imported>Im06r
 
Line 1: Line 1:
The Proof Manager is responsible for constructing proofs and maintaining existing proofs associated with proof obligations.
+
{{Navigation|Previous= [[The_Proof_Obligation_Explorer_(Rodin_User_Manual)|The Proof Obligation Explorer]]|Next= [[The_Mathematical_Language_(Rodin_User_Manual)|The Mathematical Language]]|Up= [[index_(Rodin_User_Manual)|User_Manual_index]]}}
 +
{{TOCright}}
 +
== Overview ==
 +
The Proving Perspective is made of a number of windows (views): the Proof Tree, the Goal, the Selected Hypotheses, the Proof Control, the Proof Information, and the Search Hypotheses. In subsequent sections, we study each of these windows. Below is a screenshot of the proving perspective:
 +
 
 +
[[Image:ProvPers.png|center]]
 +
 
 +
== Loading a Proof ==
 +
In order to load a proof, switch to the Proving Perspective, select the project from the Event-B Explorer, select and expand the component (context or machine), finally select the proof obligation of interest. The corresponding proof will be loaded.
 +
 
 +
== The Proof Tree ==
 +
The proof tree describe each individual proof step in the proof. The proof tree can be seen in its corresponding window as seen in the following screenshot:
  
== Overview ==
+
[[Image:ProTree.png|center]]
 +
 
 +
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 can be 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:
  
Proof obligations are generated by the proof obligation generator and have the form of ''[[Proof Manager#Sequents|sequents]]''.
+
* a green logo with a "'''<math>\surd </math>'''" 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.
  
Sequents are proved using ''[[Proof Manager#Proof Rules|proof rules]]''.
+
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.
  
The Proof Manager architecture is separated into two parts: ''extensible'' part and ''static'' part. The extensible part is responsible for generating individual proof rules. The static part is responsible for putting proof rules together to construct and manage proofs. We call components that generate valid proof rules ''[[Proof Manager#Reasoners|reasoners]]''.
+
=== Navigation within the Proof Tree===
 +
On top of the proof tree window, one can see three buttons:
  
The basic reasoning capabilities of the Proof Manager can be extended by adding new reasoners. A reasoner may implement a decision procedure for automated proof, or a derived rule schema for interactive proof.
+
* the "'''G'''" buttons allows you to see the goal of the sequent corresponding to the node
 +
* the "'''+'''" button allows you to fully expand the proof tree
 +
* the "'''-'''" allows you to fully collapse the tree: only the root stays visible.
  
By applying the generated proof rules by different reasoner, the Proof Manager builds a (partial) proof for an proof obligation by constructing ''[[Proof Manager#Proof Trees|proof trees]]''.
+
=== Manipulating the Proof Tree===
  
In order to encapsulate frequently used proof construction and manipulation steps, the Proof Manager provides the concept of ''[[Proof Manager#Tactics|tactics]]''. They provides high-level strategic proof manipulations. Adding new tactics is the second possibility for extending the Proof Manager.
+
==== 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.
  
== Sequents ==
+
==== Pruning ====
A sequent stands for something we want to prove.
+
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 by right-clicking and then selecting "Prune".
  
Sequents are of the following form
+
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 have to press the "post-tactic" button in order to be in exactly the same situation as the one delivered automatically initially.
  
<math>H \vdash G</math>
+
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).
  
where '''H''' is the set of hypotheses (predicates) and '''G''' is the goal (a predicate in the mathematical language).
+
==== Copy/Paste ====
  
The meaning of the above sequent is that: ''Under the hypotheses H, prove the goal G''.
+
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.
  
== Proof Rules ==
+
== Goal and Selected Hypotheses ==
In its pure mathematical form, a proof rule is a tool to perform formal proof and is denoted by:
+
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:
 +
[[Image:GoalHyp.png|center]]
  
{{InfRule||<math>\frac{\quad A\quad}{C}</math>}}
+
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:
  
where '''A''' is a (possibly empty) list of sequents:the antecedents of the proof rule; and '''C''' is a sequent: the consequent of the rule. And we interpret the above proof rule as follows: The proofs of each sequent of '''A''' together give a proof of sequent '''C'''.
+
[[Image:GoalHypSelect.png|center]]
  
=== Representation ===
+
Here is the result:
In Rodin, the representation for proof rules are more structure not only to reduce the space required to store the rule, but more importantly to support proof reuse.
 
  
A rule in Rodin contains the following:
+
[[Image:GoalHypSelectRes.png|center]]
  
* '''used goal''' A used goal predicate.
+
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.  
  
* '''used hypotheses''' The set of used hypotheses.
+
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 "'''⊥'''".  
  
* '''antecedents''' A list of antecedents (to be explain later).
+
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.
  
* '''reasoner''' the reasoner used to generate this proof rule (See [[reasoners]]).
+
=== Applying Proof Rules ===
 +
The red hyperlinks as well as the ('''ct''') buttons (also occasionally other green filled button 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).
  
* '''reasoner input''' the input to the reasoner to generate this proof rule (See [[reasoners]]).
+
[[Image:ApplyRewRule.png|center]]
  
Each antecedent of the proof rule contains the following information:
+
==== 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.
  
* '''new goal''' A new goal predicate.
+
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.
  
* '''added hypotheses''' The set of added hypotheses.
+
Each rule is named after the following elements:
  
With this representation, a proof rule in Rodin corresponding to a proof schema as follows:
+
* 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 (<math>\intg, \Bool</math>, any carrier set), or <math>\pow</math>(type expression), or type expression<math>\cprod</math>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).
  
<math>
+
Rewrite rules having an equivalence operator in their left part may also describe other rules. eg: the rule:
  \begin{array}{c}
 
    H, H_u, H_{A_0} \vdash G_{A_0} ~~~\ldots~~~ H, H_u, H_{A_0} \vdash G_{A_0} \\
 
    \hline
 
    H, H_u \vdash G_u
 
  \end{array}
 
</math>
 
  
Where:
+
<center><math>  \True  = \False  \;\;\defi\;\;  \bfalse </math></center>
  
* <math>H_u</math> is the set of used hypotheses
+
should also produce the rule:
  
* <math>G_u</math> is the used goal
+
<center><math> \False  = \True  \;\;\defi\;\;  \bfalse </math></center>
  
* <math>H_{A_i}</math> is the set of added hypotheses corresponding to the ith antecedent.
+
For associative operators in connection with distributive laws as in:
  
* <math>G_{A_i}</math> is the new goal corresponding to the ith antecedent.
+
<center><math> P \land (Q \lor \ldots \lor R) </math></center>
  
* <math>H</math> is the meta-variable that can be instantiated.
+
it has been decided to put the "button" on the first associative/commutative operator (here <math>\lor </math>). 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 <math> Q \lor \ldots \lor R </math> but <math> Q \lor R </math> instead. Rules are sorted according to their purpose.
  
=== Applying Proof Rules ===
+
Rules marked with a star in the first column are implemented in the current prover. Rules without a star are planned for implementation.
Given a proof rule of the form mentioned above, the following describes how to apply this rule to an input ''sequent''. The result of this process is a list of output sequents if successful or ''null'' otherwise.
+
 
 +
Rewrite rules are split into:
 +
 
 +
* [[Set Rewrite Rules]]
 +
* [[Relation Rewrite Rules]]
 +
* [[Arithmetic Rewrite Rules]]
  
* The rule is applicable if the goal of the sequent is not exactly the same as the ''used goal'' or any of the ''used hypotheses'' is not contained in the set of hypotheses of the input sequent.
+
They are also available in a single large page [[All Rewrite Rules]].
  
* In the case of applicable, the antecedent sequents are returned. The goal of each antecedent sequent is the ''new goal'' correspondingly.  The hypotheses of each antecedent sequent is the union of the old hypotheses and ''added hypotheses'' of the corresponding antecedent.
+
==== Inference Rules ====
 +
Inference rules (see [[Proof Rules]]) are applied either automatically (A) or manually (M).
  
== Reasoners ==
+
Inference rules applied automatically are applied at the end of each proof step. They have the following possible effects:
  
== Proof Trees ==
+
* 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.
  
== [[Tactics ==
+
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.
  
[[Category:Developer documentation]]
+
See [[Inference Rules]] list.
[[Category:Rodin Platform]]
 

Revision as of 15:17, 11 March 2010

Overview

The Proving Perspective is made of a number of windows (views): the Proof Tree, the Goal, the Selected Hypotheses, the Proof Control, the Proof Information, and the Search Hypotheses. In subsequent sections, we study each of these windows. Below is a screenshot of the proving perspective:

ProvPers.png

Loading a Proof

In order to load a proof, switch to the Proving Perspective, select the project from the Event-B Explorer, select and expand the component (context or machine), finally select the proof obligation of interest. The corresponding proof will be loaded.

The Proof Tree

The proof tree describe each individual proof step in the proof. The proof tree can be seen in its corresponding window as seen in the following screenshot:

ProTree.png

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 can be 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 "\surd " 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.

Navigation within the Proof Tree

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 the 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 by right-clicking and then selecting "Prune".

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 have to press the "post-tactic" button in order to be in exactly the same situation as the one delivered automatically initially.

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:

GoalHyp.png

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:

GoalHypSelect.png

Here is the result:

GoalHypSelectRes.png

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 button 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).

ApplyRewRule.png

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 (\intg, \Bool, any carrier set), or \pow(type expression), or type expression\cprodtype 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

should also produce the rule:

  \False  = \True  \;\;\defi\;\;  \bfalse

For associative operators in connection with distributive laws as in:

 P \land (Q \lor \ldots \lor R)

it has been decided to put the "button" on the first associative/commutative operator (here \lor ). 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  Q \lor \ldots \lor R but  Q \lor R 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.