Difference between revisions of "Membership in Goal"

From Event-B
Jump to navigationJump to search
imported>Billaude
imported>Nicolas
 
(46 intermediate revisions by 4 users not shown)
Line 1: Line 1:
 +
{{TOCright}}
 
= Objective =
 
= Objective =
  
This page describes the design of the reasoner MembershipGoal and its associated tactic MembershipGoalTac.<br>
+
This page describes the design of the reasoner MembershipGoal and its associated tactic MembershipGoalTac.
This reasoner discharges sequent whose goal denotes a membership which can be inferred with hypotheses. Here an basic example of what it discharges :<br>
+
 
<math>H,\quad x\in S,\quad S\subset T,\quad T\subseteq U \quad\vdash x\in U</math>
+
This reasoner discharges sequents whose goal denotes a membership which can be inferred from hypotheses, such as the following:
 +
<math>H,\quad x\in S,\quad S\subset T,\quad T\subseteq U \quad\vdash\quad x\in U</math>
  
 
= Analysis =
 
= Analysis =
  
Such sequent are proved by PP and ML. But, these provers have both drawbacks :
+
Usually, such sequents are proved by the external provers PP or ML. But, these provers have several drawbacks :
*All the visible are added as needed hypotheses, which is most of the time not the case.
+
* They do not report needed hypotheses, so that a conservative choice is made to depend on all hypotheses.
*They take quite consequent time to prove it (even with the basic example given here above, the difference in time execution is noticeable).
+
* They take substantial time to prove them (even with the basic example given above, the difference in time execution is noticeable).
*If there are too many hypotheses, or if the expression of the <math>x</math> is too complicated, they may not prove it.
+
* If there are too many hypotheses, or if the expression of the <math>x</math> or the intermediate sets <math>S, T, \dots</math> is too complicated, they may get lost into details and not discharge.
This is particularly true when in the list of inclusion expressions of each side of the relation are not equal. For example : <math>H,\quad a\in S,\quad S\subset T_1\cap T_2,\quad T_1\cup T_3\subseteq  U\quad\vdash a\in U</math>
+
 
 +
This is particularly true when in the set expressions of each side of relations are not equal, such as in:
 +
<math>H,\quad a\in S,\quad S\subset T_1\cap T_2,\quad T_1\cup T_3\subseteq  U\quad\vdash a\in U</math>
 
<p>
 
<p>
Such a reasoner contributes to prove more Proof Obligations automatically, faster and with fewer needed hypotheses which makes proof rule more legible and proof replay less sensitive to modifications.
+
Such a reasoner thus increases the rate of automated proof, faster and with fewer needed hypotheses which makes proof rules more legible and proof replay less sensitive to modifications of the models.
 +
 
 +
= Design Decision =
  
= Tactic =
+
== Tactic ==
  
 
This part explains how the tactic (MembershipGoalTac) associated to the reasoner MembershipGoal is working.
 
This part explains how the tactic (MembershipGoalTac) associated to the reasoner MembershipGoal is working.
== Goal ==
+
=== Goal ===
The tactic (as the reasoner) should works only on goals such as :
+
The tactic (as the reasoner) works only on goals of the form :
*<math><goal>\quad:\quad expresion\quad\in\quad<set></math>
+
*<math>\cdots~\in~\cdots</math>
*<math><member>\quad:\quad expresion\quad\mid\quad FA</math>
+
For example:
*<math><set>\quad:\quad expresion\otimes expresion\quad\mid\quad expresion\parallel expresion\quad\mid\quad <union>\quad\left[\cup <union>\right]</math>
 
*<math><union>\quad:\quad<cprod>\quad\left[\cprod<cprod>\right]</math>
 
*<math><cprod>\quad:\quad\left(<set>\right)\quad\mid\quad expresion</math>
 
For example those examples matches with the definition here above :
 
 
*<math>f(x)\in g\otimes h</math>
 
*<math>f(x)\in g\otimes h</math>
 
*<math>x\in A\cprod\left(B\cup C\right)</math>
 
*<math>x\in A\cprod\left(B\cup C\right)</math>
Every other goals denoting a membership should be re-
+
*<math>x\mapsto y\in A\cprod B</math>
== Hypotheses ==
+
In the last example, the reasoner will not try to prove that <math>x</math> belongs to <math>A</math> and <math>y</math> belongs to <math>B</math>, but that the maplet <math>x\mapsto y</math> belongs to the Cartesian product <math>A\cprod B</math>.
The hard part is to find the hypotheses leading to discharge the sequent. To do so, the tactic recovers three kinds of hypotheses :
+
 
#the ones related to the left member of the goal <math>\left( x\in S\right)</math> (this is the start point):
+
=== Hypotheses ===
 +
Now we have to find hypotheses leading to discharge the sequent. To do so, the tactic looks for two kinds of hypothesis :
 +
#the ones related to the left member of the goal <math>\left( x\in S\right)</math> (which will be used as a starting point):
 
#*<math>x\in \cdots</math>
 
#*<math>x\in \cdots</math>
 
#*<math>\cdots\mapsto x\mapsto\cdots\in\cdots</math>
 
#*<math>\cdots\mapsto x\mapsto\cdots\in\cdots</math>
#*<math>\left\{\cdots, x,\cdots\right\}\subseteq\cdots</math>
+
#*<math>\left\{\cdots, x,\cdots\right\}=/\subset/\subseteq\cdots</math>
#the ones denoting inclusion (all but the ones matching the description of the first point) :
+
#*<math>\left\{\cdots, \cdots\mapsto x\mapsto\cdots,\cdots\right\}=/\subset/\subseteq\cdots</math>
 +
#*<math>f\ovl\left\{\cdots, x, \cdots\right\}=/\subset/\subseteq\cdots</math>
 +
#the ones denoting inclusion (which will be used to find a path from a starting point to the goal) :
 
#*<math>\cdots\subset\cdots</math>
 
#*<math>\cdots\subset\cdots</math>
 
#*<math>\cdots\subseteq\cdots</math>
 
