コンビネータ論理►to mock a mockingbird

to mock a mockingbirdを読む(13)11章

11章では最初に省略記法についての話があります。
(xy)zwとxyzwと((xy)z)wはすべて同じ意味になります。
x(yz)wは(x(yz))wと同じですし
x(yzw)はx((yz)w)と同じです。

Exercises

次のケースで括弧を左結合として完全に表しなさい

1
2
3
4
5
6
7
8
9
10
11
12
13
14
a.xy(zwy)v = ?
b.(xyz)(wvx) = ?
c.xy(zwv)(xz) = ?
d.xy(zwv)xz = ? 注：cとは結果が異なる
e.x(y(zwv))xz = ?
f.次の式は正しいか間違っているか
  xyz(AB) = (xyz)(AB)
g.A1=A2だとするとき、BA1=BA2だと結論してよいか
またA1B=A2Bだと結論してよいか
h.xy=zだと仮定する
どちらの結論が有効か
1. xyw = zw
2. wxy = wz
注：トリッキーかつ重要

Answer

1
2
3
4
5
6
7
8
9
10
11
12
a.((xy)((zw)y))v
b.((xcy)z)((wv)x)
c.((xy)((zw)v))(xz)
d.(((xy)((zw)v))x)z
e.((x(y((zw)v)))x)z
f.正しい。どちらも((xy)z)(AB)となる
g.どちらの結論も正しい
h.1が有効
コンビネータの計算は左端か括弧の左端から始まるので
1は(xy)w,2は(wx)yという風に計算がなされるので2は成り立たない
例えばwがw a b = b aという鳥(Tコンビネータ)だった場合
wxy=yxとなりxyという形ではなくなってしまう