Konfluenznachweis für ein einfaches Umschreibungssystem

Question

Angenommen, wir haben eine einfache Sprache, die aus den Begriffen besteht:

• $ mathtt {true} $
• $ mathtt {false} $
• Wenn $ t_1, t_2, t_3 $ sind Begriffe, dann ist $ mathtt {if} : t_1 : mathtt {dann} : t_2 : mathtt {else} : t_3 $

Nehmen Sie nun die folgenden logischen Bewertungsregeln an:

$$ begin {sammeln*} dfrac {} { mathtt {if} : mathtt {true} : mathtt {dann} : t_2 : mathtt {else} : t_3 to t_2} text {[e-ifTrue]} quad dfrac {} { mathtt {if} : mathtt {false} : mathtt {dann} : t_2 : mathtt {sonst} : t_3 bis t_3 } text {[e-iiffalse]} dfrac {t_1 to t_1 '} { mathtt {if} : t_1 : mathtt {dann} : t_2: mathtt {sonst} : t_3 to mathtt {if} : t_1 ': mathtt {dann} : t_2 : mathtt {else} : t_3} text {[e-if]} end {sammeln*} $*} $ $

Angenommen, wir fügen auch die folgende funky Regel hinzu:

$$ dfrac {t_2 to t_2 '} { mathtt {if} : t_1 : mathtt {dann} : t_2 : mathtt {sonst} : t_3 to mathtt {if} : t_11: t_11 : mathtt {dann} : t_2 ': mathtt {else} : t_3} text {[e-iiffunny]} $$

Für diese einfache Sprache mit den angegebenen Bewertungsregeln möchte ich Folgendes beweisen:

Theorem: Wenn $ r rightarrow s $ und $ r rightarrow t $ dann gibt es eine Begriff $ u $, so dass $ s rightarrow u $ und $ t rightarrow u $.

Ich beweise dies durch Einführung in die Struktur von $ R $. Hier ist mein bisheriger Beweis, es hat alles gut geklappt, aber ich stecke im allerletzten Fall fest. Es scheint, als ob die Einführung in die Struktur von $ r $ nicht ausreicht. Kann mir jemand helfen?

Nachweisen. Durch Einführung von $ R $ werden wir alle Formulare, die $ R $ annehmen können, trennen:

1. $ r $ ist eine Konstante, nichts zu beweisen, da eine normale Form nichts bewertet.
2. $ r = $ wenn true dann $ r_2 $ $ $ r_3 $. (a) Beide Ableitungen wurden mit der E-Ifstrue-Regel durchgeführt. In diesem Fall $ S = T $, es gibt also nichts zu beweisen. (b) Eine Ableitung wurde mit der E-Ifstrus-Regel durchgeführt, die andere mit der E-Funny-Regel. Angenommen, $ r rightarrow S $ wurde mit E-Ifstrus fertiggestellt, der andere Fall ist gleichbedeutend nachgewiesen. Wir wissen jetzt, dass $ S = R_2 $. Wir wissen auch, dass $ t = $ wenn wahr ist, dann $ r'_2 $ $ r_3 $ und dass es einige Ableitungen $ r_2 rightarrow r'_2 $ (die Prämise) gibt. Wenn wir jetzt $ u = r'_2 $ wählen, schließen wir den Fall.
3. $ r = $ wenn falsch dann $ r_2 $ $ r_3 $. Entsprechend wie oben bewiesen.
4. $ r = $ wenn $ r_1 $ dann $ r_2 $ $ r_3 $ mit $ r_1 neq $ true oder false. (a) Beide Ableitungen wurden mit der E-IF-Regel durchgeführt. Wir wissen jetzt, dass $ s = $ wenn $ r'_1 $ dann $ r_2 $ $ r_3 $ und $ t = $ wenn $ r '' _ 1 $ dann $ r_2 $ $ r_3 $. Wir wissen auch, dass es Ableitungen gibt $ r_1 rightarrow r'_1 $ und $ r_1 rightarrow r '' _ 1 $ (die Räumlichkeiten). Wir können jetzt die Induktionshypothese verwenden, um zu sagen, dass es einen Begriff $ R '' '_ 1 $ gibt, so dass $ r'_1 rightarrow r' '_ 1 $ und $ r' '_ 1 rightarrow r' '' _ 1 $. Wir schließen jetzt den Fall mit $ u = $ if $ r '' '_ 1 $, dann $ r_2 $ $ $ r_3 $ und bemerkt, dass $ s rightarrow u $ und $ t rightarrow u $ nach der E-If-Regel. (b) Eine Ableitung wurde durch die E-IF-Regel und eine durch die E-Funny-Regel durchgeführt.

