Методы минимизации логических функций

СДНФ, собранная по этой таблице выглядит следующим образом:

Конечное выражение достигается  за счёт повторного использования операций склеивания и поглощения:

Члены этого выражения  являются простыми импликантами выражения. Переход от сокращённой формы к минимальной осуществляется с помощью импликантной матрицы.

Члены СДНФ заданной функции вписываются в столбцы, а в строки — простые импликанты, то есть члены сокращённой формы. Отмечаются столбцы членов СДНФ, которые поглощаются отдельными простыми импликантами. В следующей таблице простая импликанта   поглощает члены   и   (в первом и во втором столбцах поставлены крестики).

Импликантная  матрица

Простая импликанта

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

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

Минимальная дизъюнктивная  нормальная форма (МДНФ) заданной функции:

Структурная схема, соответствующая  выражению в МДНФ (второй этап) при  минимизации функции методом  Квайна

       (а)

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

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

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

• при  ,  , 

;

• при  ,  , 

;

Использование метода для  получения минимальной КНФ

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

для минимизации берётся  не СДНФ, а СКНФ функции;

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

 

 

 

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

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

Пример:

Минимизируем функцию четырёх  переменных F (a, b, c, d), заданную таблицей истинности.

1. Сгруппируем минтермы по количеству  единиц в них:

2. Произведём первое объединение  строк каждых предыдущих и  последующих групп:

3. Объединим строки с совпадающими  позициями

"крестиков":

4. Из двух строк с одинаковыми  значениями переменных оставляем  только одну (любую):

5. Обратим внимание на то, что  первый минтерм избыточен, так  как 0-я и 4-я строки уже  вошли в комбинацию со 2-ой и  6-ой (второй минтерм), а 1-я и  5-я - с -

9-ой и 13-ой соответственно (третий  минтерм). Пятый минтерм также  избыточен, так как 4-я; 5-я; 12-я  и 13-я строки уже сгруппированы  с 6-ой и 0-ой (четвёртый и  второй минтермы); с 13-ой (третий  минтерм); с 14-ой (четвёртый минтерм)  и с 5-ой (третий минтерм) соответственно. Поэтому удаляем первую и пятую  строки из таблицы и записываем  минимальную

Окончательно: F(a, b, c, d)= a'd'+ c'd+ bd'.

 

 

Метод Петрика

"Метод  используется для нахождения  всех минимальных покрытий конституент  единицы и позволяет получить  все тупиковые ДНФ по импликантной  матрице. Суть метода заключается  в следующем. По импликантной  матрице строится так называемое  конъюнктивное представление мипликантной  матрицы. Для этого все простые  импли-канты обозначаются разными  буквами (обычно прописными латин-скими). После этого, для каждого i-ro столбца импликантной матрицы строится дизъюнкция всех букв, обозначающих строки матрицы, пересечение которых с i-м столбцом отмечено крестиком. Конъюнктивное представление импликантной матрицы образуется как конъюнкция построенных дизъюнкций для всех столбцов матрицы. К конъюнктивному представлению матрицы могут быть применены все соотношения булевой алгебры с целью его упрощения. После раскрытия скобок и выполнения всех возможных поглощений получается дизъюнкция конъюнкций, каждая из которых содержит все импликанты тупиковой ДНФ. 
Пример. 
Задана имшшкантная матрица (табл. 4.6.1). Найти методом Петрика все тупиковые ДНФ булевой функции f, описываемой данной матрицей. 

 

 

Простые импликанты	Конституенты единицы
	/x1/x2/x3x4	/x1/x2x3x4	/x1x2/x3x4	/x1x2x3x4	x1x2x3/x4	x1x2x3x4
/x1x4	X	X	X	X
x2x3x4				X		X
x1x2x3					Х	Х

 
Имеющиеся простые  импликанты обозначим буквами:

/x₁x₄ = A. x₂x₃x₄ = B. x₁x₂x₃ = C.

Тогда конъюнктивное  представление w матрицы имеет вид

w = A*A*A*(A v B)*C(B v C).

Упростим  его.

w = A*(A v B)*C(B v C) = AC.

Тупиковая ДНФ содержит две простые импликанты: А = /x₁x₄ и C = x₁x₂x₃ и имеем вид f = /x₁x₄ v x₁x₂x₃."

 

Минимизация функции всеми  перечисленными методами

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

Пример 2. Рассмотрим функцию

Множество переменных разобьем на две группы. Одной группе сопоставим строки таблицы, второй — столбцы, так  чтобы каждой клетке соответствовала  комбинация переменных из этих групп. Карта Карно для нее имеет  вид табл. 5.

Таблица 5

Карта Карно для f₁

x1x2/x3	0	1
00
01		15
11	12	11
10	14	13

При составлении карты  Карно строки именуются всевозможными  комбинациями значений переменных первой группы так, чтобы расстояние между  соседними комбинациями было равно 1. Для нашего случая 00® 01® 11® 10 (при каждом последующем переходе изменяется только подчеркнутый символ). Аналогично именуются столбцы таблицы.

Заполнение карты производится по таблице соответствия исходной функции. В примере конъюнкции x₁x₂x₃ соответствует клетка 11/1, а  клетка 11/0 и так далее. В данной таблице каждая единица имеет порядковый индекс, который соответствует порядковому номеру данной компоненты в исходной функции (расстановка этих индексов совершенно не обязательна и здесь приведена для лучшего понимания).

Для минимизации необходимо попарно “склеить” рядом стоящие  единицы, имеющие хотя бы одну общую  компоненту. При этом надо стремиться “склеить” в один набор как  можно больше клеток. В данном примере  мы можем “склеить” 1₁,1₂,1₃,1₄ вместе. Это запишется как x_1,так как содержимое всех этих клеток зависит только от x₁ и не меняется при изменении x₂ или x₃. На следующем шаге склеим 1₁ и 1₅. В результате получим x₂x_3. Рассуждения аналогичны: при изменении x₁изменения ячеек с 1₁ и 1₅ не происходит.

Результирующей минимальной  записью исходной функции будет

Пример 3. Минимизируем функцию пяти переменных:

Карта Карно для нее  приведена в табл.6.

Таблица 6

Карта Карно для f₂

x4x5\x1x2x3	000	001	011	010	110	111	101	100
00							14	11,4
01								11
11			13					12
10			13				14	12,4

 

 

Если в конъюнкции переменная не присутствует, то 1 ставится во все клетки, удовлетворяющие присутствующим переменным. Так, например, первой конъюнкции соответствует две клетки: 100/00 и 100/01.

Минимизация приводит к формуле

 

 

Пример 4. Рассмотрим функцию

Таблица 7

Карта карно для f₃

x1x2/x3	0	1
00		1
01	1	1
11	1
10	1	1

По карте Карно в  табл.7 хорошо видно, что для данной функции существует две минимальных  формы: