《计算模型导引》第三章习题

1

习题3.1

证明括号引理：对于任何 $M\in\Lambda$，在$M$中出现的左括号的个数等于在 $M$ 中出现的右括号的个数。

证：

对 $\lambda$-项 $M$ 的结构作归纳.

当 $\rho(M)=1$时，$M$ 仅包含一变元，满足结论。

假设 $\rho(M)\leq k$ 时，结论成立。

当 $\rho(M)=k+1$ 时，

1. $M\equiv (NL)$，则 $\rho(N)\leq k, \rho(L)\leq k$，$N,L$ 中左括号数量等于右括号数量， 故 $M$ 中左括号数量等于右括号数量。
2. $M\equiv (\lambda x. N)$，则 $\rho(N)\leq k$，$N$ 中左括号数量等于右括号数量， 故 $M$ 中左括号数量等于右括号数量。

综上，结论成立。

2

习题3.2

试求 $SSSS$ 的 $\beta-\text{nf}$。

解：

根据定义有$S\equiv \lambda xyz.xz(yz)$.

故：

$$\begin{align} SSSS &= (\lambda xyz. xz(yz))SSS \\\\ &=SS(SS) \\\\ &=(\lambda xyz. xz(yz))S(SS) \\\\ &=\lambda z. Sz((SS)z) \\\\ &=\lambda z. (\lambda xyz_1. xz_1(yz_1))z((SS)z) \\\\ &=\lambda z. (\lambda z_1. zz_1(((SS)z)z_1)) \\\\ &=\lambda z. (\lambda z_1. zz_1((((\lambda xyz_2. xz_2(yz_2))S)z)z_1)) \\\\ &=\lambda z. (\lambda z_1. zz_1(Sz_1(zz_1))) \\\\ &=\lambda z. (\lambda z_1. zz_1((\lambda xyz_2. xz_2(yz_2))z_1(zz_1))) \\\\ &=\lambda z. (\lambda z_1. zz_1(\lambda z_2. z_1z_2((zz_1)z_2))) \\\\ &=\lambda x. (\lambda y. xy(\lambda z. yz(xyz)))\\\\ &=\lambda xy. xy(\lambda z. yz(xyz)) \end{align}$$

3

习题3.3

证明： $(\lambda x.xxx)(\lambda x.xxx)$ 没有 $\beta-\text{nf}$。

证：

假设 $(\lambda x.xxx)(\lambda x.xxx)$ 有 $\beta-\text{nf}$。则存在 $N\in NF_{\beta}$，使得 $(\lambda x.xxx)(\lambda x.xxx)=_{\beta} N$.

然而 $(\lambda x.xxx)(\lambda x.xxx)\rightarrow_{\beta}(\lambda x.xxx)(\lambda x.xxx)(\lambda x.xxx)$. 无法归约到 $N$。矛盾。

4

习题3.4

设 $F\in\Lambda$ 呈形 $\lambda x.M$，证明：

（1）$\lambda z.Fz=_{\beta}F$;

（2）$\lambda z.yz\not=_{\beta}y$.

注意，对于一般的 $F$, $\lambda z.Fz\not=_{\beta}F$，但$\lambda z.Fz=_{\eta}F$。

证：

（1）

$$\begin{align} \lambda z.Fz &= \lambda z.(\lambda x.M)z \\\\ &= \lambda z.M[x:=z] \\\\ &= F \\\\ \end{align}$$

（2）

假设$\lambda z.yz=_{\beta}y$. 由CR for $=_{\beta}$，存在$T$，使得 $\lambda z.yz\twoheadrightarrow_{\beta} T$，$y\twoheadrightarrow_{\beta} T$. 由 $y$ 为 $\beta-\text{nf}$，故 $T\equiv y$. 故$\lambda z.yz\twoheadrightarrow_{\beta} y$，而$\lambda z.yz\not\twoheadrightarrow_{\beta} y$，矛盾。

5

习题3.5

证明二元不动点定理：对于任何 $F,G\in\Lambda$ 存在 $X,Y\in\Lambda$ ，满足 $$ \begin{align} FXY &= X,\\ GXY &= Y. \end{align} $$

证：

根据$GXY = Y$，$Y$ 为 $GX$的不动点，故 $Y=\mathbb{Y}(GX)$.

因此 $FX(\mathbb{Y}(GX))=X$，故 $(\lambda x. Fx(\mathbb{Y}(Gx)))X=X$，即 $X=\mathbb{Y}(\lambda x. Fx(\mathbb{Y}(Gx)))$.

