49) Минимизация

Минимизация булевых функций

Минимальная ДНФ – это такая ДНФ функции, которая содержит наименьшее количество вхождений переменных по сравнению с остальными.

Элементарная конъюнкция называется импликантой функции , если она равна 0 на тех наборах, на которых f обращается в 0. Простой импликантой называется импликанта, в которой отбрасывание любой буквы ведет к получению элементарной конъюнкции, которая не является импликантой (т.е. никакая часть простой импликанты сама импликантой не является). Каждая импликанта соответствует покрытию на карте Карно, а простая импликанта – покрытию наибольшей размерности.

Дизъюнкция всех простых импликант функции называется сокращенной ДНФ. Сокращенная ДНФ функции единственна.

Сокращенная ДНФ может содержать лишние импликанты, удаление которых не меняет значения функции.

Если из сокращенной ДНФ удалить все лишние дизъюнктивные члены, и удаление любого из оставшихся приведет к изменению значения функции, то такая форма называется тупиковой ДНФ. Та из всех тупиковых ДНФ, которая имеет наименьшее число вхождений переменных, является минимальной ДНФ.

Минимальных ДНФ может быть несколько.

Процесс нахождения минимальной ДНФ из СДНФ можно разбить на следующие этапы:

1. нахождение сокращенной ДНФ (она единственна);

2. нахождение всех тупиковых ДНФ (их м.б. несколько);

3. выбор из всех тупиковых минимальной ДНФ (их тоже м.б. несколько).

Известны аналитические и графические способы построения минимальной ДНФ. Графический способ использует представление на картах Карно

Этот метод используется для формул с малым числом переменных.

Покрытие, состоящее из двух клеток, соответствует произведению всех переменных кроме одной, значением которой отличаются эти клетки. Покрытие из четырех клеток соответствует произведению, в котором отсутствуют две переменные и т.д.

Для построения минимальной ДНФ следуют двум правилам:

1. Выбирают покрытия наибольшего размера, содержащие клетки, которые не могут быть ни в каком другом покрытии.

2. Для оставшихся клеток выбирают покрытие наибольшей размерности.

Метод Квайна-Мак-Класки

Будем предполагать, что функция представлена в СДНФ. Метод Квайна-Мак-Класки позволяет получить минимальную ДНФ независимо от количества аргументов. На первом этапе выполняется построение сокращенной ДНФ (т.е. поиск всех простых импликант), на втором – получение из нее минимальной ДНФ.

Этап 1. Нахождение сокращенной ДНФ.

1. Каждому дизъюнктивному члену ставим в соответствие двоичный набор. Полученное множество 0-кубов обозначим K⁰ и разобьем его на группы по количеству единиц, обозначив группу с i единицами через K⁰_i.

2. Нахождение простых импликант. а) Применяем операцию склеивания к 0-кубам из соседних подмножеств, которые различаются одной переменной: . Склеивание возможно только между элементами соседних групп (только они могут различаться ровно одной переменной). Элементы, участвующие в склеивании, помечаем. Результат склеивания – набор 1-кубов (импликант) и, возможно, простые импликанты, которые остались не помеченными. Для 1-кубов на месте отсутствующей переменной будем писать знакx. б) Разбиваем 1-кубы на подмножества по расположению x и производим склеивание внутри каждого подмножества (принцип тот же – склеиваются 1-кубы, отличающиеся ровно одной переменной). Склеенные 1-кубы помечаем, результат склеивания – 2-кубы. Неотмеченные 1-кубы – простые импликанты. в) Аналогично склеиваем 2-кубы, 3-кубы и т.п., пока это возможно. По окончании процесса все оставшиеся непомеченными элементы являются простыми импликантами, т.е. получена сокращенная ДНФ.

Этот метод используется для формул с малым числом переменных.

Покрытие, состоящее из двух клеток, соответствует произведению всех переменных кроме одной, значением которой отличаются эти клетки. Покрытие из четырех клеток соответствует произведению, в котором отсутствуют две переменные и т.д.

Для построения минимальной ДНФ следуют двум правилам:

3. Выбирают покрытия наибольшего размера, содержащие клетки, которые не могут быть ни в каком другом покрытии.

4. Для оставшихся клеток выбирают покрытие наибольшей размерности.

Метод Квайна-Мак-Класки

Будем предполагать, что функция представлена в СДНФ. Метод Квайна-Мак-Класки позволяет получить минимальную ДНФ независимо от количества аргументов. На первом этапе выполняется построение сокращенной ДНФ (т.е. поиск всех простых импликант), на втором – получение из нее минимальной ДНФ.

Этап 1. Нахождение сокращенной ДНФ.

3. Каждому дизъюнктивному члену ставим в соответствие двоичный набор. Полученное множество 0-кубов обозначим K⁰ и разобьем его на группы по количеству единиц, обозначив группу с i единицами через K⁰_i.

4. Нахождение простых импликант. а) Применяем операцию склеивания к 0-кубам из соседних подмножеств, которые различаются одной переменной: . Склеивание возможно только между элементами соседних групп (только они могут различаться ровно одной переменной). Элементы, участвующие в склеивании, помечаем. Результат склеивания – набор 1-кубов (импликант) и, возможно, простые импликанты, которые остались не помеченными. Для 1-кубов на месте отсутствующей переменной будем писать знакx. б) Разбиваем 1-кубы на подмножества по расположению x и производим склеивание внутри каждого подмножества (принцип тот же – склеиваются 1-кубы, отличающиеся ровно одной переменной). Склеенные 1-кубы помечаем, результат склеивания – 2-кубы. Неотмеченные 1-кубы – простые импликанты. в) Аналогично склеиваем 2-кубы, 3-кубы и т.п., пока это возможно. По окончании процесса все оставшиеся непомеченными элементы являются простыми импликантами, т.е. получена сокращенная ДНФ.