令和7年度 III-4

解説

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

ラムダ式をβ簡約して、β正規形を求める問題。

解き方

① λxy.x=「2つのうち1番目を返す」(true)、λxy.y=「2番目を返す」(false)。前から順に引数を代入する
② x=λxy.y、y=λxy.x を代入 → (λxy.y)(λxy.x)(λxy.y) → 2番目を返すので λxy.y
③ ④

正解が正しい理由

λxy.xy(λxy.y) は、引数x、yを取り、「x y (λxy.y)」を返す関数である。これに、(λxy.y) と (λxy.x) を順に適用する。まず x に λxy.y を代入すると、λy. (λxy.y) y (λxy.y) となる。次に y に λxy.x を代入すると、(λxy.y)(λxy.x)(λxy.y) となる。λxy.y は、2つの引数を取り、2番目の引数を返す関数なので、(λxy.y) a b = b となり、a=λxy.x、b=λxy.y から、結果は λxy.y である。これ以上簡約できないβ正規形は λxy.y であり、④が正しい。

各選択肢について

• ① x は、簡約の結果には現れない。
• ② y という自由変数だけの式にはならず、λxy.y という関数になる。
• ③ λxy.x は、2番目の引数の (λxy.y) ではなく、1番目の引数を返す形であり誤り。
• ④ (λxy.y)(λxy.x)(λxy.y) は、2番目の引数 λxy.y を返すので、β正規形は λxy.y であり、これが正答。
• ⑤ λxy.xy は、簡約の過程で現れない式である。

覚えるべきポイント

λxy.y は「2つの引数のうち2番目を返す」関数、λxy.x は「1番目を返す」関数(チャーチ真偽値のfalse、true)。β簡約は、束縛変数に引数を代入して進める。