综上，$X=\mathbb{Y}(\lambda x. Fx(\mathbb{Y}(Gx)))$，$Y=\mathbb{Y}(GX)$.

6

习题3.6

证明：对于任何 $M,N\in\Lambda^{\circ}$，方程 $xN=Mx$ 对于 $x$ 有解。

证：

设 $x\equiv \lambda a.T$，其中 $T$ 不含 $a$，故 $xN=(\lambda a.T)N=T$.

$$T=Mx=M(\lambda a.T)=(\lambda x.M(\lambda a.x))T$$

故 $T=\mathbb{Y}(\lambda x.M(\lambda a.x))$. 综上，$x=\lambda a.\mathbb{Y}(\lambda x.M(\lambda y.x))$.

7

习题3.7

证明：对于任何 $P,Q\in\Lambda$，若 $P\twoheadrightarrow_{\beta}Q$，则存在 $n\geq 0$ 以及 $P_0,\cdots,P_n\in\Lambda$，满足：

（1）$P\equiv P_0$；

（2）$Q\equiv P_n$；

（3）对任何 $i<n$ , $P_i\rightarrow_{\beta} P_{i+1}$。

证：

由 $\twoheadrightarrow_{\beta}$ 的定义，$P\twoheadrightarrow_{\beta}Q$要么由 $P\rightarrow_{\beta}Q$得到，要么由传递性得到，传递过程中经历的 $P_i,i\in\{1,2,\cdots,n\}$即满足要求。

8

习题3.8

证明：对于任何 $P,Q\in\Lambda$，若 $P\twoheadrightarrow_{\beta}Q$，则 $\lambda z.P\twoheadrightarrow_{\beta} \lambda z.Q$.

证：

因为 $P\twoheadrightarrow_{\beta}Q$，故

$$P\equiv P_0\rightarrow_{\beta}P_1\rightarrow_{\beta}\cdots\rightarrow_{\beta}P_n\equiv Q$$

根据规则$\xi$，有

$$\lambda z.P\equiv \lambda z.P_0\rightarrow_{\beta}\lambda z.P_1\rightarrow_{\beta}\cdots\rightarrow_{\beta}\lambda z.P_n\equiv \lambda z.Q$$

9

习题3.9

证明：对于任何 $P,Q\in\Lambda$，若 $P=_{\beta}Q$，则存在 $n\in\mathbb{N}$ 以及 $P_0,\cdots,P_n\in\Lambda$，满足：

（1）$P\equiv P_0$；

（2）$Q\equiv P_n$；

（3）对任何 $i<n$ , $P_i\rightarrow_{\beta} P_{i+1}$或$P_{i+1}\rightarrow_{\beta} P_{i}$。

证：

由 $=_{\beta}$ 的定义，$P=_{\beta}Q$由传递性得到，传递过程中经历的 $P_i,i\in\{1,2,\cdots,n\}$即满足要求。

10

习题3.10

证明定理3.12：

对于任何 $M,N\in\Lambda$, $$ M=_{\beta}N\Leftrightarrow\lambda\beta \vdash M=N. $$

证：

在$\lambda\beta$公理系统中可证明的公式在$=_{\beta}$关系中可以互相转换。

从两个方向上证明.

$``\Rightarrow"$：

$P_i \twoheadrightarrow_{\beta} P_{i+1} \Rightarrow P_i =_{\beta} P_{i+1}$. 而 $P_i \twoheadrightarrow_{\beta} P_{i+1}$ 的证明过程中用到的所有性质，都同样可以应用在 $P_i =_{\beta} P_{i+1}$ 的证明上, 因而通过枚举所有情况，不难证明结论.

$``\Leftarrow"$：

反之亦然.

$(\sigma): M = N \vdash N = M$, $=_{\beta}$ 是自反的，所以 $N =_{\beta} M$;

$(\tau): M=N , N=L \vdash M=L$, $=_{\beta}$ 是传递的，所以 $M =_{\beta} N$;

$(\mu): M=N \vdash ZM=ZN$, $=_{\beta}$ 是合拍的，$ZM =_{\beta} ZN$;

$(\upsilon): M=N \vdash MZ=NZ$, $=_{\beta}$ 是合拍的，$MZ =_{\beta} NZ$;

$(\xi): M=N \vdash \lambda x.M=\lambda x.N$, $=_{\beta}$ 是合拍的，$\lambda x.M =_{\beta} \lambda x.N$.

11

习题3.11

证明定理3.13：

对于任何 $M,N\in\Lambda$, $$ M=_{\beta\eta}N\Leftrightarrow\lambda\beta\eta \vdash M=N. $$

证：

与习题3.10同理可证。