Мінімізація логічних функцій

1.

Лекція
Тема лекції: Мінімізація
логічних функцій
Ціль лекції: Уяснити загальні мету та завдання процедур мінімізації логічних
функцій з точки зору побудові економічних та швидкодіючих цифрових
схем.
Вивчити найбільш розповсюджені аналітичні та графічні методи
мінімізації логічних функцій, провести їх порівняльний аналіз.
.
План лекції
1. Общий подход к минимизации логических функций
2. Метод Квайна
3. Метод Квайна - Мак-Класки
4. Метод диаграмм Вейча
Література: А.Я. Савельев. Прикладная теория цифровых автоматов. М., Высшая школа
1987. с. 46-67.
Н.П. Бабич, И.А. Жуков. Компьютерная схемотехника. Киев. «МК-Пресс»,
2004. с.18-33.

2.

1. Общий подход к минимизации логических функций
Для разработки экономичных схем цифровых автоматов применяют минимизацию логических
функций, которые эти автоматы описывают.
Цель минимизации логических функций: найти аналитическое выражение заданной булевой
функции в форме, содержащей минимально возможное число букв.
Эта задача хорошо решается в классе дизъюнктивных и конъюнктивных нормальных форм и
включает два этапа:
Этап 1. Поиск сокращенной формы записи ДНФ исходной функции, которая представляет собой
дизъюнкцию простых импликант этой функции.
Определение: Булева функция g(x1, ..., xn) называется импликантой булевой функции f(x1, ..., xn),
если для любого набора переменных, на котором g = 1, справедливо f = 1.
Пример. Задана функция f в табличной форме:
Запись функции f и ее импликант в СДНФ
x1 x2 x3 f g1 g2 g3 g4 g5 g6
имеет вид:
0 0 0 0 0 0 0 0 0 0
ഥ