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

Question

我需要使用哪些法律来简化

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

至

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

Answer 1

无需应用任何特定的“规律”，只需写下一个简单的表格即可确定这两个表达式是等价的（假设+isOR和*is 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)。这称为andover的分布性or。进一步阅读是一篇关于Wikipedia 上布尔代数的好文章。

在您的示例中：(!Y + !Z)*(Y + Z) = !Y*(Y + Z) + !Z*(Y + Z) = !Y*Y + !Y*Z + !Z*Y + !Z*Z. Trivially 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