将以下表达式转换为仅使用 NAND 门

Question

我有以下表达式（'表示NOT）...

e'(a+b)

首先我展开...

e'a + e'b

德摩根定律...

(e'a +e'b)'
((e'a)'(e'b)')'

现在我卡住了。我使用的每个 NAND 门最多只能接受 2 个输入。我可以使用任意多的 NAND 门，但我应该尝试想出一个使用最少门的表达式。

我走在正确的轨道上吗？我该如何继续？

Answer 1

看起来不对。

你原来的表达式只有三个运算：NOT (e'), OR (a+b), AND (在我给出的最后两个表达式之间)。您应该弄清楚如何执行这三个操作中的每一个，然后将它们组合成一个整体结构。在这类问题中，知道如何做这些是至关重要的。

这是第一个方法：NOT x 等同于 x NAND x，因此 e' 等同于 e NAND e。从这里继续。

Answer 2

首先，我建议采取这个：

e'(a+b)

并使用更详细的符号编写它，使转换更容易识别为已正确完成：

(not e) and (a or b)

正如 Rory Daulton 所建议的，第一步是了解如何使用 nand 呈现基本逻辑操作。

注意 e 可以证明等同于 e 和 e，正如 Rory 指出的那样。
根据nand的定义可以证明a and b等价于not(a nand b)。使用以上结果，我们仅使用与非门就可以恢复等效表达式 (a nand b) nand (a nand b)。
你可以证明 a 或 b 等价于 De Morgan 的 not((not a) and (not b))，因此根据 nand 的定义，(not a) nand (not b)。我们可以使用以上结果仅使用与非门来导出等效表达式 (a nand a) nand (b nand b)。

回到我们的表达：

(not e) and (a or b)

我有点喜欢从外向内工作，所以我们从最外层的操作开始，然后使用上面2的规则得到：

(not e) and (a or b)
2=> ((not e) nand (a or b)) nand ((not e) nand (a or b))

现在我们在同一级别有四个子表达式，我们可以从左开始，向右工作：

(not e) and (a or b)
2=> ((not e) nand (a or b)) nand ((not e) nand (a or b))
1=> ((e nand e) nand (a or b)) nand ((not e) nand (a or b))
3=> ((e nand e) nand ((a nand a) nand (b nand b))) nand ((not e) nand (a or b))
1=> ((e nand e) nand ((a nand a) nand (b nand b))) nand ((e nand e) nand (a or b))
3=> ((e nand e) nand ((a nand a) nand (b nand b))) nand ((e nand e) nand ((a nand a) nand (b nand b)))

此电路可能如下所示：

e--+---|\   e'
   |   > >o----------------------|\  (e'(a+b))'
   +---|/                        > >o--------+---|\
                             +---|/          |   > >o--e'(a+b)
a--+---|\   a'               |               +---|/
   |   > >o--------|\        |
   +---|/          > >o------+
               +---|/   a+b
b--+---|\      |
   |   > >o----+
   +---|/   b'

将以下表达式转换为仅使用 NAND 门

Convert the following expression to use only NAND gates

math

boolean-logic

boolean

boolean-expression