МІНІМІЗАЦІЯ ЛОГІЧНИХ ФУНКЦІЙ

Про необхідність мінімізації

Структурні формули у вигляді логічних функцій в СДНФ і СКНФ однозначно визначають структуру логічної схеми комбінаційного пристрою. Однак не можна бути впевненим у тому, що побудоване за такою формулою пристрій буде найбільш повно задовольняти заданим вимогам. Якщо розглядати тотожність алгебри логіки для двох логічних функцій, То в загальному випадку кількість операцій в правій частині тотожності не дорівнює числу операцій в лівій частині. Так як для реалізації кожної операції необхідний логічний елемент, то слід віддати перевагу комбінаційному пристрою, структурна формула якого має менше число операцій. Тому шляхом тотожних перетворень структурної формули, що призводять тільки до зміни її форми, а не значень, можна спростити схему комбінаційного пристрою. Перетворення структурної формули з метою спрощення комбінаційного пристрою називається її мінімізацією.

Алгебраїчна мінімізація. Метод алгебраїчної мінімізації структурних формул комбінаційних пристроїв, представлених логічними функціями в СДНФ і СКНФ, полягає в спрощенні вихідного вираження за допомогою аксіом, законів і тотожностей алгебри логіки. Нижче коротко викладено її основні положення. У наведених співвідношеннях символи А, В, С можуть відображати як логічні змінні, так і логічні функції.

В алгебрі логіки визначено три розглянуті вище основні логічні операції (заперечення, додавання і множення) і відношення еквівалентності (=), яке задовольняє наступним властивостям:

• • рефлексивності (А = А);
• • симетричності (якщо А = В, то В = А);
• • транзитивності (якщо А = В, В = С то А = С).

Наведемо аксіоми алгебри логіки

(3.6)

(3.7)

(3.8)

(3.9)

(3.10)

(3.11)

Аксіома (3.6) відображає той уже відомий факт, що алгебра логіки оперує тільки з двійковими змінними. Аксіоми (3.7) - (3.11) є по суті справи більш загальної формою подання розглянутих вище правил логічного додавання, множення і заперечення довічних змінних.

Розглянемо основні закони алгебри логіки.

Комутативними (переместітельний) закон

(3.12)

Асоціативний (сполучний) закон

(3.13)

Дистрибутивний (розподільний) закон

(3.14)

Закон подвійності (теорема де Моргана)

(3.15)

Інші співвідношення.

правило поглинання

(3.16)

правило склеювання

(3.17)

Наведені аксіоми, закони і співвідношення, за винятком (3.11), записані парами. Кожне з вхідних в пару виразів може бути отримано з іншого заміною операцій додавання на множення, 0 на 1 і навпаки. Якщо в логічне вираження входять операції додавання і множення, то слід дотримуватися порядку виконання операцій: спочатку виконується множення, потім - додавання. У складних логічних виразах для завдання порядку виконання операцій використовуються дужки.

У виразах (3.7) - (3.10), (3.16), (3.17) права частина простіше лівої, тому шляхом відповідних перетворень можна домогтися істотного спрощення вихідного вираження.