2

我收到了以下问题：

下表描述了具有三个输入值 a、b 和 c 的布尔函数的输出 d。

 a  b  c  |  d 
----------+----
 0  0  0  |  1 
 0  0  1  |  1 
 0  1  0  |  1 
 0  1  1  |  0 
 1  0  0  |  0 
 1  0  1  |  0 
 1  1  0  |  0 
 1  1  1  |  0

使用 AND、OR、XOR、NOT、NAND、NOR 或 XNOR 的适当组合给出此布尔函数。

为什么是正确答案：

d := (((NOT a) AND (NOT b)) AND (NOT c)) OR
(((NOT a) AND (NOT b)) AND c) OR
(((NOT a) AND b) AND (NOT c))

我的答案。(((非 a) 与 (非 b)) 与 (非 c))

a   b   c     d
===============
0   0   0     1      
.
. 
.

这是如何得出的？

4

5 回答 5

2

您给出的答案称为产品总和(SOP) 公式。看看 OR 加入的三个大术语：

  • ((NOT a) AND (NOT b)) AND (NOT c))
  • ((NOT a) AND (NOT b)) AND c)
  • ((NOT a) AND b) AND (NOT c)

现在看真值表，其中恰好三行在d列中有 1。这三行中的每一行都对应于三个术语之一。

可以组成更简短的答案，例如d := (NOT a) AND (NOT(b AND c))，但它们不是您给出的乘积总和公式。

于 2012-06-03T13:37:33.207 回答
1
  • 检查表的上半部分。a必须为假fun才能为真。
  • 此外，两者b和c不能true同时。所以，它必须是!(b && c)。
  • 这应该fun归结为!a && !(b && c)
  • 您可以将德摩根定理应用于第二部分并使用!b || !c，但a即使那样也必须是错误的，所以：!a && (!b || !c)这就是您最终得到的。
于 2012-06-03T13:37:02.053 回答
1

对于 3 个变量，8 个条目 (2^3) 提供了 3 个变量、、之间所有可能变量的详尽组合。变量是（可以看出）某个函数 say 的输出。abcdf(x)

现在，由于 8 个条目包括所有可能的变化，我们可以推断出只有在特定组合发生时输出d才是布尔值。1结果是0在所有其他情况下。

因此，我们只需将所有输出为 的行组合起来1。你得到的结果如下。

程序很简单：

  • 取所有输出为 的行1。
  • 对于每一行，输出一个表达式，该表达式将导致1变量的值。
    • AND每个变量。如果任何变量有值0，NOT它在它之前AND。
  • OR在上述步骤中找到的所有 8 个表达式。
于 2012-06-03T13:38:24.960 回答
1

从（完整）真值表中导出函数的最简单方法是仅读取结果为 1（或 0）的行并写下析取（或合取）范式。

在您的表中，结果 1 比 0 少，因此析取范式会更短。从表中可以看出，d恰好 3 种情况下为 1：

  • a=0, b=0, c=0
  • a=0, b=0, c=1
  • a=0, b=1, c=0

只需将它们放在一起，您就会得到： (! = not, & = and, v = or)

d = (!a & !b & !c) v (!a & !b & c) v (!a & b & !c)

此表格自动排除所有其他情况。你仍然可以简化这个公式。仔细查看真值表会告诉您，如果和都为 0，则 的值c无关紧要。因此可以折叠前两部分以获得以下析取形式：（不再是标准形式）ab

d = (!a & !b) v (!a & b & !c)

如果应用分布性，它会变得更短：

d = !a & (!b v (b & !c))

差不多完成了：

d = !a & (!b v b) & (!b v !c)   | applying (x v !x) == 1 and (1 & y) == y
  = !a & (!b v !c)              | applying De Morgan (!a v !b) == !(a & b)
  = !a & !(b & c)

完毕。

于 2012-06-03T13:55:15.237 回答
1

正如有人提到的，你应该看看卡诺图。在维基百科上检查它 乍一看可能看起来有点复杂，但一旦你得到它，为任何真值表推导出最佳表达式是非常简单的。

下图显示了给定真值表的卡诺图。

\ AB
C\  00  01  11  10
  \----------------
0 | 1 | 1 | 0 | 0 |
  |----------------
1 | 1 | 0 | 0 | 0 |
   ----------------

使用 Karnaugh 时要做的第一件事就是将真值表复制到地图上。我会让你想办法做到这一点。

下一步是将这些分组，维基百科文章描述了如何做到这一点。

终于想出了解决办法

从卡诺图可以看出，无论 C 的值如何，当 (!A & !B) 时输出为真，当 (!A & B & !C) 时输出也为真。

因此函数可以写成： D = (!A & !B) OR (!A & B & !C)

另一种解决方案是：D = (!A & !C) OR (!A & !B & C)

于 2012-06-06T10:56:27.277 回答