练习 3.29

根据 De Morgan 定律可知, 有布尔关系 x y = ¬(¬x ¬y) ,利用这个关系,可以在只使用 logical-andlogical-not 的情况下,定义 logical-or ;这也就是说,可以在只使用 and-gateinverter 的情况下,定义 or-gate

;;; 29-or-gate.scm

(load "p191-and-gate.scm")
(load "p191-inverter.scm")

(define (or-gate input-1 input-2 output)
    (let ((invert-1 (make-wire))
          (invert-2 (make-wire))
          (and-invert-1-invert-2 (make-wire)))
        (inverter input-1 invert-1)
        (inverter input-2 invert-2)
        (and-gate invert-1 invert-2 and-invert-1-invert-2)
        (inverter and-invert-1-invert-2 output))
    'ok)

实现 or-gate 用到的 inverterand-gate 的定义都在书本 191 页:

;;; p191-inverter.scm

(define (inverter input output)
    (define (invert-input)
        (let ((new-value (logical-not (get-signal input))))
            (after-delay inverter-delay
                         (lambda ()
                            (set-signal! output new-value)))))
    (add-action! input invert-input)
    'ok)

(define (logical-not s)
    (cond ((= s 0) 1)
          ((= s 1) 0)
          (else (error "Invalid signal" s))))

(为 and-gate 补上了 logical-and

;;; p191-and-gate.scm

(define (and-gate a1 a2 output)
    (define (and-action-procedure)
        (let ((new-value (logical-and (get-signal a1) (get-signal a2))))
            (after-delay and-gate-delay
                         (lambda ()
                            (set-signal! output new-value)))))
    (add-action! a1 and-action-procedure)
    (add-action! a2 and-action-procedure)
    'ok)

(define (logical-and x y)
    (if (and (= x 1) (= y 1))
        1
        0))

模拟

使用模拟器对上面定义的 or-gate 进行测试(模拟所需的所有代码在书本的后面会给出):

1 ]=> (load "p194-simula.scm")                  ; 载入模拟器

;Loading "p194-simula.scm"...
;  Loading "28-or-gate.scm"... done
;  Loading "p190-full-adder.scm"... done
;  Loading "p190-half-adder.scm"... done
;  Loading "p191-and-gate.scm"... done
;  Loading "p191-inverter.scm"... done
;  Loading "p192-wire.scm"... done
;  Loading "p194-after-delay.scm"... done
;  Loading "p194-probe.scm"... done
;  Loading "p194-propagate.scm"... done
;  Loading "p196-agenda.scm"...
;    Loading "p181-queue.scm"... done
;  ... done
;... done
;Value: or-gate-delay

1 ]=> (load "29-or-gate.scm")                   ; 因为模拟器程序默认会载入练习 28 的 or-gate
                                                ; 因此这里要显式载入本练习的 or-gate 定义来覆盖原本的定义
;Loading "29-or-gate.scm"...
;  Loading "p191-and-gate.scm"... done
;  Loading "p191-inverter.scm"... done
;... done
;Value: or-gate

1 ]=> (define input-1 (make-wire))              ; 定义三条线路

;Value: input-1

1 ]=> (define input-2 (make-wire))

;Value: input-2

1 ]=> (define output (make-wire))

;Value: output

1 ]=> (or-gate input-1 input-2 output)          ; 连接线路到 or-gate 上

;Value: ok

1 ]=> (propagate)                               ; 执行模拟

;Value: done

1 ]=> (get-signal output)                       ; 因为两条输入线路的值都是默认的 0 ,所以 output 的信号为 (logical-or 0 0) 等于 0

;Value: 0

1 ]=> (set-signal! input-1 1)                   ; 将其中一条输入线路的值设置为 1

;Value: done

1 ]=> (propagate)                               ; 重新执行模拟

;Value: done

1 ]=> (get-signal output)                       ; 这次两条输入线路的值分别是 1 和 0 ,所以 output 的信号为 (logical-or 1 0) 等于 1

;Value: 1

or-gate-delay

因为这个 or-gate 定义只是单纯的调用 and-gateinverter ,所以它的延迟值由 and-gate-delayinverter-delay 决定。

整个 or-gate 共调用了三次 inverter ,一次 and-gate ,因此 or-gate 的延迟等于 3 * inverter-delay + and-gate-delay

or-gate 的另一个定义

前面说过, logical-or 的定义可以由布尔关系 x y = ¬(¬x ¬y) 给出,而其中的关系 ¬(a b) 又可以表示为另一个逻辑操作 logical-nand ,如果将 logical-nand 引入公式,那么就得出了新的 logical-or 定义: x y = ¬x | ¬y ,其中符号 | 表示求两布尔值的 logical-nand

