Імпліканта

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

Більш точно:

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

Де:

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

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

${\displaystyle f(x,y,z,w)=xy+yz+w}$

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

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

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

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

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

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

Див. також

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

Примітки

1. Де Мікелі, Джованні. Синтез та оптимізація цифрових схем. McGraw-Hill, Inc, 1994 р.

Посилання

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