根据 De Morgan 定律可知, 有布尔关系 x ∨ y = ¬(¬x ∧ ¬y)
,利用这个关系,可以在只使用 logical-and
和 logical-not
的情况下,定义 logical-or
;这也就是说,可以在只使用 and-gate
和 inverter
的情况下,定义 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
用到的 inverter
和 and-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
定义只是单纯的调用 and-gate
和 inverter
,所以它的延迟值由 and-gate-delay
和 inverter-delay
决定。
整个 or-gate
共调用了三次 inverter
,一次 and-gate
,因此 or-gate
的延迟等于 3 * inverter-delay + and-gate-delay
。
前面说过, 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