汇合的证明一个简单的改写系统

Question

假设我们有一个简单的语言，由的条款：

• $\mathtt{真}$
• $\mathtt{假}$
• 如果$t_1,t_2,t_3$的条款随后以美元\mathtt{如果}\:t_1\:\mathtt{然后}\:t_2\:\mathtt{别}\:t_3$

现在以下假设逻辑评估规则：

$$\开始{收集*} \dfrac{} {\mathtt{如果}\:\mathtt{真}\:\mathtt{然后}\:t_2\:\mathtt{别}\:t_3\到t_2} \文字{[E-IfTrue]}\四 \dfrac{} {\mathtt{如果}\:\mathtt{假}\:\mathtt{然后}\:t_2\:\mathtt{别}\:t_3\到t_3} \文字{[E-IfFalse]}\\ \dfrac{t_1\到t_1'} {\mathtt{如果}\:t_1\:\mathtt{然后}\:t_2\:\mathtt{别}\:t_3 o\mathtt{如果}\:t_1'\:\mathtt{然后}\:t_2\:\mathtt{别}\:t_3} \文字{[E-如果]}\\ \端{收集*}$$

假设我们还添加以下时髦的规则：

$$ \dfrac{t_2\到t_2'} {\mathtt{如果}\:t_1\:\mathtt{然后}\:t_2\:\mathtt{别}\:t_3 o\mathtt{如果}\:t_1\:\mathtt{然后}\:t_2'\:\mathtt{别}\:t_3} \文字{[E-IfFunny]} $$

对于这个简单的语言与所给出的评估规则，我希望证明如下：

定理：如果$r\右元和美元r\右t$然后有一些术语$u$这样$s\右u$和$t\右u$.

我证明这种感应通过在结构$r$.这里是我的证明迄今为止，它的所有工作很好，但我被困在最后一种情况。这似乎是感应的结构$r$不满足，任何人都可以帮帮我吗？

证明。 通过诱导美元r$，我们将单独所有形式$r$可以采取：

1. $r$为constante，没有什么证明由于通常的形式并不评估的任何东西。
2. $r=$如果真的那么$r_2$别$r_3$.(a)两个派生完成与电子IfTrue规则。在这种情况下$s=t$，所以没有什么可以证明。(b)一个deriviation样做是与E-IfTrue规则，其它的电子有趣的规则。假设$r\右元是完成与电子IfTrue，其他情况下是效地证明。我们现在知道$s=r_2$.我们也知道，$t=$如果真的那么$r'_2$别$r_3美元，存在着一些deriviation$r_2\右r'_2$(的前提下).如果我们现在选择$u＝r'_2$，我们得出的结论的情况。
3. $r=$如果假然后$r_2$别$r_3$.等效地证明如上。
4. $r=$如果$r_1$然后$r_2$别$r_3$美元r_1\新$真正的或虚假的。(a)两deriviations是在E-如果规则。我们现在知道$s=$如果$r'_1$然后$r_2$别$r_3美元$t=$如果$r"_1$然后$r_2$别$r_3$.我们也知道，还存在deriviations$r_1\右r'_1$美元r_1\右r"_1$(场地).我们现在可以使用的感应hypothese来说，存在一些长期$r"'_1$这样$r'_1\右r"'_1$美元r"_1\右r"'_1$.我们现在得出的结论的情况下通过说$u=$如果$r"'_1$然后$r_2$别$r_3美元，注意到$s\右u$和$t\右u$通过E-如果规则。(b)一个推导是通过E-如果规则和一个通过电子-有趣的规则。

这后一种情况，在那里推导是通过电子如果与一个通过电子-有趣的是这种情况下，我失踪了...我不能看起来能够使用的假设。

帮助将非常感激。

Answer 1

好的，所以让我们考虑一下$ r = mathtt {if} ：t_1 ： mathtt {then} ：t_2 ： mathtt {else} ：t_3 $，$ s $是通过应用程序衍生而来的， e-if规则和$ t $是通过应用e-funny规则来得出的：so $ s = mathtt {if} ：t'_1 ： mathtt {then} ：t_2 ：t_2 ： mathtt {else} {else} ：t_3 $ where $ t_1 rightArrow t'_1 $和$ t = mathtt {if} ：t_1 ： mathtt {then} ：t'_2 ：t'_2 ： mathtt {else} t_2 rightarrow t'_2 $。

我们正在寻找的$ u $是$ u = mathtt {if} ：t'_1 ： mathtt {then} ：t'_2 ： mathtt {else} ：t_3 $。 $ s rightArrow u $遵循规则e-funny和$ t rightarrow u $ thrue e-if。

Answer 2

一个小小的术语可能的帮助，如果你想看看这个：这些规则是 重写 规则, 他们什么都没有做类型systems1.酒店你想证明被称为 汇合;更具体地说，它的 强汇合:如果一个术语，可以减少在不同的方式在一个步骤，他们能够重新汇聚在下一个步骤。在一般情况下，汇允许有任何数量的步骤，而不只有一个：如果$r\到^*s$美元r\到^*t$然后有$u$这样$s\到^*u$和$t\到^*u$—如果一个术语，可以减少在不同的方式，不管有多远，他们已经分歧，他们可以最终收回。

最好的方式来证明一个酒店这样的感应定义改写的规则是通过诱导的结构推导的减少，而不是结构的减期限。在这里，要么工作，因为该规则的遵循的结构的左手术语，但推理规则更为简单。而不是潜入这个词，你把所有对的规则，看看什么样的术语可能是左侧。在这个例子中，你将得到同样的情况下结束的，但是快一点.

在这种情况下，给你麻烦，一面减少了"如果"的一部分，其他侧降低了"那么"的一部分。没有重叠的两个部分之间改变($t1$在[E-如果],$t_2$在[E-IfFunny])，而且也没有约束美元t_2$在[E-如果]或在$t_1$在[E-IfFunny].所以，当你有一个术语，这两种规则的适用必须的形式$\mathtt{如果}\:r_1\:\mathtt{然后}\:r_2\:\mathtt{别}\:r_3$，你可以选择适用的规则在任何顺序：

$$\开始{列}{rcl} &\mathtt{如果}\:r_1\:\mathtt{然后}\:r_2\:\mathtt{别}\:r_3&\\ {\小\文字{[E-如果]}}\swarrow&&\searrow{\小\文字{[E-IfFunny]}}\\ \mathtt{如果}\:r_1'\:\mathtt{然后}\:r_2\:\mathtt{别}\:r_3&&\mathtt{如果}\:r_1\:\mathtt{然后}\:r_2'\:\mathtt{别}\:r_3\\ {\小\文字{[E-IfFunny]}}\searrow&&\swarrow{\小\文字{[E-如果]}}\\ &\mathtt{如果}\:r_1'\:\mathtt{然后}\:r_2'\:\mathtt{别}\:r_3&\\ \端{列}$$

¹ _{有时你会看到的类型和重写在一起，但在其核心他们正交的概念。}