离散数学问题集--问题5.9

问题 5.9 综合了计算机组成原理、数字逻辑和离散数学中的关键概念，旨在帮助学生理解二进制算术运算的硬件实现、逻辑门与算术运算的关系，以及如何使用数学方法来验证数字系统的正确性。它强调了从规范到实现再到验证的完整过程。

思想

• 函数抽象：$\mathrm{num}({\alpha }_n)$：将二进制字符串映射到非负整数
• 递归：$\mathrm{num}({\alpha }_{n+1})=a_{n+1}{2}^{n+1}+\mathrm{num}({\alpha }_n)$
• 用求和位和进位来表示两个二进制数的加法：

思路

• 加法器的抽象规范–>加法器的电路实现–>数学方法验证实现是否符合规范

拓展问题

1. 问题5.9都考察了哪些知识点？讲到了哪些重要的结论？
2. 如何将问题5.9的结论推广到十进制？

Problem 5.9

For any binary string $\alpha$, let $\mathrm{num}(\alpha )$ be the nonnegative integer it represents in binary notation (possibly with leading zeroes). For example, $\mathrm{num}(10)=2$, and $\mathrm{num}(0101)=5$.

An $n+1$-bit adder adds two $n+1$-bit binary numbers. More precisely, an $n+1$-bit adder takes two length $n+1$ binary strings
$$\begin{array}{rl}{\alpha }_n& ::=a_n...a_1{a}_0,\\ {\beta }_n& ::=b_n...b_1{b}_0,\end{array}$$
and a binary digit $C_0$ as inputs, and produces a length-$(n+1)$ binary string
$${\sigma }_n::=s_n...s_1{s}_0,$$
and a binary digit $c_{n+1}$ as outputs, and satisfies the specification:
$$\mathrm{num}({\alpha }_n)+\mathrm{num}({\beta }_n)+c_0=2^{n+1}{c}_{n+1}+\mathrm{num}({\sigma }_n).\text{\hspace{1em}(5.9)}$$
There is a straightforward way to implement an $n+1$-bit adder as a digital circuit: an $n+1$-bit ripple-carry circuit has $1+2(n+1)$ binary inputs
$$a_n,...,a_1,a_0,b_n,...,b_1,b_0,c_0,$$
and $n+2$ binary outputs,
$$c_{n+1},s_n,...,s_1,s_0.$$
As in Problem 3.6, the ripple-carry circuit is specified by the following formulas:
$$\begin{array}{rl}{s}_i& ::=a_i\oplus b_i\oplus c_i\\ c_{i+1}& ::=(a_i\wedge b_i)\vee (a_i\wedge c_i)\vee (b_i\wedge c_i)\end{array}\text{\hspace{1em}(5.10)(5.11)}$$
for $0\le i\le n$, where we follow the convention that $1$ corresponds to T and $0$ corresponds to F.

(a) Verify that definitions (5.10) and (5.11) imply that
$$a_n+b_n+c_n=2c_{n+1}+s_n.\text{\hspace{1em}(5.12)}$$
for all $n\in \mathbb{N}$.

证明：对任意的 $n\in \mathbb{N}$，

• $\text{左边}=a_n+b_n+c_n$。
• 可用 $1$ 位的行波进位加法器来实现。它的输入为 $a_n$，$b_n$，$c_n$，输出为 $c_{n+1}$，$s_n$。
• 根据 (5.10) 和 (5.11) 有，$s_n=a_n\oplus b_n\oplus c_n$，$c_{n+1}=(a_n\wedge b_n)\vee (b_n\wedge c_n)\vee (c_n\wedge a_n)$。
• $\text{右边}=2c_{n+1}+s_n=2[(a_n\wedge b_n)\vee (b_n\wedge c_n)\vee (c_n\wedge a_n)]+a_n\oplus b_n\oplus c_n$。

下面使用真值表来验证。

$a_n$	$b_n$	$c_n$	$a_n+b_n+c_n$	$s_n=a_n\oplus b_n\oplus c_n$	$a_n\wedge b_n$	$b_n\wedge c_n$	$c_n\wedge a_n$	$c_{n+1}=(a_n\wedge b_n)\vee (b_n\wedge c_n)\vee (c_n\wedge a_n)$	$2c_{n+1}+s_n$
0	0	0	0	0	0	0	0	0	0
1	0	0	1	1	0	0	0	0	1
0	1	0	1	1	0	0	0	0	1
0	0	1	1	1	0	0	0	0	1
1	1	0	2	0	1	0	0	1	2
1	0	1	2	0	0	0	1	1	2
0	1	1	2	0	0	1	0	1	2
1	1	1	3	1	1	1	1	1	3

(b) Prove by induction on $n$ that an $n+1$-bit ripple-carry circuit really is an $n+1$-bit adder, that is, its outputs satisfy (5.9).

Hint: You may assume that, by definition of binary representation of integers,
$$\mathrm{num}({\alpha }_{n+1})=a_{n+1}{2}^{n+1}+\mathrm{num}({\alpha }_n).\text{\hspace{1em}(5.13)}$$

证明：使用强归纳法。

归纳假设 $P(n)$ 为公式 (5.9)。

基础情形：$n=0$

• $\text{左边}=\mathrm{num}({\alpha }_0)+\mathrm{num}({\beta }_0)+c_0$。
• $\text{右边}=2c_1+\mathrm{num}({\sigma }_0)$。
• 根据 $n+1$位加法器的规范可知：${\alpha }_0=a_0$，${\beta }_0=b_0$，${\sigma }_0=s_0$。因为只有 $1$ 位，所以 $\mathrm{num}({\alpha }_0)=a_0$，$\mathrm{num}({\beta }_0)=b_0$，$\mathrm{num}({\sigma }_0)=s_0$。
• $\text{左边}=\mathrm{num}({\alpha }_0)+\mathrm{num}({\beta }_0)+c_0=a_0+b_0+c_0$。
• $\text{右边}=2c_1+\mathrm{num}({\sigma }_0)=2c_1+s_0$。
• 根据公式(5.12)可知，$\text{左边}=\text{右边}$。

归纳步骤：

• 假设 $P(k)$ 对所有 $k\le n$ 都成立。
• 当 $k=n+1$ 时，$\text{左边}=\mathrm{num}({\alpha }_{n+1})+\mathrm{num}({\beta }_{n+1})+c_0$。
• 根据公式(5.13)有：
  $$\begin{array}{rl}\text{左边}& =a_{n+1}{2}^{n+1}+\mathrm{num}({\alpha }_n)+b_{n+1}{2}^{n+1}+\mathrm{num}({\beta }_n)+c_0\\ & =(a_{n+1}{2}^{n+1}+b_{n+1}{2}^{n+1})+(\mathrm{num}({\alpha }_n)+\mathrm{num}({\beta }_n)+c_0)\\ & =2^{n+1}(2c_{n+2}+s_{n+1}-c_{n+1})+(2^{n+1}{c}_{n+1}+\mathrm{num}({\sigma }_n))\\ & =2^{n+2}{c}_{n+2}+2^{n+1}{s}_{n+1}-2^{n+1}{c}_{n+1}+2^{n+1}{c}_{n+1}+s_n\\ & =2^{n+2}{c}_{n+2}+(2^{n+1}{s}_{n+1}+\mathrm{num}({\sigma }_n))\\ & =2^{n+2}{c}_{n+2}+\mathrm{num}({\sigma }_{n+1})\\ & =\text{右边}.\end{array}$$

综上所述，$P(n)$ 对任意的 $n\in \mathbb{N}$ 都成立。