根据以上关系,可以给出相应的 nand-gate 定义:

;;; 29-nand-gate.scm

(define nand-gate-delay 3)

(define (nand-gate input-1 input-2 output)
    (define (nand-action-procedure)
        (let ((new-value
                (logical-nand (get-signal input-1) (get-signal input-2))))
            (after-delay nand-gate-delay
                         (lambda ()
                            (set-signal! output new-value)))))
    (add-action! input-1 nand-action-procedure)
    (add-action! input-2 nand-action-procedure)
    'ok)

(define (logical-nand x y)
    (if (and (= x 1) (= y 1))
        0
        1))

因为这个 nand-gate 定义并不存在于书本中,所以我们需要(自作主张地)设置一个 nand-gate-delay ,这样 nand-gate 才能实际运行起来:

1 ]=> (load "p194-simula.scm")                  ; 载入模拟器

;Loading "p194-simula.scm"...
;  Loading "28-or-gate.scm"... done
;  Loading "p190-full-adder.scm"... done
;  Loading "p190-half-adder.scm"... done
;  Loading "p191-and-gate.scm"... done
;  Loading "p191-inverter.scm"... done
;  Loading "p192-wire.scm"... done
;  Loading "p194-after-delay.scm"... done
;  Loading "p194-probe.scm"... done
;  Loading "p194-propagate.scm"... done
;  Loading "p196-agenda.scm"...
;    Loading "p181-queue.scm"... done
;  ... done
;... done
;Value: or-gate-delay

1 ]=> (load "29-nand-gate.scm")                 ; 载入 nand-gate

;Loading "29-nand-gate.scm"... done
;Value: logical-nand

1 ]=> (define input-1 (make-wire))              ; 定义输入和输出线路

;Value: input-1

1 ]=> (define input-2 (make-wire))

;Value: input-2

1 ]=> (define output (make-wire))

;Value: output

1 ]=> (nand-gate input-1 input-2 output)        ; 执行模拟

;Value: ok

1 ]=> (propagate)

;Value: done

1 ]=> (get-signal output)                       ; 0 NAND 0 = 1

;Value: 1

1 ]=> (set-signal! input-1 1)                   ; 将两条输入线路的值都设为 1

;Value: done

1 ]=> (set-signal! input-2 1)

;Value: done

1 ]=> (nand-gate input-1 input-2 output)

;Value: ok

1 ]=> (propagate)

;Value: done

1 ]=> (get-signal output)                       ; 1 NAND 1 = 0

;Value: 0

确定 nand-gate 可以正常运行之后,就可以使用它来重定义 or-gate 了:

;;; 29-another-or-gate.scm

(load "29-nand-gate.scm")

(define (or-gate input-1 input-2 output)
    (let ((invert-1 (make-wire))
          (invert-2 (make-wire)))
        (inverter input-1 invert-1)
        (inverter input-1 invert-2)
        (nand-gate invert-1 invert-2 output)))

测试:

1 ]=> (load "p194-simula.scm")

;Loading "p194-simula.scm"...
;  Loading "28-or-gate.scm"... done
;  Loading "p190-full-adder.scm"... done
;  Loading "p190-half-adder.scm"... done
;  Loading "p191-and-gate.scm"... done
;  Loading "p191-inverter.scm"... done
;  Loading "p192-wire.scm"... done
;  Loading "p194-after-delay.scm"... done
;  Loading "p194-probe.scm"... done
;  Loading "p194-propagate.scm"... done
;  Loading "p196-agenda.scm"...
;    Loading "p181-queue.scm"... done
;  ... done
;... done
;Value: or-gate-delay

1 ]=> (load "29-another-or-gate.scm")

;Loading "29-another-or-gate.scm"...
;  Loading "29-nand-gate.scm"... done
;... done
;Value: or-gate

1 ]=> (define input-1 (make-wire))

;Value: input-1

1 ]=> (define input-2 (make-wire))

;Value: input-2

1 ]=> (define output (make-wire))

;Value: output

1 ]=> (or-gate input-1 input-2 output)

;Value: ok

1 ]=> (propagate)

;Value: done

1 ]=> (get-signal output)                   ; 0 OR 0 = 0

;Value: 0

1 ]=> (set-signal! input-1 1)

;Value: done

1 ]=> (or-gate input-1 input-2 output)

;Value: ok

1 ]=> (propagate)

;Value: done

1 ]=> (get-signal output)                   ; 1 OR 0 = 1

;Value: 1

See also

关于 nand 操作符的更多信息,可以参考相应的维基百科词条: http://en.wikipedia.org/wiki/Logical_NAND

讨论

blog comments powered by Disqus