コンビネータ論理Extra practice 2.35(a)

コンビネータ論理の問題。

Lambda-Calculus and Combinators: An Introduction
Hindley & Seldin より

Extra practice 2.35(a)

次のコンビネータを簡約化せよ。
ただし、
$BXY\ \triangleright_\omega\ X(YZ) $
$CXYZ\ \triangleright_\omega\ XZY $
$WXY\ \triangleright_\omega\ XYY $

(i)

$KSuxyz$
$\equiv(KSu)xyz\equiv Sxyz\equiv xz(yz)$

(ii)

$S(Kx)(KIy)z$
$\equiv(Kx)z((KIy)z)\equiv x(Iz)\equiv xz$

(iii)

$CSIxy$
$\equiv(CSIx)y\equiv SxIy\equiv xy(Iy)\equiv xyy$

(iv)

$S(CI)xy$
$\equiv(CI)y(xy)\equiv CIy(xy)\equiv I(xy)y\equiv(xy)y\equiv xyy$

(v)

$B(BS)Bxyzu$
$\equiv(BS)(Bx)yzu
\equiv B\underline{S}(\underline{Bx})\underline{y}zu
\equiv S(\underline{(Bx)y})\underline{z}\ \underline{u}$
$\equiv(B\underline{x})\underline{y}\ \underline{u}(zu)
\equiv x(yu)(zu)$

(vi)

$BB(BB)uvwxy$
$\equiv B((BB)u)vwxy
\equiv (BB)u(vw)xy
\equiv B(u(vw))xy$
$\equiv (u(vw))(xy)$

(vii)

$B(BW(BC))(BB(BB))xyzu$
$\equiv(BW(BC))((BB(BB))x) yzu$
$\equiv(BW(BC))(B(BBx)) y zu$ by $(BB(BB))x=B(BBx)$
$\equiv W((BC)(B(BBx))) y zu$
$\equiv ((BC)(B(BBx))) y y zu$
$\equiv C((B(BBx)) y) y zu$
$\equiv ((B(BBx))y) zy u$
$\equiv (BBx)(yz) yu$
$\equiv B(x(yz)) yu$
$\equiv (x(yz)) (yu)\equiv x(yz) (yu)$