Імпліканта

В булевій алгебрі, імпліканта - покриття одного, або декількох мінтермів в сумі добутків (або макстермів в добутку суми) булевої функції. Формально, кон'юктивний одночлен P в сумі добутків є імплікантою в булевій функції F.

Більш точно:

якщо P, то F (таким чином P є імплікантою з F), F також приймає значення 1, якщо P дорівнює 1.

Де:

• F - булева функція з N змінних.
• P - кон'юнктивний одночлен.

Це означає, що $P=>F$ по відношенню до природного порядку булевого простору. Наприклад, функція

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

імплікується з $xy$, $xyz$, $xyzw$, $w$ і багатьох інших, це імпліканти $f$.

Проста імпліканта

Простою імплікантою функції є імпліканта, яка не може бути покрита більш загальною (більш зниженою - з меншою кількістю літералів ) імплікантою. Квайн визначив просту імпліканту з F: видалення будь-якого літералу з P призводить до того, що вона вже не буде імплікантою F. Основні прості імпліканти є простими імплікантами, які покривають вихід функції так, що ніяка комбінація інших простих імплікант не в змозі покрити його.

Використовуючи наведений вище приклад, можна легко побачити, що в той час як $xy$ є простою імплікантою, $xyz$ і $xyzw$ - ні. З останніх декількох літералів можуть бути видалені, щоб зробити імпліканту простою:

• $x$, $y$ і $z$ можуть бути видалені, поступаючись $w$.
• Крім того, $z$ і $w$ можуть бути видалені, поступаючись $xy$.
• Нарешті, $x$ і $w$ можуть бути видалені, поступаючись $yz$.

Процес видалення літералів з логічного терму називають розширенням терму. Розширення на один літерал подвоює кількість вхідних комбінацій, для яких терм є істинним (у двійковій булевій алгебрі). На прикладі функції вище, ми можемо розширити $xyz$, щоб $xy$ або $yz$ без зміни покриття $f$. Сума всіх простих імплікант булевої функції називається повною сумою цієї функції.

Див. також

• Метод Куайна
• Карта Карно

Посилання

• Слайди пояснюють імпліканти, прості імпліканти і основні прості імпліканти [Архівовано 12 листопада 2009 у Wayback Machine.]
• Приклади знаходження основних простих імплікант використанням карт Карно [Архівовано 16 січня 2013 у Wayback Machine.]