Implikant

U Bulovoj logici, implikant je „pokrivač“ (oblik zbira ili proizvoda) jednog ili više minterma u sumi od proizvoda (ili makterma u proizvodu suma) u Bulovoj funkciji. Minterm se zove proizvod zato što predstavlja logično I skupa promenljivih, a makterm se zove suma jer predstavljaj logično ILI skupa promenljivih. Formalno, oblik proizvoda P u sumi proizvoda je implikant Bulove funkcije F ako P implicira F. Preciznije:

P podrazumeva F (i na taj način je implikant od F) ako F uzima vrednost 1, kad god je P jednako 1, gde je:

• F Bulova funkcija sa n promenljivih.
• P je oblik proizvoda.

To znači da je P$=>$F u odnosu na prirodni redosled Bulovog prostora. Na primer, funkcija

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

se podrazumeva po $xy$, po $xyz$, po $xyzw$, po $w$ i mnogim drugima, to su implikanti od $f$.

Prost implikant

Prvi (prost) implikant funkcije je implikant koji ne može biti pokriven opštijim (više redukovanim - što znači sa manjim brojem literala) implikantom. V. V. Kvajn je definisao prvi (prost) implikant F kao implikant koji je minimalan - to jest, uklanjanje bilo kog literala iz P rezultuje u ne-implikant za F. Suštinski prvi (prost) implikanti su glavni implikanti koji pokrivaju izlaz funkcije koji ni jedna kombinacija drugih glavnih implikanta nije je u stanju da pokrije.

Koristeći gornji primer, lako se može videti da, dok je $xy$ (i drugi) prvi (prost) implikant, to $xyz$ i $xyzw$ to nisu. Iz drugog kasnijeg primera, više literala se mogu ukloniti da bi se on načinio prvim:

• $x$, $y$ i $z$ se mogu ukloniti, dajući $w$.
• Alternativno, $z$ i $w$ se mogu ukloniti, dajući $xy$.
• Na kraju, $x$ i $w$ se mogu uklonititi, dajući $yz$.

Proces uklanjanja literala iz Bulovih termin se zove prošireni oblik. Proširenje jednim literalom udvostručuje broj ulaznih kombinacija za koje je oblik tačan (u binarnoj Bulovoj algebri). Koristeći funkciju u gornjem primeru, može da se proširi $xyz$ do $xy$ ili do $yz$ bez promene pokrivača $f$.

Zbir svih prvih (prostih) implikanata Bulove funkcije se zove celokupna suma', minimalna pokrivajuća suma ili Blake kanonski oblik.

Vidi još

• Kvajn–Maklaskijev algoritam
• Karnoova karta