3.2

试求 $SSSS$ 的 $\beta$-nf。

解

$S \equiv \lambda xyz.xz(yz)$，有 $SS =_{\beta} \lambda yz.Sz(yz) =_\beta\lambda yz.(\lambda t.zt(yzt)) =_\beta \lambda yzt.zt(yzt)$

$\therefore SS_1S_2S_3 = _\beta S_1S_3(S_2S_3) =_\beta \lambda uv.[uv(SSuv)] = _\beta \lambda uv.[uv (\lambda w. vw(uvw)) ]$

更进一步，所求的 $\beta$-nf 为 $\lambda uvw. uv(vw(uvw))$

注意引入新变元要换名