次のラムダ式をβ簡約することによって得られるβ正規形として最も適切なものは どれか。
((λxy.xy) (λx.xy) λz.z)
① x ② y ③ λx.x ④ λy.y ⑤ λz.z
②
ラムダ式はラムダ計算式ともいう。
例えば f(x) = x+1 の関数は λx.x+1 と表記される。
この関数の引数が2であれば、
f(2) = 2+1 = 3 であるが、ラムダ式では
(λx.x+1)2 と表記し、(λx.x+1)2 → 2+1 → 3 となる。
また、f(x, y) = x+y の関数は、λx.λy.x+y もしくは λxy.x+y と表記され、
(x, y) = (2, 3)の場合
(λx.λy.(x+y))23 → (λy.(2+y))3 → 2+3 → 5
もしくは
(λxy.x+y)23 → (λy.2+y)3 → 2+3 → 5 となる。
簡約は、ラムダ式を実行していくことである。
(λxy.x) (λx.xx) (λz.z) の場合、
(λxy.x) (λx.xx) (λz.z)
→ λy.(λx.xx)(λz.z)
→ λx.xx ・・・f(y) = λx.xx の y に(λz.z)を適用したのと同じ。
となる。
もう一つ、 (λxy.x)yz のような場合は注意が必要で、yをxに入れると
(λxy.x)yz → (λy.y)z となる。
この時、y.yは異なるにも関わらず同じ y とみなして、zをyに入れて、
(λy.y)z → z とするのは誤りとなる。
このような場合は、 (λxy.x)yz の yをwなどに置き換え、
(λxw.x)yz → (λw.y)z → yが正しい変換となる。
この置き換えは、α変換という。
これらを踏まえ、問題のラムダ式をβ簡約すると、以下のとおりとなる。
((λxy.xy) (λx.xy) λz.z)
→ (λy.(λx.xy)y) λz.z
→ (λw.(λx.xy)w)λz.z ・・・α変換。y → w
→ (λx.xy)λz.z ・・・λw.(λx.xy)は、f(w) = λx.xy
→ (λz.z)y ・・・λx.xyは、f(x) = xy （これは x×y という掛算ではない。）
→ y
| Ⅲ－２ | 目次 | Ⅲ－４ |