Тупиковые днф и решение задачи минимизации.
Покрытие множества Nf максимальными гранями(возможно не всеми) называется неприводимым если при удалении мз него любой грани оно перестаёт быть покрытием.
ДНФ, которая соответствует неприводимому покрытию называется тупиковой.
Если решать задачу минимизации перебором всевозможных покрытий множества Nf максимальными гранями, то можно ограничиться только перебором неприводимых покрытий и соответственно тупиковых ДНФ, так как удаление любой грани из покрытия приводят к уменьшению, как числа конъюнкций, так и числа букв. Среди неприводимых покрытий (тупиковых ДНФ) всегда существует минимальное покрытие и минимальная ДНФ как для числа букв так и для числа элементов конъюнкции. Следовательно, задача минимизации сводится к перебору всевозможных тупиковых ДНФ.
-
Содержание
- Множества. Основные понятия.
- Операции над множествами и их свойства.
- Декартово произведение. Разбиение множеств.
- Алгебра множеств
- Отношение. Бинарное отношение
- Алгебра бинарных отношений
- Отображение. Виды отображений
- Отношение порядка. Изоморфизм упорядоченных множеств.
- Алгебраические системы. Изоморфизм алгебраических систем.
- Функции алгебры логики.
- Формулы. Реализация функций формулами.
- Эквивалентность формул. Свойства элементарных булевых функций.
- Двойственные функции. Принцип двойственности
- Разложение булевых функций по переменным. Сднф.
- Полнота и замкнутость.
- Представление булевых функций в виде полинома Жегалкина. Теорема Жегалкина.
- Классы т0, т1.
- Класс s.
- Класс м.
- Класс l
- Теорема о функциональной полноте. Проверка системы функций на полноту.
- Задача минимизации булевых функций.
- Задача минимизации булевых функций в геометрической постановке.
- Сокращенные днф.
- Тупиковые днф и решение задачи минимизации.
- Графы. Основные понятия.
- Орграфы. Основные понятия.
- Маршруты. Цепи. Циклы. Связность.
- Операции над графами