🗊Презентация Лекция 8. Минимизация. Элементы математической логики и теории автоматов (продолжение)

ТЕМА 5. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ И ТЕОРИИ АВТОМАТОВ (ПРОДОЛЖЕНИЕ) Минимизация функций алгебры логики Метод карт Карно. Неполностью определенные логические функции и их минимизация

1 Минимизация функций алгебры логики Минимизация функций алгебры логики (ФАЛ) является одним из основных этапов анализа и синтеза цифровых устройств. Основной целью минимизации логических функций является получение их минимальных дизъюнктивных или конъюнктивных форм. ДНФ (КНФ) функции f(x1, x2,…, xn) называется минимальной, если она содержит наименьшее число переменных хi по сравнению со всеми другими эквивалентными ДНФ (КНФ). Существуют различные аналитические и табличные методы минимизации. Метод непосредственных преобразований. Метод карт Карно.

1. Метод непосредственных преобразований. Сущность метода непосредственных преобразований заключается с том, что минимизация исходной ФАЛ осуществляется путем применения основных законов и тождеств алгебры логики. 1. Метод непосредственных преобразований. Сущность метода непосредственных преобразований заключается с том, что минимизация исходной ФАЛ осуществляется путем применения основных законов и тождеств алгебры логики. Сокращенной ДНФ называется форма представления ФАЛ, которая получается из СНДФ путем склеивания вначале конституэнт единицы между собой по всем переменным, а затем конъюнкций ранга n-1, n-2 и т. д. Простая импликанта – это конъюнкция, которая не склеивается ни с какой другой конъюнкцией, входящей в данную ФАЛ. Используя понятие импликанты, сокращенную ДНФ можно определить как дизъюнкцию простых импликант.

Пример 1. Минимизировать функцию, заданную в СНДФ. Пример 1. Минимизировать функцию, заданную в СНДФ.

2 Метод карт Карно.

При минимизации функции пяти переменных пользуются картой из 32 клеток. При минимизации функции пяти переменных пользуются картой из 32 клеток.

3 Неполностью определенные логические функции и их минимизация На практике часто на ряде наборов значения логической функций не заданы, поскольку на этих наборах значение функции для проектировщика цифрового устройства не представляет интереса. Такие функции принято называть неполностью определенными. Их обычно доопределяют таким образом, чтобы максимально упростить соответствующие ФАЛ. Для этой цели удобно применять карты Карно.