Імпліканта

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

Більш точно:

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

Де:

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

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

Проста імпліканта[ред. | ред. код]

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

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

  • , і можуть бути видалені, поступаючись .
  • Крім того, і можуть бути видалені, поступаючись .
  • Нарешті, і можуть бути видалені, поступаючись .

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

Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

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

Посилання[ред. | ред. код]