imported>Mathieu |
imported>Im06r |
| Line 1: |
Line 1: |
| − | {{Navigation|Previous= [[User_Manual_The_Proof_Obligation_Explorer|The Proof Obligation Explorer]]|Next= [[User_Manual_The_Mathematical_Language|The Mathematical Language]]|Up= [[User_Manual_index|User_Manual_index]]}}<div>
| + | Return to [[Rodin Plug-ins]] |
| | | | |
| | + | The Theory plug-in is the successor of the Rule-based Prover (which will be referred to as RbP) plug-in. The Theory plug-in |
| | + | provides capabilities to extend the Event-B language and the proving infrastructure in a familiar fashion to Rodin users. If you are looking for the user manual or the latest news on the Theory plug-in, please refer to [[Theory News and Support|Theory News and Support]]. |
| | + | This page provides useful information about the plug-in and its design. |
| | | | |
| − | The Proving Perspective is made of a number of windows: the proof tree, the goal, the selected hypotheses, the proof control, the proof information, and the searched hypotheses. In subsequent sections, we study these windows, but before that let us see how one can load a proof.
| + | ===Motivation=== |
| | | | |
| − | = Loading a Proof = | + | ===Overview=== |
| | | | |
| − | In order to load a proof, enter the Proof Obligation window, select the project, select and expand the component, finally select the proof obligation: the corresponding proof will be loaded. As a consequence:
| + | ===Capabilities=== |
| | | | |
| − | * the proof tree is loaded in the Proof Tree window. As we shall see in section [[User_Manual_The_Proving_Perspective#tree|6.2]], each node of the proof tree is associated with a sequent.
| + | ===Insider Look=== |
| − | * In case the proof tree has some "pending" nodes (whose sequents are not discharged yet) then the sequent corresponding to the first pending node is decomposed: its goal is loaded in the Goal window (section [[User_Manual_The_Proving_Perspective#goal|6.3]]), whereas parts of its hypotheses (the "selected" ones) are loaded in the Selected Hypotheses window (section [[User_Manual_The_Proving_Perspective#goal|6.3]]).
| |
| − | * In case the proof tree has no pending node, then the sequent of the root node is loaded as explained previously.
| |
| | | | |
| − | = The Proof Tree =
| + | :[http://eprints.ecs.soton.ac.uk/18269/ Issam Maamria, Michael Butler, Andrew Edmunds, and Abdolbaghi Rezazadeh. On an Extensible Rule-based Prover for Event-B, ABZ'2010.] |
| | + | :[http://eprints.ecs.soton.ac.uk/21221/ Issam Maamria, Michael Butler. Rewriting and Well-Definedness within a Proof System.] |
| | | | |
| − | == Description of the Proof Tree == | + | ===Improvements and Bugs=== |
| | | | |
| − | The proof tree can be seen in the corresponding window as shown in the following screen shot:
| + | See also the late [[Rule-based Prover Plug-in]], the last release of the which was v0.3. The Theory plug-in starts at version v0.5. |
| − | | |
| − | <center>[[Image:um-0095.png|\includegraphics[scale=.5]{snapshots/pic112}]]</center>
| |
| − | | |
| − | Each line in the proof 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. Here is an illustration of the previous tree:
| |
| − | | |
| − | <center>[[Image:um-0096.png|\includegraphics[scale=.5]{tree}]]</center>
| |
| − | | |
| − | Each node is labelled with a comment explaining how it can be discharged. By selecting a node in the proof tree, the corresponding sequent is decomposed and loaded in the Goal and Selected Hypotheses windows as explained in section [[User_Manual_The_Proving_Perspective#loadproof|6.1]].
| |
| − | | |
| − | == Decoration ==
| |
| − | | |
| − | The leaves of the tree are decorated with three kinds of logos:
| |
| − | | |
| − | * a green logo with a "<math>\surd </math>" in it means that this leaf is discharged,
| |
| − | * a red 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 (section [[User_Manual_The_Proving_Perspective#prune|]]): the node will become "red" 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.
| |
| − | | |
| − | == Hiding ==
| |
| − | | |
| − | The little triangle 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 red 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 [[User_Manual_The_Proving_Perspective#proofcontrol|6.4]]).
| |
| − | | |
| − | Note that after pruning, the post-tactic (section [[User_Manual_The_Proving_Perspective#post|6.8]]) is not applied to the new current sequent: if needed you have to press the "post-tactic" button in the Proof Control window (section [[User_Manual_The_Proving_Perspective#proofcontrol|6.4]]). 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:
| |
| − | | |
| − | <center>[[Image:um-0098.png|\includegraphics[scale=.5]{snapshots/pic104}]]</center>
| |
| − | | |
| − | A selected hypothesis can be deselected by first clicking in the 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:
| |
| − | | |
| − | <center>[[Image:um-0099.png|\includegraphics[scale=.5]{snapshots/pic105}]]</center>
| |
| − | | |
| − | Here is the result:
| |
| − | | |
| − | <center>[[Image:um-0100.png|\includegraphics[scale=.5]{snapshots/pic106}]]</center>
| |
| − | | |
| − | Notice that the deselected hypotheses are not lost: you can get them back by means of the Searched Hypotheses window (section [[User_Manual_The_Proving_Perspective#srchhyp|6.7]]).
| |
| − | | |
| − | The three other buttons next to the red (-) button allow you to do the reverse operation, namely keeping some hypotheses. The (ct) button next to the goal allows you to do a proof by contradiction: pressing it makes the negation of the goal being a selected hypothesis whereas the goal becomes "false". The (ct) button next to a selected hypothesis allows you to do another kind of proof by contradiction: pressing it makes the negation of the hypothesis the goal whereas the negated goal becomes an hypothesis.
| |
| − | | |
| − | = The Proof Control Window =
| |
| − | | |
| − | The Proof Control window contains the buttons which you can use to perform an interactive proof. Next is a screen shot where you can see successively from top to bottom:
| |
| − | | |
| − | * some selected hypotheses,
| |
| − | * the goal,
| |
| − | * the "Proof Control" window,
| |
| − | * a small editing area within which you can enter parameters used by some buttons of the Proof Control window
| |
| − | * the smiley (section [[User_Manual_The_Proving_Perspective#smiley|6.5]])
| |
| − | | |
| − | <center>[[Image:um-0101.png|\includegraphics[scale=.5]{snapshots/pic108}]]</center>
| |
| − | | |
| − | The Proof Control window offers a number of buttons which we succinctly describe from left to right:
| |
| − | | |
| − | * (p0): the prover PP attempts to prove the goal (other cases in the list)
| |
| − | * (R) review: the user forces the current sequent to be discharged, it is marked as being reviewed (it’s logo is blue-colored)
| |
| − | * (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 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 yourself the auto-prover within an interactive proof.
| |
| − | * the post-tactic is executed (see section [[User_Manual_The_Proving_Perspective#post|6.8]]),
| |
| − | * lasso: load in the Selected Hypotheses window those unseen 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,
| |
| − | * show the Cache Hypotheses window,
| |
| − | * load the previous non-discharged 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 took directly 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.
| |
| − | | |
| − | = The Smiley =
| |
| − | | |
| − | The smiley can take three different colors: (1) red, meaning that the proof tree contains one or more non-discharged sequents, (2) blue, meaning that all non-discharged sequents of the proof tree have been reviewed, (3) green, meaning that all sequents of the proof tree are discharged.
| |
| − | | |
| − | = The Operator "Buttons" =
| |
| − | | |
| − | In the goal and in the selected, searched, or cache hypotheses some operators are colored in red. It means that they are "buttons" you can press. When doing so, the meaning (sometimes several) is shown in a menu where you can select various options. The operation performed by these options is described in sections [[User_Manual_The_Proving_Perspective#inter rewr|]] and [[User_Manual_The_Proving_Perspective#inter infr|]].
| |
| − | | |
| − | = The Search Hypotheses Window =
| |
| − | | |
| − | A window is provided which contains the hypotheses having a character string in common with the one in the editing area. For example, if we search for hypotheses involving the character string "cr", then after pressing the "search hypothesis" button in the proof control window, we obtain the following:
| |
| − | | |
| − | <center>[[Image:um-0102.png|\includegraphics[scale=.5]{snapshots/pic111}]]</center>
| |
| − | | |
| − | Such hypotheses can be moved to the "Selected Hypotheses" window (button (+)) or removed from the "Search Hypotheses" window (button (-)). As for the selected hypotheses, other buttons situated next to the previous ones, allow you to move or remove all hypotheses. By pressing the (ct) button the negation of the corresponding hypothesis becomes the new goal.
| |
| − | | |
| − | = The Automatic Post-tactic =
| |
| − | | |
| − | In this section, we present the various rewrite or inference rules which are applied automatically as a systematic post-tactic after each proof step. Note that the post-tactic can be disabled by using the "'''P'''<math>\! \! \! \! /</math>" button situated on the right of the proof control window.
| |
| − | | |
| − | The post-tactic is made of two different rules: rewrite rules, which are applied on any sub-formula of the goal or selected hypotheses (section [[User_Manual_The_Proving_Perspective#auto rewr|]]) and inference rules which are applied on the current sequent (section [[User_Manual_The_Proving_Perspective#auto infer|]]).
| |
| − | | |
| − | == Rewrite rules ==
| |
| − | | |
| − | The following rewrite rules are ''applied automatically'' in a systematic fashion from left to right either in the goal or in the selected hypotheses. They all correspond to predicate logical equivalences or expression equalities and result in simplifications. They are sorted according to their main purpose. | |
| − | | |
| − | '''Conjunction'''
| |
| − | | |
| − | <center><math> \begin{array}{l} P \land \ldots \land \mathord {\top }\land \ldots \land Q \; \; ==\; \; P \land \ldots \land Q \\ P \land \ldots \land \mathord {\bot }\land \ldots \land Q \; \; ==\; \; \mathord {\bot }\\ P \land \ldots \land Q \land \ldots \land \neg \, Q \land \ldots \land R \; \; ==\; \; \mathord {\bot }\\ P \land \ldots \land Q \land \ldots \land Q \land \ldots \land R \; \; ==\; \; P \land \ldots \land Q \land \ldots \land R\\ \end{array} </math></center>
| |
| − | | |
| − | '''Disjunction'''
| |
| − | | |
| − | <center><math> \begin{array}{l} P \lor \ldots \lor \mathord {\top }\lor \ldots \lor Q \; \; ==\; \; \mathord {\top }\\ P \lor \ldots \lor \mathord {\bot }\lor \ldots \lor Q \; \; ==\; \; P \lor \ldots \lor Q \\ P \lor \ldots \lor Q \lor \ldots \lor \neg \, Q \lor \ldots \lor R \; \; ==\; \; \mathord {\top }\\ P \lor \ldots \lor Q \lor \ldots \lor Q \lor \ldots \lor R \; \; ==\; \; P \lor \ldots \lor Q \lor \ldots \lor R \end{array} </math></center>
| |
| − | | |
| − | '''Implication'''
| |
| − | | |
| − | <center><math> \begin{array}{l} \mathord {\top }\mathbin \Rightarrow P \; \; ==\; \; P \\ \mathord {\bot }\mathbin \Rightarrow P \; \; ==\; \; \mathord {\top }\\ P \mathbin \Rightarrow \mathord {\top }\; \; ==\; \; \mathord {\top }\\ P \mathbin \Rightarrow \mathord {\bot }\; \; ==\; \; \neg \, P \\ P \mathbin \Rightarrow P \; ==\; \; \mathord {\top }\end{array} </math></center>
| |
| − | | |
| − | <br />'''Equivalence'''
| |
| − | | |
| − | <center><math> \begin{array}{l} P \mathbin \Leftrightarrow \mathord {\top }\; \; ==\; \; P \\ \mathord {\top }\mathbin \Leftrightarrow P\; \; ==\; \; P \\ P \mathbin \Leftrightarrow \mathord {\bot }\; \; ==\; \; \neg \, P \\ \mathord {\bot }\mathbin \Leftrightarrow P \; \; ==\; \; \neg \, P \\ P \mathbin \Leftrightarrow P\; \; ==\; \; \mathord {\top }\end{array} </math></center>
| |
| − | | |
| − | '''Negation'''
| |
| − | | |
| − | <center><math> \begin{array}{l} \neg \, \mathord {\top }\; \; ==\; \; \mathord {\bot }\\ \neg \, \mathord {\bot }\; \; ==\; \; \mathord {\top }\\ \neg \, \neg \, P \; \; ==\; \; P \\ E\neq F \; \; ==\; \; \neg \, E = F \\ E\notin F \; \; ==\; \; \neg \, E \in F \\ E\not\subset F \; \; ==\; \; \neg \, E \subset F \\ E\not\subseteq F \; \; ==\; \; \neg \, E \subseteq F \\ \neg \, a\leq b \; \; ==\; \; a>b \\ \neg \, a\geq b \; \; ==\; \; a<b \\ \neg \, a> b \; \; ==\; \; a\leq b \\ \neg \, a< b \; \; ==\; \; a \geq b \\ \neg \, (E=\mathord {\mathrm{FALSE}}) \; \; ==\; \; \ (E=\mathord {\mathrm{TRUE}}) \\ \neg \, (E=\mathord {\mathrm{TRUE}}) \; \; ==\; \; \ (E=\mathord {\mathrm{FALSE}}) \\ \neg \, (\mathord {\mathrm{FALSE}}=E) \; \; ==\; \; \ (\mathord {\mathrm{TRUE}}= E) \\ \neg \, (\mathord {\mathrm{TRUE}}=E) \; \; ==\; \; \ (\mathord {\mathrm{FALSE}}= E) \end{array} </math></center>
| |
| − | | |
| − | '''Quantification'''
| |
| − | | |
| − | <center><math> \begin{array}{l} \forall x \, \mathord {\mkern 1mu\cdot \mkern 1mu}\, (\, P \land Q) \; \; ==\; \; (\forall x \, \mathord {\mkern 1mu\cdot \mkern 1mu}\, P) \; \land \; (\forall x \, \mathord {\mkern 1mu\cdot \mkern 1mu}\, Q) \\ \exists x \, \mathord {\mkern 1mu\cdot \mkern 1mu}\, (\, P \lor Q) \; \; ==\; \; (\exists x \, \mathord {\mkern 1mu\cdot \mkern 1mu}\, P) \; \lor \; (\exists x \, \mathord {\mkern 1mu\cdot \mkern 1mu}\, Q) \\ \forall \ldots ,z,\ldots \, \mathord {\mkern 1mu\cdot \mkern 1mu}\, P(z) \; \; ==\; \; \forall z\, \mathord {\mkern 1mu\cdot \mkern 1mu}\, P(z) \\ \exists \ldots ,z,\ldots \, \mathord {\mkern 1mu\cdot \mkern 1mu}\, P(z) \; \; ==\; \; \exists z\, \mathord {\mkern 1mu\cdot \mkern 1mu}\, P(z) \\ \end{array} </math></center>
| |
| − | | |
| − | '''Equality'''
| |
| − | | |
| − | <center><math> \begin{array}{l} E = E \; \; ==\; \; \mathord {\top }\\ E \neq E \; \; ==\; \; \mathord {\bot }\\ E\mapsto F = G \mapsto H \; \; ==\; \; E = G \; \land \; F = H \\ \end{array} </math></center><center><math> \begin{array}{l} \mathord {\mathrm{TRUE}}=\mathord {\mathrm{FALSE}}\; \; ==\; \; \ \mathord {\bot }\\ \mathord {\mathrm{FALSE}}=\mathord {\mathrm{TRUE}}\; \; ==\; \; \ \mathord {\bot }\end{array} </math></center>
| |
| − | | |
| − | '''Set Theory'''
| |
| − | | |
| − | <center>[[Image:um-0112.png|$ \begin{array}{l} S \mathbin {\mkern 1mu\cap \mkern 1mu}\ldots \mathbin {\mkern 1mu\cap \mkern 1mu}\emptyset \mathbin {\mkern 1mu\cap \mkern 1mu}\ldots \mathbin {\mkern 1mu\cap \mkern 1mu}T \; \; ==\; \; \emptyset \\ S \mathbin {\mkern 1mu\cap \mkern 1mu}\ldots \mathbin {\mkern 1mu\cap \mkern 1mu}T \mathbin {\mkern 1mu\cap \mkern 1mu}\ldots \mathbin {\mkern 1mu\cap \mkern 1mu}T \mathbin {\mkern 1mu\cap \mkern 1mu}\ldots \mathbin {\mkern 1mu\cap \mkern 1mu}U \; \; ==\; \; S \mathbin {\mkern 1mu\cap \mkern 1mu}\ldots \mathbin {\mkern 1mu\cap \mkern 1mu}T \mathbin {\mkern 1mu\cap \mkern 1mu}\ldots \mathbin {\mkern 1mu\cap \mkern 1mu}U \\ S \mathbin {\mkern 1mu\cup \mkern 1mu}\ldots \mathbin {\mkern 1mu\cup \mkern 1mu}\emptyset \mathbin {\mkern 1mu\cup \mkern 1mu}\ldots \mathbin {\mkern 1mu\cup \mkern 1mu}T \; \; ==\; \; S \mathbin {\mkern 1mu\cup \mkern 1mu}\ldots \mathbin {\mkern 1mu\cup \mkern 1mu}T \\ S \mathbin {\mkern 1mu\cup \mkern 1mu}\ldots \mathbin {\mkern 1mu\cup \mkern 1mu}T \mathbin {\mkern 1mu\cup \mkern 1mu}\ldots \mathbin {\mkern 1mu\cup \mkern 1mu}T \mathbin {\mkern 1mu\cup \mkern 1mu}\ldots \mathbin {\mkern 1mu\cup \mkern 1mu}U \; \; ==\; \; S \mathbin {\mkern 1mu\cup \mkern 1mu}\ldots \mathbin {\mkern 1mu\cup \mkern 1mu}T \mathbin {\mkern 1mu\cup \mkern 1mu}\ldots \mathbin {\mkern 1mu\cup \mkern 1mu}U \\ \emptyset \; \subseteq \; S \; \; ==\; \; \mathord {\top }\\ S \; \subseteq \; S \; \; ==\; \; \mathord {\top }\\ E \; \in \; \emptyset \; \; ==\; \; \mathord {\bot }\\ B \; \in \; \{ A, \ldots , B, \ldots ,C\} \; \; ==\; \; \mathord {\top }\\ \{ A, \ldots , B, \ldots ,B, \ldots ,C\} \; \; ==\; \; \{ A, \ldots , B, \ldots ,C\} \\ E \; \in \; \{ \, x\, |\, P(x)\, \} \; \; ==\; \; P(E) \\ S \setminus S \; \; ==\; \; \emptyset \\ S \setminus \emptyset \; \; ==\; \; S \\ \emptyset \setminus S \; \; ==\; \; \emptyset \\ r^{-1-1} \; \; ==\; \; r \\ \mathop {\mathrm{dom}}\nolimits (\{ x\mapsto a, \ldots , y \mapsto b\} \; \; ==\; \; \{ x, \ldots , y\} \\ \mathop {\mathrm{ran}}\nolimits (\{ x\mapsto a, \ldots , y \mapsto b\} \; \; ==\; \; \{ a, \ldots , b\} \\ (f \mathbin {\lhd \mkern -9mu-}\ldots \mathbin {\lhd \mkern -9mu-}\{ E \mapsto F\} )(E) \; \; ==\; \; F \\ E \in \{ F\} \; \; ==\; \; E = F \ \ \ \ \ \hbox{where $F$ is a single expression} \end{array} $]]</center><center>[[Image:um-0113.png|$ \begin{array}{l} \{ E\} = \{ F\} \; \; ==\; \; E = F \ \ \ \ \ \hbox{where $E$ and $F$ are single expressions} \\ \{ x \mapsto a,\ldots , y \mapsto b\} ^{-1} \; \; ==\; \; \{ a \mapsto x,\ldots , b \mapsto y\} \\ Ty = \emptyset \; \; ==\; \; \mathord {\bot }\\ \emptyset = Ty \; \; ==\; \; \mathord {\bot }\\ t \in Ty \; \; ==\; \; \mathord {\top }\end{array} $]]</center>
| |
| − | | |
| − | In the three previous rewrite rules, <math>Ty</math> denotes a type expression, that is either a basic type (<math>\mathord {\mathbb Z}, \mathord {\mathrm{BOOL}}</math>, any carrier set), or <math>\mathop {\mathbb P\hbox{}}\nolimits </math>(type expression), or type expression<math>\mathbin \times </math>type expression, and <math>t</math> denotes an expression of type <math>Ty</math>.
| |
| − | | |
| − | <center><math> \begin{array}{l} U \setminus U \setminus S \; ==\; S \\ S \mathbin {\mkern 1mu\cup \mkern 1mu}\ldots \mathbin {\mkern 1mu\cup \mkern 1mu}U \mathbin {\mkern 1mu\cup \mkern 1mu}\ldots \mathbin {\mkern 1mu\cup \mkern 1mu}T \; \; ==\; \; U \\ S \mathbin {\mkern 1mu\cap \mkern 1mu}\ldots \mathbin {\mkern 1mu\cap \mkern 1mu}U \mathbin {\mkern 1mu\cap \mkern 1mu}\ldots \mathbin {\mkern 1mu\cap \mkern 1mu}T \; \; ==\; \; S \mathbin {\mkern 1mu\cap \mkern 1mu}\ldots \mathbin {\mkern 1mu\cap \mkern 1mu}T \\ S \setminus U \; \; ==\; \; \emptyset \\ \end{array} </math></center>
| |
| − | | |
| − | In the four previous rules, <math>S</math> and <math>T</math> are supposed to be of type <math>\mathop {\mathbb P\hbox{}}\nolimits (U)</math>.
| |
| − | | |
| − | <center><math> \begin{array}{l} r \mathbin ;\emptyset \; \; ==\; \; \emptyset \\ \emptyset \mathbin ;r \; \; ==\; \; \emptyset \\ f(f^{-1}(E)) \; \; ==\; \; E \\ f^{-1}(f(E)) \; \; ==\; \; E \\ S \; \subseteq \; A \mathbin {\mkern 1mu\cup \mkern 1mu}\ldots \mathbin {\mkern 1mu\cup \mkern 1mu}S \mathbin {\mkern 1mu\cup \mkern 1mu}\ldots \mathbin {\mkern 1mu\cup \mkern 1mu}B \; \; ==\; \; \mathord {\top }\\ A \mathbin {\mkern 1mu\cap \mkern 1mu}\ldots \mathbin {\mkern 1mu\cap \mkern 1mu}S \mathbin {\mkern 1mu\cap \mkern 1mu}\ldots \mathbin {\mkern 1mu\cap \mkern 1mu}B \; \subseteq \; S \; \; ==\; \; \mathord {\top }\\ A \mathbin {\mkern 1mu\cup \mkern 1mu}\ldots \mathbin {\mkern 1mu\cup \mkern 1mu}B \; \subseteq \; S \; \; ==\; \; A\subseteq S \; \land \; \ldots \; \land \; B\subseteq S \\ S \; \subseteq \; A \mathbin {\mkern 1mu\cap \mkern 1mu}\ldots \mathbin {\mkern 1mu\cap \mkern 1mu}B \; \; ==\; \; S \subseteq A \; \land \; \ldots \; \land \; S \subseteq B \\ A \mathbin {\mkern 1mu\cup \mkern 1mu}\ldots \mathbin {\mkern 1mu\cup \mkern 1mu}B \; \subset \; S \; \; ==\; \; A\subset S \; \land \; \ldots \; \land \; B\subset S \\ S \; \subset \; A \mathbin {\mkern 1mu\cap \mkern 1mu}\ldots \mathbin {\mkern 1mu\cap \mkern 1mu}B \; \; ==\; \; S \subset A \; \land \; \ldots \; \land \; S \subset B \\ A \; \setminus B \; \subseteq \; S \; \; ==\; \; A \; \subseteq \; B \mathbin {\mkern 1mu\cup \mkern 1mu}S \end{array} </math></center>
| |
| − | | |
| − | '''Finiteness'''
| |
| − | | |
| − | <center><math> \begin{array}{l} \mathop {\mathrm{finite}}\nolimits \, (\emptyset ) \; \; ==\; \; \mathord {\top }\\ \mathop {\mathrm{finite}}\nolimits \, (\{ a, \ldots , b\} ) \; \; ==\; \; \mathord {\top }\\ \mathop {\mathrm{finite}}\nolimits \, (S \mathbin {\mkern 1mu\cup \mkern 1mu}T) \; \; ==\; \; \mathop {\mathrm{finite}}\nolimits \, (S) \; \land \; \mathop {\mathrm{finite}}\nolimits \, (T) \end{array} </math></center><center><math> \begin{array}{l} \mathop {\mathrm{finite}}\nolimits \, (\mathop {\mathbb P\hbox{}}\nolimits (S)) \; \; ==\; \; \mathop {\mathrm{finite}}\nolimits \, (S) \\ \mathop {\mathrm{finite}}\nolimits \, (S \mathbin \times T) \; \; ==\; \; S = \emptyset \; \; \lor \; \; T = \emptyset \; \; \lor \; \; (\mathop {\mathrm{finite}}\nolimits \, (S) \; \land \; \mathop {\mathrm{finite}}\nolimits \, (T)) \\ \mathop {\mathrm{finite}}\nolimits \, (r^{-1}) \; \; ==\; \; \mathop {\mathrm{finite}}\nolimits \, (r) \\ \mathop {\mathrm{finite}}\nolimits \, (a \mathbin {.\mkern 1mu.}b) == \mathord {\top }\\ \end{array} </math></center>
| |
| − | | |
| − | '''Cardinality'''
| |
| − | | |
| − | <center><math> \begin{array}{l} \mathop {\mathrm{card}}\nolimits (\emptyset ) \; \; ==\; \; 0 \\ \mathop {\mathrm{card}}\nolimits \, (\{ E\} ) \; \; ==\; \; 1 \\ \mathop {\mathrm{card}}\nolimits \, (\mathop {\mathbb P\hbox{}}\nolimits (S)) \; \; ==\; \; 2^{\mathop {\mathrm{card}}\nolimits (S)} \\ \mathop {\mathrm{card}}\nolimits \, (S \mathbin \times T) \; \; ==\; \; \mathop {\mathrm{card}}\nolimits (S) * \mathop {\mathrm{card}}\nolimits (T) \\ \mathop {\mathrm{card}}\nolimits \, (S \setminus T) \; \; ==\; \; \mathop {\mathrm{card}}\nolimits (S)-\mathop {\mathrm{card}}\nolimits \, (S \mathbin {\mkern 1mu\cap \mkern 1mu}T) \\ \mathop {\mathrm{card}}\nolimits \, (S \mathbin {\mkern 1mu\cup \mkern 1mu}T) \; \; ==\; \; \mathop {\mathrm{card}}\nolimits (S)+\mathop {\mathrm{card}}\nolimits (T)-\mathop {\mathrm{card}}\nolimits \, (S \mathbin {\mkern 1mu\cap \mkern 1mu}T) \\ \mathop {\mathrm{card}}\nolimits \, (S) = 0 \; \; ==\; \; S = \emptyset \\ 0 = \mathop {\mathrm{card}}\nolimits \, (S) \; \; ==\; \; S = \emptyset \\ \neg \, \mathop {\mathrm{card}}\nolimits \, (S) = 0 \; \; ==\; \; \neg \, S = \emptyset \\ \neg \, 0 = \mathop {\mathrm{card}}\nolimits \, (S) \; \; ==\; \; \neg \, S = \emptyset \\ \mathop {\mathrm{card}}\nolimits \, (S) > 0 \; \; ==\; \; \neg \, S = \emptyset \\ 0 < \mathop {\mathrm{card}}\nolimits \, (S) \; \; ==\; \; \neg \, S = \emptyset \\ \mathop {\mathrm{card}}\nolimits \, (S) = 1 \; \; ==\; \; \exists x \, \mathord {\mkern 1mu\cdot \mkern 1mu}\, S = \{ x\} \\ 1 = \mathop {\mathrm{card}}\nolimits \, (S) \; \; ==\; \; \exists x \, \mathord {\mkern 1mu\cdot \mkern 1mu}\, S = \{ x\} \end{array} </math></center>
| |
| − | | |
| − | '''Arithmetic'''
| |
| − | | |
| − | <center><math> \begin{array}{l} E+\ldots +0+\ldots +F \; \; ==\; \; E+\ldots +F \\ E-0 \; \; ==\; \; E \\ 0-E \; \; ==\; \; -E \\ -(-E) \; \; ==\; \; E \\ E*\ldots *1*\ldots *F \; \; ==\; \; E*\ldots *F \\ E*\ldots *0*\ldots *F \; \; ==\; \; 0\end{array} </math></center><center>[[Image:um-0128.png|$ \begin{array}{l} (-E)*\ldots *(-F)\; ==\; E*\ldots *F \hspace{5em} \hbox{(if an even number of -)} \\ (-E)*\ldots *(-F)\; ==\; -\, (E*\ldots *F) \hspace{3.4em} \hbox{(if an odd number of -)} E/1 \; \; ==\; \; E \\ 0/E \; \; ==\; \; 0 \\ (-E)/(-F)\; \; ==\; E/F \\ E^1 \; \; ==\; \; E \\ E^0 \; \; ==\; \; 1 \\ 1^ E \; \; ==\; \; 1 \\ -(i) \; \; ==\; \; (-i) \ \ \ \hbox{where $i$ is a literal} \\ -((-i)) \; \; ==\; \; i \ \ \ \hbox{where $i$ is a literal} \\ i=j \; \; ==\; \; \mathord {\top }\; \; \hbox{or}\; \; \mathord {\bot }\; \; \hbox{(computation)}\; \; \ \ \ \hbox{where $i$ and $j$ are literals} \\ i \leq j \; \; ==\; \; \mathord {\top }\; \; \hbox{or}\; \; \mathord {\bot }\; \; \hbox{(computation)}\; \; \ \ \ \hbox{where $i$ and $j$ are literals} \\ i < j \; \; ==\; \; \mathord {\top }\; \; \hbox{or}\; \; \mathord {\bot }\; \; \hbox{(computation)}\; \; \ \ \ \hbox{where $i$ and $j$ are literals} \\ i \geq j \; \; ==\; \; \mathord {\top }\; \; \hbox{or}\; \; \mathord {\bot }\; \; \hbox{(computation)}\; \; \ \ \ \hbox{where $i$ and $j$ are literals} \\ i > j \; \; ==\; \; \mathord {\top }\; \; \hbox{or}\; \; \mathord {\bot }\; \; \hbox{(computation)}\; \; \ \ \ \hbox{where $i$ and $j$ are literals} \\ E \leq E \; \; ==\; \; \mathord {\top }\\ E < E \; \; ==\; \; \mathord {\bot }\\ E \geq E \; \; ==\; \; \mathord {\top }\\ E > E \; \; ==\; \; \mathord {\bot }\\ \end{array} $]]</center>
| |
| − | | |
| − | ==utomatic inference rules ==
| |
| − | | |
| − | The following inference rules are ''applied automatically'' in a systematic fashion 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.
| |
| − | | |
| − | <br />
| |
| − | | |
| − | '''Axioms'''
| |
| − | | |
| − | <center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H},\hbox{\bf P} \; \; \vdash \; \; \hbox{\bf P} \end{array} \ \ \ \ \ \ {\sf HYP} \; \; \\ \end{array} </math> <math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H},\hbox{\bf Q} \; \; \vdash \; \; \hbox{\bf P} \lor \ldots \lor \hbox{\bf Q} \lor \ldots \lor \hbox{\bf R} \end{array} \ \ \ \ \ \ {\sf HYP\_ OR}\; \; \\ \end{array} </math></center><center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H},\; \hbox{\bf P},\; \neg \, \hbox{\bf P} \; \; \vdash \; \; \hbox{\bf Q} \end{array} \ \ \ \ \ \ {\sf CNTR} \; \; \\ \end{array} </math></center><center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H},\mathord {\bot }\; \; \vdash \; \; \hbox{\bf P} \end{array} \ \ \ \ \ \ {\sf FALSE\_ HYP} \; \; \\ \end{array} </math> <math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H} \; \; \vdash \; \; \mathord {\top }\end{array} \ \ \ \ \ \ {\sf TRUE\_ GOAL} \; \; \\ \end{array} </math></center>
| |
| − | | |
| − | '''Simplification'''
| |
| − | | |
| − | <center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H},\; \hbox{\bf P} \; \; \vdash \; \; \hbox{\bf Q} \\[.5ex] \hbox{\bf H},\; \hbox{\bf P},\; \hbox{\bf P} \; \; \vdash \; \; \hbox{\bf Q} \end{array} \ \ \ \ \ {\sf DBL\_ HYP} \; \; \\ \end{array} </math></center>
| |
| − | | |
| − | '''Conjunction'''
| |
| − | | |
| − | <center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H},\hbox{\bf P},\hbox{\bf Q} \; \; \vdash \; \; \hbox{\bf R} \\[.5ex] \hbox{\bf H},\; \hbox{\bf P} \land \hbox{\bf Q} \; \; \vdash \; \; \hbox{\bf R} \end{array} \ \ \ \ \ {\sf AND\_ L} \; \; \\ \end{array} </math> <math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H} \; \; \vdash \; \; \hbox{\bf P} \hspace{4em} \hbox{\bf H} \; \; \vdash \; \; \hbox{\bf Q}\\[.5ex] \hbox{\bf H} \; \; \vdash \; \; \hbox{\bf P} \; \land \; \hbox{\bf Q} \end{array} \ \ \ \ \ {\sf AND\_ R} \; \; \\ \end{array} </math></center>
| |
| − | | |
| − | '''Implication'''
| |
| − | | |
| − | <center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H},\; \hbox{\bf Q},\; \hbox{\bf P} \land \ldots \land \hbox{\bf R} \mathbin \Rightarrow \hbox{\bf S} \; \; \vdash \; \; \hbox{\bf T} \\[.5ex] \hbox{\bf H},\; \hbox{\bf Q},\; \hbox{\bf P} \land \ldots \land \hbox{\bf Q} \land \ldots \land \hbox{\bf R} \mathbin \Rightarrow \hbox{\bf S} \; \; \vdash \; \; \hbox{\bf T} \end{array} \ \ \ \ \ {\sf IMP\_ L1} \; \; \\ \end{array} </math></center><center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H}, \hbox{\bf P} \; \; \vdash \; \; \hbox{\bf Q} \\[.5ex] \hbox{\bf H} \; \; \vdash \; \; \hbox{\bf P} \mathbin \Rightarrow \hbox{\bf Q} \end{array} \ \ \ \ \ {\sf IMP\_ R} \; \; \\ \end{array} </math></center><center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H},\hbox{\bf P} \mathbin \Rightarrow \hbox{\bf Q}, \hbox{\bf P} \mathbin \Rightarrow \hbox{\bf R}\; \; \vdash \; \; \hbox{\bf S} \\[.5ex] \hbox{\bf H},\; \hbox{\bf P} \mathbin \Rightarrow \hbox{\bf Q} \land \hbox{\bf R} \; \; \vdash \; \; \hbox{\bf S} \end{array} \ \ \ \ \ {\sf IMP\_ AND\_ L} \; \; \\ \end{array} </math> <math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H},\hbox{\bf P} \mathbin \Rightarrow \hbox{\bf R}, \hbox{\bf Q} \mathbin \Rightarrow \hbox{\bf R}\; \; \vdash \; \; \hbox{\bf S} \\[.5ex] \hbox{\bf H},\; \hbox{\bf P} \lor \hbox{\bf Q} \mathbin \Rightarrow \hbox{\bf R} \; \; \vdash \; \; \hbox{\bf S} \end{array} \ \ \ \ \ {\sf IMP\_ OR\_ L} \; \; \\ \end{array} </math></center>
| |
| − | | |
| − | '''Negation'''
| |
| − | | |
| − | <center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H},\; E \in \{ a,\ldots , c\} \; \; \vdash \; \; \; \; \hbox{\bf P} \\[.5ex] \hbox{\bf H},\; E \in \{ a,\ldots , b, \ldots , c\} , \neg \, (E=b) \; \; \vdash \; \; \hbox{\bf P} \end{array} \ \ \ \ \ {\sf } \; \; \\ \end{array} </math></center><center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H},\; E \in \{ a,\ldots , c\} \; \; \vdash \; \; \; \; \hbox{\bf P} \\[.5ex] \hbox{\bf H},\; E \in \{ a,\ldots , b, \ldots , c\} , \neg \, (b=E) \; \; \vdash \; \; \hbox{\bf P} \end{array} \ \ \ \ \ {\sf } \; \; \\ \end{array} </math></center>
| |
| − | | |
| − | '''Quantification'''
| |
| − | | |
| − | <center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H},\; \hbox{\bf P(x)} \; \; \vdash \; \; \hbox{\bf Q} \\[.5ex] \hbox{\bf H},\; \exists \, \hbox{\bf x}\, \mathord {\mkern 1mu\cdot \mkern 1mu}\, \hbox{\bf P(x)} \; \; \vdash \; \; \hbox{\bf Q} \end{array} \ \ \ \ \ \begin{array}{c} \hbox{\sf \boldmath XST\_ L} \\ \hbox{({\bf x} not free in {\bf H} and {\bf Q})} \end{array}\; \; \; \\ \end{array} </math></center><center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H}\; \; \vdash \; \; \hbox{\bf P(x)} \\[.5ex] \hbox{\bf H} \; \; \vdash \; \; \forall \hbox{\bf x}\, \mathord {\mkern 1mu\cdot \mkern 1mu}\, \hbox{\bf P(x)} \end{array} \ \ \ \ \ \begin{array}{c} \hbox{\sf \boldmath ALL\_ R} \\ \hbox{({\bf x} not free in {\bf H})} \end{array}\; \; \; \\ \end{array} </math></center>
| |
| − | | |
| − | '''Equality'''
| |
| − | | |
| − | <center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H(E)} \; \; \vdash \; \; \; \; \hbox{\bf P(E)} \\[.5ex] \hbox{\bf H(x)},\; x=E \; \; \vdash \; \; \hbox{\bf P(x)} \end{array} \ \ \ \ \ {\sf EQL\_ LR} \; \; \\ \end{array} </math> <math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H(E)} \; \; \vdash \; \; \; \; \hbox{\bf P(E)} \\[.5ex] \hbox{\bf H(x)},\; E=x \; \; \vdash \; \; \hbox{\bf P(x)} \end{array} \ \ \ \ \ {\sf EQL\_ RL} \; \; \\ \end{array} </math></center>
| |
| − | | |
| − | In these two rules <math>x</math> is a variable which is not free in <math>E</math>
| |
| − | | |
| − | == 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:
| |
| − | | |
| − | <center>[[Image:um-0147.png|\includegraphics[scale=.4]{snapshots/pic129}]]</center>
| |
| − | | |
| − | In the left part you can see the ordered sequence of individual tactics composing the post-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.
| |
| − | | |
| − | = Interactive Tactics =
| |
| − | | |
| − | In this section, the rewrite rules and inference rules, which you can use to perform an interactive proof, are presented. Each of these rules 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.
| |
| − | | |
| − | == Interactive Rewrite Rules ==
| |
| − | | |
| − | Most of the rewrite rules correspond to distributive laws. For associative operators in connection with such laws as in:
| |
| − | | |
| − | <center><math> P \land (Q \lor \ldots \lor R) </math></center>
| |
| − | | |
| − | 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.
| |
| − | | |
| − | <br />
| |
| − | | |
| − | '''Conjunction'''
| |
| − | | |
| − | <center><math> \begin{array}{l} P \land (Q \lor R) \; \; ==\; \; (P \land Q) \lor (P \land R) \end{array} </math></center>
| |
| − | | |
| − | '''Disjunction'''
| |
| − | | |
| − | <center><math> \begin{array}{l} P \lor (Q \land R) \; \; ==\; \; (P \lor Q) \land (P \lor R) \\ P \lor Q \lor \ldots \lor R \; \; ==\; \; \neg \, P \mathbin \Rightarrow (Q \lor \ldots \lor R) \end{array} </math></center>
| |
| − | | |
| − | '''Implication'''
| |
| − | | |
| − | <center><math> \begin{array}{l} P \mathbin \Rightarrow Q \; \; ==\; \; \neg \, Q \mathbin \Rightarrow \neg P \\ P \mathbin \Rightarrow (Q \mathbin \Rightarrow R) \; \; ==\; \; P \land Q \mathbin \Rightarrow R \\ P \mathbin \Rightarrow (Q \land R) \; \; ==\; \; (P \mathbin \Rightarrow Q) \; \land \; (P \mathbin \Rightarrow R) \\ P \lor Q \; \mathbin \Rightarrow \; R\; \; ==\; \; (P \mathbin \Rightarrow R) \; \land \; (Q \mathbin \Rightarrow R) \end{array} </math></center>
| |
| − | | |
| − | '''Equivalence'''
| |
| − | | |
| − | <center><math> \begin{array}{l} P \mathbin \Leftrightarrow Q \; \; ==\; \; (P \mathbin \Rightarrow Q) \; \land \; (Q \mathbin \Rightarrow P) \end{array} </math></center>
| |
| − | | |
| − | '''Negation'''
| |
| − | | |
| − | <center><math> \begin{array}{l} \neg \, (P \land Q) \; \; ==\; \; \neg \, P \lor \neg \, Q \\ \neg \, (P \lor Q) \; \; ==\; \; \neg \, P \land \neg \, Q \\ \neg \, (P \mathbin \Rightarrow Q)\; \; ==\; \; P \land \neg \, Q \\ \neg \, \forall x \, \mathord {\mkern 1mu\cdot \mkern 1mu}\, P \; \; ==\; \; \exists x \, \mathord {\mkern 1mu\cdot \mkern 1mu}\, \neg \, P \\ \neg \, \exists x \, \mathord {\mkern 1mu\cdot \mkern 1mu}\, P \; \; ==\; \; \forall x \, \mathord {\mkern 1mu\cdot \mkern 1mu}\, \neg \, P \\ \neg \, (S = \emptyset ) \; \; ==\; \; \exists x \, \mathord {\mkern 1mu\cdot \mkern 1mu}\, x \in S \end{array} </math></center>
| |
| − | | |
| − | '''Set Theory'''
| |
| − | | |
| − | Most of the rules are concerned with simplifying set membership predicates.
| |
| − | | |
| − | <center><math> \begin{array}{l} E \mapsto F \; \in \; S \mathbin \times T \; \; ==\; \; E \in S \; \land \; F \in T \\ E \in \mathop {\mathbb P\hbox{}}\nolimits (S) \; \; ==\; \; E \subseteq S \\ S \subseteq T \; \; ==\; \; \forall x\, \mathord {\mkern 1mu\cdot \mkern 1mu}\, (\, x\in S \; \mathbin \Rightarrow \; x \in T\, ) \end{array} </math></center>
| |
| − | | |
| − | In the previous rule, <math>x</math> denotes several variables when the type of <math>S</math> and <math>T</math> is a Cartesian product.
| |
| − | | |
| − | <center><math> \begin{array}{l} E \in S \mathbin {\mkern 1mu\cup \mkern 1mu}T \; \; ==\; \; E \in S \; \lor \; E \in T \\ E \in S \mathbin {\mkern 1mu\cap \mkern 1mu}T \; \; ==\; \; E \in S \; \land \; E \in T \\ E \in S \setminus T \; \; ==\; \; E \in S \; \land \; \neg \, (E \in T) \\ E \in \{ A, \ldots , B\} \; \; \; ==\; \; \; E=A \; \lor \; \ldots \; \lor \; E=B \\ E \in \mathop {\mathrm{union}}\nolimits \, (S)\; \; ==\; \; \exists s \, \mathord {\mkern 1mu\cdot \mkern 1mu}\, s \in S \; \land \; E \in s \\ \; E \in (\bigcup \nolimits \; x \, \mathord {\mkern 1mu\cdot \mkern 1mu}\, x \in S \; \land \; P\; |\; T\, ) \; \; ==\; \; \exists x \, \mathord {\mkern 1mu\cdot \mkern 1mu}\, x \in S \; \land \; P \; \land \; E \in T \\ \; E \; \in \; \mathop {\mathrm{inter}}\nolimits \, (S) \; \; ==\; \; \forall s \, \mathord {\mkern 1mu\cdot \mkern 1mu}\, s \in S \; \mathbin \Rightarrow \; E \in s \\ \; E \; \in \; (\bigcap \nolimits \; x \, \mathord {\mkern 1mu\cdot \mkern 1mu}\, x \in S \; \land \; P\; |\; T\, )\; \; ==\; \; \forall x \, \mathord {\mkern 1mu\cdot \mkern 1mu}\, x \in S \; \land \; P \; \mathbin \Rightarrow \; E \in T \\ E \in \mathop {\mathrm{dom}}\nolimits (r)\; \; ==\; \; \exists y \, \mathord {\mkern 1mu\cdot \mkern 1mu}\, E \mapsto y \; \in \; r \\ F \in \mathop {\mathrm{ran}}\nolimits (r) \; \; ==\; \; \exists x \, \mathord {\mkern 1mu\cdot \mkern 1mu}\, x \mapsto F \; \in \; r \\ E \mapsto F \in r^{-1}\; \; ==\; \; F \mapsto E \in r \\ E \mapsto F \; \in \; S \mathbin \lhd r \; \; ==\; \; E \in S \; \; \land \; \; E \mapsto F \in r \\ E \mapsto F \; \in \; r \mathbin \rhd T \; \; ==\; \; E \mapsto F \in r \; \; \land \; \; F \in T \\ E \mapsto F \; \in \; S \mathbin {\lhd \mkern -14mu-}r \; \; ==\; \; E \notin S \; \; \land \; \; E \mapsto F \in r \\ E \mapsto F \; \in \; r \mathbin {\rhd \mkern -14mu-}T\; \; ==\; \; E \mapsto F \in r \; \; \land \; \; F \notin T \\ F \in r[w]\; \; ==\; \; \exists x \, \mathord {\mkern 1mu\cdot \mkern 1mu}\, x \in w \; \; \land \; \; x \mapsto F \in r \\ E \mapsto F \in (p \mathbin ;q)\; \; ==\; \; \exists x \, \mathord {\mkern 1mu\cdot \mkern 1mu}\, E \mapsto x \in p \; \; \land \; \; x \mapsto F \in q \\ p \mathbin {\lhd \mkern -9mu-}q\; \; ==\; \; (\mathop {\mathrm{dom}}\nolimits \, (q) \mathbin {\lhd \mkern -14mu-}p) \; \mathbin {\mkern 1mu\cup \mkern 1mu}\; q \\ E \mapsto F \in {\sf id}\, (S)\; \; ==\; \; E \in S \; \; \land \; \; F=E \\ E \mapsto (F \mapsto G) \in p \mathbin \otimes q\; \; ==\; \; E \mapsto F \in p \; \; \land \; \; E \mapsto G \in q \\ (E \mapsto G) \mapsto (F \mapsto H) \in p \mathbin \| q\; \; ==\; \; E \mapsto F \in p \; \; \land \; \; G \mapsto H \in q \\ r \in S \mathbin {\leftarrow \mkern -14mu\leftrightarrow }T \; \; ==\; \; r \in S \mathbin \leftrightarrow T \; \land \; \mathop {\mathrm{dom}}\nolimits (r) = S \\ r \in S \mathbin {\leftrightarrow \mkern -14mu\rightarrow }T \; \; ==\; \; r \in S \mathbin \leftrightarrow T \; \land \; \mathop {\mathrm{ran}}\nolimits (r) = T \\ r \in S \mathbin {\leftrightarrow \mkern -14mu\leftrightarrow }T \; \; ==\; \; r \in S \mathbin \leftrightarrow T \; \land \; \mathop {\mathrm{dom}}\nolimits (r) = S \; \land \; \mathop {\mathrm{ran}}\nolimits (r) = T \\ f \in S \mathbin {\mkern 6mu\mapstochar \mkern -6mu\rightarrow } T \; \; ==\; \; f \in S \mathbin \leftrightarrow T \; \land \; \forall x,y,z \mathord {\mkern 1mu\cdot \mkern 1mu}x\mapsto y \in f \; \land \; x \mapsto z \in f \; \mathbin \Rightarrow \; y=z \\ f \in S \mathbin \rightarrow T \; \; ==\; \; f \in S \mathbin {\mkern 6mu\mapstochar \mkern -6mu\rightarrow } T \; \land \; \mathop {\mathrm{dom}}\nolimits (f)=S \\ f \in S \mathbin {\mkern 9mu\mapstochar \mkern -9mu\rightarrowtail } T \; \; ==\; \; f \in S \mathbin {\mkern 6mu\mapstochar \mkern -6mu\rightarrow } T \; \land \; f^{-1} \in T \mathbin {\mkern 6mu\mapstochar \mkern -6mu\rightarrow } S \end{array} </math></center><center><math> \begin{array}{l} f \in S \mathbin \rightarrowtail T \; \; ==\; \; f \in S \mathbin {\mkern 9mu\mapstochar \mkern -9mu\rightarrowtail } T \; \land \; \mathop {\mathrm{dom}}\nolimits (f) = S \\ f \in S \mathbin {\mkern 6mu\mapstochar \mkern -6mu\twoheadrightarrow } T \; \; ==\; \; f \in S \mathbin {\mkern 6mu\mapstochar \mkern -6mu\rightarrow } T \; \land \; \mathop {\mathrm{ran}}\nolimits (f) = T \\ f \in S \mathbin \twoheadrightarrow T \; \; ==\; \; f \in S \mathbin {\mkern 6mu\mapstochar \mkern -6mu\twoheadrightarrow } T \; \land \; \mathop {\mathrm{dom}}\nolimits (f) = S\\ f \in S \mathbin { \rightarrowtail \mkern -18mu\twoheadrightarrow } T \; \; ==\; \; f \in S \mathbin \rightarrowtail T \; \land \; \mathop {\mathrm{ran}}\nolimits (f)=T \\ (p \mathbin {\mkern 1mu\cup \mkern 1mu}q)^{-1} \; \; ==\; \; p^{-1} \mathbin {\mkern 1mu\cup \mkern 1mu}q^{-1} \\ (p \mathbin {\mkern 1mu\cap \mkern 1mu}q)^{-1} \; \; ==\; \; p^{-1} \mathbin {\mkern 1mu\cap \mkern 1mu}q^{-1} \\ (s \mathbin \lhd r)^{-1} \; \; ==\; \; r^{-1} \mathbin \rhd s \\ (s \mathbin {\lhd \mkern -14mu-}r)^{-1} \; \; ==\; \; r^{-1} \mathbin {\rhd \mkern -14mu-}s \\ (r \mathbin \rhd s)^{-1} \; \; ==\; \; s \mathbin \lhd r^{-1} \\ (r \mathbin {\rhd \mkern -14mu-}s)^{-1} \; \; ==\; \; s \mathbin \lhd r^{-1} \\ (p \mathbin ;q)^{-1} \; \; ==\; \; q^{-1} \mathbin ;p^{-1} \\ (s \mathbin {\mkern 1mu\cup \mkern 1mu}t) \mathbin \lhd r \; \; ==\; \; (s \mathbin \lhd r) \mathbin {\mkern 1mu\cup \mkern 1mu}(t \mathbin \lhd r) \\ (s \mathbin {\mkern 1mu\cap \mkern 1mu}t) \mathbin \lhd r \; \; ==\; \; (s \mathbin \lhd r) \mathbin {\mkern 1mu\cap \mkern 1mu}(t \mathbin \lhd r) \\ (s \mathbin {\mkern 1mu\cup \mkern 1mu}t) \mathbin {\lhd \mkern -14mu-}r \; \; ==\; \; (s \mathbin {\lhd \mkern -14mu-}r) \mathbin {\mkern 1mu\cap \mkern 1mu}(t \mathbin {\lhd \mkern -14mu-}r) \\ (s \mathbin {\mkern 1mu\cap \mkern 1mu}t) \mathbin {\lhd \mkern -14mu-}r \; \; ==\; \; (s \mathbin {\lhd \mkern -14mu-}r) \mathbin {\mkern 1mu\cup \mkern 1mu}(t \mathbin {\lhd \mkern -14mu-}r) \\ s \mathbin \lhd (p \mathbin {\mkern 1mu\cup \mkern 1mu}q) \; \; ==\; \; (s \mathbin \lhd p) \mathbin {\mkern 1mu\cup \mkern 1mu}(s \mathbin \lhd q) \\ s \mathbin \lhd (p \mathbin {\mkern 1mu\cap \mkern 1mu}q) \; \; ==\; \; (s \mathbin \lhd p) \mathbin {\mkern 1mu\cap \mkern 1mu}(s \mathbin \lhd q) \\ s \mathbin {\lhd \mkern -14mu-}(p \mathbin {\mkern 1mu\cup \mkern 1mu}q) \; \; ==\; \; (s \mathbin {\lhd \mkern -14mu-}p) \mathbin {\mkern 1mu\cup \mkern 1mu}(s \mathbin {\lhd \mkern -14mu-}q) \\ s \mathbin {\lhd \mkern -14mu-}(p \mathbin {\mkern 1mu\cap \mkern 1mu}q) \; \; ==\; \; (s \mathbin {\lhd \mkern -14mu-}p) \mathbin {\mkern 1mu\cap \mkern 1mu}(s \mathbin {\lhd \mkern -14mu-}q) \\ r \mathbin \rhd (s \mathbin {\mkern 1mu\cup \mkern 1mu}t) \; \; ==\; \; (r \mathbin \rhd s) \mathbin {\mkern 1mu\cup \mkern 1mu}(r \mathbin \rhd t) \\ r \mathbin \rhd (s \mathbin {\mkern 1mu\cap \mkern 1mu}t) \; \; ==\; \; (r \mathbin \rhd s) \mathbin {\mkern 1mu\cap \mkern 1mu}(r \mathbin \rhd t) \\ r \mathbin {\rhd \mkern -14mu-}(s \mathbin {\mkern 1mu\cup \mkern 1mu}t) \; \; ==\; \; (r \mathbin {\rhd \mkern -14mu-}s) \mathbin {\mkern 1mu\cap \mkern 1mu}(r \mathbin {\rhd \mkern -14mu-}t) \\ r \mathbin {\rhd \mkern -14mu-}(s \mathbin {\mkern 1mu\cap \mkern 1mu}t) \; \; ==\; \; (r \mathbin {\rhd \mkern -14mu-}s) \mathbin {\mkern 1mu\cup \mkern 1mu}(r \mathbin {\rhd \mkern -14mu-}t) \\ (p \mathbin {\mkern 1mu\cup \mkern 1mu}q) \mathbin \rhd s \; \; ==\; \; (p \mathbin \rhd s) \mathbin {\mkern 1mu\cup \mkern 1mu}(q \mathbin \rhd s) \\ (p \mathbin {\mkern 1mu\cap \mkern 1mu}q) \mathbin \rhd s \; \; ==\; \; (p \mathbin \rhd s) \mathbin {\mkern 1mu\cap \mkern 1mu}(q \mathbin \rhd s) \\ (p \mathbin {\mkern 1mu\cup \mkern 1mu}q) \mathbin {\rhd \mkern -14mu-}s \; \; ==\; \; (p \mathbin {\rhd \mkern -14mu-}s) \mathbin {\mkern 1mu\cup \mkern 1mu}(q \mathbin {\rhd \mkern -14mu-}s) \\ (p \mathbin {\mkern 1mu\cap \mkern 1mu}q) \mathbin {\rhd \mkern -14mu-}s \; \; ==\; \; (p \mathbin {\rhd \mkern -14mu-}s) \mathbin {\mkern 1mu\cap \mkern 1mu}(q \mathbin {\rhd \mkern -14mu-}s) \\ r[S \mathbin {\mkern 1mu\cup \mkern 1mu}T] \; \; ==\; \; r[S] \mathbin {\mkern 1mu\cup \mkern 1mu}r[T] \end{array} </math></center><center><math> \begin{array}{l} (p \mathbin {\mkern 1mu\cup \mkern 1mu}q)[S] \; \; ==\; \; p[S] \mathbin {\mkern 1mu\cup \mkern 1mu}q[S] \\ \mathop {\mathrm{dom}}\nolimits (p \mathbin {\mkern 1mu\cup \mkern 1mu}q) \; \; ==\; \; \mathop {\mathrm{dom}}\nolimits (p) \mathbin {\mkern 1mu\cup \mkern 1mu}\mathop {\mathrm{dom}}\nolimits (q) \\ \mathop {\mathrm{ran}}\nolimits (p \mathbin {\mkern 1mu\cup \mkern 1mu}q) \; \; ==\; \; \mathop {\mathrm{ran}}\nolimits (p) \mathbin {\mkern 1mu\cup \mkern 1mu}\mathop {\mathrm{ran}}\nolimits (q) \\ S \subseteq T \; \; ==\; \; (U \setminus T) \subseteq (U \setminus S) \end{array} </math></center>
| |
| − | | |
| − | In the previous rule, the type of <math>S</math> and <math>T</math> is <math>\mathop {\mathbb P\hbox{}}\nolimits (U)</math>.
| |
| − | | |
| − | <center><math> \begin{array}{l} S = T \; \; ==\; \; S \subseteq T \; \land \; T \subseteq S \end{array} </math></center>
| |
| − | | |
| − | In the previous rule, <math>S</math> and <math>T</math> are sets
| |
| − | | |
| − | <center><math> \begin{array}{l} S \; \subseteq \; A \setminus B \; \; ==\; \; S \subseteq A \; \, \land \; \, S \mathbin {\mkern 1mu\cap \mkern 1mu}B = \emptyset \\ p \mathbin ;(q \mathbin {\mkern 1mu\cup \mkern 1mu}r) \; \; ==\; \; (p \mathbin ;q) \mathbin {\mkern 1mu\cup \mkern 1mu}(p \mathbin ;r) \\ (q \mathbin {\mkern 1mu\cup \mkern 1mu}r) \mathbin ;p \; \; ==\; \; (q \mathbin ;p) \mathbin {\mkern 1mu\cup \mkern 1mu}(r \mathbin ;p) \\ (p \mathbin ;q)[s] \; \; ==\; \; q[p[s]] \\ (s \mathbin \lhd p) \mathbin ;q \; \; ==\; \; s \mathbin \lhd (p \mathbin ;q) \\ (s \mathbin {\lhd \mkern -14mu-}p) \mathbin ;q \; \; ==\; \; s \mathbin {\lhd \mkern -14mu-}(p \mathbin ;q) \\ p \mathbin ;(q \mathbin \rhd s) \; \; ==\; \; (p \mathbin ;q) \mathbin \rhd s \\ p \mathbin ;(q \mathbin {\rhd \mkern -14mu-}s) \; \; ==\; \; (p \mathbin ;q) \mathbin {\rhd \mkern -14mu-}s \\ U \setminus (S \mathbin {\mkern 1mu\cap \mkern 1mu}T) \; \; ==\; \; (U\setminus S) \mathbin {\mkern 1mu\cup \mkern 1mu}(U \setminus T) \\ U \setminus (S \mathbin {\mkern 1mu\cup \mkern 1mu}T) \; \; ==\; \; (U\setminus S) \mathbin {\mkern 1mu\cap \mkern 1mu}(U \setminus T) \\ U \setminus (S \setminus T) \; \; ==\; \; (U\setminus S) \mathbin {\mkern 1mu\cup \mkern 1mu}T \\ \end{array} </math></center>
| |
| − | | |
| − | In the three previous rules, <math>S</math> and <math>T</math> are supposed to be of type <math>\mathop {\mathbb P\hbox{}}\nolimits (U)</math>.
| |
| − | | |
| − | '''Cardinality'''
| |
| − | | |
| − | <center><math> \begin{array}{l} \mathop {\mathrm{card}}\nolimits \, (S) \leq \mathop {\mathrm{card}}\nolimits (T) \; \; ==\; \; S \subseteq T \\ \mathop {\mathrm{card}}\nolimits \, (S) \geq \mathop {\mathrm{card}}\nolimits (T) \; \; ==\; \; T \subseteq S \\ \mathop {\mathrm{card}}\nolimits \, (S) < \mathop {\mathrm{card}}\nolimits (T) \; \; ==\; \; S \subset T \\ \mathop {\mathrm{card}}\nolimits \, (S) > \mathop {\mathrm{card}}\nolimits (T) \; \; ==\; \; T \subset S \\ \mathop {\mathrm{card}}\nolimits \, (S) = \mathop {\mathrm{card}}\nolimits (T) \; \; ==\; \; S = T \end{array} </math></center>
| |
| − | | |
| − | In the five previous rules, <math>S</math> and <math>T</math> must be of the same type.
| |
| − | | |
| − | == Interactive Inference rules ==
| |
| − | | |
| − | '''Disjunction'''
| |
| − | | |
| − | <center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H}, \; \hbox{\bf P} \; \; \vdash \; \; \hbox{\bf R} \ \ \ \ \ldots \ \ \ \ \hbox{\bf H}, \; \hbox{\bf Q} \; \; \vdash \; \; \hbox{\bf R} \\[.5ex] \hbox{\bf H},\; \hbox{\bf P} \lor \ldots \lor \hbox{\bf Q} \; \; \vdash \; \; \hbox{\bf R} \end{array} \ \ \ \ \ {\sf CASE} \; \; \\ \end{array} </math></center>
| |
| − | | |
| − | '''Implication'''
| |
| − | | |
| − | <center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H} \; \; \vdash \; \; \hbox{\bf P} \hspace{3em} \hbox{\bf H},\; \hbox{\bf P},\; \hbox{\bf Q} \; \; \vdash \; \; \hbox{\bf R} \\[.5ex] \hbox{\bf H},\; \hbox{\bf P} \mathbin \Rightarrow \hbox{\bf Q} \; \; \vdash \; \; \hbox{\bf R} \end{array} \ \ \ \ \ {\sf MH} \; \; \\ \end{array} </math></center><center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H} \; \; \vdash \; \; \neg \, \hbox{\bf Q} \hspace{3em} \hbox{\bf H},\; \neg \, \hbox{\bf Q},\; \neg \, \hbox{\bf P} \; \; \vdash \; \; \hbox{\bf R} \\[.5ex] \hbox{\bf H},\; \hbox{\bf P} \mathbin \Rightarrow \hbox{\bf Q} \; \; \vdash \; \; \hbox{\bf R} \end{array} \ \ \ \ \ {\sf HM} \; \; \\ \end{array} </math></center>
| |
| − | | |
| − | '''Equivalence'''
| |
| − | | |
| − | <center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H(Q)}, \hbox{\bf P} \mathbin \Leftrightarrow \hbox{\bf Q} \; \; \vdash \; \; \hbox{\bf G(Q)}\\[.5ex] \hbox{\bf H(P)},\; \hbox{\bf P} \mathbin \Leftrightarrow \hbox{\bf Q} \; \; \vdash \; \; \hbox{\bf G(P)} \end{array} \ \ \ \ \ {\sf EQV} \hbox{ \ \ \ \bf postponed}\; \; \; \\ \end{array} </math></center>
| |
| − | | |
| − | '''Set Theory'''
| |
| − | | |
| − | <center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H},\; G=E ,\; \hbox{\bf P}(F)\; \; \vdash \; \; \hbox{\bf Q} \hspace{3em} \hbox{\bf H},\; \neg \, (G=E) ,\; \hbox{\bf P}(f(G))\; \; \vdash \; \; \hbox{\bf Q}\\[.5ex] \hbox{\bf H},\; \hbox{\bf P}((f\mathbin {\lhd \mkern -9mu-}\{ E \mapsto F\} )(G)) \; \; \vdash \; \; \hbox{\bf Q} \end{array} \ \ \ \ \ {\sf OV\_ L} \; \; \\ \end{array} </math></center><center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H},\; G=E \; \; \vdash \; \; \hbox{\bf Q}(F) \hspace{3em} \hbox{\bf H},\; \neg \, (G=E) \; \; \vdash \; \; \hbox{\bf Q}(f(G))\\[.5ex] \hbox{\bf H} \; \; \vdash \; \; \hbox{\bf Q}((f\mathbin {\lhd \mkern -9mu-}\{ E \mapsto F\} )(G)) \end{array} \ \ \ \ \ {\sf OV\_ R} \; \; \\ \end{array} </math></center><center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H},\; G \in \mathop {\mathrm{dom}}\nolimits (g) ,\; \hbox{\bf P}(g(G))\; \; \vdash \; \; \hbox{\bf Q} \hspace{3em} \hbox{\bf H},\; \neg \, G \in \mathop {\mathrm{dom}}\nolimits (g) ,\; \hbox{\bf P}(f(G))\; \; \vdash \; \; \hbox{\bf Q}\\[.5ex] \hbox{\bf H},\; \hbox{\bf P}((f\mathbin {\lhd \mkern -9mu-}g)(G)) \; \; \vdash \; \; \hbox{\bf Q} \end{array} \ \ \ \ \ {\sf OV\_ L} \; \; \\ \end{array} </math></center><center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H},\; G \in \mathop {\mathrm{dom}}\nolimits (g) \; \; \vdash \; \; \hbox{\bf Q}(g(G)) \hspace{3em} \hbox{\bf H},\; \neg \, G \in \mathop {\mathrm{dom}}\nolimits (g) \; \; \vdash \; \; \hbox{\bf Q}(f(G))\\[.5ex] \hbox{\bf H} \; \; \vdash \; \; \hbox{\bf Q}((f\mathbin {\lhd \mkern -9mu-}g)(G)) \end{array} \ \ \ \ \ {\sf OV\_ R} \; \; \\ \end{array} </math></center>
| |
| − | | |
| − | In the four previous rules the <math>\mathbin {\lhd \mkern -9mu-}</math> operator must appear at the "top level"
| |
| − | | |
| − | <center>[[Image:um-0173.png|$ \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H} \; \; \vdash \; \; f^{-1} \in A \mathbin {\mkern 6mu\mapstochar \mkern -6mu\rightarrow } B \hspace{3em}\hbox{\bf H} \; \; \vdash \; \; \hbox{\bf Q}(f[S] \mathbin {\mkern 1mu\cap \mkern 1mu}f[T]) \\[.5ex] \hbox{\bf H} \; \; \vdash \; \; \hbox{\bf Q}(f[S \mathbin {\mkern 1mu\cap \mkern 1mu}T]) \end{array} \ \ \ \ \ \hbox{\sf $\mathbin {\mkern 1mu\cap \mkern 1mu}$DIS\_ R} \; \; \\ \end{array} $]]</center><center>[[Image:um-0174.png|$ \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H} \; \; \vdash \; \; f \in A \mathbin {\mkern 6mu\mapstochar \mkern -6mu\rightarrow } B \hspace{3em}\hbox{\bf H} \; \; \vdash \; \; \hbox{\bf Q}(f^{-1}[S] \setminus f^{-1}[T]) \\[.5ex] \hbox{\bf H} \; \; \vdash \; \; \hbox{\bf Q}(f^{-1}[S \setminus T]) \end{array} \ \ \ \ \ \hbox{\sf $\setminus $DIS\_ R} \; \; \\ \end{array} $]]</center>
| |
| − | | |
| − | In the two previous rules, the occurrence of <math>f^{-1}</math> must appear at the "top level". Moreover <math>A</math> and <math>B</math> denote some type. Similar left distribution rules exist
| |
| − | | |
| − | <center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H} \; \; \vdash \; \; \hbox{WD}(\hbox{\bf Q}(\{ f(E)\} )) \hspace{3em}\hbox{\bf H} \; \; \vdash \; \; \hbox{\bf Q}(\{ f(E)\} ) \\[.5ex] \hbox{\bf H} \; \; \vdash \; \; \hbox{\bf Q}(f[\{ E\} ]) \end{array} \ \ \ \ \ \hbox{\sf SIM\_ R} \; \; \\ \end{array} </math></center>
| |
| − | | |
| − | In the previous rule, the occurrence of <math>f</math> must appear at the "top level". A similar left simplification rule exists.
| |
| − | | |
| − | <center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H} \; \; \vdash \; \; \hbox{WD}(\hbox{\bf Q}(g(f(x)))) \hspace{3em}\hbox{\bf H} \; \; \vdash \; \; \hbox{\bf Q}(g(f(x))) \\[.5ex] \hbox{\bf H} \; \; \vdash \; \; \hbox{\bf Q}((f \mathbin ;g)(x)) \end{array} \ \ \ \ \ \hbox{\sf SIM\_ R} \; \; \\ \end{array} </math></center>
| |
| − | | |
| − | In the previous rule, the occurrence of <math>f \mathbin ;g</math> must appear at the "top level". A similar left simplification rule exists.
| |
| − | | |
| − | '''Finiteness'''
| |
| − | | |
| − | <center>[[Image:um-0182.png|$ \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H} \; \; \vdash \; \; S \subseteq T \hspace{4em} \hbox{\bf H} \; \; \vdash \; \; \mathop {\mathrm{finite}}\nolimits \, (T)\\[.5ex] \hbox{\bf H} \; \; \vdash \; \; \mathop {\mathrm{finite}}\nolimits \, (S) \end{array} \ \ \ \ \ \ \ \hbox{\sf fin$\subseteq $\_ R} \; \; \; \\ \end{array} $]]</center>
| |
| − | | |
| − | For applying the previous rule, the user has to write the set corresponding to <math>T</math> in the editing area of the Proof Control Window.
| |
| − | | |
| − | <center>[[Image:um-0183.png|$ \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H} \; \; \vdash \; \; \mathop {\mathrm{finite}}\nolimits \, (S) \; \lor \; \ldots \; \lor \; \mathop {\mathrm{finite}}\nolimits \, (T)\\[.5ex] \hbox{\bf H} \; \; \vdash \; \; \mathop {\mathrm{finite}}\nolimits \, (S \; \mathbin {\mkern 1mu\cap \mkern 1mu}\; \ldots \; \mathbin {\mkern 1mu\cap \mkern 1mu}\; T) \end{array} \ \ \ \ \ \ \ \hbox{\sf fin$\mathbin {\mkern 1mu\cap \mkern 1mu}$\_ R} \; \; \; \\ \end{array} $]]</center><center>[[Image:um-0184.png|$ \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H} \; \; \vdash \; \; \mathop {\mathrm{finite}}\nolimits \, (S)\\[.5ex] \hbox{\bf H} \; \; \vdash \; \; \mathop {\mathrm{finite}}\nolimits \, (S \; \setminus \; T) \end{array} \ \ \ \ \ \ \ \hbox{\sf fin$\setminus $\_ R} \; \; \; \\ \end{array} $]]</center><center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H} \; \; \vdash \; \; r \; \in \; S \mathbin \leftrightarrow T \hspace{3em} \hbox{\bf H} \; \; \vdash \; \; \mathop {\mathrm{finite}}\nolimits \, (S) \hspace{3em} \hbox{\bf H} \; \; \vdash \; \; \mathop {\mathrm{finite}}\nolimits \, (T)\\[.5ex] \hbox{\bf H} \; \; \vdash \; \; \mathop {\mathrm{finite}}\nolimits \, (r) \end{array} \ \ \ \ \ \ \ \hbox{\sf fin\_ rel\_ R} \; \; \; \\ \end{array} </math></center>
| |
| − | | |
| − | For applying the previous rule, the user has to write the set corresponding to <math>S \mathbin \leftrightarrow T</math> in the editing area of the Proof Control Window.
| |
| − | | |
| − | <center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H} \; \; \vdash \; \; \mathop {\mathrm{finite}}\nolimits \, (r) \\[.5ex] \hbox{\bf H} \; \; \vdash \; \; \mathop {\mathrm{finite}}\nolimits \, (r[s]) \end{array} \ \ \ \ \ \ \ \hbox{\sf fin\_ rel\_ img\_ R} \; \; \; \\ \end{array} </math></center><center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H} \; \; \vdash \; \; \mathop {\mathrm{finite}}\nolimits \, (r) \\[.5ex] \hbox{\bf H} \; \; \vdash \; \; \mathop {\mathrm{finite}}\nolimits \, (\mathop {\mathrm{ran}}\nolimits (r)) \end{array} \ \ \ \ \ \ \ \hbox{\sf fin\_ rel\_ ran\_ R} \; \; \; \\ \end{array} </math></center><center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H} \; \; \vdash \; \; \mathop {\mathrm{finite}}\nolimits \, (r) \\[.5ex] \hbox{\bf H} \; \; \vdash \; \; \mathop {\mathrm{finite}}\nolimits \, (\mathop {\mathrm{dom}}\nolimits (r)) \end{array} \ \ \ \ \ \ \ \hbox{\sf fin\_ rel\_ dom\_ R} \; \; \; \\ \end{array} </math></center><center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H} \; \; \vdash \; \; f \; \in \; S \mathbin {\mkern 6mu\mapstochar \mkern -6mu\rightarrow } T \hspace{3em} \hbox{\bf H} \; \; \vdash \; \; \mathop {\mathrm{finite}}\nolimits \, (S) \\[.5ex] \hbox{\bf H} \; \; \vdash \; \; \mathop {\mathrm{finite}}\nolimits \, (f) \end{array} \ \ \ \ \ \ \ \hbox{\sf fin\_ fun1\_ R} \; \; \; \\ \end{array} </math></center>
| |
| − | | |
| − | For applying the previous rule, the user has to write the set corresponding to <math>S \mathbin {\mkern 6mu\mapstochar \mkern -6mu\rightarrow } T</math> in the editing area of the Proof Control Window.
| |
| − | | |
| − | <center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H} \; \; \vdash \; \; f^{-1} \; \in \; S \mathbin {\mkern 6mu\mapstochar \mkern -6mu\rightarrow } T \hspace{3em} \hbox{\bf H} \; \; \vdash \; \; \mathop {\mathrm{finite}}\nolimits \, (S) \\[.5ex] \hbox{\bf H} \; \; \vdash \; \; \mathop {\mathrm{finite}}\nolimits \, (f) \end{array} \ \ \ \ \ \ \ \hbox{\sf fin\_ fun2\_ R} \; \; \; \\ \end{array} </math></center>
| |
| − | | |
| − | For applying the previous rule, the user has to write the set corresponding to <math>S \mathbin {\mkern 6mu\mapstochar \mkern -6mu\rightarrow } T</math> in the editing area of the Proof Control Window.
| |
| − | | |
| − | <center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H} \; \; \vdash \; \; f \; \in \; S \mathbin {\mkern 6mu\mapstochar \mkern -6mu\rightarrow } T \hspace{3em} \hbox{\bf H} \; \; \vdash \; \; \mathop {\mathrm{finite}}\nolimits \, (s) \\[.5ex] \hbox{\bf H} \; \; \vdash \; \; \mathop {\mathrm{finite}}\nolimits \, (f[s]) \end{array} \ \ \ \ \ \ \ \hbox{\sf fin\_ fun\_ img\_ R} \; \; \; \\ \end{array} </math></center><center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H} \; \; \vdash \; \; f \; \in \; S \mathbin {\mkern 6mu\mapstochar \mkern -6mu\rightarrow } T \hspace{3em} \hbox{\bf H} \; \; \vdash \; \; \mathop {\mathrm{finite}}\nolimits \, (S) \\[.5ex] \hbox{\bf H} \; \; \vdash \; \; \mathop {\mathrm{finite}}\nolimits \, (\mathop {\mathrm{ran}}\nolimits (f)) \end{array} \ \ \ \ \ \ \ \hbox{\sf fin\_ fun\_ ran\_ R} \; \; \; \\ \end{array} </math></center>
| |
| − | | |
| − | For applying the previous rule, the user has to write the set corresponding to <math>S \mathbin {\mkern 6mu\mapstochar \mkern -6mu\rightarrow } T</math> in the editing area of the Proof Control Window.
| |
| − | | |
| − | <center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H} \; \; \vdash \; \; f^{-1} \; \in \; S \mathbin {\mkern 6mu\mapstochar \mkern -6mu\rightarrow } T \hspace{3em} \hbox{\bf H} \; \; \vdash \; \; \mathop {\mathrm{finite}}\nolimits \, (S) \\[.5ex] \hbox{\bf H} \; \; \vdash \; \; \mathop {\mathrm{finite}}\nolimits \, (\mathop {\mathrm{dom}}\nolimits (f)) \end{array} \ \ \ \ \ \ \ \hbox{\sf fin\_ fun\_ dom\_ R} \; \; \; \\ \end{array} </math></center>
| |
| − | | |
| − | For applying the previous rule, the user has to write the set corresponding to <math>S \mathbin {\mkern 6mu\mapstochar \mkern -6mu\rightarrow } T</math> in the editing area of the Proof Control Window.
| |
| − | | |
| − | <center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H} \; \; \vdash \; \; \mathop {\mathrm{finite}}\nolimits (S) \\[.5ex] \hbox{\bf H} \; \; \vdash \; \; \exists n\, \mathord {\mkern 1mu\cdot \mkern 1mu}\, (\forall x \, \mathord {\mkern 1mu\cdot \mkern 1mu}\, x \in S \; \mathbin \Rightarrow \; n \leq x) \end{array}\; \; \; \\ \end{array} </math></center><center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H} \; \; \vdash \; \; \mathop {\mathrm{finite}}\nolimits (S) \\[.5ex] \hbox{\bf H} \; \; \vdash \; \; \exists n\, \mathord {\mkern 1mu\cdot \mkern 1mu}\, (\forall x \, \mathord {\mkern 1mu\cdot \mkern 1mu}\, x \in S \; \mathbin \Rightarrow \; x \geq n) \end{array}\; \; \; \\ \end{array} </math></center><center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H} \; \; \vdash \; \; \mathop {\mathrm{finite}}\nolimits (S) \\[.5ex] \hbox{\bf H} \; \; \vdash \; \; \exists n\, \mathord {\mkern 1mu\cdot \mkern 1mu}\, (\forall x \, \mathord {\mkern 1mu\cdot \mkern 1mu}\, x \in S \; \mathbin \Rightarrow \; n \geq x) \end{array}\; \; \; \\ \end{array} </math></center><center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H} \; \; \vdash \; \; \mathop {\mathrm{finite}}\nolimits (S) \\[.5ex] \hbox{\bf H} \; \; \vdash \; \; \exists n\, \mathord {\mkern 1mu\cdot \mkern 1mu}\, (\forall x \, \mathord {\mkern 1mu\cdot \mkern 1mu}\, x \in S \; \mathbin \Rightarrow \; x \leq n) \end{array}\; \; \; \\ \end{array} </math></center>
| |
| − | | |
| − | In the four previous rules, <math>S</math> must not contain any bound variable.
| |
| − | | |
| − | <center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H} \; \; \vdash \; \; \exists n\, \mathord {\mkern 1mu\cdot \mkern 1mu}\, (\forall x \, \mathord {\mkern 1mu\cdot \mkern 1mu}\, x \in S \; \mathbin \Rightarrow \; n \leq x) \hspace{3em} \hbox{\bf H} \; \; \vdash \; \; S \subseteq \mathord {\mathbb Z}\setminus \mathord {\mathbb N_1}\\[.5ex] \hbox{\bf H} \; \; \vdash \; \; \mathop {\mathrm{finite}}\nolimits (S) \end{array}\; \; \; \\ \end{array} </math></center><center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H} \; \; \vdash \; \; \exists n\, \mathord {\mkern 1mu\cdot \mkern 1mu}\, (\forall x \, \mathord {\mkern 1mu\cdot \mkern 1mu}\, x \in S \; \mathbin \Rightarrow \; x \leq n) \hspace{3em} \hbox{\bf H} \; \; \vdash \; \; S \subseteq \mathord {\mathbb N}\\[.5ex] \hbox{\bf H} \; \; \vdash \; \; \mathop {\mathrm{finite}}\nolimits (S) \end{array}\; \; \; \\ \end{array} </math></center>
| |
| − | | |
| − | '''Cardinality'''
| |
| − | | |
| − | <center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H},\, a \leq b \; \; \vdash \; \; \hbox{\bf Q}(b-a+1) \hspace{3em} \hbox{\bf H},\, b < a \; \; \vdash \; \; \hbox{\bf Q}(0) \\[.5ex] \hbox{\bf H} \; \; \vdash \; \; \hbox{\bf Q}(\mathop {\mathrm{card}}\nolimits \, (a\mathbin {.\mkern 1mu.}b)) \end{array}\; \; \; \\ \end{array} </math></center><center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H},\, a \leq b,\, \hbox{\bf P}(a-b+1) \; \; \vdash \; \; \hbox{\bf Q} \hspace{3em} \hbox{\bf H},\, b < a ,\, \hbox{\bf P}(0)\; \; \vdash \; \; \hbox{\bf Q} \\[.5ex] \hbox{\bf H},\, \hbox{\bf P}(\mathop {\mathrm{card}}\nolimits \, (a\mathbin {.\mkern 1mu.}b)) \; \; \vdash \; \; \hbox{\bf Q} \end{array}\; \; \; \\ \end{array} </math></center>
| |
| − | | |
| − | In the two previous rules, <math>\mathop {\mathrm{card}}\nolimits (a \mathbin {.\mkern 1mu.}b)</math> must appear at "top-level".
| |
| − | | |
| − | <center><math> \begin{array}{|l|}\; \; \; \begin{array}{c} \hbox{\bf H} \; \; \vdash \; \; \hbox{\bf P}(S \subseteq T) \\[.5ex] \hbox{\bf H} \; \; \vdash \; \; \hbox{\bf P}(\mathop {\mathrm{card}}\nolimits \, (S) \leq \mathop {\mathrm{card}}\nolimits (T)) \end{array}\; \; \; \\ \end{array} </math></center>
| |
| − | | |
| − | There are similar rules for other cases
| |
| − | | |
| − | </div>{{Navigation|Previous= [[User_Manual_The_Proof_Obligation_Explorer|The Proof Obligation Explorer]]|Next= [[User_Manual_The_Mathematical_Language|The Mathematical Language]]|Up= [[User_Manual_index|User_Manual_index]]}}
| |
| − | n
| |
| − | [[Category:User Documentation|The Proving Perspective]]
| |
| − | [[Category:Rodin Platform|The Proving Perspective]]
| |
| − | [[Category:User Manual|The Proving Perspective]]
| |