#*<math>\cdots\subseteq\cdots</math>
#the one from which we can infer inclusion :
+
#*<math>\cdots=\cdots</math>
#*<math>f\in A\;op\;B \quad\vdash\quad f\subseteq A\cprod B\quad\bigl(</math> where <math>op</math>  is one of :<math>\quad\rel, \trel, \srel, \strel, \pfun, \tfun, \pinj, \tinj, \psur, \tsur, \tbij\bigr)</math>
+
Then, it will search a link between these hypotheses so that the sequent can be discharged.
#*<math>f\subseteq A\cprod B \quad\vdash\quad f\otimes f\subseteq A\cprod\left(B\cprod B\right)</math>
+
 
Then, it will search a link between those hypotheses so that the sequent can be discharged.
+
=== Find a path ===
== Find a path ==  
+
Now that we have found all the hypotheses that could be useful to the reasoner, it remains to find a path among these hypotheses leading to discharge the sequent. Depending on the relations on each side of the inclusion, we will act differently. <math>f</math> always denotes an expression (it may be a domain, a range, etc.).
Now that we recovered all the hypotheses that could be useful for the reasoner, it <i>just</i> remains to find a path among the hypotheses leading to discharge the sequent. Depending on the relations on each side of the inclusion, we will act differently. <math>f</math> always represent an expression (may be a domain, a range, etc.).
 
 
#The following sequent is provable because <math>f\subseteq \varphi (f)</math>.
 
#The following sequent is provable because <math>f\subseteq \varphi (f)</math>.
 
#*<math>x\in f,\quad \varphi (f)\subseteq g\quad\vdash\quad x\in g</math>
 
#*<math>x\in f,\quad \varphi (f)\subseteq g\quad\vdash\quad x\in g</math>
 
#*<math>\varphi (f) = f\quad\mid\quad f\cup h \quad\mid\quad h\cup f \quad\mid\quad h\ovl f</math>
 
#*<math>\varphi (f) = f\quad\mid\quad f\cup h \quad\mid\quad h\cup f \quad\mid\quad h\ovl f</math>
 +
#*<math>f=g\bunion h\quad\mid\quad \varphi(f)=g\bunion k\bunion h\bunion l</math>
 +
#*<math>f=i\ovl j\quad\mid\quad\varphi(f)=g\ovl h\ovl i\ovl j</math>
 
#The following sequent is provable because <math>\psi (f)\subseteq f</math>.
 
#The following sequent is provable because <math>\psi (f)\subseteq f</math>.
 
#*<math>x\in \psi (f),\quad f\subseteq g\quad\vdash\quad x\in g</math>
 
#*<math>x\in \psi (f),\quad f\subseteq g\quad\vdash\quad x\in g</math>
 
#*<math>\psi (f) = f\quad\mid\quad f\cap h \quad\mid\quad h\cap f \quad\mid\quad f\setminus h \quad\mid\quad f\ransub A \quad\mid\quad f\ranres A \quad\mid\quad A\domsub f \quad\mid\quad A\domres f</math>
 
#*<math>\psi (f) = f\quad\mid\quad f\cap h \quad\mid\quad h\cap f \quad\mid\quad f\setminus h \quad\mid\quad f\ransub A \quad\mid\quad f\ranres A \quad\mid\quad A\domsub f \quad\mid\quad A\domres f</math>
#We can generalized the first two points. This is the Russian dolls system. We can easily prove a sequent with multiple inclusions by going from hypothesis to hypothesis.
+
#*<math>\psi(f)=g\binter h\binter k\binter l\quad\mid\quad f=g\binter k</math>
#*<math>x\in \psi (f),\quad \varphi (f)\subseteq g\quad\vdash\quad x\in g</math>
+
#By keeping the notation <math>\psi(f)\subseteq f\subseteq\varphi(f)</math> we also deduce that :
#For some relations, <i>positions</i> are needed to be known to continue to find hypotheses, but it is not always necessary.
+
#*<math>\psi(A)\domres\psi(f)\subseteq\varphi(A)\domres\varphi(f)</math>
 +
#*<math>\psi(f)\ranres\psi(A)\subseteq\varphi(f)\ranres\varphi(A)</math>
 +
#*<math>\varphi(A)\domsub\psi(f)\subseteq\psi(A)\domres\varphi(f)</math>
 +
#*<math>\psi(f)\ransub\varphi(A)\subseteq\varphi(f)\ransub\psi(A)</math>
 +
#*<math>\psi(f)\setminus\varphi(g)\subseteq\varphi(f)\setminus\psi(g)</math>
 +
#For some relations, [[#positions|positions]] are needed to be known to continue to find hypotheses, but it is not always necessary.
 
#*<math>x\mapsto y\in f,\quad f\subseteq A\cprod B\quad\vdash\quad x\in A</math>
 
#*<math>x\mapsto y\in f,\quad f\subseteq A\cprod B\quad\vdash\quad x\in A</math>
 
#*<math>x\in dom(f),\quad f\subseteq A\cprod B\quad\vdash\quad x\in A</math>
 
#*<math>x\in dom(f),\quad f\subseteq A\cprod B\quad\vdash\quad x\in A</math>
 
#*<math>x\in ran(f),\quad f\subseteq A\cprod B\quad\vdash\quad x\in B</math>
 
#*<math>x\in ran(f),\quad f\subseteq A\cprod B\quad\vdash\quad x\in B</math>
#*<math>x\in f,\quad f\otimes g\subseteq A\cprod\left(B\cprod C\right)\quad\vdash\quad x\in A\cprod B</math>
 
#*<math>x\in f,\quad f\parallel g\subseteq \left(A\cprod C\right)\cprod\left(B\cprod D\right)\quad\vdash\quad x\in A\cprod B</math>
 
#Those rewrites can be useful when the Russian dolls system does not succeed.
 
#*<math>dom(f)\cup dom(g) = dom(f\ovl g)</math>
 
#*<math>ran(f)\cup ran(g)\subseteq ran(f\ovl g)</math>
 
#*<math>dom(A\domres f) = dom(f)\cap A</math>
 
