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

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

Problem 22 Two Useful Laws

以下の2つの有用な式を証明せよ

1
2
a. Cx = RxR
b. Cx = B(Tx)R

解

1
2
3
4
5
6
7
8
前問より再掲
C x y z = x z y
R y x z = x z y
R x R y z = x z y
よってC x = R x Rである

またC x = R x R = (BBT) x R
 = B(Tx)R

Problem 23

CardinalはRobinから導出できた。
なら逆にRobinはCardinalから導出できるか。

解

1
2
3
4
R x y z = y z x
C y x z = y z x
C C x y z = y z x
よってR=CCである

Problem 24 Finches

Finch Fは以下の条件を満たす

1
F x y z = z y x

これを導くにはいくつかの方法がある。
finchはbluebird,robin,cardinalから簡単に導ける。
またbluebirdとcardinal,bluebirdとrobinからも。
finchを導け

解

1
2
3
4
5
6
7
8
9
F x y z = z y x
R x z y = z y x
C (R x) y z = z y x
B C R x y z = z y x

よってF = B C Rである
またF = B C (C C)
 = B (RRR) R
である

Problem 25

Finchはthrushとeagleからも導ける。
どうやれば導けるか

解

1
2
3
4
5
6
7
8
F x y z = z y x
T x (z y)= z y x
T x (T y z) = z y x
E T x T y z = z y x
T T (E T x) y z = z y x
E T T E T x y z = z y x

よってF = E T T E Tである

Problem 26

これで、あなたはfinchを2通りに表せるようになった。
BとTを用いてこれらを2通りで表せ。
一方は他方より短くなる

解

1
2
3
4
5
6
7
F = BCR = B(B(T(BBT))(BBT))(BBT)
F = ETTET = B(BBB)TTET
 = (BBB)(TT)ET
 = B(B(TT))ET
 = B(TT)(ET)
 = B(TT)(B(BBB)T)
ETTET経由のほうが4文字短くなる