In diesem letzteren Fall, in dem eine Ableitung von E-If durchgeführt wurde und eine von E-Funny der Fall ist, fehlt ich ... Ich kann anscheinend nicht in der Lage sein, die Hypothesen zu verwenden.

Hilfe wird sehr geschätzt.

Answer 1

Okay, also betrachten wir den Fall, dass $ r = mathtt {if} : t_1 : mathtt {dann} : t_2 : mathtt {else} : t_3 $, $ s $ wurde abgeleitet, indem die angewendet wurde E-If Regel und $ t $ wurden abgeleitet, indem die E-Funny-Regel angewendet wird: SO $ S = Mathtt {if} : t'_1 : mathtt {dann} : t_2 : mathtt {else} : t_3 $ wob t_2 rightarrow t'_2 $.

Die $ u $, nach der wir suchen, ist $ u = mathtt {if} : t'_1 : mathtt {dann} : t'_2 : mathtt {else} : t_3 $. $ s rightarrow u $ folgt aus Regel e-funny und $ t rightarrow u $ folgt aus Regel E-IF.

Answer 2

Eine kleine Terminologie kann helfen, wenn Sie dies nachsehen möchten: Diese Regeln sind umschreiben Regeln, Sie haben nichts mit Typsystemen zu tun. Die Eigenschaft, die Sie beweisen möchten, heißt genannt Zusammenfluss; Genauer gesagt ist es starker Zusammenfluss: Wenn ein Begriff in einem Schritt auf unterschiedliche Weise reduziert werden kann, können er beim nächsten Schritt zurückversetzen. Im Allgemeinen ermöglicht Confluence eine beliebige Anzahl von Schritten und nicht nur eine: Wenn $ r bis^*s $ und $ r bis $ ist, dann gibt es $ u $ so, dass $ s bis^*u $ und $ t to^*u $ - Wenn eine Begriff auf unterschiedliche Weise reduziert werden kann, egal wie weit sie unterschiedlich sind, können sie schließlich zurückkehren.

Der beste Weg, um eine Eigenschaft solcher induktiv definierter Umschreibungsregeln zu beweisen, besteht darin, die Struktur der Ableitung der Reduktion und nicht durch die Struktur des reduzierten Terms zu beweisen. Hier funktioniert entweder, weil die Regeln der Struktur des linken Begriffs folgen, aber die Begründung auf die Regeln einfacher ist. Anstatt in den Begriff einzutauchen, nehmen Sie alle Regelnpaare ein und sehen, welcher Begriff für beide eine linke Seite sein kann. In diesem Beispiel erhalten Sie am Ende die gleichen Fälle, aber etwas schneller.

In dem Fall, der Ihnen Probleme gibt, reduziert eine Seite den „If“ -Teil und die andere Seite reduziert den „dann“ -Teil. Es gibt keine Überlappung zwischen den beiden Teilen, die sich ändern ($ t1 $ in [e-if], $ t_2 $ in [e-iiffunny]), und es gibt keine Einschränkungen für $ t_2 $ in [e-if] oder auf $ t_1 $ in [e-iiffunny]. Wenn Sie also einen Begriff haben, für den beide Regeln gelten - die aus der Form $ mathtt {if} : r_1 : mathtt {dann} : r_2 : mathtt {else} : r_3 $, Sie, Sie kann die Regeln in beiden Reihenfolge anwenden:

$$ begin {array} {rcl} & mathtt {if} : r_1 : mathtt {dann} : r_2 : mathtt {else} : r_3 & { small text {[e -If]}} swarrow & & searrow { small text {[e-iiffunny]}} mathtt {if} : r_1 ': mathtt {dann} : r_2 : mathtt {mathtt {dann} : r_2 : mathtt { sonst} : r_3 & & mathtt {if} : r_1 : mathtt {dann} : r_2 ': mathtt {else} : r_3 { small text {[e-iflny]}}} } searrow & & swarrow { small text {[e-if]}} & mathtt {if} : r_1 ': mathtt {dann} : r_2' : mathtt {else}} : r_3 & end {Array} $$

¹ _{Sie werden manchmal Typen sehen und zusammenschreiben, aber im Kern sind sie orthogonale Konzepte.}