蕴涵项

在布尔逻辑的積項和式中(和項積式亦可),乘积项P 是布尔函数 F涵项(),如果 P 蕴涵 F。更加准确的说:

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

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

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

蕴涵自 xy,xyz,xyzw,w 和很多其他的项: 它们是 f 的涵项

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

F質涵小项(prime implicant)为最少化文字數量的涵项——就是说,如果从 P 去除任何“文字”(literal)都导致 P 成為 F 的非涵项。例如100101是某逻辑函数的两个涵项,那么10x就是函数的一个質涵项,其中的1和0两个数字不可再去掉;

必要質涵大项(essential prime implicant)为蘊涵於不满足任何其他質涵项的極小項(minterm)的那些質涵项——若存在只被一個質涵項覆蓋的極小項,則覆蓋該極小項的質涵項基本質涵項。如果以卡诺图的形式来描述逻辑函数,可以发现只有一种方式可以圈选这个输入组合。

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

*x、y 和 z 可以去除,生成 w。
*可作为选择的,z 和 w 可以去除,生成 xy。
*最后,x 和 w 可以被去除,生成 yz。

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

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

参见

  • 奎因-麦克拉斯基算法
  • 规范形式 (布尔代数)

评论 (0)

  • 还没有评论,来抢沙发吧。