離散數學問題集--問題5.9

問題 5.9 綜合了計算機組成原理、數字邏輯和離散數學中的關鍵概念，旨在幫助學生理解二進制算術運算的硬件實現、邏輯門與算術運算的關系，以及如何使用數學方法來驗證數字系統的正確性。它強調了從規范到實現再到驗證的完整過程。

問題5.9的思路

思想

函數抽象： $\operatorname{num}(\alpha_{n})$ ：將二進制字符串映射到非負整數
遞歸： $\operatorname{num}(\alpha_{n + 1})=a_{n + 1}2^{n + 1}+\operatorname{num}(\alpha_{n})$
用求和位和進位來表示兩個二進制數的加法：

思路

加法器的抽象規范–>加法器的電路實現–>數學方法驗證實現是否符合規范

拓展問題

問題5.9都考察了哪些知識點？講到了哪些重要的結論？
如何將問題5.9的結論推廣到十進制？

Problem 5.9

For any binary string $\alpha$ , let $\operatorname{num}(\alpha)$ be the nonnegative integer it represents in binary notation (possibly with leading zeroes). For example, $\operatorname{num}(10)=2$ , and $\operatorname{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{align*} \alpha_{n}&::=a_{n}...a_{1}a_{0},\\ \beta_{n}&::=b_{n}...b_{1}b_{0}, \end{align*}$
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:
$\operatorname{num}(\alpha_{n})+\operatorname{num}(\beta_{n})+c_{0}=2^{n + 1}c_{n + 1}+\operatorname{num}(\sigma_{n}). \tag{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{align*} s_{i}&::=a_{i}\oplus b_{i}\oplus c_{i} \tag{5.10}\\ c_{i + 1}&::=(a_{i} \land b_{i}) \lor (a_{i} \land c_{i}) \lor (b_{i} \land c_{i}) \tag{5.11} \end{align*}$
for $0\leq i\leq 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}. \tag{5.12}$
for all $\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}\land b_{n})\lor(b_{n}\land c_{n})\lor(c_{n}\land a_{n})$ 。
$\text{右邊}=2c_{n+1}+s_n=2[(a_{n}\land b_{n})\lor(b_{n}\land c_{n})\lor(c_{n}\land 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}\land b_{n}$	$b_{n}\land c_{n}$	$c_{n}\land a_{n}$	$c_{n+1} = (a_{n} \land b_{n}) \lor (b_{n}\land c_{n})\lor (c_{n}\land 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,
$\operatorname{num}(\alpha_{n + 1})=a_{n + 1}2^{n + 1}+\operatorname{num}(\alpha_{n}). \tag{5.13}$

證明：使用強歸納法。

歸納假設 $P (n)$ 為公式 (5.9)。

基礎情形： $n = 0$

$\text{左邊}=\operatorname{num}(\alpha_{0})+\operatorname{num}(\beta_{0})+c_{0}$ 。
$\text{右邊}=2c_1+\operatorname{num}(\sigma_{0})$ 。
根據 $n + 1$ 位加法器的規范可知： $\alpha_0=a_0$ ， $\beta_0=b_0$ ， $\sigma_0=s_0$ 。因為只有 $1$ 位，所以 $\operatorname{num}(\alpha_{0})=a_0$ ， $\operatorname{num}(\beta_{0})=b_0$ ， $\operatorname{num}(\sigma_{0})=s_0$ 。
$\text{左邊}=\operatorname{num}(\alpha_{0})+\operatorname{num}(\beta_{0})+c_{0}=a_0+b_0+c_0$ 。
$\text{右邊}=2c_1+\operatorname{num}(\sigma_{0})=2c_1+s_0$ 。
根據公式(5.12)可知， $\text{左邊}=\text{右邊}$ 。

歸納步驟：

假設 $P (k)$ 對所有 $k\leq n$ 都成立。
當 $k = n + 1$ 時， $\text{左邊}=\operatorname{num}(\alpha_{n+1})+\operatorname{num}(\beta_{n+1})+c_{0}$ 。
根據公式(5.13)有：
$\begin{align*} \text{左邊}&=a_{n+1}2^{n+1}+\operatorname{num}(\alpha_{n})+b_{n+1}2^{n+1}+\operatorname{num}(\beta_{n})+c_0\\ &=(a_{n+1}2^{n+1}+b_{n+1}2^{n+1})+(\operatorname{num}(\alpha_{n})+\operatorname{num}(\beta_{n})+c_0)\\ &=2^{n+1}(2c_{n+2}+s_{n+1}-c_{n+1})+(2^{n+1}c_{n+1}+\operatorname{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}+\operatorname{num}(\sigma_{n}))\\ &=2^{n+2}c_{n+2}+\operatorname{num}(\sigma_{n+1})\\ &=\text{右邊}. \end{align*}$

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

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/pingmian/76140.shtml
繁體地址，請注明出處：http://hk.pswp.cn/pingmian/76140.shtml
英文地址，請注明出處：http://en.pswp.cn/pingmian/76140.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！