蕴涵项

维基百科,自由的百科全书
跳转至: 导航搜索

布尔逻辑中,乘积项(极小项)P布尔函数 F蕴涵项英语implicant),如果 P 蕴涵 F。更加准确的说:

  • Fn 个变量的布尔函数
  • P 是乘积项。
  • 对于 n 个变量的使 P 得到值 1 的所有组合,F 也等于 1。所以 P 蕴涵 F

这意味着在布尔空间的自然次序上 P < F。比如,函数

f(x,y,z,w)=xy+yz+w \,

蕴涵自 xyxyzxyzww 和很多其他的项: 它们是 f 的蕴涵项。

威拉德·冯·奥曼·蒯因定义:

  1. F素蕴涵项(prime implicant)为最小化的蕴涵项——就是说,如果从 P 去除任何“文字”(literal)都导致 F 的非蕴涵项。例如100101是某逻辑函数的两个蕴涵项,那么10x就是函数的一个素蕴涵项,其中的1和0两个数字不可再去掉;
  2. 本质素蕴涵项(essential prime implicant)为某些输入值的组合满足 P 但不满足任何其他素蕴涵项的那些蕴涵项,如果以卡诺图的形式来描述逻辑函数,可以发现只有一种方式可以圈选这个输入组合。

使用上面的例子,你可以轻易的看到尽管 xy(和其他的项)是素蕴涵项,xyzxyzw 不是。从后者,可以去除多个文字来使它成为素的:

  • xyz 可以去除,生成 w
  • 可作为选择的,zw 可以去除,生成 xy
  • 最后,xw 可以被去除,生成 yz

将布尔项中文字去除的过程叫做'对这个项的扩展'。扩展一个文字加倍使这个项为真的输入组合的数目(在二元布尔代数中)。 如上例中,将xyz扩展为xy或yz不影响f的结果。

布尔函数的所有素蕴涵项的总和叫做这个函数的完全和

参见[编辑]