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

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

Problem 43 an Old Proverb

あることわざがある。
曰く、「cardinalがいたら、quacky birdなしにはquirky birdを持つことができないし、quirky birdなしにquacky birdを持つことができない」
この諺が真実なのはなぜか

解

1
2
3
4
5
6
Q3 x y z = z (x y)
C Q3 x y z = Q3 y x z = z (x y) = Q4
Q4 x y z = z (y x)
C Q4 x y z = Q4 y x z = z (x y) = Q3
よってことわざが成り立つ。
Q3=BTだったのでQ4=C(BT)である(F* Bのかわりに)

Problem 44

Quacky birdはQ1とTから導出できるか

解

1
2
3
4
Q4 x y z = z (y x)
Q1 T x y z = T (y x) z = z (y x) = Q4
よってQ1 Tと導出できる
Q1はBCBなのでQ4=Q1T=BCBT=C(BT)と前問の結果が導ける

Problem 45 An Interesting Fact About the Queer Bird Q

以前みたようにQueer Bird QはBとTから導ける。
では、BをQとTから導けるか

解

1
2
3
4
5
6
B x y z = x (y z)
Q y x z = x (y z)
T x (Q y) z = x (y z)
Q Q (Tx)yz = x (y z)
Q T (Q Q) x y z = x ( y z)
よってB = QT(QQ)である

Problem 46

CardinalはBとTから導出するよりも簡単にQとTから導出できる。
4文字からなる式だが、それを見つけよ

解

1
2
3
4
5
6
C x y z = x z y
T y (x z) = x z y
Q x (Ty)z = x  zy
Q T (Q x) y z = x z y
Q Q (Q T) x y z = x z y
よってQQ(QT)がcardinalである

Problem 47 Goldfinches

Goldfinch Gは以下の条件を満たす。

1
G x y z w = x w (y z)

GをBとTから導け

解

1
2
3
4
5
G x y z w = x w (y z)
=C x (y z) w
=B (C x) y z w
= B B C x y z w
よってG = B B Cである