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

to mock a mockingbirdを読む(31)12章

Exercise 4

psi bird Ψは以下の条件を満たす

1
Ψxyzw = x(yz)(yw)

psi birdはコンビネータ論理ではスタンダードなものである。
B,C,Wからpsi birdが導出できることを示せ

ヒント：H*=BHとしてH*とD2から簡単に導出できる。
D2 x y z w v = x (y z) (w v)であった

解

1
2
3
4
5
psi x y z w = x (yz)(yw)
= D2 x y z y w
= H* D2 x y z w

よってΨ=H* D2である

Exercise 5

ΨがΦとBとKから導けるのは奇妙な事実である。
ここでは問題を二つに分ける。
a.以下の条件を満たすΓがΦとBから導けることを示せ

1
Γxyzwv = y(zw)(xywv)

b.ΦがΓとKから導出できることを示せ

解

1
2
3
4
a.
自分では解けませんでしたが解答は
Γ=Φ(Φ(ΦB))B
b.Φ=Γ(KK)

Exercise 6

Sと、BとTから導出した鳥を用いて
以下の条件を満たすS’を導出せよ

1
S' xyz = yz(xz)

解

1
2
3
4
5
S' x y z = y z (x z)
= Syxz
= CSxyz

よってS'=CSである

Exercise 7

CQ^WがStarlingであるようなQのみから導出できるQ^が存在する。
6文字からなるのだがこれを導出せよ

解

1
2
これも自力では解けませんでした
解はQ^=Q(QQ(QQ))Q