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

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

Problem 1

Mockingbird,Bluebird,Robinを用いて賢人鳥(sage bird)を導出せよ。
これは5文字の式からなる

解

1
2
3
4
5
11章のproblem 2より
任意の鳥xについてΘx = M(BxM)とおける。
M(BxM)=M(RMBx)
=BM(RMB)x
よってΘ=BM(RMB)となる

Problem 2

B,C,Mからなる5文字の賢人鳥を見つけよ

解

1
2
3
4
5
BxM=CBMxであるので
M(BxM)=M(CBMx)
=BM(CBM)x

よってBM(CBM)はsage birdである

Problem 3

もっとシンプルな賢人鳥の式はM,B,Lを用いて表せる
これを見つけよ

解

1
2
3
4
9章のproblem 25でxはLx(Lx)が好きだということを見た。
Lx(Lx)=M(Lx)=BMLx
よってBMLはsage birdである。
CBM=RMB=Lであるので、problem 1,2の答えを再度確かめることができる

Problem 4

M,B,Wを用いて賢人鳥を導出せよ

解

1
2
一つ前の章のProblem 3よりBWBはLarkであるので
BM(BWB)がSage birdである

Problem 5

賢人鳥をB,C,Wから導くのはより難しいが、導けるか

解

一旦保留し、Problem 7の解答で答える

Problem 6

Q,L,Wを用いて賢人鳥を求めよ

解

1
2
3
4
5
6
Lx(Lx)
=QL(Lx)x
=QL(QL)xx
=W(QL(QL))x

よってW(QL(QL))はsage bird

Problem 7

再度Problem 5を解け

解

1
2
3
4
5
6
7
8
Q=CBであるので(原著はQ=BCと誤植がある)
前問の結果より
W(QL(QL))
=W(CBL(CBL))
=W(B(CBL)L)
ここでL=BWBであるので
=W(B(CB(BWB))(BWB))
これがSage Birdである