Тема 6 Минимизация булевых функций
Цель данного раздела – изложение основных методов построения минимальных дизъюнктивно нормальных форм.
6.1 Сокращенная и тупиковая ДНФ. В разделе 3 было показано, что любая булева функция может быть представлена дизъюнктивной нормальной формой. Следует отметить, что дизъюнктивная нормальная форма часто допускает упрощение. При этом путем различных тождественных преобразований получится дизъюнктивная нормальная форма, эквивалентная исходной, но содержащая меньшее число вхождений символов.
Дизъюнктивная нормальная форма называется Минимальной, если она включает минимальное число символов по сравнению со всеми другими эквивалентами ей дизъюнктивными нормальными формами.
Заметим, что если некоторый символ в формуле, скажем , встречается, например, два раза, то при подсчете числа символов в формуле он учитывается два раза.
Основной вопрос данного параграфа – это как для произвольной булевой функции построить ей минимальную дизъюнктивную нормальную форму. Эта задача называется Проблемой минимизации булевых функций.
Существует тривиальный алгоритм построения минимальной ДНФ для произвольной булевой функции . Для этого все ДНФ, составленные из символов упорядочиваются по числу букв и по порядку для каждой ДНФ Д проверяется соотношение . Первая по порядку ДНФ, для которой это соотношение выполняется, есть, очевидно, минимальная ДНФ функции .
Число различных ДНФ, составленных из переменных , равно .
Прежде чем доказать данное утверждение, приведем следующее определение.
Конъюнкция называется Элементарной, если при .
Число R называется Рангом элементарной конъюнкции. В случае r=0 конъюнкция называется Пустой и Полагается равной 1.
Так как каждая из N переменных либо не входит в элементарную, либо входят в нее с отрицанием, либо без отрицания, то число элементарных конъюнкций, составленных из равно . Ясно, что число различных ДНФ, составленных из переменной , равно числу подмножеств множества, из элементов, т. е. .
Рассмотрим геометрическую интерпретацию задачи минимизации булевых функций.
Обозначим через множество всех точек , где . Ясно, что — множество всех вершин единичного n-мерного куба.
Сопоставим каждой булевой функции Подмножество Из , определенное следующим образом:
Вершин трехмерного единичного куба
Данное соответствие является взаимно однозначным и обладает следующими свойствами:
1) булевой функции Соответствует подмножество ;
2) булевой функции соответствует подмножество ;
3) булевой функции соответствует подмножество .
Докажем утверждение 2. Пусть
А это значит, что .
Пусть ДНФ, где — элементарные конъюнкции. Подмножество называется интервалом R-го ранга, если оно соответствует элементарной конъюнкции К R-го ранга. Как показано выше, . Итак, с каждой ДНФ функции F связано покрытие такими интервалами , что .
Пусть — ранг интервала . Тогда совпадает с числом букв в ДНФ функции .
Теперь ясно, что задача построения минимальной ДНФ сводится к отысканию такого покрытия подмножества интервалами , чтобы число было наименьшим.
Интервал , содержащий , называется Максимальным для булевой функции, если не существует интервала , такого, что .
Заметим, что соотношение выполняется тогда и только тогда, когда элементарная конъюнкция получается из элементарной конъюнкции К путем вычеркивания непустого числа сомножителей.
Очевидно, что каждый интервал из содержится в некотором максимальном интервале. Если — список всех максимальных интервалов подмножества , то нетрудно видеть, что .
ДНФ булевой функции f, соответствующая покрытию подмножества всеми максимальными интервалами, называется Сокращенной ДНФ функции F.
Ясно, что сокращенная ДНФ для любой булевой функции f определяется однозначно.
Пример 1. Пусть . Обозначим , , . Найдем соответствующие этим конъюнкциям интервалы , , .
Изобразим эти интервалы
Очевидно, что и — все максимальные интервалы. Интервал не является максимальным, ибо . Следовательно, покрытию подмножества соответствует сокращенная ДНФ функции , равная .
Данный геометрический подход дает и метод построения сокращенной ДНФ.
Теперь рассмотрим аналитический метод построения сокращенной ДНФ – метод Блейка. Этот метод основан на следующей теореме.
Теорема 1. Если в произвольной ДНФ булевой функции F произвести все возможные обобщения склеивания и устранить затем все элементарные поглощения, то в результате получиться сокращенная ДНФ функции F.
Следовательно, чтобы найти сокращенную ДНФ, надо к произвольной ДНФ данной функции применить правило обобщенного склеивания до тех пор, пока это возможно, а затем правило поглощения.
Пример 2. Найти сокращенную ДНФ для функции . Применяя правило обобщенного склеивания, получаем: .
Затем правило поглощения и находим сокращенную ДНФ: .
Рассмотрим еще один метод построения сокращенной ДНФ – метод Нельсона. Этот метод основан на следующей теореме.
Теорема 2. Если в произвольной КНФ булевой функции раскрыть все скобки в соответствии с дистрибутивным законом и устранить все элементарные поглощения, то в результате получится сокращенная ДНФ этой функции.
Пример 3. Найти сокращенную ДНФ для функции
После раскрытия скобок с помощью дистрибутивного закона, получаем:
Так как , , то имеем:
Далее, применяя правило поглощения, получаем сокращенную ДНФ:
Рассмотрим табличный метод построения сокращенной ДНФ. Этот метод основан на составлении прямоугольной таблицы (минимизирующей карты).
Минимизирующие карты для булевых функций от трех и от четырех переменных изображены на следующих таблицах.
X1 X2
Объединяя соседние клетки, соответствующие единичным значениям булевой функции f в максимальные интервалы, и сопоставляя им элементарные конъюнкции, получим сокращенную ДНФ. Отметим, что клетки, расположенные по краям таблицы, также считаются соседними. Покажем работу этого метода на следующем примере.
Пример 4. Найти сокращенную ДНФ для функции, заданной следующей таблицей.
X1 X2
В данной таблице объединены клетки в максимальные интервалы
Этим интервалам соответствуют элементарные конъюнкции
Следовательно, сокращенная ДНФ для данной функции имеет вид:
Построение сокращенной ДНФ есть только первый этап решения задачи минимизации булевой функции. В общем случае сокращенная ДНФ не является минимальной. Следующая теорема устанавливает связь между минимальной и сокращенной ДНФ.
Теорема 3. Минимальная ДНФ булевой функции получается из сокращенной ДНФ данной функции путем удаления некоторых элементарных конъюнкций.
Доказательство этого утверждения следует из того факта, что покрытие подмножества , отвечающее минимальной ДНФ, состоит только из максимальных интервалов. Действительно, если бы покрытие содержало не максимальный интервал, то его можно было бы заменить объемлющим максимальным интервалом. В результате этого сумма рангов интервалов данного покрытия уменьшилась бы, что противоречит предположению о минимальности ДНФ.
Покажем, что в классе монотонных функций понятия минимальной и сокращенной ДНФ совпадают.
Теорема 4. Сокращенная ДНФ монотонной булевой функции не содержит отрицаний переменных и является минимальной ДНФ этой функции.
Пусть К – элементарная конъюнкция, входящая в сокращенную ДНФ. Предположим, что К содержит отрицание переменных. Обозначим через произведение всех переменных, входящих в К без отрицания. Пусть – набор переменных, в которых всем переменным, входящим в , приписано значение 1, а всем остальным – значение 0. Ясно, что при этом наборе значение функции Равно 1. Элементарная конъюнкция обращается в 1 при всех наборах . Очевидно, что при этих наборах значение функции также равно 1. Следовательно, .
Получили противоречие с максимальностью интервала . Итак, сокращенная ДНФ булевой функции Не содержит отрицаний переменных.
Пусть — любая элементарная конъюнкция из сокращенной ДНФ. Конъюнкция К является единственной конъюнкцией сокращенной ДНФ, которая обращается в единицу в вершине с координатами . Действительно, если бы в сокращенной ДНФ какая-нибудь другая элементарная конъюнкция обращалась в этой вершине в 1, то не содержала бы, во-первых, букв , и, во-вторых, букв . Поэтому в конъюнкцию могли бы входить лишь буквы , причем не все. Но тогда . Получили противоречие с максимальностью интервала . Следовательно, для любого максимального интервала существует вершина куба , которая покрывается только этим интервалом. Поэтому из покрытия соответствующего сокращенной ДНФ, нельзя удалить ни одного из интервалов. Теперь, применяя предыдущую теорему, получаем требуемый результат.
Следует отметить, что сокращенная ДНФ в большинстве случаев допускает дальнейшие упрощения за счет того, что некоторые элементарные конъюнкции могут поглощаться дизъюнкциями других элементарных конъюнкций. Действительно, в сокращенной ДНФ
Элементарная конъюнкция поглощается дизъюнкцией остальных элементарных конъюнкций, т. е. .
Ввиду этого введем следующее определение.
Покрытие области истинности булевой функции максимальными интервалами называется Неприводимым, если после удаления из него любого интервала оно перестает быть покрытием. ДНФ булевой функции , соответствующая неприводимому покрытию, называется Тупиковой.
Теорема 5. Всякая минимальная ДНФ является тупиковой.
Доказательство этого утверждения следует из того, что покрытие, соответствующее минимальной ДНФ, является неприводимым.
Заметим, что булева функция может обладать несколькими различными минимальными ДНФ. Существуют также тупиковые ДНФ, не являющиеся минимальными ДНФ. Соответствующие примеры будут разобраны ниже.
Из того, что минимальная ДНФ является тупиковой, следует общая схема решения задачи минимизации булевых функций.
1. Выделяются все максимальные интервалы, и строится сокращенная ДНФ.
2. Строятся все тупиковые ДНФ.
3. Среди всех тупиковых ДНФ выделяются все минимальные ДНФ.
Рассмотрим алгоритм построения всех тупиковых ДНФ. Суть данного алгоритма состоит в следующем:
1) для булевой функции строим сокращенную ДНФ;
2) для каждой вершины из выделяем в сокращенной ДНФ функции F все такие элементарные конъюнкции , что ;
3) составляем выражение вида
4) применяем к выражению вида (*) законы дистрибутивности и поглощения. В результате получаем .
Тупиковая ДНФ. ДНФ Квайна
Построение сокращенной ДНФ является первым шагом в процессе получения минимальной ДНФ. Следующий шаг минимизации – это построение, так называемых, тупиковых ДНФ.
Дадим определение тупиковой ДНФ:
Покрытие множества Nf максимальными гранями называется неприводимым, если совокупность этих граней, получающаяся из исходной путем выбрасывания какой-либо грани, не будет уже покрытием Nf .
ДНФ, которая соответствует неприводимому покрытию, называется тупиковой ДНФ.
Минимальная ДНФ содержится среди тупиковых.
Тупиковые ДНФ получаются путем выбрасывания из сокращенной ДНФ некоторых простых импликант.
Существуют алгоритмы, при помощи которых получаются единственные для данной функции тупиковые ДНФ. К таким тупиковым ДНФ относится ДНФ Квайна.
Введем сопутствующие понятия.
Ядровая грань: максимальная грань называется ядровой, если ей принадлежит вершина, принадлежащая покрытию Nf только этой грани и не принадлежащая никакой другой максимальной грани.
Множество всех ядровых граней покрытия Nf , называется ядром Nf .
Теперь познакомимся с определением ДНФ Квайна:
ДНФ, которую получают путем выбрасывания всех простых импликант, соответствующих максимальным граням, которые покрываются ядром, называется ДНФ Квайна.
Алгоритм построения ДНФ Квайна:
1. получить сокращенную ДНФ;
2. найти ядровые грани;
3. удалить импликанты, покрываемые ядром.
Полученная ДНФ, является ДНФ Квайна.
В предыдущем примере Nk3 – не является ядровой гранью, т.к. каждая вершина принадлежит другим граням. Тогда сокращенную ДНФ можно еще раз минимизировать, выбросив конъюнкцию , получим ДНФ Квайна : .
Оставшиеся грани Nk1 и Nk2 покрывают Nf . Продемонстрируем это на рисунке:
Отметим справедливость следующего утверждения:
Для любой не тождественно ложной функции существует единственная ДНФ Квайна.
Задачи для самостоятельного решения.
1. Минимизировать функцию, принимающую значение 1, если большинство переменных равны 1, методом минимизирующих карт.
2. Для формулы составить множество Nf и изобразить его вершинами куба. Минимизировать методом Карно. Составить сокращенную ДНФ. Определить ядровые грани. Составить ДНФ Квайна.
3. Графически представлено нольмерное покрытие множества Nf . Составить СДНФ и СКНФ. Составить покрытие ядровыми гранями и записать соответствующую ДНФ Квайна. По данному рисунку составить карту Карно и минимизировать функцию. Сравнить результаты.
4. Дана функция f(00101110). Составить множество Nf и изобразить его графически.
5. Для функции из задания 4 составить СКНФ и сокращенную ДНФ. Изобразить сокращенную ДНФ. Найти ядровые грани и построить ДНФ Квайна.
6. Функция представлена картой Карно. Построить минимальную ДНФ с помощью этой карты.
7. Дана функция от четырех переменных f(2,3,6,7,11,13,14,15)=1. Минимизировать ее методом Квайна и методом Карно.
1. Определение минимальной ДНФ.
2. Что собой представляет минимизирующая карта?
3. Сформулировать утверждение, которое используется в методе минимизирующих карт.
4. Алгоритм построения минимальной ДНФ с помощью минимизирующей карты.
5. Этапы минимизации СДНФ при применении метода Квайна.
6. Что представляет собой карта Карно?
7. Сколько ячеек можно включать в контуры и почему?
8. Что представляет собой единичный n-мерный куб?
9. Какие наборы входят в множество Nf ?
10. Что называется (n-r)- мерной гранью? Как определяется ранг конъюнкции и ранг ДНФ?
11. Задача минимизации в геометрической форме.
12. Какая грань называется максимальной? Что такое простая импликанта? Какая ДНФ называется сокращенной?
13. Методика построения сокращенной ДНФ.
14. Какое покрытие называется неприводимым? Какие ДНФ называются тупиковыми?
Минимизация переключательных функций
- Операция попарного неполного склеивания:
- Операция элементарного поглощения:
Теорема. Если в СДНФ какой-либо переключательной функции выполнить все возможные операции неполного попарного склеивания и элементарного поглощения, то в результате получится СкДНФ(сокращенная дизъюнктивная нормальная форма), эквивалентная исходной функции.
Итерационый алгоритм. Задача в нахождении по полной системе импликант (конституэнт единицы) полной системы простых импликант.
- Исходным является множество конституэнт единицы функции — импликанты нулевого ранга.
- Выполняются все возможные операции неполного попарного склеивания для элементарных конъюнкций длины n. (где n-кол-во аргументов).
- подмножество элементарных конъюнкций длины n (оставшиеся)
- подмножество элементарных конъюнкций длины n-1
Алгоритм завершается, когда подмножество является пустым, либо нельзя выполнить ни одной операции неполного попарного склеивания.
Таким образом, получаем систему простых импликант функции.
Нахождение тупиковых ДНФ
Стратегическая задача нахождения приведенной системы простых импликант заключается в нахождении наилучших покрытий единиц функции простыми импликантами.
Для системы простых импликант для заданной функции может быть получено несколько приведенных систем. Следует считать, что среди них есть такая, которая дает тупиковую нормальную форму минимальной длины.
Находятся такие единицы функции, которые покрываются только какой-то одной импликантой из системы простых импликант (для каждой единицы считаем сколько ее покрывает импликант и отмечаем их).
Повторяем шаг 1 и шаг 2 для оставшихся множеств (находится псевдоядро). Но перед повторением должен быть дополнительный шаг, который уменьшает перебор. (выкидываем из тех, которые покрывают одни и те же единицы(из оставшихся) ту импликанту, которая имеет наибольшую длину)
И так далее до тех пор, пока не будут покрыты все единицы функции.
Велика вероятность, что на каком-то шаге не найдется ни одной единицы функции, которая покрывается одной импликантой. В этом случае ищется наилучшее (наименьшей длины) покрытие оставшихся единиц функции методом перебора:
- Пусть A входит в ТДНФ, а B,C. нет.
- Пусть В входит в ТДНФ, а A,C. нет.
- Пусть C входит в ТДНФ, а A,B. нет.
- .
Пример минимизации переключательной функции методом Квайна
Функция задана вектором: 883F . Запишем 16-ричное число 883F в двоичной виде в столбец значений функции таблицы истинности.
Цена ДНФ является суммой длин всех входящих в нее конъюнкций.
Минимизация функции методом Квайна.
В результате на данном шаге получаем простые импликанты: 
, 
СкДНФ: 
v v v
Нахождение тупиковых форм.
- Единицы ДНФ, покрываемые импликантами СкДНФ, обозначаются «+».Импликанты, попадающие в ядро помечаются «*».
- Единицы функции, которые покрываются только какой-то одной импликантой из системы простых импликант, помечаются “>”.
- Единицы функции, покрываемые ядром, но не покрываемые только какой-то одной импликантой из системы простых импликант, помечаются “>>”.
МДНФ: v v , цена=7
Графический метод минимизации — Карты Карно
Карты Карно рассматриваются как перестроенная соответствующим образом таблица истинности функции.
Карты Карно — определенная плоская развертка n-мерного булева куба.
Строится таблица истинности функции определенным образом. Каждая клетка таблицы соответствует вполне определенной вершине булева куба. Нулевые значения не записываются.
Карта Карно для функции 4-х переменных:
Карта Карно рассматривается как поверхность фигуры под названием тор («бублик»).
p-клетки — клетки карты Карно, соответствующие единичному значению функции.
Соседние наборы — наборы, которые различаются только одним аргументом (одной орбитой).
Любой паре соседних наборов в Карте Карно соответствуют соседние клетки.
Две соседние p-клетки на карте Карно дают импликанту первого ранга. Например, клетки 1100 и 1101 отличаются только значением переменной x3, следовательно, они дают импликанту 124.
Две соседние импликанты первого ранга образуют импликанту второго ранга.
На этой карте соседние клетки образуют импликанты a,b,c,d,e. При этом импликанты a и b являются соседними, поэтому они образуют импликанту второго ранга.
Если функция имеет 5 переменных, то рисуются 2 Карты Карно: для x5=0 и для x5=1. Если 6 переменных — 4 Карты, так чтобы в соседних картах соседние клетки имели одинаковые координаты:
Соседние p-клетки, соответствующие импликанте образуют компактную группу.
Количество p-клеток в компактной группе является степенью двойки.
Задача минимизации переключательной функции с помощью карт Карно заключается в нахождении импликант высшего ранга (соответствующих компактным группам наибольшей размерности), покрывающих p-клетки функции наилучшим образом.
Если на картах Карно выделить все компактные группы наибольшей размерности, то дизъюнкция соответствующих конъюнкций даст СкДНФ.
Пример минимизации функции 4-х переменных методом Карт Карно
Нахождение тупиковых форм.
Машинно-ориентированные методы минимизации переключательных функций.
Основаны на применении соответствующих алгебр(или соответствующих алгебраический преобразований).
Вопрос 1. Интервальная форма задания функции. Постановка задачи минимизации.
Геометрический представление: (отображение функции на n-мерный булев куб) Любому набору значений аргументов соответствует элементарная конъюнкция, содержащая все эти переменные — конституента единицы.
Те вершины n-мерного булева куба, в которых функция принимает единичное значение называются 0-кубами.
Два 0-куба образуют 1-куб, если соответствующие булевы вектора(их координаты) отличаются между собой значением только одной координаты(или одной компоненты). Эти координаты носят название свободной координаты. Обозначение x, остальные координаты 0-куба называются связанными и имеют либо 1, либо 0 значение. 0-кубы, образующие 1-куб называются его гранями. Два 1-куба образуют 2-куб, если свободная координата у них одинакова и они различаются значением только одной связанной компоненты.( 1-кубы — грани соответствующего 2-куба).
И так далее до n-куба( в случае тавтологии).
В общем случае, r-куб-это такой куб в булевом пространстве, у которого r свободных компонент и n-r связанных компонент.
Пример:
(1x1xx1) — 3-куб
(1x1x01),(1x1x11)- два 2-куба. Они являются гранями этого 3-куба(образуют его).
Если для какой-то функции взять все возможные кубы одинаковой размерности, то получаем множество кубов(или комплекс кубов).
K r (f) — комплекс r-кубов функции f/
Для некоторой функции всегда есть комплекс
(Если K n (f) содержит куб, то f — константа 1
Подмножество вершин булева куба, соответствующие кубу размерности r называется интервалом булева пространства ранга r. (интервал 1 ранга — 1×1, интервал 2 ранга — x1x)
Для нашего примера:
K 0 (f)=<101,110,111,010,011>
K 1 (f)=<01x,11x,1x1,x11,x10>
K 2 (f)=
В общем случае комплекс кубов определенного ранга не является покрытием исходной функции(за исключением K 0 ).
В нашем примере K 2 не является покрытием, хотя K 1 — покрытие. K(f)=K 0 ∪K 1 ∪K 2 — для нашей функции
Куб большей размерности покрывает кубы меньшей размерности, если они могут быть получены из него последовательным применением оператора граней.
(x1x) имеет грани (01x) и (11x), которые имеют грани : (010),(011) и (110),(111)
Если взять интервал булева пространства, то аналитически его можно описать в виде соответствующих элементарных конъюнкций.
Некоторый комплекс кубов — L, таких, что каждая вершина из комплекса K 0 (f) включена по крайней мер в один из кубов комплекса L, называется покрытием комплекса K функции f.
Каждое покрытие комплекса K(f) определяет некоторую ДНФ переключательной функции.
Не учитывается инверсия аргументов на нулевом уровне.
Минимизация
Цена r-куба: c=n-r — число связанных переменных, количество символов в элементарной конъюнкции(совпадает с ценой в смысле Квайне)
—цена покрытия, где qr-количество кубов размерности r в покрытии L. 
-вторая функция цены покрытия(учитывает число кубов)
Задача минимизации: Найти такое покрытие L комплекса K(f), цена которого будет минимальна — минимизация в смысле Квайне.
Задача решается алгебраически, вводится свой математический аппарат. Это аппарат исчисления кубических комплексов (задает операции над кубами).
Каждая операция проходит в два этапа:
I Этап. Предварительное вычисление путем покоординатной обработки кубов по правилам, задаваемым с помощью таблиц покоординатной обработки.
II Этап. Окончательный.
Операция вычитания кубов удаляет из куба a общую часть кубов уменьшаемого и вычитаемого (т.е. пересечение кубов a и b).
В результате вычитания можем иметь несколько кубов.
Если куб a входит в куб b, то результат — ∅
Пример:
a#b = (1×1)#(x11) = (z0z) = (101)
c#b = (1xx)#(x11) = (z00) =
Нахождение множества простых импликант
K(f)=K 0 ∪K 1 ∪. ∪K i ∪. ∪K n-1 — комплекс K функции f
z⊆K является простой импликантой этого комплекса, если δi(z)=∅ (δi — оператор сограней), то есть не существует какого-либо другого куба, который бы включал в себя исходный куб z.
Z(f)=
Необходимо получить весь комплекс K функции f, используя операторы граней и сограней.
Берем куб z из K и проверяем, есть ли какой-то куб, гранью которого является рассматриваемый.
Операция *(«звездочка») позволяет получить множество Z — кубов, соответствующих простым импликантам функции.
Алгоритм (*) — нахождение множества кубов, соответствующих простым импликантам функции.
- Ĉ0(f) — неупорядоченное покрытие
причем одна и та же единица функции может покрываться несколькими кубами - C0 = Ĉ0 —
(тоже, что и поглощение в методе Квайне) - C0*C0попарно
- в результате 3) находится множество 0-кубов:
C1(f) и т.д. в общем случае покрытием функции не являются
Алгоритм заканчивается, когда на каком-то шаге получаем множество C, содержащее один куб.
Результат — множество Z — множество простых импликант.
Z = ∪Zi
Алгоритм извлечения
- Является покрытием исходного множества кубов функции;
- С минимальной ценой покрытия, если покрытий несколько.
Для решения этой задачи исходные данные фактически — исходный комплекс функции, то есть некоторый исходный комплекс K 0 (f) и Z(f).
Определение: возьмем некоторую вершину d∈K0. Говорят, что эта вершина является обособленной вершиной комплекса на множестве простых импликант Z, если существует такой куб z∈Z, что вершина d накрывается только этой импликантой z.
Такая импликанта будет простая. Вершина d называется различающей. А импликанта получила название экстремаль.
Любое минимальное покрытие содержит экстремали нулевого ранга.
Пример:
Различающие вершины: (0;0;1) и (0;1;0)
E0=< a, d>, осталось покрыть одну вершину — (1;1;1)
Задача минимизации: необходимо найти все обособленные вершины и выделить импликанты, накрывающие эти обособленные вершины.
Такие импликанты образуют множество экстремалей.
Задача решается, если известно K 0 (f), то есть все вершины.
Некоторая простая импликанта e∈Z является экстремалью, если e∩K ≠ e∩U'(e,Z)∩K, а e∩K ≠ ∅,
U'(e,Z) = U(e,Z) — e,
U(e,Z) = < z | z∈Z, Z∩e ≠ ∅>.
Z — множество простых импликант,
U(e,Z) — окрестность куба e, т.е. все простые импликанты из Z, которые имеют общие части с импликантой e.
U'(e,Z) — окрестность без самой импликанты.
Функция может быть не полностью определена:
L — комплекс, где функция определена и равна 1,
D — комплекс, где значение функции не определено,
Если из простой импликанты e удалить все подкубы (Z-e), и остается, по крайней мере, одна вершина булева куба, которая содержится в исходном комплексе функции, то оставшиеся вершины является выделенными, или отмеченными.
Нахождение множества экстремалей
- Каждая простая импликанта проверяется на наличие в ней выделенной вершины, т.е. вычисляется e#(Z-e), если результат вычитания кубов не пустой, то такая импликанта может быть экстремалью.
Если результат пересечения не пустой, значит в L (комплексе единичных значений) имеются обособленные вершины, а e является экстремалью.
Операция, которая позволяет сократить в последующем перебор и исключить из 
i не максимальные кубы — упорядочивание.
- L = ∅ => покрытие единственное
E = ∪Ei - L ≠ ∅ Если проверка на экстремальность не дает результата, т.е. ни одна простая импликанта не содержит квазеопорных вершин, а операция упорядочивания не дает результата.
Пример:
В этом случае не остается никакого другого варианта решения, кроме волюнтаристского.
простая импликанта входит в минимальное покрытие
Все вычисления в ручном варианте сводятся к вычислениям над таблицами.
Минимизация функции методом кубических покрытий.
Рассмотрим комплекс кубов К(f) = L D, где L – множество единичных наборов, D – множество наборов, на которых ДНФ не определена.
Нахождение тупиковых форм.
Содержание
- Постановка задачи
- Решение задачи
- Анализ переключательной функции
- Метод Квайна
- Карты Карно
- Кубические покрытия
1. Постановка задачи
Минимизировать переключательную функцию шести аргументов. Функция задана в виде наборов, на которых значения функции равны единице либо не определены. Наборы задаются в шестнадцатеричной системе счисления. В скобках заданы наборы, на которых значение функции не определено:
y => (2) v (3B) v (20) v (21) v (1D) v (6) v (1B) v (D) v (24) v (2C) v (23) v (B) v 36 v 1C v 3A v 7 v A v 8 v 10 v 38 v 12 v 15 v 5 v 1F v 3F v 1A v 17 v 3E v 3D v 39 v 9 v 37 v 19 v 2A v 11 v 18 v 4 v 3C v 2E v 29 v 0 v 2D v 28 v 25 v 14 v 1E
Необходимо выполнить следующие задачи:
- Доопределить функцию нулями, минимизировать полученную функцию методом Квайна;
- Доопределить функцию единицами и произвести минимизацию, используя карты Карно;
- Минимизировать исходную функцию методом кубических покрытий;
- Проанализировать полученные результаты;
2. Решение задачи
2.1 Анализ переключательной функции
Представим исходную последовательность в виде таблицы истинности.
(2) v (3B) v (20) v (21) v (1D) v (6) v (1B) v (D) v (24) v (2C) v (23) v (B) v 36 v 1C v 3A v 7 v A v 8 v 10 v 38 v 12 v 15 v 5 v 1F v 3F v 1A v 17 v 3E v 3D v 39 v 9 v 37 v 19 v 2A v 11 v 18 v 4 v 3C v 2E v 29 v 0 v 2D v 28 v 25 v 14 v 1E
Таблица истинности исходной функции
Набор Значение исходной функции Набор Значение исходной функции x 1 x 2 x 3 x 4 x 5 x 6 x 1 x 2 x 3 x 4 x 5 x 6 000000 1 100000 ? 000001 0 100001 ? 000010 ? 100010 0 000011 0 100011 ? 000100 1 100100 ? 000101 1 100101 1 000110 ? 100110 0 000111 1 100111 0 001000 1 101000 1 001001 1 101001 1 001010 1 101010 1 001011 ? 101011 0 001100 0 101100 ? 001101 ? 101101 1 001110 0 101110 1 001111 0 101111 0 010000 1 110000 0 010001 1 110001 0 010010 1 110010 0 010011 0 110011 0 010100 1 110100 0 010101 1 110101 0 010110 0 110110 1 010111 1 110111 1 011000 1 111000 1 011001 1 111001 1 011010 1 111010 1 011011 ? 111011 ? 011100 1 111100 1 011101 ? 111101 1 011110 1 111110 1 011111 1 111111 1 ‘?’ обозначено значение наборов, на которых функция не определена.
Цена ДНФ является суммой длин всех входящих в нее конъюнкций.
2.2 Минимизация функции методом Квайна.
Доопределим функцию нулями, получим конституэнты единицы, затем выполним операции попарного неполного склеивания и элементарного поглощения.
На данном шаге все импликанты участвовали в операциях попарного неполного склеивания и были поглощены своими собственными частями. Поэтому простые импликанты на этом шаге не получены.
В результате на данном шаге получаем простые импликанты:
x 2 x 3 x 4 x 5 x 6 , x 1 x 2 x 4 x 5 x 6В результате на данном шаге получаем простые импликанты:
x 3 x 4 x 5 , x 3 x 4 x 6 , x 2 x 3 x 6Нахождение тупиковых форм.
- Единицы ДНФ, покрываемые импликантами СкДНФ, обозначаются «+».Импликанты, попадающие в ядро помечаются «*».
- Единицы функции, которые покрываются только какой-то одной импликантой из системы простых импликант, помечаются “>”.
- Единицы функции, покрываемые ядром, но не покрываемые только какой-то одной импликантой из системы простых импликант, помечаются “>>”.
2.3 Минимизация функции методом Карт Карно.
Дополним функцию единицами и построим Карты Карно.
Нахождение тупиковых форм.
2.4 Минимизация функции методом кубических покрытий.
Рассмотрим комплекс кубов К(f) = L D, где L – множество единичных наборов, D – множество наборов, на которых ДНФ не определена.
Будем выполнять операцию «*» для получения множества простых импликант.
Нахождение тупиковых форм.
E:
11x11x
0xx0x0
01xx0x
1x1xx0
x11xxx
0x01x1
xx1x01
x0010x
МДНФ: x 1 x 2 x 4 x 5 v x 1 x 4 x 6 v x 1 x 2 x 5 v x 1 x 3 x 6 v x 2 x 3 v x 1 x 3 x 4 x 6 v x 3 x 5 x 6 v x 2 x 3 x 4 x 5 , цена=26
3. Анализ полученных результатов
Результат метода Кубических покрытий
f3 = x 1 x 2 x 4 x 5 v x 1 x 4 x 6 v x 1 x 2 x 5 v x 1 x 3 x 6 v x 2 x 3 v x 1 x 3 x 4 x 6 v x 3 x 5 x 6 v x 2 x 3 x 4 x 5 , цена=26Общая таблица истинности
Набор Исходная После Квайна После Карно После Кубических покрытий x 1 x 2 x 3 x 4 x 5 x 6 f0 f1 f2 f3 000000 1 1 1 1 000001 0 0 0 0 000010 ? 0 1 1 000011 0 0 0 0 000100 1 1 1 1 000101 1 1 1 1 000110 ? 0 1 0 000111 1 1 1 1 001000 1 1 1 1 001001 1 1 1 1 001010 1 1 1 1 001011 ? 0 1 0 001100 0 0 0 0 001101 ? 0 1 1 001110 0 0 0 0 001111 0 0 0 0 010000 1 1 1 1 010001 1 1 1 1 010010 1 1 1 1 010011 0 0 0 0 010100 1 1 1 1 010101 1 1 1 1 010110 0 0 0 0 010111 1 1 1 1 011000 1 1 1 1 011001 1 1 1 1 011010 1 1 1 1 011011 ? 0 1 1 011100 1 1 1 1 011101 ? 0 1 1 011110 1 1 1 1 011111 1 1 1 1 100000 ? 0 1 0 100001 ? 0 1 0 100010 0 0 0 0 100011 ? 0 1 0 100100 ? 0 1 1 100101 1 1 1 1 100110 0 0 0 0 100111 0 0 0 0 101000 1 1 1 1 101001 1 1 1 1 101010 1 1 1 1 101011 0 0 0 0 101100 ? 0 1 1 101101 1 1 1 1 101110 1 1 1 1 101111 0 0 0 0 110000 0 0 0 0 110001 0 0 0 0 110010 0 0 0 0 110011 0 0 0 0 110100 0 0 0 0 110101 0 0 0 0 110110 1 1 1 1 110111 1 1 1 1 111000 1 1 1 1 111001 1 1 1 1 111010 1 1 1 1 111011 ? 0 1 1 111100 1 1 1 1 111101 1 1 1 1 111110 1 1 1 1 111111 1 1 1 1 АНАЛИЗ
По таблице истинности видно, что минимизация функции проведена верно.
В результате минимизации получили минимальные дизъюнктивные нормальные формы:
- Доопределив функцию нулями, методом Квайна получили МДНФ цены 46
- Доопределив функцию единицами, методом карт Карно получили МДНФ цены 37
- Доопределяя функцию по ходу выполнения алгоритма, методом кубических покрытий получили МДНФ цены 26
Метод кубических покрытий приводит к наименьшей МДНФ. Это связано с тем, что минимизируется не полностью определенная функция. В результате минимальная форма принимает на наборах, на которых исходная функция не определена, такие значения, которые соответствуют наиболее оптимальному покрытию. Из всех методов наиболее трудоемким оказывается также метод кубических покрытий, но он удобен для программной реализации минимизации. Наименее трудоемким оказался метод Квайне.