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

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

Problem 16

コンビネータ論理で基本的な役割をもつ鳥にCardinalがいる
Cardinalは次の条件を満たす。

1
C x y z = x z y

Cardinalはpermuting birdsとして知られる重要な鳥のファミリーに属する。
簡単にいえば、permuting birdsがいれば順番の入れ替えができるようになる。

問い
CardinalとKestrelがいる森にはIdentity birdがいることを示せ

解

1
2
3
CKCx = KxC=x
CKKx = KxK=x
よってI=CKCあるいはI=CKKである

Problem 17

もっとも基本的なpermuting birdにthrushがいる。
thrushは以下の条件を満たす。

1
T x y = y x

CardinalとIdentity birdからthrushを導出せよ

解

1
2
CIxy = Iyx = yx
よってT = CIである

Problem 18

2つの鳥xとyがcommute(可換)であるとは以下の条件を満たすことを言う。

1
x y = y x

森にthrushがおり、森の各鳥はなんらかの鳥が好きであるとする。
すると少なくとも1つの鳥Aが各鳥とcommuteすることを示せ

解

1
2
3
4
5
6
Tはある鳥Aが好きなので
TA = A
TAx = Ax
またTの性質より
TAx = xA
よってAは各xとcommute