跳至內容

蘊涵項

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

布林運算的積項和式中(和項積式亦可),乘積項P布林函數 F涵項(英語:implicant),如果 P 蘊涵 F。更加準確的說:

  • Fn 個變數的布林函數
  • P 是乘積項。
  • 若對於使 P 得到值 1 的所有組合,F 也等於 1,則 P 蘊涵 F (PF涵項)。

這意味著在布林空間的自然次序上 P⇒F。比如,函數

蘊涵自 和很多其他的項: 它們是 涵項

威拉德·馮·奧曼·蒯因定義:

  1. F質涵項(prime implicant)為最少化文字數量的涵項——就是說,如果從 P 去除任何「文字」(literal)都導致 P 成為 F 的非涵項。例如100101是某邏輯函數的兩個涵項,那麼10x就是函數的一個質涵項,其中的1和0兩個數字不可再去掉;
  2. 基本質涵項(essential prime implicant)為蘊涵於不滿足任何其他質涵項的極小項(minterm)的那些質涵項——若存在只被一個質涵項覆蓋的極小項,則覆蓋該極小項的質涵項基本質涵項。如果以卡諾圖的形式來描述邏輯函數,可以發現只有一種方式可以圈選這個輸入組合。

使用上面的例子,你可以輕易的看到儘管 (和其他的項)是質涵項 不是。從後者,可以去除多個文字來使它成為素的:

  • 可以去除,生成
  • 可作為選擇的, 可以去除,生成
  • 最後, 可以被去除,生成

將布林項中文字去除的過程叫做「對這個項的擴充 」。擴充一個文字將倍增使這個項為「真」的輸入組合的數目(在二元布林代數中)。 如上例中,將xyz擴充為xy或yz不影響f的結果。

布林函數的所有質蘊涵項的總和叫做這個函數的完全和

參見

[編輯]