2017-12-13 8 views
2

私は\x->\y->xの中で2番目のxが最初のものに拘束されていることを知っています(私が間違っていることを修正してください)。\x->\x->x最後のxは中間のものに拘束されています。しかし、これはアルファ等価性に関しては違いがありますか? x - > x-> x alphaは x - > y-> xと等価ですか?

アルファは\x->\y->xに相当しますか?

+0

私は心配する必要がないように非常に努力します。 *名前を再利用しない* – Caleth

答えて

2

二つの用語t1t2アルファ同等である場合、任意のコンテキストのE[.]E[t1]E[t2]は同じ用語を減少させます。

したがって、2つの用語があり、それらを2つの異なる用語に縮小するコンテキストがある場合、それらはアルファに相当しないことがわかります。

ここでは、t1 = \x.\x.xt2 = \x.\y.xがあり、2つの異なる用語を適用するコンテキストをとります。 v1v2、あなたが持っている:

t1 v1 v2 = (\x.\x.x) v1 v2 --> (\x.x) v2 --> v2 

t2 v1 v2 = (\x.\y.x) v1 v2 --> (\y.v1) v2 --> v1 

このようにあなたは、彼らがアルファ等価ではありません推測することができます。

あなたは本当にアルファ等価で作業したい場合は、自由変数と有界変数の理解に時間を費やし、変数バインディングの点でアルファに相当するものが何であるかを尋ねる必要があります。

関連する問題