令和元年度(再試験) III-3

解説

この問題で問われていること

ラムダ式のβ簡約を、束縛変数と自由変数を区別しながら行う問題。

解き方

① β簡約: 関数に引数を代入していく。引数に含まれる自由変数(ここではy)は名前を変えずに残る(束縛変数の方を名前替えする)
② (λxy.xy)(λx.xy)(λz.z) → (λx.xy)(λz.z) → (λz.z)y → y
③ y(②)

正解が正しい理由

式は、(λxy. xy) に、(λx. xy) と (λz. z) を順に適用したもの。λxy. xy = λx.λy. x y。1つ目の引数(λx. xy)をxに代入すると、λy'. (λx. xy) y'(内側のy'は、引数中の自由変数yと衝突しないよう、名前を変えたもの)。これに2つ目の引数(λz. z)を適用すると、(λx. xy)(λz. z)となる。xにλz.zを代入すると、(λz. z) y。これをさらに簡約すると、yとなる。この式の中のyは、引数(λx. xy)の中に現れた自由変数のyである。したがってβ正規形はyで、②が正しい。

この問題で必要な基礎

■ ラムダ式の読み方
「λx.本体」は「xを受け取って本体を返す関数」です。λxy.本体 は、xとyを順に受け取る関数です。

■ β簡約(関数に値を渡す)
ラムダ式に値を渡すことは、本体の中の変数をその値で置き換えることです。例えば(λz.z) y は、zをyに置き換えてyになります。

■ 束縛変数と自由変数
λの後ろに書かれた変数(λx.のx)は、その関数の引数として使われる「束縛変数」で、名前を変えても意味は変わりません。一方、どのλにも対応しない変数(この問題の(λx.xy)の中のy)は「自由変数」で、簡約しても消えずに残ります。値を代入するときは、自由変数が別のλに取り込まれないよう、束縛変数の名前を付け替えます。

各選択肢について

• ① xは、束縛変数で、簡約後には残らない。
• ② 簡約すると、引数中の自由変数yが残り、β正規形はyとなる。これが正答。
• ③ λx. xは、恒等関数で、この式の最終結果としては現れない。
• ④ λy. yは、恒等関数で、この式の最終結果としては現れない(y'に名前を変えた束縛変数は、消える)。
• ⑤ λz. zは、引数として渡された恒等関数で、最終的にはyに適用されて消える。

覚えるべきポイント

β簡約では、代入時に自由変数が束縛されないよう、必要に応じてα変換(束縛変数の名前の付け替え)を行う。自由変数はそのまま残る。