6 МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ

6.1 Цель занятия

Ознакомление c целями минимизации булевых функций и способами определения сложности их дизъюнктивных и конъюнктивных нормальных форм. Изучение метода минимизирующих карт (диаграмм Карно-Вейча).

6.2 Методические указания по организации самостоятельной работы студентов

6.2.1 При подготовке к практическому занятию необходимо повторить лекционный материал, теоретический материал, представленный в пункте 6.2.2 настоящих методических указаний, соответствующие разделы литературы [1-10] по следующим вопросам:

• основные понятия и определения, используемые при минимизации булевой функции;

• оценка формы булевой функции при помощи индекса (коэффициента) простоты;

• задача минимизации булевых функций в аналитической форме и геометрической форме (задача о покрытии);

• основные подходы для решения задачи минимизации булевых функций в современной теории и практике алгебры логики;

• операции дизъюнктивного и конъюнктивного склеивания и поглощения;

• анализ некоторых аналитических и геометрических методов получения минимальных ДНФ (КНФ) (метод Квайна−Мак-Класки, метод Порецкого-Блейка, метод минимизирующих карт (диаграммы Карно-Вейча), метод многомерных кубов и др.);

• методика использования минимизирующих карт (методика диаграмм Карно и Вейча).

Подготовка и выполнение практического занятия проводится в два этапа.

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

При выполнении первого этапа обучаемый должен предложить и записать индивидуальный пример для каждого из рассмотренных выше понятий и определений.

Второй этап выполнения практического занятия связан с решением практических заданий, представленных в подразделе 6.3 на основе предложенных типовых примеров (см. раздел 6.4).

6.2.2 Основные теоретические положения по изучаемой теме.

6.2.2.1 Основные понятия и определения минимизации булевых функций.

Функция алгебры логики может быть представлена различными формулами (в частности, различными ДНФ и КНФ), а, следовательно, практически может быть реализована различными эквивалентными функциональными схемами.

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

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

Пример. Функция в булевом базисе преобразуется к виду:

.

Если в качестве базиса приняты отрицание и импликация, то функция будет иметь вид .

Для оценки формы булевой функции, которая наиболее предпочтительна для практической реализации, обычно вводится индекс (коэффициент) простоты , где  формула, реализующая функцию, характеризующий «сложность» ДНФ (КНФ). Наиболее часто встречаются следующие виды коэффициентов простоты:

а)  число символов (букв) переменных, встречающихся в записи ДНФ (КНФ);

б)  число элементарных конъюнкций (дизъюнкций), входящих в ;

в)  число символов инверсий, встречающихся в записи ДНФ (КНФ).

Пример. Сравним две формулы и , реализующие одну функцию. Для них: и , следовательно проще, чем ; и , следовательно, проще, чем ; и , следовательно, проще, чем .

Рассмотрим некоторые определения, используемые при минимизации булевых функций.

Определение. Импликантой некоторой функции называется функция , такая, что на всех интерпретациях, на которых равна единице, тоже равна единице.

Минтермы любого ранга, входящие в состав ДНФ функции, являются её импликантами.

Определение. Множество , состоящее из импликант функции , называется покрытием (или полной системой импликант) функции , если каждое единичное значение функции покрывается единицей хотя бы одной импликанты из множества .

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

Всякая элементарная конъюнкция , входящая в состав элементарной конъюнкции и содержащая меньше переменных, чем конъюнкция , называется собственной частью конъюнкции , и говорят, что конъюнкция покрывает конъюнкцию .

Определение. Простой импликантой функции называется такая конъюнкция-импликанта, что никакая её собственная часть не является импликантой данной функции.

Множество всех простых импликант функции составляет покрытие данной функции.

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

Определение. Дизъюнктивным ядром булевой функции называется такое множество её простых импликант, которое образует покрытие , но после удаления импликанты теряет это свойство, то есть перестает быть полной системой импликант.

Определение. Тупиковой ДНФ называется ДНФ данной булевой функции, состоящая только из простых импликант.

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

Определение. Минимальной ДНФ (МДНФ) булевой функции называется одна из её тупиковых ДНФ, которой соответствует наименьшее значение критерия минимизации (индекса простоты) ДНФ.

Пример. Пусть имеется функция , заданная в виде СДНФ:

.

Выполним операции полного склеивания следующим образом:

.

Операцию склеивания можно выполнить другим способом:

.

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

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

Проблема синтеза логических схем в булевом базисе связана с задачей минимизации булевых функций, которая в общем случае имеет две постановки:

• в аналитической форме;

• в геометрической форме (задача о покрытии).

Употребляются два языка: аналитический и геометрический.

Для решения данной задачи в современной теории и практике алгебры логики существуют следующие основные подходы:

• перебор (просмотр) всех возможных ДНФ и КНФ произвольной функции с целью поиска минимальной формы (первый подход);

• упрощение конкретной функции, достигаемое путем различных тождественных преобразований, с целью получения формулы, эквивалентной исходной, но реализуемой проще (второй подход).

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

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

В общем случае минимальные формы булевых функций аналитически получают в такой последовательности:

• получают и анализируют конкретную функцию алгебры логики, определенную для всевозможных наборов значений аргументов;

• полученную функцию представляют через основные операции в любой из двух совершенных нормальных форм (СДНФ или СКНФ);

• находят сокращенную ДНФ (КНФ) (любая функция имеет одну такую форму);

• находят возможные тупиковые ДНФ (КНФ);

• из полученных тупиковых форм выбирают минимальные ДНФ (КНФ).

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

Рассмотрим данные операции, принимая следующие обозначения:  некоторая элементарная конъюнкция переменных;  некоторая элементарная дизъюнкция переменных;  булева переменная.

Операция неполного дизъюнктивного склеивания: .

Операция дизъюнктивного поглощения: .

Выполнение двух указанных операций последовательно представляет собой выполнение операции полного дизъюнктивного склеивания: .

Операция неполного конъюнктивного склеивания: .

Операция конъюнктивного поглощения: .

Операция полного конъюнктивного склеивания: .

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

6.2.2.2 Метод минимизирующих карт (диаграммы Карно-Вейча).

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

Карты Карно (диаграммы Вейча) представляют собой специально организованные таблицы соответствия (истинности). Значения не более двух переменных располагаются в заголовках строк и столбцов карты в таком порядке, что каждый последующий отличается от предыдущего значением только одной из переменных, например, (0, 0), (0, 1), (1, 1), (1, 0). Клетки, расположенные по краям таблицы, считаются соседними и обладают этим свойством.

Каждой конституенте соответствует одна ячейка таблицы. Нуль или единица в ячейке определяет значение функции на данной интерпретации.

При таком расположении минтермы (макстермы), к которым применима операция склеивания, располагаются в соседних ячейках карты, и склеивание производится графически посредством объединения ячеек в группы.

Пример. Карты Карно для функций двух переменных имеют вид таблицы (таблица 6.1), где столбцы соответствуют значениям первой переменной, а строки − значениям второй переменной функции (в ячейках указаны соответствующие минтермы в виде формул с абстрактными переменными).

Таблица 6.1 − Структура карты Карно для двух переменных

	0	1
0
1

Пример. Структура карты Карно для функции трех переменных имеет вид таблицы (в ячейках указаны соответствующие минтермы в виде формул с абстрактными переменными) (см. таблицу 6.2).

Таблица 6.2 − Структура карты Карно для трех переменных

	00	01	11	10
0
1

Для конкретной булевой функции карта Карно заполняется следующим образом. В ячейки, соответствующие интерпретациям, на которых функция равна единице, записывают единицы. Указанные ячейки соответствуют конституентам единицы, присутствующим в СДНФ функции. В остальные ячейки записывают нули.

Пример. Построить карту Карно для функции .

В ячейки таблицы, соответствующие минтермам данной СДНФ, записываем единицы, в остальные ячейки − нули (см. таблицу. 6.3).

Таблица 6.3 − Карта Карно для функции

	00	01	11	10
0	1	0	0	0
1	1	1	1	0

К конституентам единицы, соответствующим любым двум соседним ячейкам, можно применить операцию склеивания, так как они отличаются только одной переменной.

На карте Карно для функции трех переменных каждая ячейка имеет три соседние ячейки, на карте Карно для функции четырех переменных − четыре, на карте Карно для функции пяти переменных − пять и т.д.

При минимизации на множестве ДНФ в склеивании участвуют только ячейки, содержащие единицы. Как правило, в картах Карно нули в ячейках не указывают, оставляя данные ячейки пустыми.

Пример. В таблицах 6.4 и 6.5 приведены карты Карно для трех переменных с отмеченными соседними ячейками для ячеек А и В.

Таблица 6.4 − Карта Карно для функции с отмеченными соседними ячейками для ячейки А

	00	01	11	10
0			А
1

Таблица 6.5 − Карта Карно для функции с отмеченными соседними ячейками для ячейки В

	00	01	11	10
0				В
1