#*<math>ran(f\ranres A) = ran(f)\cap A</math>
 
#*<math>A\subseteq X,\quad\land\quad B\subseteq Y\quad\vdash\quad A\cprod B\subseteq X\cprod Y</math>
 
#*<math>f\in A\;op_1\;B\;\lor\; f\subseteq A\cprod B\quad\vdash\quad f\subseteq A\cprod B</math>
 
#*<math>f\in A\;op_1\;B\;\lor\; f\subseteq A\cprod B\quad\vdash\quad f^{-1}\subseteq B\cprod A</math>
 
#*<math>f\in A\;op_1\;B\;\lor\; f\subseteq A\cprod B\quad\vdash\quad f[A]\subseteq B</math>
 
#*<math>f\in A\;op_1\;B\;\lor\; f\subseteq A\cprod B\quad\vdash\quad f\domres prj1 = prj1\ranres f\subseteq A\cprod B\cprod A</math>
 
#*<math>f\in A\;op_1\;B\;\lor\; f\subseteq A\cprod B\quad\vdash\quad f\domres prj2 = prj2\ranres f\subseteq A\cprod B\cprod B</math>
 
#*<math>f\in A\;op_1\;B\;\lor\; f\subseteq A\cprod B\quad\vdash\quad f\domres id = id\ranres f\subseteq (A\cprod B)\cprod(A\cprod B)</math>
 
#*<math>f\in A\;op_1\;B\;\lor\; f\subseteq A\cprod B,\quad g\in B\;op_2\;C\;\lor\; g\subseteq B\cprod C \quad\vdash\quad f;g = g\circ f \subseteq A\cprod C</math>
 
#*<math>f\in A\;op_1\;B\;\lor\; f\subseteq A\cprod B,\quad g\in A\;op_2\;C\;\lor\; g\subseteq A\cprod C \quad\vdash\quad f\otimes g \subseteq A\cprod (B\cprod C)</math>
 
#*<math>f\in A\;op_1\;B\;\lor\; f\subseteq A\cprod B,\quad g\in C\;op_2\;D\;\lor\; g\subseteq C\cprod D \quad\vdash\quad f\parallel g \subseteq (A\cprod C)\cprod (B\cprod D)</math>
 
#:<math>\bigl(</math> where <math>op_1</math> and <math>op_2</math> are ones of :<math>\quad\rel, \trel, \srel, \strel, \pfun, \tfun, \pinj, \tinj, \psur, \tsur, \tbij\bigr)</math>
 
  
By using these inclusion and rewrites, it tries to find a path among the recovered hypotheses. Every hypotheses denoting an inclusion should be used only once. Every hypotheses from which new hypothesis can be inferred could be used as many times as wanted. Among all paths that lead to discharge the sequent, the tactic give the first it finds. Moreover, so that the reasoner does not do the same work as the tactic of writing new hypothesis, it gives all needed hypotheses and added hypotheses in the input.
+
By using these inclusions the tactic tries to find a path among the recovered hypotheses. Every one of them should only be used once, avoiding possible infinite loop <math>\left(A\subseteq B,\; B\subseteq A\right)</math>.
 +
 
 +
