Spring 2012 IA165 Combinatory Logic for Computational Semantics by Juyeon Kang
Classwork N°3
due to 9th March 2012
1. Normal form
When a combinatorial expression X cannot be anymore reduced by reaching to an
expression x, we say that x is the normal form of X. Give the normal form of the given
combinatorial expressions. The β-reduction rule of the basic combinators is given in the
following: Bxyz ≥β x(yz)
Cxyz ≥β x(zy)
Sxyz ≥β xz(yz)
Ix ≥β x
Kxy ≥β x
Wxy ≥β xyy
Φxyzu ≥β x(yu)(zu)
ψ xyzu ≥ β x(yz)(yu)
(1) WKx
(2) BCCxyz
(3) CSIfx
(4) SS(KI)fx
(5) B(BS)Bfxyz
(6) BB(BB)fgxgy
(7) S(BBS)(KK)xyz
(8) B(BW(BC))(BB(BB))fgxy
(9) Φ(Φ(ΦB))B(KK)fgxy
Please comment the definitions that you could find by reducing the given combinators. For
example, is the definition [W≡SS(KI)] an acceptable definition according your calculus?