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

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同理可证。