Since Rodin 3.0, the path search is delegated to the [http://www.sat4j.org Sat4j] solver. The problem encoding to SAT is done by representing each inclusion of the form <math>A\subseteq B</math> into the clause <math>\{\lnot x\in A,\; x\in B\}</math> and feeding the solver with all clauses that derive from the hypotheses and the negation of the goal. As soon as the solver reports the problem as unsatisfiable, the tactic obtains an unsat core and traces it back to the corresponding hypotheses.
 +
 
 +
== Reasoner ==
 +
 
 +
This part describe how the reasoner MembershipGoal works.
 +
 
 +
==== Goal ====
 +
 
 +
First, it checks that the goal matches the description made in the part [[#Tactic|tactic]] : <math>x\in S</math>. Thus, we record the member ''x'' as well as the set ''S''
 +
 
 +
==== Input ====
 +
 
 +
Then, it checks that the input is a hypothesesReasonerInput (an input with an array of predicates). Every given predicates must be a hypothesis of the sequent. Only one must be a membership with the same member as the goal so that there are no ambiguity. All the other ones must denote set inclusion or equality.
 +
 
 +
==== Find a path ====
 +
 
 +
With the same reasoning as for the tactic, we try to find a path leading to discharge the goal.
 +
 
 +
==== Trusted Base ====
 +
 
 +
At that point, the reasoner performs the same jobs as the tactic which is quite complicated. That poses one problem : it is hard to prove the reasoner to be sound (only doing what it was meant to, not discharging sequents that cannot be proved). Because the reasoner is in the trusted base, we should be absolutely sure of what it performs. How to validate the found path ?
 +
 
 +
As we know, the reasoner condense several inferences rules in only one proof rule. To validate the found path, we have to validate every single inference rule. To achieve it, we create, internally to the reasoner, a small proof tree built from internal proof rules (implemented in class Rules). Each rule contains one predicate and an array of rules (its antecedents). When the path is searched, the corresponding rule is created. When the path is found, we check that the predicate of the root rule is the same as the goal. If not, it means the found path was incorrect, so the reasoner fails, else the sequent is discharged.
 +
 
 +
Example of rules :
 +
:<math>name\;of\;the\;rule\quad\frac{predicate\;of\;first\;antecedent\cdots predicate\;of\;last\;antecedent}{consequent\;of\;that\;rule}\left[parameters\right]</math>
 +
:<math>Hypothesis\quad\frac{}{predicate}\left[predicate\right]</math>
 +
:<math>IncludeBunion\quad\frac{A\bunion B\bunion C\bunion D\subseteq Z}{B\bunion C\subseteq Z}\left[B,~C\right]</math>
 +
:<math>Composition\quad\frac{x\in A,~A\subseteq B}{x\in B}\left[~\right]</math>
 +
 
 +
= Implementation =
 +
 
 +
This section explains how the reasoner has been implemented.
 +
 
 +
=== Hypotheses ===
 +
From the hypotheses, the reasoner derives new hypotheses leading to discharge the sequent. As explained in the design decision part, there are two kinds of hypotheses which are recovered (membership and inclusion). So, we developped two extractors which extract useful predicates from the hypotheses with these [[#Inference rules|inference rules]]. For each new hypothesis a rationale is built, this rationale contains the derived predicate and a rule used as a justification.
 +
 +
=== Find a path ===
 +
 
 +
Let's consider the following sequent : <math> x \in B,\quad f \ovl \{ x \mapsto y \} \in A \rel B,\quad dom(A \cprod B) \subseteq C,\quad A \binter B\binter C \subseteq D \quad\vdash\quad x\in D </math>
 +
 
 +
 
 +
From the hypotheses and the negation of the goal the reasoner derives new predicates.
 +
For instance, from the hypothesis "<math> f \ovl \{ x \mapsto y \} \in A \rel B </math>" the reasoner derives the predicates <math>x \in A</math> and <math>x \in dom(A \cprod B)</math>.
 +
 
 +
Afterwards, the reasoner has to encode the new predicates in SAT clauses. For this purpose, it converts all new hypotheses in SAT proposition by extracting all set contained into the predicate. And then, it encodes the proposition SAT in Dimacs CNF format. Finally, the clauses encoded are inserted one by one into the SAT problem until the solver reports the problem as unsatisfiable in order to obtain a minimal solution to the SAT core.
 +
 
 +
{| class="wikitable" style="text-align:center; width:80%;"
 +
|+ SAT problem encoding
 +
|-
 +
! scope=col | Sequent
 +
! scope=col | SAT proposition
 +
! scope=col | Dimacs CNF format
 +
|-
 +
|<math>x \in B</math>
 +
|<math>x \in B</math>
 +
|<math>2</math>
 +
|-
 +
|<math>x \in A</math>
 +
|<math>x \in A</math>
 +
|<math>3</math>
 +
|-
 +
|<math>x \in dom(A \cprod B)</math>
 +
|<math>x \in dom(A \cprod B)</math>
 +
|<math>4</math>
 +
|-
 +
|<math>dom(A \cprod B) \subseteq C</math>
 +
|<math> \lnot x \in dom(A \cprod B),\quad x \in C </math>
 +
|<math>-4 \quad 5 </math>
 +
|-
 +
|<math>A \binter B \binter C \subseteq D</math>
 +
|<math>\lnot x \in A, \quad \lnot x \in B, \quad \lnot x \in C, \quad x \in D </math>
 +
|<math>-3 \quad -2 \quad -5 \quad 1</math>
 +
|-
 +
|<math> \vdash\quad x \in D </math>
 +
|<math>\lnot x \in D</math>
 +
|<math>-1</math>
 +
|}
 +
 
 +
Afterwards, the reasoner traces each clause of the explanation returned by the SAT solver back to the corresponding hypotheses. However, the clauses returned by the SAT solver are sorted by their insertion order in the SAT core. So the reasoner reorders them by using topological sorting. Specifically, when the reasoner adds a rationale, we are guaranteed that all rationales on which it depends are already in the list.
 +
 
 +
Now, the reasoner has to build the path, for each hypothesis into the list, a new rationale is built and saved into an array at the index of the list. If the hypothesis denotes a membership, the rationale is directly saved into the array. Else the reasoner retrieves from the array all rationales on which it depends and then from these rationales it builds a new rationale and saves it into the array.   
 +
 
 +
However, the path building is unidirectional, it works with a sat problem with clauses containing whith at most one positive literal. Indeed, the current version can't find a path with hypotheses in the following form :
 +
* <math> x \in ... \binter / \bunion ... </math>
 +
* <math> ... \subseteq ... \binter / \bunion ... </math>
 +
 
 +
 
 +
An example of found path in a tree form:
 +
 
 +
    Comp: <math> x \in D </math>
 +
        ├──  Hyp:  <math> A \binter B \binter C \subseteq D </math>
 +
        └──  Inter: <math> x \in A \binter B \binter C </math>
 +
                ├──  Hyp: <math> x \in A </math>
 +
                ├──  Hyp: <math> x \in B </math>
 +
                └──  Comp: <math> x \in C </math>
 +
                        ├──  Hyp: <math> dom(A \cprod  B) \subseteq C </math>
 +
                        └──  Hyp: <math> x \in dom(A \cprod B) </math>
  
= Reasoner =
 
  
This part describes how the reasoner works.
+
Finally, the reasoner checks that the generated rule from the rationale is equal to the goal. If so, the sequent is discharged. Else, a failure is returned
  
== Goal ==
+
= Inference rules =
The goal must match the same kind of goal as describes in the tactic part.
 
  
== Input ==
+
Here the rules that should be implemented for the reasoner MembershipGoal.  
Because we do not want to do the job of re-writing, every added hypotheses used to discharge the sequent should be contained in the input (the reasoner must extend HypothesesReasoner) as well as hypotheses used to perform the re-writing and hypotheses used to discharge the sequent. Thus we get those obligations :
 
*Every added hypotheses must be re-writable with hypotheses contained in the sequent and in the input.
 
*Every added hypotheses should be used to discharge the sequent.
 
*Hypotheses used to perform re-writing could be also used to discharge a sequent and may be used several times to prove that added hypotheses are re-writable.
 
*Hypotheses used to discharge the sequent should be used only once in the path (no loop allowed).
 
*It checks that with all these hypotheses can actually discharge the sequent
 
  
If all those tests pass, then the sequent is discharged. The added hypotheses are set as AddedHyps, and all the other hypotheses of the input are set as NeededHps.
+
{| class="wikitable" style="text-align:center; width:80%;"
 +
|+ Inference rules for the reasoner MembershipGoal
 +
|-
 +
! scope=col | Inference Rule
 +
! scope=col | Side condition
 +
! scope=col | Implemented
 +
|-
 +
|align="left"|<math> x\in A,\;\; A\subseteq B\vdash x\in B </math>
 +
|align="left"|
 +
|<math>\checkmark</math>
 +
|-
 +
|align="left"|<math> A\subset B\vdash A\subseteq B </math>
 +
|align="left"|
 +
|<math>\checkmark</math>
 +
|-
 +
|align="left"|<math> A=B\vdash A\subseteq B</math>
 +
|align="left"|
 +
|<math>\checkmark</math>
 +
|-
 +
|align="left"|<math> A=B\vdash B\subseteq A</math>
 +
|align="left"|
 +
|<math>\checkmark</math>
 +
|-
 +
|align="left"|<math> A\subseteq B\vdash \dom(A)\subseteq\dom(B)</math>
 +
|align="left"|
 +
|<math>\checkmark</math>
 +
|-
 +
|align="left"|<math> A\subseteq B\vdash \ran(A)\subseteq\ran(B)</math>
 +
|align="left"|
 +
|<math>\checkmark</math>
 +
|-
 +
|align="left"|<math> x\in\dom(A\cprod B)\vdash x\in A</math>
 +
|align="left"|
 +
|<math>\checkmark</math>
 +
|-
 +
|align="left"|<math> y\in\ran(A\cprod B)\vdash y\in B</math>
 +
|align="left"|
 +
|<math>\checkmark</math>
 +
|-
 +
|align="left"|<math> x\mapsto y\in f\vdash x\in\dom(f)</math>
 +
|align="left"|
 +
|<math>\checkmark</math>
 +
|-
 +
|align="left"|<math> x\mapsto y\in f\vdash y\in\ran(f)</math>
 +
|align="left"|
 +
|<math>\checkmark</math>
 +
|-
 +
|align="left"|<math> \left\{a,\cdots,x,\cdots, z\right\}\subseteq A\vdash x\in A</math>
 +
|align="left"|
 +
|<math>\checkmark</math>
 +
|-
 +
|align="left"|<math> f\ovl\cdots\ovl g\ovl\cdots\ovl h\subseteq A\vdash g\ovl\cdots\ovl h\subseteq A</math>
 +
|align="left"|
 +
|<math>\checkmark</math>
 +
|-
 +
|align="left"|<math> f\in A\;op\;B\vdash f\subseteq A\cprod B</math>
 +
|align="left"|where <math>\mathit{op}</math> is one of <math>\rel</math>, <math>\trel</math>, <math>\srel</math>, <math>\strel</math>, <math>\pfun</math>, <math>\tfun</math>, <math>\pinj</math>, <math>\tinj</math>, <math>\psur</math>, <math>\tsur</math>, <math>\tbij</math>
 +
|<math>\checkmark</math>
 +
|-
 +
|align="left"|<math>e\subseteq f,\;\; f\setminus g\subseteq h\quad\vdash\quad e\setminus g\subseteq h</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>g\subseteq k,\;\; f\setminus g\subseteq h \quad\vdash\quad f\setminus k\subseteq h</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>e\subseteq f\setminus g,\;\; f\subseteq h\quad\vdash\quad e\subseteq h\setminus g</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>e\subseteq f\setminus g,\;\; k\subseteq g \quad\vdash\quad e\subseteq f\setminus k</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>e\subseteq f,\;\; f\ranres B\subseteq g \quad\vdash\quad e\ranres B\subseteq g</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>A\subseteq B ,\;\; f\ranres B\subseteq g \quad\vdash\quad f\ranres A\subseteq g</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>f\subseteq g\ranres A ,\;\; g\subseteq h \quad\vdash\quad f\subseteq h\ranres A</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>f\subseteq g\ranres A ,\;\; A\subseteq B \quad\vdash\quad f\subseteq g\ranres B</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>A\subseteq B ,\;\; B\domres f\subseteq g \quad\vdash\quad A\domres f\subseteq g</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>e\subseteq f ,\;\; B\domres f\subseteq g \quad\vdash\quad B\domres e\subseteq g</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>f\subseteq A\domres g ,\;\; A\subseteq B \quad\vdash\quad f\subseteq B\domres g</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>f\subseteq A\domres g ,\;\; g\subseteq h \quad\vdash\quad f\subseteq A\domres h</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>e\subseteq f ,\;\; f\ransub A\subseteq g \quad\vdash\quad e\ransub A\subseteq g</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>f\ransub A\subseteq g ,\;\; A\subseteq B \quad\vdash\quad f\ransub B\subseteq g</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>f\subseteq g\ransub A ,\;\; g\subseteq h \quad\vdash\quad f\subseteq h\ransub A</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>f\subseteq g\ransub B ,\;\; A\subseteq B \quad\vdash\quad f\subseteq g\ransub A</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>A\domsub f\subseteq g ,\;\; A\subseteq B \quad\vdash\quad B\domsub f\subseteq g</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>e\subseteq f ,\;\; A\domsub f\subseteq g \quad\vdash\quad A\domsub e\subseteq g</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>A\subseteq B ,\;\; f\subseteq B\domsub g \quad\vdash\quad f\subseteq A\domsub g</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>f\subseteq A\domsub g ,\;\; g\subseteq h \quad\vdash\quad f\subseteq A\domsub h</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>e\subseteq f ,\;\; f\ovl g\ovl\cdots\ovl h\subseteq k \quad\vdash\quad e\ovl g\ovl\cdots\ovl h\subseteq k</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>f\subseteq g\ovl h\ovl\cdots\ovl k ,\;\; e\subseteq g \quad\vdash\quad f\subseteq e\ovl h\ovl\cdots\ovl k</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>Z\subseteq B,\;\; A\bunion\cdots\bunion B\bunion\cdots\bunion C\subseteq D\quad\vdash\quad A\bunion\cdots\bunion Z\bunion\cdots\bunion C\subseteq D</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>B\subseteq Z ,\;\; D\subseteq A\bunion\cdots\bunion B\bunion\cdots\bunion C \quad\vdash\quad D\subseteq A\bunion\cdots\bunion Z\bunion\cdots\bunion C</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>Z\subseteq B,\;\; A\binter\cdots\binter B\binter\cdots\binter C\subseteq D\quad\vdash\quad A\binter\cdots\binter Z\binter\cdots\binter C\subseteq D</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>B\subseteq Z ,\;\; D\subseteq A\binter\cdots\binter B\binter\cdots\binter C \quad\vdash\quad D\subseteq A\binter\cdots\binter Z\binter\cdots\binter C</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>A\subseteq B,\;\; B\cprod D\subseteq E \quad\vdash\quad A\cprod D\subseteq E</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>C\subseteq D,\;\; B\cprod D\subseteq E \quad\vdash\quad B\cprod C\subseteq E</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>A\subseteq B\cprod D,\;\; B\subseteq C \quad\vdash\quad A\subseteq C\cprod D</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>A\subseteq B\cprod D,\;\; D\subseteq E\quad\vdash\quad A\subseteq B\cprod E</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>\dom(f\domres\prjone)\defi f</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>\dom(f\domres\prjtwo)\defi f</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>\dom(f\domres\id)\defi f</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>\ran(\prjone\ranres f)\defi f</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>\ran(\prjtwo\ranres f)\defi f</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>\ran(\id\ranres f)\defi f</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>\ran(f\domres\prjone)\defi\dom(f)</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>\ran(f\domres\prjtwo)\defi\ran(f)</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|align="left"|<math>\ran(f\domres\id)\defi f</math>
 +
|align="left"|
 +
|<math></math>
 +
|-
 +
|}
  
 
[[Category:Design proposal]]
 
[[Category:Design proposal]]

Latest revision as of 13:50, 5 June 2014

Objective

This page describes the design of the reasoner MembershipGoal and its associated tactic MembershipGoalTac.

This reasoner discharges sequents whose goal denotes a membership which can be inferred from hypotheses, such as the following:

H,\quad x\in S,\quad S\subset T,\quad T\subseteq U \quad\vdash\quad x\in U

Analysis

Usually, such sequents are proved by the external provers PP or ML. But, these provers have several drawbacks :

  • They do not report needed hypotheses, so that a conservative choice is made to depend on all hypotheses.
  • They take substantial time to prove them (even with the basic example given above, the difference in time execution is noticeable).
  • If there are too many hypotheses, or if the expression of the x or the intermediate sets S, T, \dots is too complicated, they may get lost into details and not discharge.

This is particularly true when in the set expressions of each side of relations are not equal, such as in:

H,\quad a\in S,\quad S\subset T_1\cap T_2,\quad T_1\cup T_3\subseteq  U\quad\vdash a\in U

Such a reasoner thus increases the rate of automated proof, faster and with fewer needed hypotheses which makes proof rules more legible and proof replay less sensitive to modifications of the models.

Design Decision

Tactic

This part explains how the tactic (MembershipGoalTac) associated to the reasoner MembershipGoal is working.

Goal

The tactic (as the reasoner) works only on goals of the form :

  • \cdots~\in~\cdots

For example:

  • f(x)\in g\otimes h
  • x\in A\cprod\left(B\cup C\right)
  • x\mapsto y\in A\cprod B

In the last example, the reasoner will not try to prove that x belongs to A and y belongs to B, but that the maplet x\mapsto y belongs to the Cartesian product A\cprod B.

Hypotheses

Now we have to find hypotheses leading to discharge the sequent. To do so, the tactic looks for two kinds of hypothesis :

  1. the ones related to the left member of the goal \left( x\in S\right) (which will be used as a starting point):
    • x\in \cdots
    • \cdots\mapsto x\mapsto\cdots\in\cdots
    • \left\{\cdots, x,\cdots\right\}=/\subset/\subseteq\cdots
    • \left\{\cdots, \cdots\mapsto x\mapsto\cdots,\cdots\right\}=/\subset/\subseteq\cdots
    • f\ovl\left\{\cdots, x, \cdots\right\}=/\subset/\subseteq\cdots
  2. the ones denoting inclusion (which will be used to find a path from a starting point to the goal) :
    • \cdots\subset\cdots
    • \cdots\subseteq\cdots
    • \cdots=\cdots

Then, it will search a link between these hypotheses so that the sequent can be discharged.

Find a path

Now that we have found all the hypotheses that could be useful to the reasoner, it remains to find a path among these hypotheses leading to discharge the sequent. Depending on the relations on each side of the inclusion, we will act differently. f always denotes an expression (it may be a domain, a range, etc.).

  1. The following sequent is provable because f\subseteq \varphi (f).
    • x\in f,\quad \varphi (f)\subseteq g\quad\vdash\quad x\in g
    • \varphi (f) = f\quad\mid\quad f\cup h \quad\mid\quad h\cup f \quad\mid\quad h\ovl f
    • f=g\bunion h\quad\mid\quad \varphi(f)=g\bunion k\bunion h\bunion l
    • f=i\ovl j\quad\mid\quad\varphi(f)=g\ovl h\ovl i\ovl j
  2. The following sequent is provable because \psi (f)\subseteq f.
    • x\in \psi (f),\quad f\subseteq g\quad\vdash\quad x\in g
    • \psi (f) = f\quad\mid\quad f\cap h \quad\mid\quad h\cap f \quad\mid\quad f\setminus h \quad\mid\quad f\ransub A \quad\mid\quad f\ranres A \quad\mid\quad A\domsub f \quad\mid\quad A\domres f
    • \psi(f)=g\binter h\binter k\binter l\quad\mid\quad f=g\binter k
  3. By keeping the notation \psi(f)\subseteq f\subseteq\varphi(f) we also deduce that :
    • \psi(A)\domres\psi(f)\subseteq\varphi(A)\domres\varphi(f)
    • \psi(f)\ranres\psi(A)\subseteq\varphi(f)\ranres\varphi(A)
    • \varphi(A)\domsub\psi(f)\subseteq\psi(A)\domres\varphi(f)
    • \psi(f)\ransub\varphi(A)\subseteq\varphi(f)\ransub\psi(A)
    • \psi(f)\setminus\varphi(g)\subseteq\varphi(f)\setminus\psi(g)
  4. For some relations, positions are needed to be known to continue to find hypotheses, but it is not always necessary.
    • x\mapsto y\in f,\quad f\subseteq A\cprod B\quad\vdash\quad x\in A
    • x\in dom(f),\quad f\subseteq A\cprod B\quad\vdash\quad x\in A
    • x\in ran(f),\quad f\subseteq A\cprod B\quad\vdash\quad x\in B

By using these inclusions the tactic tries to find a path among the recovered hypotheses. Every one of them should only be used once, avoiding possible infinite loop \left(A\subseteq B,\; B\subseteq A\right).

Since Rodin 3.0, the path search is delegated to the Sat4j solver. The problem encoding to SAT is done by representing each inclusion of the form A\subseteq B into the clause \{\lnot x\in A,\; x\in B\} and feeding the solver with all clauses that derive from the hypotheses and the negation of the goal. As soon as the solver reports the problem as unsatisfiable, the tactic obtains an unsat core and traces it back to the corresponding hypotheses.

Reasoner

This part describe how the reasoner MembershipGoal works.

Goal

First, it checks that the goal matches the description made in the part tactic : x\in S. Thus, we record the member x as well as the set S

Input

Then, it checks that the input is a hypothesesReasonerInput (an input with an array of predicates). Every given predicates must be a hypothesis of the sequent. Only one must be a membership with the same member as the goal so that there are no ambiguity. All the other ones must denote set inclusion or equality.

Find a path

With the same reasoning as for the tactic, we try to find a path leading to discharge the goal.

Trusted Base

At that point, the reasoner performs the same jobs as the tactic which is quite complicated. That poses one problem : it is hard to prove the reasoner to be sound (only doing what it was meant to, not discharging sequents that cannot be proved). Because the reasoner is in the trusted base, we should be absolutely sure of what it performs. How to validate the found path ?

As we know, the reasoner condense several inferences rules in only one proof rule. To validate the found path, we have to validate every single inference rule. To achieve it, we create, internally to the reasoner, a small proof tree built from internal proof rules (implemented in class Rules). Each rule contains one predicate and an array of rules (its antecedents). When the path is searched, the corresponding rule is created. When the path is found, we check that the predicate of the root rule is the same as the goal. If not, it means the found path was incorrect, so the reasoner fails, else the sequent is discharged.

Example of rules :

name\;of\;the\;rule\quad\frac{predicate\;of\;first\;antecedent\cdots predicate\;of\;last\;antecedent}{consequent\;of\;that\;rule}\left[parameters\right]
Hypothesis\quad\frac{}{predicate}\left[predicate\right]
IncludeBunion\quad\frac{A\bunion B\bunion C\bunion D\subseteq Z}{B\bunion C\subseteq Z}\left[B,~C\right]
Composition\quad\frac{x\in A,~A\subseteq B}{x\in B}\left[~\right]

Implementation

This section explains how the reasoner has been implemented.

Hypotheses

From the hypotheses, the reasoner derives new hypotheses leading to discharge the sequent. As explained in the design decision part, there are two kinds of hypotheses which are recovered (membership and inclusion). So, we developped two extractors which extract useful predicates from the hypotheses with these inference rules. For each new hypothesis a rationale is built, this rationale contains the derived predicate and a rule used as a justification.

Find a path

Let's consider the following sequent :  x \in B,\quad f \ovl \{ x \mapsto y \} \in A \rel B,\quad dom(A \cprod B) \subseteq C,\quad A \binter B\binter C \subseteq D \quad\vdash\quad x\in D


From the hypotheses and the negation of the goal the reasoner derives new predicates. For instance, from the hypothesis " f \ovl \{ x \mapsto y \} \in A \rel B " the reasoner derives the predicates x \in A and x \in dom(A \cprod B).

Afterwards, the reasoner has to encode the new predicates in SAT clauses. For this purpose, it converts all new hypotheses in SAT proposition by extracting all set contained into the predicate. And then, it encodes the proposition SAT in Dimacs CNF format. Finally, the clauses encoded are inserted one by one into the SAT problem until the solver reports the problem as unsatisfiable in order to obtain a minimal solution to the SAT core.

SAT problem encoding
Sequent SAT proposition Dimacs CNF format
x \in B x \in B 2
x \in A x \in A 3
x \in dom(A \cprod B) x \in dom(A \cprod B) 4
dom(A \cprod B) \subseteq C  \lnot x \in dom(A \cprod B),\quad x \in C -4 \quad 5
A \binter B \binter C \subseteq D \lnot x \in A, \quad \lnot x \in B, \quad \lnot x \in C, \quad x \in D -3 \quad -2 \quad -5 \quad 1
 \vdash\quad x \in D \lnot x \in D -1

Afterwards, the reasoner traces each clause of the explanation returned by the SAT solver back to the corresponding hypotheses. However, the clauses returned by the SAT solver are sorted by their insertion order in the SAT core. So the reasoner reorders them by using topological sorting. Specifically, when the reasoner adds a rationale, we are guaranteed that all rationales on which it depends are already in the list.

Now, the reasoner has to build the path, for each hypothesis into the list, a new rationale is built and saved into an array at the index of the list. If the hypothesis denotes a membership, the rationale is directly saved into the array. Else the reasoner retrieves from the array all rationales on which it depends and then from these rationales it builds a new rationale and saves it into the array.

However, the path building is unidirectional, it works with a sat problem with clauses containing whith at most one positive literal. Indeed, the current version can't find a path with hypotheses in the following form :

  •  x \in ... \binter / \bunion ...
  •  ... \subseteq ... \binter / \bunion ...


An example of found path in a tree form:

    Comp:  x \in D 
       ├──  Hyp:   A \binter B \binter C \subseteq D 
       └──  Inter:  x \in A \binter B \binter C 
               ├──  Hyp:  x \in A 
               ├──  Hyp:  x \in B 
               └──  Comp:  x \in C 
                       ├──  Hyp:  dom(A \cprod  B) \subseteq C 
                       └──  Hyp:  x \in dom(A \cprod B) 


Finally, the reasoner checks that the generated rule from the rationale is equal to the goal. If so, the sequent is discharged. Else, a failure is returned

Inference rules

Here the rules that should be implemented for the reasoner MembershipGoal.

Inference rules for the reasoner MembershipGoal
Inference Rule Side condition Implemented
 x\in A,\;\; A\subseteq B\vdash x\in B \checkmark
 A\subset B\vdash A\subseteq B \checkmark
 A=B\vdash A\subseteq B \checkmark
 A=B\vdash B\subseteq A \checkmark
 A\subseteq B\vdash \dom(A)\subseteq\dom(B) \checkmark
 A\subseteq B\vdash \ran(A)\subseteq\ran(B) \checkmark
 x\in\dom(A\cprod B)\vdash x\in A \checkmark
 y\in\ran(A\cprod B)\vdash y\in B \checkmark
 x\mapsto y\in f\vdash x\in\dom(f) \checkmark
 x\mapsto y\in f\vdash y\in\ran(f) \checkmark
 \left\{a,\cdots,x,\cdots, z\right\}\subseteq A\vdash x\in A \checkmark
 f\ovl\cdots\ovl g\ovl\cdots\ovl h\subseteq A\vdash g\ovl\cdots\ovl h\subseteq A \checkmark
 f\in A\;op\;B\vdash f\subseteq A\cprod B where \mathit{op} is one of \rel, \trel, \srel, \strel, \pfun, \tfun, \pinj, \tinj, \psur, \tsur, \tbij \checkmark
e\subseteq f,\;\; f\setminus g\subseteq h\quad\vdash\quad e\setminus g\subseteq h
g\subseteq k,\;\; f\setminus g\subseteq h \quad\vdash\quad f\setminus k\subseteq h
e\subseteq f\setminus g,\;\; f\subseteq h\quad\vdash\quad e\subseteq h\setminus g
e\subseteq f\setminus g,\;\; k\subseteq g \quad\vdash\quad e\subseteq f\setminus k
e\subseteq f,\;\; f\ranres B\subseteq g \quad\vdash\quad e\ranres B\subseteq g
A\subseteq B ,\;\; f\ranres B\subseteq g \quad\vdash\quad f\ranres A\subseteq g
f\subseteq g\ranres A ,\;\; g\subseteq h \quad\vdash\quad f\subseteq h\ranres A
f\subseteq g\ranres A ,\;\; A\subseteq B \quad\vdash\quad f\subseteq g\ranres B
A\subseteq B ,\;\; B\domres f\subseteq g \quad\vdash\quad A\domres f\subseteq g
e\subseteq f ,\;\; B\domres f\subseteq g \quad\vdash\quad B\domres e\subseteq g
f\subseteq A\domres g ,\;\; A\subseteq B \quad\vdash\quad f\subseteq B\domres g
f\subseteq A\domres g ,\;\; g\subseteq h \quad\vdash\quad f\subseteq A\domres h
e\subseteq f ,\;\; f\ransub A\subseteq g \quad\vdash\quad e\ransub A\subseteq g
f\ransub A\subseteq g ,\;\; A\subseteq B \quad\vdash\quad f\ransub B\subseteq g
f\subseteq g\ransub A ,\;\; g\subseteq h \quad\vdash\quad f\subseteq h\ransub A
f\subseteq g\ransub B ,\;\; A\subseteq B \quad\vdash\quad f\subseteq g\ransub A
A\domsub f\subseteq g ,\;\; A\subseteq B \quad\vdash\quad B\domsub f\subseteq g
e\subseteq f ,\;\; A\domsub f\subseteq g \quad\vdash\quad A\domsub e\subseteq g
A\subseteq B ,\;\; f\subseteq B\domsub g \quad\vdash\quad f\subseteq A\domsub g
f\subseteq A\domsub g ,\;\; g\subseteq h \quad\vdash\quad f\subseteq A\domsub h
e\subseteq f ,\;\; f\ovl g\ovl\cdots\ovl h\subseteq k \quad\vdash\quad e\ovl g\ovl\cdots\ovl h\subseteq k
f\subseteq g\ovl h\ovl\cdots\ovl k ,\;\; e\subseteq g \quad\vdash\quad f\subseteq e\ovl h\ovl\cdots\ovl k
Z\subseteq B,\;\; A\bunion\cdots\bunion B\bunion\cdots\bunion C\subseteq D\quad\vdash\quad A\bunion\cdots\bunion Z\bunion\cdots\bunion C\subseteq D
B\subseteq Z ,\;\; D\subseteq A\bunion\cdots\bunion B\bunion\cdots\bunion C \quad\vdash\quad D\subseteq A\bunion\cdots\bunion Z\bunion\cdots\bunion C
Z\subseteq B,\;\; A\binter\cdots\binter B\binter\cdots\binter C\subseteq D\quad\vdash\quad A\binter\cdots\binter Z\binter\cdots\binter C\subseteq D
B\subseteq Z ,\;\; D\subseteq A\binter\cdots\binter B\binter\cdots\binter C \quad\vdash\quad D\subseteq A\binter\cdots\binter Z\binter\cdots\binter C
A\subseteq B,\;\; B\cprod D\subseteq E \quad\vdash\quad A\cprod D\subseteq E
C\subseteq D,\;\; B\cprod D\subseteq E \quad\vdash\quad B\cprod C\subseteq E
A\subseteq B\cprod D,\;\; B\subseteq C \quad\vdash\quad A\subseteq C\cprod D
A\subseteq B\cprod D,\;\; D\subseteq E\quad\vdash\quad A\subseteq B\cprod E
\dom(f\domres\prjone)\defi f
\dom(f\domres\prjtwo)\defi f
\dom(f\domres\id)\defi f
\ran(\prjone\ranres f)\defi f
\ran(\prjtwo\ranres f)\defi f
\ran(\id\ranres f)\defi f
\ran(f\domres\prjone)\defi\dom(f)
\ran(f\domres\prjtwo)\defi\ran(f)
\ran(f\domres\id)\defi f