蘊(yùn)涵項(xiàng)是布爾邏輯中的一個(gè)重要概念，涉及乘積項(xiàng)與布爾函數(shù)的關(guān)系。乘積項(xiàng) P 被認(rèn)為是布爾函數(shù) F 的蘊(yùn)涵項(xiàng)，如果 P 蘊(yùn)涵 F。這種關(guān)系在布爾空間的自然次序上表現(xiàn)為 P?F。素蘊(yùn)涵項(xiàng)是指不能進(jìn)一步簡(jiǎn)化的蘊(yùn)涵項(xiàng)，而本質(zhì)素蘊(yùn)涵項(xiàng)則是指那些覆蓋獨(dú)特極小項(xiàng)的素蘊(yùn)涵項(xiàng)。
簡(jiǎn)介
在布爾邏輯中，乘積項(xiàng)(極小項(xiàng)) P 是布爾函數(shù) F 的蘊(yùn)涵項(xiàng)，如果 P 蘊(yùn)涵 F。更加準(zhǔn)確的說(shuō):
- F 是 n 個(gè)變量的布爾函數(shù)。
- P 是乘積項(xiàng)。
- 對(duì)于 n 個(gè)變量的使 P 得到值 1 的所有組合，F(xiàn) 也等于 1。所以 P 蘊(yùn)涵 F。
這意味著在布爾空間的自然次序上 P < F。比如，函數(shù)f(x,y,z,w) = xy + yz + w。
蘊(yùn)涵自 xy，xyz，xyzw，w 和很多其他的項(xiàng): 它們是 f 的蘊(yùn)涵項(xiàng)。
威拉德·馮·奧曼·因定義 F 的素蘊(yùn)涵項(xiàng)為最小化的蘊(yùn)涵項(xiàng) - 就是說(shuō)，如果從 P 去除任何文字都導(dǎo)致 F 的非蘊(yùn)涵項(xiàng)。定義本質(zhì)素蘊(yùn)涵項(xiàng)為某些輸入值的組合滿足 P 但不滿足任何其他素蘊(yùn)涵項(xiàng)的那些蘊(yùn)涵項(xiàng)。
使用上面的例子，你可以輕易的看到盡管 xy (和其他的項(xiàng))是素蘊(yùn)涵項(xiàng)，xyz 和 xyzw 不是。從后者，可以去除多個(gè)文字來(lái)使它成為素的:
- x、y 和 z 可以去除，生成 w。
- 可作為選擇的，z 和 w 可以去除，生成 xy。
- 最后，x 和 w 可以被去除，生成 yz。
向布爾項(xiàng)增加文字的過(guò)程叫做擴(kuò)展這個(gè)項(xiàng)。擴(kuò)展一個(gè)文字加倍使這個(gè)項(xiàng)為真的輸入組合的數(shù)目(在二元布爾代數(shù)中)。
布爾函數(shù)的所有素蘊(yùn)涵項(xiàng)的總和叫做這個(gè)函數(shù)的完全和。在布爾邏輯的積項(xiàng)和式中(和項(xiàng)積式亦可)，這些蘊(yùn)涵項(xiàng)的概念同樣適用。質(zhì)涵項(xiàng)（prime implicant）是指最少化文字?jǐn)?shù)量的蘊(yùn)涵項(xiàng)，即從中去除任何文字都會(huì)導(dǎo)致它不再是 F 的蘊(yùn)涵項(xiàng)。例如，若100和101是某邏輯函數(shù)的兩個(gè)蘊(yùn)涵項(xiàng)，則10x就是該函數(shù)的一個(gè)質(zhì)涵項(xiàng)，其中的1和0兩個(gè)數(shù)字不可再去掉。
基本質(zhì)涵項(xiàng)（essential prime implicant）是指蘊(yùn)涵于不滿足任何其他質(zhì)涵項(xiàng)的極小項(xiàng)的那些質(zhì)涵項(xiàng)。若存在只被一個(gè)質(zhì)涵項(xiàng)覆蓋的極小項(xiàng)，則覆蓋該極小項(xiàng)的質(zhì)涵項(xiàng)為基本質(zhì)涵項(xiàng)。在卡諾圖中，這些基本質(zhì)涵項(xiàng)可以通過(guò)唯一的圈選方式來(lái)識(shí)別。例如，在上述函數(shù) f 中，xy 是一個(gè)質(zhì)涵項(xiàng)，而 xyz 和 xyzw 不是，因?yàn)樗鼈兛梢酝ㄟ^(guò)去除文字來(lái)簡(jiǎn)化為 xy 或 yz，而不影響 f 的結(jié)果。
參考資料 >