蘊涵項

蘊涵項

在布爾邏輯中,乘積項(極小項) 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。
向布爾項增加文字的過程叫做擴展這個項。擴展一個文字加倍使這個項為真的輸入組合的數目(在二元布爾代數中)。
布爾函式的所有素蘊涵項的總和叫做這個函式的完全和。

相關詞條

熱門詞條

聯絡我們