Минимизация булевых функций
![]()
|
Минимизация булевых функций. Совершенные нормальные формы записи логических функций дают однозначное представление логических функций, но иногда являются очень громоздкими. Поэтому для булевых функций, представленных в виде СДНФ или СКНФ, возникает задача минимизации. Индексом простоты (или сложностью) булевой функции называется функция ![]()
Примеры. 1) ![]() ![]() ![]() ![]() ![]() 2) ![]() ![]() 3) ![]() ![]() Пример. Пусть ![]() ![]() Эту функцию можно упростить ![]() Вычислим индексы простоты для ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Следовательно, ![]() ![]() Задача минимизации заданной логической функции сводится к представлению ее дизъюнктивной (или конъюнктивной) нормальной формой, имеющей наименьший индекс простоты. В качестве индекса простоты наиболее часто используется индекс ![]() Пример. ![]() ![]() Построение сокращенной ДНФ методом Блейка. Сокращенной д.н.ф. функции ![]() В основе использования метода Блейка лежат операции склеивания и операции поглощения. Законы поглощения ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Отметим, что формулы во втором столбце получаются из формул первого столбца с помощью принципа двойственности. Закон склеивания (объединения конъюнкций): ![]() Закон обобщенного склеивания: ![]() Пример. Получить сокращенную ДНФ методом Блейка 1) ![]() ![]() Минимизация булевых функций методом Квайна– Мак-Класки. Импликантой ![]() ![]() ![]() 1) Если на некотором наборе ![]() ![]() ![]() 2 При исключении хотя бы одного множителя из ![]() Пример. ![]() ![]() Рассмотрим ![]() ![]() ![]() Если вычеркнуть один множитель из ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Пусть на некотором наборе ![]() ![]() ![]() ![]() ![]() Система импликант функции ![]() ![]() Сокращенной ДНФ функции ![]() Утверждение. Сокращенная ДНФ. функции ![]() Действительно, дизъюнкция всех импликант из полной системы импликант равна 1 на тех наборах, где равна 1 функция ( в соответствии с определением импликанты ![]() ![]() ![]() Сокращенная д.н.ф. функции ![]() Система импликант функции ![]() ![]() Тупиковой ДНФ называется дизъюнкция всех импликант, составляющих приведенную систему. Тупиковая ДНФ- выражение, полученное из сокращенной ДНФ, дальнейшее упрощение которого невозможно в рамках ДНФ. Минимальной ДНФ называется тупиковая ДНФ, состоящая из наименьшего числа букв. Одна и та же сокращенная ДНФ может иметь несколько тупиковых ДНФ и несколько минимальных ДНФ. Процесс минимизации на первом этапе сводится к построению полной системы импликант, затем приведенной системы существенных импликант, из которых строится сокращенная ДНФ, затем строятся тупиковые ДНФ и затем уже выбирается минимальная ДНФ. Решение задачи осуществляется в соответствии со схемой ![]() Получение сокращенной ДНФ (нахождение импликантов функции ![]() Пример 1. ![]() ![]() ![]() Получение сокращенной ДНФ основывается на законе склеивания ![]()
![]() Импликантами функции ![]() ![]() ![]() ![]() ![]() ![]() ![]() Сокращенная ДНФ ![]() ![]() ![]() ![]() На рис. изображены импликанты и склеиваемые наборы переменных. Отметим, что на рисунке номера наборов приведены в восьмеричной системе счисления. 2. Следующий этап – построение тупиковой ДНФ. Для этого нужно составить импликантную таблицу. Строки этой таблицы обозначены импликантами функции, а столбцы минтермами функции. Каждая импликанта является частью какого-нибудь дизъюнктивного члена в СДНФ и обращается в единицу на том же наборе, что и соответствующий минтерм. На пересечении строки, в которой записана импликанта, и столбцов соответствующих минтермов, частью которых является импликанта, поставим крестики. Тупиковые формы являются дизъюнкциями тех импликантов, которые накрывают все минтермы, т.е. в таблице нужно выбрать такие строки, чтобы во всех столбцах был как минимум один плюс. Чтобы построить тупиковую форму, нужно выбрать минимальное число строк, покрывающих крестиками все столбцы. Ясно, что в систему выбранных строк должны обязательно входить строки, содержащие плюсы, которые являются единственными в столбце. Такие строки называются базисными. Простые импликанты, стоящие в базисных строках, образуют ядро рассматриваемой функции. Обведем кружочками плюсы в строках, соответствующих этим импликантам. Из оставшихся импликант выбираем минимальное число таких, которые покрывают крестиками все свободные столбцы (т.е. те, которые не содержат ![]() Импликантная таблица
В тупиковую ДНФ обязательно должна входить ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() На рисунке изображены все тупиковые ДНФ: ![]() Среди всех тупиковых ДНФ выбираем ДНФ наименьшей длины: МДНФ: ![]() ![]() Матричный метод Карно. ![]() Матричный метод основан на некоторых геометрических построениях. Соотношение между двоичными переменными можно представить в наглядной геометрической форме. Рассмотрим логическую функцию двух переменных. Все четыре конъюнкции двух двоичных переменных (члены СДНФ) могут быть изображены на плоскости в виде точек с координатами 00,01,10,11, где первая цифра соответствует переменной ![]() ![]() ![]() Координаты вершин квадрата, выраженные двоичными числами, соответствуют двоичным номерам конъюнкций.: 00 сответствует ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Число 0 соответствует переменной ![]() ![]() ![]() Геометрической моделью функции трех переменных может служить трехмерный куб, вершины которого соответствуют членам СДНФ. Координаты соседних вершин отличаются, как и в случае плоской модели, только одним двоичным знаком, а соответствующие члены только одной переменной. Вследствие этого линии, соединяющие соседние вершины куба можно обозначить двумя переменными, которые на этой линии не меняют свое значение, а грани куба – одной переменной. ![]() Соединение двух соседних вершин линией позволяет исключить одну переменную, причем это исключение можно выполнить, сравнив двоичные обозначения вершин. Например, сравнивая 011 и 111, получим ![]() ![]() Точно также соединение линиями 4 вершин, лежащих на одной грани, позволяет исключить две переменные. Действительно, сравнив 011 с 111 и 001 с 101, получим ![]() ![]() ![]() Вначале была исключена переменная ![]() ![]() В результате осталась одна переменная ![]() Для функции четырех переменных геометрической моделью является четырехмерный куб. Однако изобразить его на плоскости невозможно и использовать для минимизации сложно. Более удобной для минимизации является карта Карно. Карта Карно построена так, что два соседних столбца (строки) отличаются одним знаком. Любая конъюнкция четырех переменных изображается на карте одной клеткой, находящейся на пересечении строки и столбца, обозначения которых образуют двоичный номер конъюнкции. Конъюнкции, соответствующие соседним клеткам, отличаются только одной переменной. Соседними на карте Карно являются не только клетки, находящиеся внутри карты, но и на концах каждой строки и каждого столбца. Любая функция может быть задана на матрице единицами в клетках, соответствующих входящим в СДНФ конъюнкциям – минтермам, и нулями в остальных клетках, которые можно не записывать. Например, функция ![]() ![]() ![]() ![]() В результате минимизации получим функцию ![]() Преобразования, выполненные на карте Карно, соответствуют следующим алгебраическим преобразованиям ![]() Пример. 2. Пусть функция ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() 2.. Пусть функция ![]() ![]() ![]() ![]() ![]() В результате минимизации получится функция ![]() 3.. Пусть функция ![]() ![]() Здесь имеется два четырехклеточных подквадрата. ![]() ![]() В результате получится функция ![]() Эту задачу можно решить иначе, если рассматривать один восьмиклеточный подквадрат ![]() ![]() ![]() Таким образом, задача минимизации сводится к геометрической задаче отыскания правильных конфигураций. При использовании карты Карно нужно стремиться объединить единичные клетки в подквадраты с возможно большим числом клеток, чтобы количество подквадратов было как можно меньше. При решении задачи таким способом могут получиться объединения клеток в одинаковое число подквадратов с одним и тем же числом клеток. Каждый из таких вариантов будет соответствовать одной из минимальных форм функции. ![]() ![]() Карта Карно в этом случае имеет вид ![]() Размещение единиц здесь таково, что их нельзя объединить в подквадраты. В то же время функцию легко минимизировать методом Блейка. ![]() С помощью матрицы Карно можно найти минимальное выражение для функции не только в дизъюнктивной форме, но и в конъюктивной форме. Для этого в карте Карно необходимо выбирать подквадраты из нулей, а не из единиц и помнить о том, что в этом случае 0x, а 1 ![]() Пример. Найти минимальную функцию в к.н.ф, если ![]() Составим ![]() ![]() ![]() ![]() ![]() ![]() Отсюда получим ![]() ![]() ![]() Полученное выражение является минимальной КНФ. Матричный метод является наиболее эффективным при решении задачи минимизации функций четырех переменных. Для большего числа переменных его использовать затруднительно. При пяти и шести переменных приходится прибегать к некоторым преобразованиям функции для того, чтобы в дальнейшем можно было использовать матричный метод. Например, если имеется функция пяти переменных, то можно вынести за одну скобку некоторую переменную, а за вторую скобку ее отрицание. Тогда внутри скобок окажется функция четырех переменных, которую можно минимизировать матричным методом. Пример. ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Минимизация частично определенных булевых функций. В реальных задачах очень часто бывает так, что значение булевой функции на некоторых наборах не определено и может доопределяться произвольно. В этом случае доопределение функции было бы целесообразно производить таким образом, чтобы ее минимальная нормальная форма имела наименьшее число букв из всех возможных вариантов доопределения. Рассмотрим простой пример. Пусть функция задана картой Карно или диаграммой Вейча, представленных соответственно таблицами ![]() Эту функцию можно доопределить на неопределенных наборах единицами или нулями Это приводит к разным минимальным ДНФ. Однако более простая минимальная ДНФ получается, если произвести доопределение так, как это сделано на следующей диаграмме Вейча Алгоритм поиска минимальной ДНФ частично определенной функции ![]() 1) Найти любым известным способом сокращенную ДНФ функции, получающейся доопределением единицами исходной функции ![]() 2) Выбрать минимальную ДНФ по импликантной матрице, где в столбцах выписаны лишь те минтермы (конституенты единицы) функции ![]() Аналогичный алгоритм (с доопределением нулевыми наборами) может быть предложен для поиска КНФ. При этом доопределение таблицы значений функции ![]() ![]() |