哪些定律简化了这个布尔表达式？

Question

我需要用哪些定律来简化

!X + (!Y + !Z)*(Y + Z)

至

!X + (Y*!Z) + (!Y*Z)

Answer 1

无需应用任何特定的 'laws'，只需写下一个简单的 table 即可确定这两个表达式是等价的（前提是 + 是 OR 和 * 是 AND):

Y  Z  !Y  !Z  (!Y+!Z)*(Y+Z)      (Y*!Z) +(!Y*Z)
0  0  1   1   (1+1=1)*(0+0=0)=0  (0*1=0)+(1*0=0)=0
0  1  1   0   (1+0=1)*(0+1=1)=1  (0*0=0)+(1*1=1)=1
1  0  0   1   (0+1=1)*(1+0=1)=1  (1*1=1)+(0*0=0)=1
1  1  0   0   (0+0=0)*(1+1=1)=0  (1*0=0)+(0*1=0)=0

同样可以推导出(X or Y) and Z等价于(X and Z) or (Y and Z)。这称为 and 在 or 上的分配率。进一步阅读维基百科上关于 Boolean algebra 的一篇不错的文章。

在您的示例中：(!Y + !Z)*(Y + Z) = !Y*(Y + Z) + !Z*(Y + Z) = !Y*Y + !Y*Z + !Z*Y + !Z*Z。平凡 A and not A == false，然后你的表达式简化为 !Y*Z + !Z*Y 并进一步简化为 Y*!Z + !Y*Z 因为交换性。

Answer 2

你可以先从乘法对加法的分配律着手：

!X + (!Y + !Z)*(Y + Z) = !X + !Y*Y + !Z*Y + !Y*Z + !Z*Z

然后，我们可以使用补码来删除形式为 !p*p:

的元素

= !X + 0 + !Z*Y + !Y*Z + 0

最后删除 0，因为它们是 + 的中性。

Answer 3

如果没记错的话（我记错了你的记法），那么这是一个简单连词内的 SLD 解析：http://en.wikipedia.org/wiki/SLD_resolution

哪些定律简化了这个布尔表达式？

Which laws simplify this boolean expression?

boolean-expression

simplification

boolean-algebra