ОСНОВИ ДИСКРЕТНОГО АНАЛІЗУ.
Автори: Н.Д.Федоренко,В.В.Демченко

     3.8. МІНІМІЗАЦІЯ БУЛЕВИХ ФУНКЦІЙ

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

Змінні на досить часто називають термами. Повний набір із n термів утворює конституенту. В процесі мінімізації деякі терми із конституент зникнуть. Тоді частину, яка залишилась, називають імплікантою.

Імпліканту називають простою, якщо він утворює кон'юнкцію змінних. Довільна кон'юнкція отримана із імпліканти викресленням змінної не є імплікантою.

      Приклад 3. Розглянемо функцію (штрих Шефера). Таблиця 10 значень функції: Таблиця 10.

      Функції та імплікати, бо та входять в f та f , . Дійсно:

      За основу розв'язання задач мінімізації довільних логічних функцій приймаємо схему, що вміщує три етапи:

1) на першому етапі складається таблиця істинності функції ;

2) на другому етапі виконується пошук простих імплікант , тобто будується скорочена доскональна нормальна форма;

3) на третьому етапі проводиться побудова тупикових (без зайвих імплікант) доскональних нормальних форм, з числа яких відбирають мінімальні доскональні нормальні форми.

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

      Розглянемо дані методи.

ЗМІСТ