Лекція №3 - Методи мінімізації логічних функцій

1. Метод Квайна

2. Метод Квайна-Мак-Класкі

3. Метод Блейка-Порецького

4. Метод Нельсона

5. Метод карт Карно-Вейча

6. Мінімізація кон’юнктивних нормальних форм

7. Мінімізація в базисах І-НЕ та АБО-НЕ

8. Мінімізація не повністю визначених функцій алгебри логіки

9. Мінімізація систем булевих функцій

Розглянемо основні методи мінімізації логічних функцій в класі диз’юнктивних нормальних форм. При цьому під мінімальними будемо розуміти диз’юнктивні нормальні форми (ДНФ), які містять найменшу сумарну кількість змінних (букв) в усіх диз’юнктивних членах.

Нагадаємо деякі поняття.

Елементарним добутком (кон’юнкцією) будемо називати кон’юнкцію декількох різних змінних, що взяті із запереченнями або без них. Наприклад x, xy, xy, xyz і тому подібні.

Диз’юнктивною нормальною формою (ДНФ) називають диз’юнкцію елементарних кон’юнкцій.

Мінімальною диз’юнктивною нормальною формою булевої функції називають ДНФ, яка містить найменьшу кількість букв ( відносно всіх інших ДНФ, які представляють задану функцію).

Наведемо два твердження (без доведення), які є корисними при отриманні мінімальних ДНФ:

1) диз’юнкція будь-якого числа імплікант булевої функції f також є імплікантою цієї функції;

2) будь-яка булева функція f еквівалентна диз’юнкції всіх своїх імплікант; така форма подання булевої функції називається скороченою ДНФ.

Простими імплікантами логічної функції f називають такі елементарні кон’юнкції, які самі входять до даної функції, тобто є імплікантами функції f, але ніяка їх власна частина не є імплікантою функції f.

Прості імпліканти являють собою найкоротші елементарні добутки, що входять до даної логічної функції. Звідси випливає, що логічна функція f дорівнює диз’юнкції всіх простих імплікант.

Будь-яка логічна функція має нескінченну множину простих імплікант, кількість яких менша або дорівнює кількості конституант одиниці в досконалій диз'юнктивній нормальній формі (ДДНФ).