12,080
edits
Changes
Directory:Jon Awbrey/Papers/Propositional Equation Reasoning Systems (view source)
Revision as of 18:54, 2 November 2008
, 18:54, 2 November 2008→Case analysis-synthesis theorem
Let ''Q'' be a proposition with an unspecified, but context-appropriate number of variables, say, none, or ''x'', or ''x''<sub>1</sub>, … ''x''<sub>''k''</sub>, as the case may be. (To be more precise, I should have said "sentence ''Q''".)
Let ''Q'' be a proposition with an unspecified, but context-appropriate number of variables, say, none, or ''x'', or ''x''<sub>1</sub>, … ''x''<sub>''k''</sub>, as the case may be. (To be more precise, I should have said "sentence ''Q''".)
* Strings and graphs sans labels are called ''bare''.
:* Strings and graphs sans labels are called ''bare''.
* A bare terminal node, "o", is known as a ''stone''.
:* A bare terminal node, "o", is known as a ''stone''.
* A bare terminal edge, "|", is known as a ''stick''.
:* A bare terminal edge, "|", is known as a ''stick''.
Let the ''replacement expression'' of the form ''Q''[o/''x''] denote the proposition that results from ''Q'' by replacing every token of the variable ''x'' with a blank, that is to say, by erasing ''x''.
Let the ''replacement expression'' of the form ''Q''[o/''x''] denote the proposition that results from ''Q'' by replacing every token of the variable ''x'' with a blank, that is to say, by erasing ''x''.
I think that I am at long last ready to state the following:
I think that I am at long last ready to state the following:
<pre>
o-----------------------------------------------------------o
| Case Analysis-Synthesis Theorem (CAST)` ` ` ` ` ` ` ` ` ` |
o-----------------------------------------------------------o
| ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` `x` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` `o` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` `x` `|` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` Q[o/x] o---o Q[|/x] ` ` |
| ` ` ` ` ` ` `Q` ` ` ` ` ` ` ` ` ` ` ` ` ` \ / ` ` ` ` ` ` |
| ` ` ` ` ` ` `@` ` ` ` ` ` ` = ` ` ` ` ` ` `@` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
o-----------------------------------------------------------o
| ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` `Q` ` ` ` ` ` ` = ` ( Q[o/x] x , Q[|/x] (x) ) |
| ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
o-----------------------------------------------------------o
</pre>
In order to think of tackling even the roughest sketch toward a proof of this theorem, we need to add a number of axioms and axiom schemata. Because I abandoned proof-theoretic purity somewhere in the middle of grinding this calculus into computational form, I never got around to finding the most elegant and minimal, or anything near a complete set of axioms for the ''cactus language'', so what I list here are just the slimmest rudiments of the hodge-podge of ''rules of thumb'' that I have found over time to be necessary and useful in most working settings. Some of these special precepts are probably provable from genuine axioms, but I have yet to go looking for a more proper formulation.
In order to think of tackling even the roughest sketch toward a proof of this theorem, we need to add a number of axioms and axiom schemata. Because I abandoned proof-theoretic purity somewhere in the middle of grinding this calculus into computational form, I never got around to finding the most elegant and minimal, or anything near a complete set of axioms for the ''cactus language'', so what I list here are just the slimmest rudiments of the hodge-podge of ''rules of thumb'' that I have found over time to be necessary and useful in most working settings. Some of these special precepts are probably provable from genuine axioms, but I have yet to go looking for a more proper formulation.
<pre>
o-----------------------------------------------------------o
| Precept L_1.` Indifference` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
o-----------------------------------------------------------o
| ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` a ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` o ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` a ` | ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` o---o ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` `\ /` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` @ ` ` ` ` = ` ` ` ` @ ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
o-----------------------------------------------------------o
| ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` `(a, (a)) ` ` = ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
o-----------------------------------------------------------o
| ` ` ` ` ` ` ` ` Split <---- | ----> Merge ` ` ` ` ` ` ` ` |
o-----------------------------------------------------------o
</pre>
<pre>
o-----------------------------------------------------------o
| Precept L_2.` Equality. `The Following Are Equivalent:` ` |
o-----------------------------------------------------------o
| ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` b ` ` ` ` ` ` ` a ` b ` ` ` ` ` ` ` a ` ` ` ` ` |
| ` ` ` ` ` o ` ` ` ` ` ` ` o---o ` ` ` ` ` ` ` o ` ` ` ` ` |
| ` ` ` a ` | ` ` ` ` ` ` ` `\ /` ` ` ` ` ` ` ` | ` b ` ` ` |
| ` ` ` o---o ` ` ` ` ` ` ` ` o ` ` ` ` ` ` ` ` o---o ` ` ` |
| ` ` ` `\ /` ` ` ` ` ` ` ` ` | ` ` ` ` ` ` ` ` `\ /` ` ` ` |
| ` ` ` ` @ ` ` ` ` = ` ` ` ` @ ` ` ` ` = ` ` ` ` @ ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
o-----------------------------------------------------------o
| ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
| ` ` `(a, (b)) ` ` = ` ` ((a , b)) ` ` = ` ` ((a), b)` ` ` |
| ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
o-----------------------------------------------------------o
</pre>
<pre>
o-----------------------------------------------------------o
| Precept L_3.` Dispersion` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
o-----------------------------------------------------------o
| ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
| For k > 1, the following equation holds:` ` ` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
| ` y_1 ` `y_2` `...` ` y_k ` ` x y_1 `x y_2` `...` x y_k ` |
| ` `o------o-...-o------o` ` ` ` `o------o-...-o------o` ` |
| ` ` \ ` ` ` ` ` ` ` ` / ` ` ` ` ` \ ` ` ` ` ` ` ` ` / ` ` |
| ` ` `\` ` ` ` ` ` ` `/` ` ` ` ` ` `\` ` ` ` ` ` ` `/` ` ` |
| ` ` ` \ ` ` ` ` ` ` / ` ` ` ` ` ` ` \ ` ` ` ` ` ` / ` ` ` |
| ` ` ` `\` ` ` ` ` `/` ` ` ` ` ` ` ` `\` ` ` ` ` `/` ` ` ` |
| ` ` ` ` \ ` ` ` ` / ` ` ` ` ` ` ` ` ` \ ` ` ` ` / ` ` ` ` |
| ` ` ` ` `\` ` ` `/` ` ` ` ` ` ` ` ` ` `\` ` ` `/` ` ` ` ` |
| ` ` ` ` ` \ ` ` / ` ` ` ` ` ` ` ` ` ` ` \ ` ` / ` ` ` ` ` |
| ` ` ` ` ` `\` `/` ` ` ` ` ` ` ` ` ` ` ` `\` `/` ` ` ` ` ` |
| ` ` ` ` ` ` \ / ` ` ` ` ` ` ` ` ` ` ` ` ` \ / ` ` ` ` ` ` |
| ` ` ` ` ` `x @` ` ` ` ` ` ` = ` ` ` ` ` ` `@` ` ` ` ` ` ` |
| ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
| ` ` x (y_1, ..., y_k) ` ` ` = ` ` (x y_1, ..., x y_k) ` ` |
| ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` |
o-----------------------------------------------------------o
| ` ` ` ` ` Distill ` ` <---- | ----> ` ` Disperse` ` ` ` ` |
o-----------------------------------------------------------o
</pre>
To see why the ''Dispersion Rule'' holds, look at it this way: If ''x'' is true, then the presence of ''x'' makes no difference on either side of the equation, but if ''x'' is false, then both sides of the equation are false.
To see why the ''Dispersion Rule'' holds, look at it this way: If ''x'' is true, then the presence of ''x'' makes no difference on either side of the equation, but if ''x'' is false, then both sides of the equation are false.