蕴涵项
数学名词
蕴涵项是一个数学名词,在布尔逻辑中,乘积项(极小项) P 是布尔函数 F 的蕴涵项,如果 P 蕴涵 F。
更加准确的说:
F 是 n 个变量的布尔函数。
P 是乘积项。
对于 n 个变量的使 P 得到值 1 的所有组合,F 也等于 1。所以 P 蕴涵 F。
这意味着在布尔空间的自然次序上 P < F。比如,函数
f(x,y,z,w) = xy + yz + w
蕴涵自 xy,xyz,xyzw,w 和很多其他的项: 它们是 f 的蕴涵项。
威拉德·冯·奥曼·蒯因定义 F 的素蕴涵项为最小化的蕴涵项 - 就是说,如果从 P 去除任何文字都导致 F 的非蕴涵项。定义本质素蕴涵项为某些输入值的组合满足 P 但不满足任何其他素蕴涵项的那些蕴涵项。
使用上面的例子,你可以轻易的看到尽管 xy (和其他的项)是素蕴涵项,xyz 和 xyzw 不是。从后者,可以去除多个文字来使它成为素的:
x、y 和 z 可以去除,生成 w。
可作为选择的,z 和 w 可以去除,生成 xy。
最后,x 和 w 可以被去除,生成 yz。
向布尔项增加文字的过程叫做扩展这个项。扩展一个文字加倍使这个项为真的输入组合的数目(在二元布尔代数中)。
布尔函数的所有素蕴涵项的总和叫做这个函数的完全和。
参考资料
最新修订时间:2024-07-19 23:12
目录
概述
参考资料