Как найти минимальная дизъюнктивная нормальная форма - Исправление недочетов и поиск решений вместе с Examum.ru

Содержание

1 Сокращенная ДНФ
2 Минимальная ДНФ
3 Минимизация ДНФ
- 3.1 Визуализация гиперкубами
- 3.2 Карты Карно
- 3.3 Метод Квайна
  - 3.3.1 Описание алгоритма
  - 3.3.2 Пример
4 См. также
5 Источники информации

Сокращенная ДНФ

Определение:

Сокращенная ДНФ (англ. reduced disjunctive normal form) — форма записи функции, обладающая следующими свойствами:

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

Например:
содержится в .

Функцию можно записать с помощью сокращенной ДНФ не единственным способом.

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

Минимальная ДНФ

Определение:

Минимальная ДНФ (англ. minimal disjunctive normal form) — такая сокращенная ДНФ, в которой содержится минимальное количество вхождений переменных.

Каждая минимальная ДНФ является сокращенной, но не каждая сокращенная — минимальна.
Например, запись является минимальной ДНФ для медианы (она же сокращенная, как видно в примере выше); а запись — не минимальная, но сокращенная ДНФ.

Минимизация ДНФ

Рассмотрим несколько способов минимизации дизъюнктивных нормальных форм:

Визуализация гиперкубами

Этот способ работает при количестве переменных не больше трёх (в противном необходимо вводить четвёртое или следующие за ним измерения для представления фигур).
Сначала мы рисуем куб в системе отсчёта (названия координатных осей соответствуют названиям переменных). Затем каждую вершину обрабатываем следующим образом:

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

В итоге нашу изначальную ДНФ можно записать как .

Карты Карно

Построим следующую таблицу , где — число переменных:

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

Например, ДНФ

будет выглядеть на картах Карно так:

Теперь покрываем прямоугольниками (длины сторон которых — степени двойки ()) те ячейки карт Карно, которые содержат в себе единицу (на каждом ходу мы выбираем такой прямоугольник, чтобы он покрывал наибольшее количество ещё не покрытых клеток) до тех пор, пока не покроем все такие ячейки.

Для карт Карно на примере это выглядело бы так:

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

То есть, в этом примере получаем:

Метод Квайна

Этот метод основан на применении двух основных операций:

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

Операция элементарного поглощения:

(где — некоторая элементарная конъюнкция, то есть конъюнкт, в который каждая из переменных входит не более одного раза)

Например:

Пусть , тогда:

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

Операция элементарного поглощения:

Метод состоит в последовательном выполнении всех возможных склеиваний и затем всех поглощений частей СДНФ пока это может быть осуществимо.

Описание алгоритма

Исходным является множество пар вида или
Выполняются все возможные операции неполного попарного склеивания для элементарных конъюнкций длины (где — число аргументов).
Выполняются все возможные операции элементарного поглощения для элементарных конъюнкций длины (общая часть «» имеет длину )
В результате получилось множество элементарных конъюнкций, разделяемых на два подмножества (по длине):
- подмножество элементарных конъюнкций длины (оставшиеся)
- подмножество элементарных конъюнкций длины
Если множество элементарных конъюнкций длины не пусто, то заново выполняются операции неполного попарного склеивания и элементарного поглощения для конъюнкций длины и так далее.

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

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

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

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

Пример

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

Набор

Значение

исходной

функции

Проведём операции неполного склеивания и поглощения:

№	Элементарная конъюнкция	Поглощение

№ склеивания	Результат

На данном шаге все элементы вида или участвовали в операциях попарного неполного склеивания и были поглощены своими собственными частями. Поэтому элементы сокращённой ДНФ на этом шаге не получены.

№	Элементарная конъюнкция	Поглощение

№ склеивания	Результат

На данном этапе получаем элементы сокращённой ДНФ и

№	Элементарная конъюнкция	Поглощение

Обе элементарные конъюнкции на данном шаге являются элементами сокращённой ДНФ.

В результате выполнения алгоритма мы получаем следующую сокращённую ДНФ:

Переход от сокращённой формы к минимальной:

Единицы ДНФ, покрываемые элементами или обозначаются «+». Пары и , попадающие в ядро помечаются «*».
Единицы функции, которые покрываются только каким-то одним конъюнктом из системы элементов сокращённой ДНФ, помечаются “>”.
Единицы функции, покрываемые ядром, но не покрываемые только каким-то одним конъюнктом из системы элементов сокращённой ДНФ помечаются “>>”.

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

См. также

ДНФ
КНФ

Источники информации

Минимизация логических функций методом Куайна — Википедия
Метод Квайна
Карта Карно — Википедия
Минимизация булевых функций в классе ДНФ
Минимизация ДНФ методом Квайна

Источник

Построение минимальных ДНФ

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

Определение 6.5. Булеву функцию называют импликантой булевой функции , если для любых наборов значений переменных из g=1 следует f=1 .

Замечание 6.7. Напомним, что функции и можно рассматривать как функции от одного и того же числа переменных. Обозначая это число через , можно так уточнить понятие импликанты: функция $gin mathcal{P}_{2,n}$ есть импликанта функции $gin mathcal{P}_{2,n}$ если для каждого набора a $widetilde{alpha}inmathbb{B}^n$ из g(widetilde{alpha})=1 следует f(widetilde{alpha})=1 . Термин «импликанта» естественным образом ассоциируется и с логической связкой, называемой импликацией, и с одноименной булевой функцией. Действительно, если д импликанта , то из (gto f)=1 и g=1 следует, что f=1 , т.е. истинно высказывание

$(forallwidetilde{alpha}inmathbb{B}^n)bigl((g(widetilde{alpha})=1)Rightarrow (f(widetilde{alpha})=1)bigr).$

Если функция представлена СДНФ, то любая ее элементарная конъюнкция (констпигпуентпа единицы функции ) будет ее импликантой. Полезно заметить также, что если g_1 и g_2 — импликанты , то дизъюнкция g_1lor g_2 также является импликантой . Действительно, если g_1lor g_2=1 , то g_1=1 или g_2=1 . Но тогда, поскольку каждая из этих функций есть импликанта , и есть импликанта .

Из определения 6.5 и понятия равных булевых функций (см. определение 6.2) следует, что булевы функции и равны, если и только если каждая из них служит импликантой другой: f=1Leftrightarrow g=1 .

Определение 6.6. ДНФ называют минимальной, если она содержит наименьшее число литералов среди всех ДНФ, эквивалентных ей.

Обратим внимание на то, что под числом литералов в ДНФ понимают число всех подформул этой ДНФ, которые являются литералами. Так, СДНФ (6.9) содержит 12 литералов (по три литерала в каждой из четырех элементарных конъюнкции).

Пример 6.10. ДНФ $x_1x_2lor overline{x}_1x_2$ не является минимальной, так как ее можно преобразовать к эквивалентной ДНФ, не содержащей ни одного из литералов $widetilde{x}_1:$

$x_1x_2lor overline{x}_1x_2=(x_1lorwidetilde{x}_1)x_2=x_2,.$

Вместо четырех литералов в исходной ДНФ получаем ДНФ, состоящую из одного литерала.
Определение 6.7. Длиной ДНФ называют число входящих в нее элементарных конъюнкций.
ДНФ называют кратчайшей, если она имеет наименьшую длину среди всех эквивалентных ей ДНФ.

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

Наша задача состоит в том, чтобы описать метод построения минимальной ДНФ, эквивалентной заданной булевой функции. Мы рассмотрим простейший метод такого рода, основанные на алгоритме Квайна — Мак-Клоски. Этот алгоритм исходит обязательно из СДНФ, которая строится по таблице функции так, как это было описано ранее.

Алгоритм Квайна–Мак-Клоски

Опишем последовательно этапы, составляющие алгоритм Квайна–Мак-Клоски.

1. Склейка. Пусть K_1 и K_2 — две элементарные конъюнкции, входящие в исходную СДНФ Ф, которая представляет функцию , причем для некоторого переменного и некоторой элементарной конъюнкции выполняются равенства K_1=xK и $K_2=overline{x}K$ . Тогда имеем, согласно тождествам булевой алгебры,

$K_1lor K_2=xKlor overline{x}=(xlor overline{x})K=K,.$

Мы получаем элементарную конъюнкцию , которая содержит на один литерал меньше, чем K_1 и K_2 , и является, как и обе конъюнкции K_1 и K_2 , импликантой . Образно говоря, мы «склеили» две импликанты в одну, в которой число литералов на единицу меньше.

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

Установим геометрический смысл простой склейки* (с точки зрения структуры, или «геометрии», булева куба).

Из доказательства теоремы о представлении булевой функции в виде ДНФ (см. теорему 6.2) мы знаем, что существует взаимно однозначное соответствие между множеством элементарных конъюнкций СДНФ, представляющей функцию , и множеством C_f^1 ее конституент единицы. Это соответствие, напомним, таково, что каждому набору $widetilde{alpha}=(alpha_1,ldots,alpha)in C_f^1$ отвечает элементарная конъюнкция $K_{widetilde{alpha}}=x_{1}^{alpha_1}cdotldots x_{n}^{alpha_n}$ , принимающая значение 1 только на наборе . Тогда простая склейка может быть применена только к таким двум элементарным конъюнкциям $K_{widetilde{alpha}}$ и $K_{widetilde{beta}}$ , соответствующим наборам $widetilde{alpha}, widetilde{beta}in C_f^1$ , что для некоторого i~(1leqslant ileqslant n)

$begin{aligned}widetilde{alpha}&= (alpha_1,ldots, alpha_{i-1},alpha_{i}, alpha_{i+1}, ldots, alpha_{n}),\[2pt] widetilde{beta}&= (alpha_1,ldots, alpha_{i-1}, overline{alpha}_{i}, alpha_{i+1}, ldots, alpha_{n}).end{aligned}$

Это значит, что наборы widetilde{alpha}, widetilde{beta} таковы, что один из них доминирует над другим (они различаются значением только одной компоненты), т.е. они образуют ребро булева куба $mathbb{B}^n$ .

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

С алгебраической же точки зрения мы из двух элементарных конъюнкций $K_{widetilde{alpha}}$ и $K_{widetilde{beta}}$ получаем новую элементарную конъюнкцию $x_{1}^{alpha_1}ldots x_{i-1}^{alpha_{i-1}} x_{i+1}^{alpha_{i+1}}ldots x_{n}^{alpha_n}$ , лишенную литерала $x_{i}^{alpha_i}$ .

Итак, применяя простую склейку к исходной СДНФ Phi , получаем новую ДНФ Phi_1 ; к ней также применяем простую склейку — получаем ДНФ Phi_2 ; продолжаем выполнять эту операцию до тех пор, пока не окажется, что для некоторого в ДНФ Phi_k уже нельзя склеить никакие две элементарные конъюнкции. Такое всегда найдется, так как СДНФ Phi состоит из конечного числа элементарных конъюнкций, а они, в свою очередь, состоят из конечного числа литералов. Полученную в результате ДНФ Phi_k называют сокращенной ДНФ функции , а ее элементарные конъюнкции — простыми импликантами булевой функции .

Замечание 6.8. Понятие простой импликанты определено через процедуру многократного повторения простой склейки. Иногда простую импликанту булевой функции определяют независимо от понятия о склейке как такую элементарную конъюнкцию в составе некоторой ДНФ, представляющей функцию , что удаление из нее любого литерала лишает ее свойства «быть импликантой». Например, конъюнкция $x_1x_2 overline{x}_3$ не является простой импликантой мажоритарной функции, так как из ее СДНФ (6.9) можно удалить литерал $overline{x}_3$ и получить конъюнкцию x_1x_2 , которая будет снова импликантой функции, но уже, как будет показано далее, простой.

Можно доказать, что эти два определения простой импликанты равносильны.

Геометрия описанного выше многократного повторения простой склейки, как можно показать, состоит в дальнейшем «склеивании» каждой пары соседних ребер {граней размерности 1), на которых значение функции равно 1, в грани размерности 2, соседних граней размерности 2 в грани размерности 3 и т.д. Разбираемый ниже пример поясняет эту идею.

Пример 6.11. Зададим функцию от трех переменных следующей СДНФ:

$f=overline{x}_1overline{x}_2overline{x}_3lor overline{x}_1overline{x}_2 x_3lor x_1overline{x}_2overline{x}_3lor x_1overline{x}_2x_3,.$

(6.11)

Подвергнем простой склейке первую и третью, а также вторую и четвертую элементарные конъюнкции в (6.11):

$f=overline{x}_2overline{x}_3loroverline{x}_2x_3,.$

(6.12)

Склейка первой и третьей конъюнкций в формуле

С геометрической точки зрения склейка первой и третьей конъюнкций в формуле (6.11) означает, что функция принимает единичное значение на ребре [000,100] (рис. 6.6), а склейка второй и четвертой конъюнкций точно так же определяет ребро [001,101], Эти ребра являются соседними, и, кроме того, оказывается, что функция / принимает единичное значение и на другой паре соседних ребер: [000, 001] и [100,101]. Здесь сказывается существенное отличие «геометрии» булева куба от классической: в булевом кубе ребро — это пара вершин, между которыми нет никаких «точек». Тогда любая пара соседних ребер образует грань размерности 2, любая пара соседних граней размерности 2 образует грань размерности 3 и т.д. Таким образом, если функция принимает единичное значение на двух соседних ребрах булева куба, то она равна 1 в любой точке образуемой ими грани размерности 2, если она равна 1 на двух параллельных соседних гранях размерности 2, то она равна 1 на соответствующей грани размерности 3 и т.д.

Применяя простую склейку к (6.12) (по переменному x_3 ), получаем $f(x_1,x_2,x_3)=overline{x}_2$ . Побочным результатом склейки явилось и удаление фиктивных переменных функции x_1 и x_3 .

Пример 6.12. Рассмотрим СДНФ мажоритарной функции (6.9).
Имеем следующие склейки:

$overline{x}_1x_2x_3lor x_1x_2x_3=x_2x_3,qquad x_1overline{x}_2x_3lor x_1x_2x_3=x_1x_3,qquad x_1x_2overline{x}_3lor x_1x_2x_3=x_1x_2.$

В данном случае сразу получаем сокращенную ДНФ: Phi_1=x_1x_2lor x_1x_3lor x_2x_3 .

Карты Карно

Для булевых функций от трех и четырех переменных процедура склейки наглядно и просто выполняется на так называемых картах Карио. Форма карт Карно, представляющих собой прямоугольные таблицы, для функции от трех переменных показана на рис. 6.7, а для функции от четырех переменных — на рис. 6.8. На рис. 6.7 строки отмечены наборами значений переменного x_1 , а столбцы — x_2,x_3 , а на рис. 6.8 строки — наборами значений переменных x_1,x_2 , а столбцы — x_3,x_4 .

Форма карт Карно для функций от трех и четырёх переменных

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

С геометрической точки зрения карта Карно есть способ изображения булева куба (размерностей 3 и 4). Любая пара соседних клеток (с учетом «закрученности» карты) определяет некоторое ребро булева куба, а любой прямоугольник, состоящий из 2^k клеток (или, как говорят, прямоугольник с площадью 2^k ) для некоторого , определяет грань размерности .

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

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

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

С геометрической точки зрения такой прямоугольник площади 2 соответствует ребру булева куба, в каждой вершине которого функция принимает значение 1. Запись прямоугольника в виде слова можно понимать как обозначение соответствующего ребра. Так, на карте, показанной на рис. 6.9, прямоугольник 11× обозначает ребро [110,111], прямоугольники же 1×1 и ×11 — ребра [101,111] и [011,111] соответственно.

По таким обозначениям легко получить и ту импликанту, которая является результатом простой склейки: для этого достаточно записать литерал x_i (соответственно $overline{x}_i$ ), если в i-й позиции стоит 1 (соответственно 0), и пропустить литерал ж», если в i-й позиции стоит «крестик». Так, по слову 1×0 получим импликанту $x_1overline{x}_3$ .

Наличие на карте Карно двух прямоугольников площади 2, находящихся в соседних столбцах или строках, показывает, что функция принимает значение 1 на некоторой паре соседних ребер, т.е. на некоторой грани размерности 2. Тогда они могут быть объединены в один большой прямоугольник площади 4 (рис. 6.10).

Наличие на карте Карно двух прямоугольников площади и их объединение

Этот прямоугольник можно записать в виде слова хОх, показывая тем самым, что соответствующая грань (размерности 2) образована любой из двух пар соседних ребер: (×00, ×01) (два вертикальных прямоугольника площади 2) или (00×, 10×) (два горизонтальных прямоугольника площади 2).

Точно так же можно объединять в один прямоугольник площади 8 два соседних прямоугольника площади 4 (рис. 6.11).

Карты Карно

Если такие большие прямоугольники находить сразу, то «поглощаемые» ими меньшие прямоугольники уже не рассматриваются. Тем самым, находя на карте Карно прямоугольники максимальной площади и не содержащиеся друг в друге, мы находим грани максимальных размерностей и максимальные по включению, такие, на которых заданная функция принимает единичное значение. Поскольку грань размерности имеет 2^k вершин, то выделяемые описанным способом прямоугольники могут состоять только из 2^k клеток (для некоторого , не превышающего числа переменных). Так, на карте, приведенной на рис. 6.12, получим два прямоугольника площади 4: ×0×0 и 0×0×, соответствующие граням размерности 2, и один прямоугольник 01×1, отвечающий ребру, которое не содержится ни в одной из указанных выше граней. Подчеркнем еще раз, что соседство клеток, прямоугольников и само выделение прямоугольников на карте Карно производится с учетом ее «закрученности». В этой связи интересен » прямоугольник» на карте, приведенной на рис. 6.12, обозначенный ×0×0. Он образован двумя парами противоположных угловых клеток.

Таким образом, если на карте Карно сразу выделять все максимальные (в указанном выше смысле) прямоугольники площади 2^k (для некоторого kgeqslant0 и не превышающего числа переменных), то тем самым мы «геометрически» реализуем описанный ранее алгебраический итерационный процесс склейки и в результате получаем все простые импликанты исходной функции (составляющие сокращенную ДНФ). Эти импликанты восстанавливаются по записям прямоугольников точно так же, как описано выше для простой склейки. Так, для карты, приведенной на рис. 6.12, получим сокращенную ДНФ в виде

$overline{x}_2 overline{x}_4lor overline{x}_1 overline{x}_3lor overline{x}_1x_2x_4,.$

2. Определение ядра. Говорят, что элементарная конъюнкция покрывает элементарную конъюнкцию (и пишут Ksucc L ), если любой литерал, входящий в , входит в . Так,

$x_1x_2succ x_1x_2x_3,qquad x_1x_3succ x_1 overline{x}_2x_3$ , но $x_1x_3nsucc x_1x_2overline{x}_3$ .

Поскольку вторая конъюнкция содержит литерал $overline{x}_3$ , отсутствующий в первой конъюнкции. Легко понять, что если Ksucc L , то Klor L=K (согласно тождествам поглощения).

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

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

Множество всех ядровых импликант (склеек) сокращенной ДНФ называют ядром.

Пример 6.13. а. У мажоритарной функции все импликанты являются ядровыми. Напротив, у функции, изображенной на карте Карно на рис. 6.13, ядро пусто, т.е. ядровых импликант нет вовсе.

Две карты Карно

б. На карте Карно на рис. 6.14 в ядро попадают склейки 0times,times1,~ 0times1times,~ 1times00 .

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

В остальных случаях переходят к отысканию так называемых тупиковых ДНФ.

3. Перечисление тупиковых ДНФ. Простую импликанту называют избыточной (относительно некоторой ДНФ, содержащей только простые импликанты и эквивалентной исходной СДНФ), если ее можно удалить из этой ДНФ без потери эквивалентности ее исходной СДНФ. Так, сокращенная ДНФ (см. рис. 6.14) содержит избыточные импликанты: импликанта, соответствующая прямоугольнику 10times0 , или импликанта, соответствующая прямоугольнику times010 , может быть удалена (но не обе сразу!). Это значит, что каждая из этих импликант является избыточной относительно сокращенной ДНФ, но удаление одной из них приводит к новой ДНФ, относительно которой вторая из упомянутых импликант уже не будет избыточной. В том случае, когда каждую элементарную конъюнкцию исходной СДНФ покрывает некоторая ядровая импликанта, импликанты, не вошедшие в ядро, можно удалить одновременно.

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

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

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

Для СДНФ, карта Карно которой приведена на рис. 6.14, имеются две тупиковые ДНФ (первые три конъюнкции соответствуют ядру):

$begin{gathered}overline{x}_1x_4lor overline{x}_1x_3lor x_1overline{x}_3cdot overline{x}_4lor overline{x}_2 x_3 overline{x}_4,\[2pt] overline{x}_1x_4lor overline{x}_1x_3lor x_1overline{x}_3cdot overline{x}_4lor x_1overline{x}_2cdot overline{x}_4. end{gathered}$

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

Присвоим каждой простой импликанте сокращенной ДНФ некоторое имя: т.е. обозначим их, например, как K_1,K_2,ldots,K_m . Для любой единицы карты Карно, не покрываемой ядром, перечислим все простые импликанты, которые ее покрывают, записав их в виде элементарной дизъюнкции, в которой переменными считаются введенные выше имена простых импликант. Переменное, именующее данную простую импликанту, принимает, по определению, значение 1, если данная простая импликанта выбирается для покрытия рассматриваемой единицы
карты Карно.

Записав все элементарные дизъюнкции, составим из них КНФ. Рассмотрим карту Карно на рис. 6.13. Обозначив

$begin{array}{lll}K_1=x_1overline{x}_2(10times),&qquad K_2= overline{x}_2 x_3(times01), &qquad K_3= overline{x}_1x_3(0times1),\[2pt] K_4= overline{x}_1 x_2(01times), &qquad K_5=x_2overline{x}_3(times10),&qquad K_6= x_1overline{x}_3(1times0), end{array}$

получим

(K_1lor K_6)land (K_1lor K_2)land (K_2lor K_3)land (K_3lor K_4)land (K_4lor K_5)land (K_5lor K_6).

(6.13)

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

Для нашего примера поступим так: вычислим конъюнкцию первой и второй скобки в выражении (6.13), а также третьей и четвертой, пятой и шестой скобок, после чего получим

$begin{aligned}(K_1lor K_1 K_2lor K_6 K_1lor K_6 K_2) &land (K_2 K_3lor K_2 K_4lor K_3lor K_3 K_4)land\[2pt] &land (K_4 K_5lor K_4 K_6lor K_5lor K_5 K_6). end{aligned}$

(6.14)

Используя тождества поглощения, в первой скобке в формуле (6.14) мы можем удалить все члены, содержащие K_1 , во второй скобке — все члены, содержащие K_3 , в третьей скобке — все члены, содержащие K_5 . Проделав это, раскрыв все три скобки и применив еще раз поглощение, окончательно получим

K_1 K_3 K_5lor K_1 K_3 K_4 K_6lor K_1 K_2 K_4 K_5lor K_2 K_3 K_5 K_6lor K_2 K_4 K_6.

(6.15)

Элементарные конъюнкции в (6.15) определяют тупиковые ДНФ. Более того, так как в данном случае отсутствуют ядровые импликанты, найденные конъюнкции исчерпывают тупиковые ДНФ. Первая тупиковая ДНФ состоит из конъюнкций K_1,,K_3 и K_5 , т.е. имеет вид $x_1 overline{x}_2lor overline{x}_1x_3lor x_2 overline{x}_3$ . Точно так же определяются остальные тупиковые ДНФ.

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

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

4. Отыскание среди тупиковых ДНФ кратчайших и минимальных. Среди найденных тупиковых ДНФ находят кратчайшие и минимальные. Можно легко показать, что минимальная ДНФ всегда является кратчайшей, но обратное неверно. Так, $x_1x_2loroverline{x}_2=x_1lor overline{x}_2$ и первая ДНФ кратчайшая, но не минимальная. Действительно, легко сообразить, что вторая из записанных ДНФ минимальна. Следовательно, представляемую ею функцию нельзя представить ДНФ, содержащей менее двух элементарных конъюнкций. Но в первой ДНФ три литерала, а во второй — два. Из пяти тупиковых ДНФ, соответствующих функции Патрика (6.15), кратчайшими являются две. Каждая из них минимальна, так как обе они имеют одинаковое число литералов.

Карта Карно

Пример 6.14. Рассмотрим карту Карно на рис. 6.15. В результате проведения склейки получим следующую сокращенную ДНФ*:

$overline{x}_1overline{x}_3lor overline{x}_1overline{x}_2lor overline{x}_2 overline{x}_4lor overline{x}_2overline{x}_3lor overline{x}_3x_4lor x_1x_2x_4lor x_1x_2x_3lor x_1x_3overline{x}_4,.$

Ядро составляют склейки (простые импликанты) $overline{x}_1overline{x}_3$ и $overline{x}_1overline{x}_3$ .

Шесть клеток, содержащих единицу, на карте Карно остаются непокрытыми ядровыми склейками. Для неядровых склеек (обозначенных K_1,ldots,K_6 ) составляем функцию Патрика в виде

(K_3lor K_4) (K_4lor K_5) (K_5lor K_6) (K_1lor K_2) (K_2lor K_3) (K_1lor K_6).

Преобразуя ее аналогично функции (6.13), получаем

K_1K_3K_5lor K_2K_4K_6lor K_2K_3K_5K_6lor K_1K_2K_4K_5lor K_1K_3K_4K_6,.

Имеем, следовательно, пять тупиковых ДНФ. Запишем их, для наглядности, так:

$underbrace{overline{x}_1overline{x}_3lor overline{x}_1 overline{x}_2}_{text{yadro}}lor begin{cases}overline{x}_2overline{x}_4lor overline{x}_3x_4lor x_1x_2x_3,\ overline{x}_2overline{x}_3lor x_1x_2x_4lor x_1x_3overline{x}_4,\ overline{x}_2 overline{x}_3lor overline{x}_3x_4lor x_1x_2x_3lor x_1x_3overline{x}_4,\ overline{x}_2 overline{x}_4lor overline{x}_2overline{x}_3lor x_1x_2x_4lor x_1x_2x_3,\ overline{x}_2 overline{x}_4lor overline{x}_3x_4lor x_1x_2x_4lor x_1x_3overline{x}_4. end{cases}$

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

$overline{x}_1overline{x}_3lor overline{x}_1overline{x}_2lor overline{x}_2 overline{x}_4lor overline{x}_3x_4lor x_1x_2x_3,.$

«Обратим еще раз внимание на то, что каждый выделяемый прямоугольник на карте Карно имеет площадь, равную некоторой степени двойки. Поэтому, например, три соседние единичные клетки не могут быть объединены в один прямоугольник, а их «накроют» два прямоугольника площадью 2, пересекающиеся по одной клетке.

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

Метод Блейка

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

$begin{cases}xK_1lor overline{x}K_2= xK_1lor overline{x}K_2lor K_1K_2,\ K_1lor K_1K_2=K_1.end{cases}$

Первое из тождеств (6.16) называют тождеством (или правилом) обобщенного склеивания, второе — тождеством (или правилом) поглощения.

«Технология» использования метода Блейка такова: применяют тождество обобщенного склеивания до тех пор, пока не перестанут появляться новые элементарные конъюнкции (вида К1К2). После этого применяют тождество поглощения.

Таблицы Квайна

Как только сокращенная ДНФ тем или иным способом найдена, приступают к нахождению ядра. Ядро можно определить (без использования карты Карно) с помощью так называемой таблицы Квайна. Столбцы этой таблицы соответствуют элементарным конъюнкциям исходной СДНФ, а строки — простым импликантам сокращенной ДНФ. На пересечении строки и столбца проставляется знак «+» (плюс), если простая импликанта данной строки покрывает элементарную конъюнкцию данного столбца. Ядро вычисляется так: отмечаем столбцы с единственным знаком «+», тогда простые импликанты тех и только тех строк, в которые попал этот знак, образуют ядро. Для примера 6.13.6 (см. рис. 6.14) получим таблицу Квайна, изображенную на рис. 6.16. (В целях экономии места элементарные конъюнкции в таблице заменены цифровыми обозначениями соответствующих вершин и граней булева куба — точно так же как при обозначении прямоугольников на картах Карно. Ядровые импликанты выделены жирным шрифтом.)

Таблица Квайна

По таблице Квайна можно составить и функцию Патрика для перечисления тупиковых ДНФ. Для этого нужно отметить все столбцы таблицы, в которых на пересечении со строками, соответствующими ядровым импликантам, не стоит знак «+». Для разбираемого примера таковым является только последний столбец. Чтобы покрыть соответствующую элементарную конъюнкцию СДНФ, можно выбрать одну из двух простых импликант: $x_1 overline{x}_2 overline{x}_4$ или $overline{x}_2x_3overline{x}_4$ .

Построение минимальных ДНФ частичных булевых функций

В заключение рассмотрим очень кратко применение карт Карно к построению минимальных ДНФ частичных булевых функций, т.е. частичных отображений из множества ${0;1}^n$ в множество {0;1} .

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

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

Пример 6.15. Пусть частичная функция f(x_1,x_2,x_3) задана картой Карно, приведенной на рис. 6.17. Прямоугольник максимальной площади (равной 4), состоящий из единицы и прочерков, записывается как 0times,times . Следовательно, минимальная ДНФ для заданной функции будет $overline{x}_1$ .

Частичная булевая функция, заданная картой Карно

По поводу рассмотренного примера возникает такой вопрос: почему не принят во внимание другой прямоугольник (площади 2), содержащий клетку с единицей и клетку с прочерком: times00 ? Связано это вот с чем. Перед тем как выделять упомянутые выше прямоугольники, мы на самом деле доопределяем исходную частичную функцию (получая обычную булеву функцию) так, чтобы в максимальном числе клеток, в которых стоят прочерки (но не нули!), появились единицы. Точнее говоря, среди прямоугольников (с прочерками), содержащих данную единицу, выбирают для замены прочерков единицами такой, который имеет максимальную площадь. Прочерки же в остальных прямоугольниках заменяют нулями.

В примере 6.15 мы доопределяем исходную функцию так, что получается функция f_1 , задаваемая картой Карно, приведенной на рис. 6.18. Эта функция имеет минимальную ДНФ $overline{x}_1$ . Следовательно, и частичная исходная функция может быть представлена такой ДНФ, поскольку на всех наборах, на которых она определена, она принимает такое же значение, как и функция f_1 .

Карты Карно 2

Конечно, мы могли бы доопределить функцию по-другому, так, чтобы получилась функция f_2 , заданная картой Карно, приведенной на рис. 6.19. Ясно, что $f_2= overline{x}_2overline{x}_3$ поэтому и частичная функция может быть определена такой ДНФ. Но эта ДНФ не минимальна для данной частичной (именно частичной!) функции, поскольку первый способ доопределения дал ДНФ, содержащую лишь один литерал.

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

Пример 6.16. Для карты на рис. 6.20 следует взять обе склейки на четыре позиции: 00times,times и times,times00 , получив для заданной этой картой частичной функции минимальную ДНФ в виде $overline{x}_1 overline{x}_2lor overline{x}_3 overline{x}_4$ .

Карта Карно булевой функции четырех переменных

Заметим, что без использования склеек с прочерками мы вообще не могли бы минимизировать данную функцию. Нужно также отметить, что не всегда использование «частичности» функции позволяет получить минимальную ДНФ для нее. Так, на представленной на рис. 6.20 карте в случае, если мы переместим нижнюю единицу на строку выше, обычная склейка на две позиции дает лучший результат: $overline{x}_1overline{x}_3overline{x}_4$ , а записанная выше ДНФ уже не будет минимальной (и даже кратчайшей).

Математический форум (помощь с решением задач, обсуждение вопросов по математике).

Кнопка "Поделиться"

Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.

Источник

§ 2.3. Минимизация дизъюнктивных нормальных форм

Элементарная
конъюнкция, ранг элементарной
конъюнкции. Дизъюнктивная нормальная
форма (ДНФ), сложность ДНФ. Минимальная
ДНФ. Импликанта, простая импликанта.
Сокращенная ДНФ. Тупиковая ДНФ.
Представление булевой функции в виде
сокращенной, тупиковой и минимальной
ДНФ.

Базовые понятия и утверждения

1. Постановка задачи минимизации ДНФ.
Пусть задан алфавит переменных
.

Определение. Формулу вида
,
где для любого

равно 0 или 1
и все переменные разные (,
если
),
называют элементарной конъюнкцией
ранга r над множеством
X.

Константу 1
считают элементарной конъюнкцией ранга
0.

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

Например, пусть
задан алфавит переменных
.
Тогда формула

— элементарная конъюнкция ранга 3,
а формула

— элементарная конъюнкция ранга 2
над множеством
.
Формула
,
напротив, элементарной конъюнкцией не
является, так как в этой формуле дважды
упоминается переменная
.

Пример 1.
Перечислить все элементарные
конъюнкции над множеством
:
1,
,
,
,
,
,,
,
.

Вообще, используя алфавит из

переменных
,
можно составить

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

этапов. На первом этапе принять решение
относительно переменной

(есть три возможности — включить ее в
конъюнкцию саму по себе, включить ее
отрицание или не включать ее вовсе), на
втором — принять решение относительно
переменной

(вновь имеем три возможности) и т.д.
Действуя описанным образом, мы составим

элементарных конъюнкций (в их число
входит и константа 1
— сопоставим ее случаю, когда ни одна из
переменных в конъюнкцию не включена).

Пример 2. Перечислить
все элементарные конъюнкции ранга 3
над множеством
,
обращающиеся в 1
на наборе
.

◄ Произвольная элементарная конъюнкция
равна 1 в том
и только в том случае, когда все
образующие ее
множители
одновременно
равны 1.
Значит, переменная

может войти в элементарную конъюнкцию,
обращающуюся в 1
на наборе
,
только без отрицания, а остальные
переменные — обязательно с отрицанием.
Таким образом, перебрав все варианты
выбора трех переменных из множества
,
получим четыре конъюнкции:
,
,
,
.
►

Определение. Формулу вида

(
при
),
где через

обозначены элементарные конъюнкции
над множеством X,
называют дизъюнктивной
нормальной формой над множеством X.

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

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

Например,

— ДНФ сложности 6;

— ДНФ сложности 4;

— ДНФ сложности 3 над множеством
.

Заметим, что формулы

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

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

Так, для функции
,
реализуемой рассмотренными выше ДНФ
,
,
,
дизъюнктивная нормальная форма

является минимальной.

Задача минимизации ДНФ формулируется
так: для всякой булевой функции

найти представление в виде минимальной
ДНФ.

Задачу минимизации ДНФ можно решить
методом полного перебора, организовав
его следующим образом.

1. Построить все ДНФ над множеством
.

Выше было показано, что число различных
элементарных конъюнкций над алфавитом
из

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

ДНФ (вычтя из

единицу, мы учли, что если не включить
в строящийся объект ни одну из элементарных
конъюнкций, то ДНФ не образуется).

2. Отобрать из построенных ДНФ те, которые
задают функцию
.

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

3. Для каждой отобранной ДНФ определить
сложность; ДНФ наименьшей сложности и
есть искомые минимальные ДНФ функции
.

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

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

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

также обращается в 1.

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

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

Пример 3.
Перечислить все простые импликанты
функции
.

◄ Имеем девять элементарных конъюнкций
над переменными
:
1,
,
,
,
,
,,
,
.
Относительно каждой из них выясним,
является ли она импликантой, и если это
так, то простая ли она.

Для удобства дальнейших рассуждений
перечислим значения функции

на всех наборах значений переменных:
,
,
,
.

1 импликантой
не является, так как обращается в 1
на всех наборах, в то время как
.

не является импликантой
,
так как на наборе

она обращается в 1, в то время как
.

обращается в 1
на наборах
,
,
и на каждом из этих наборов

также равна 1,
следовательно,

— импликанта
.
Эта импликанта простая, так как конъюнкция
1, полученная
из нее путем удаления
,
импликантой не является.

обращается в 1
на наборах

и
,
а
,
следовательно,

не является импликантой
.

обращается в 1
на одном наборе
,
и
,
следовательно,

— импликанта
.
Однако простой эта импликанта не
является, так как конъюнкция
,
полученная из нее путем удаления буквы
,
является импликантой.

обращается в 1
на одном наборе

и
,
следовательно,

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

обращается в 1
на наборе
,
а
,
следовательно,

не является импликантой
.

обращается в 1
на наборе
,
,
следовательно,

импликанта
.
Однако простой эта импликанта не
является, так как конъюнкция
,
полученная из нее путем удаления
,
является импликантой.

Таким образом, функция

имеет две простые импликанты:

и.
►

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

Например, для
функции

(см. пример 3) сокращенная ДНФ имеет вид
.

Из определения сокращенной ДНФ
непосредственно следует, что сокращенная
ДНФ у функции единственна.

Справедливо следующее утверждение:
сокращенная ДНФ функции
задает функцию

(доказательство приведено во второй
части параграфа).

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

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

Имеет место следующий теоретический
факт: минимальная ДНФ функции является
тупиковой ДНФ (доказательство приведено
во второй части параграфа).

3. Построение минимальных ДНФ.
Рассмотрим алгоритм построения
минимальных ДНФ функции, исходя из СДНФ.
Обоснование данного алгоритма можно
найти в [1].

Алгоритм состоит из трех этапов: сначала
получают сокращенную ДНФ, далее строят
все тупиковые ДНФ и, наконец, из тупиковых
ДНФ выделяют минимальные.

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

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

а) операция неполного склеивания,
состоящая в замене выражения

на
;

б) операция поглощения, состоящая в
замене выражения

на
;

в) операция удаления дублируемых членов,
состоящая в замене выражения

на
.

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

удаляем те конъюнкции ранга n,
которые возможно удалить таким образом.
Убираем дублируемые члены
.
Полученную в итоге ДНФ обозначаем
.

-й
шаг. К началу этого шага нами построена
ДНФ
.
К каждой паре конъюнкций ранга

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

совпадает с
,
то

— искомая сокращенная ДНФ. В противном
случае, увеличив значение

на единицу, повторяем
-й
шаг.

В качестве примера
построим методом Квайна сокращенную
ДНФ функции
:

2-й этап: построение
тупиковых ДНФ.

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

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

Пусть

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

принимает значение 1.
Пусть булевы векторы

— элементы носителя функции
,

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

и столбца

проставлено число
,
равное 1, если импликанта

на наборе

обращается в единицу, и равное 0 в
противном случае (табл. 2.20). Назовем эту
таблицу импликантной.

_{Таблица 2.20}
		…		…
		…		…
…	…	…	…	…	…
		…		…
…	…	…	…	…	…
		…		…

По импликантной таблице составим
формулу вида
,
т.е. каждому булеву вектору

()
сопоставим дизъюнкцию тех импликант,
значение которых на

равно 1, и запишем конъюнкцию
всех выписанных дизъюнкций.

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

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

_{Таблица 2.21}
	₀₀₀	011	100	₁₁₀	111
	₁	0	1	₀	0
	0	1	0	0	1
	₀	0	1	₁	0
	0	0	0	1	1

Тогда

Имеем две тупиковые ДНФ, каждая из
которых задает функцию

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

Таблица 2.22

0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	0

Например, для функции

обе тупиковые ДНФ имеют сложность,
равную 6, и, следовательно, обе являются
минимальными.

Пример 4.
Построить минимальные ДНФ функции:

а)
;

б)
.

◄ а) Зададим функции таблицей (табл.
2.22).

1-й этап. Строим
сокращенную ДНФ функции:

2-й и 3-й этапы
для данной функции можно опустить.
Действительно, нетрудно убедиться, что
при опускании любой буквы в сокращенной
ДНФ, получается формула, функцию

не представляющая. Следовательно,
сокращенная ДНФ

функции

является также тупиковой и минимальной.

Таблица 2.23

0	0	0	0	1
0	0	0	1	0
0	0	1	0	0
0	0	1	1	0
0	1	0	0	1
0	1	0	1	0
0	1	1	0	0
0	1	1	1	1
1	0	0	0	1
1	0	0	1	0
1	0	1	0	0
1	0	1	1	0
1	1	0	0	1
1	1	0	1	0
1	1	1	0	1
1	1	1	1	1

б) Зададим функции таблицей
(табл. 2.23).

1-й этап. Построим
сокращенную ДНФ функции:

Переход I: операция
неполного склеивания применена к парам
конъюнкций 1 и 2, 1 и 4, 2 и 5, 3 и 7, 4 и 5, 5 и 6,
6 и 7.

Переход II: применена
операция поглощения — каждая из конъюнкций
4-го ранга поглощена какой-то из конъюнкций
3-го ранга.

Переход III: операция
неполного склеивания применена к парам
конъюнкций 8 и 12, 9 и 10.

Переход IV: применена
операция поглощения и убраны дублирующие
члены.

Итак, мы нашли сокращенную ДНФ функции:
.

2-й этап. Введем
обозначения для простых импликант
функции:
,
,
,
.
Составим импликантную таблицу (табл.
2.24).

_{Таблица 2.24}
	₀₀₀₀	0100	₀₁₁₁	1000	₁₁₀₀	₁₁₁₀	₁₁₁₁
	₀	0	₁	0	₀	₀	₁
	0	0	0	0	1	1	0
	₀	0	₀	0	₀	₁	₁
	1	1	0	1	1	0	0

Тогда

Таким образом, имеем две тупиковые ДНФ,
реализующие функцию
:

3-й этап. Тупиковые
ДНФ функции

имеют одинаковую сложность (равную 8),
и, следовательно, обе являются минимальными.
►

Источник

6.1 Сокращенная и тупиковая ДНФ

6.2 Метод импликантных матриц

Цель данного раздела – изложение основных методов построения минимальных дизъюнктивно нормальных форм.

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

Дизъюнктивная нормальная форма называется Минимальной, если она включает минимальное число символов по сравнению со всеми другими эквивалентами ей дизъюнктивными нормальными формами.

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

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

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

Число различных ДНФ, составленных из переменных , равно .

Прежде чем доказать данное утверждение, приведем следующее определение.

Конъюнкция называется Элементарной, если при .

Число R называется Рангом элементарной конъюнкции. В случае r=0 конъюнкция называется Пустой и Полагается равной 1.

Так как каждая из N переменных либо не входит в элементарную, либо входят в нее с отрицанием, либо без отрицания, то число элементарных конъюнкций, составленных из равно . Ясно, что число различных ДНФ, составленных из переменной , равно числу подмножеств множества, из элементов, т. е. .

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

Обозначим через множество всех точек , где . Ясно, что — множество всех вершин единичного n-мерного куба.

Сопоставим каждой булевой функции Подмножество Из , определенное следующим образом:

Например, функции

X	Y	Z
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

Соответствует подмножество

Вершин трехмерного единичного куба

Данное соответствие является взаимно однозначным и обладает следующими свойствами:

1) булевой функции Соответствует подмножество ;

2) булевой функции соответствует подмножество ;

3) булевой функции соответствует подмножество .

Докажем утверждение 2. Пусть

Отсюда .

Тогда .

А это значит, что .

Отсюда .

Пусть ДНФ, где — элементарные конъюнкции. Подмножество называется интервалом R-го ранга, если оно соответствует элементарной конъюнкции К R-го ранга. Как показано выше, . Итак, с каждой ДНФ функции F связано покрытие такими интервалами , что .

Пусть — ранг интервала . Тогда совпадает с числом букв в ДНФ функции .

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

Интервал , содержащий , называется Максимальным для булевой функции, если не существует интервала , такого, что .

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

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

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

Ясно, что сокращенная ДНФ для любой булевой функции f определяется однозначно.

Пример 1. Пусть . Обозначим , , . Найдем соответствующие этим конъюнкциям интервалы , , .

Изобразим эти интервалы

Очевидно, что и — все максимальные интервалы. Интервал не является максимальным, ибо . Следовательно, покрытию подмножества соответствует сокращенная ДНФ функции , равная .

Данный геометрический подход дает и метод построения сокращенной ДНФ.

Теперь рассмотрим аналитический метод построения сокращенной ДНФ – метод Блейка. Этот метод основан на следующей теореме.

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

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

Пример 2. Найти сокращенную ДНФ для функции . Применяя правило обобщенного склеивания, получаем: .

Затем правило поглощения и находим сокращенную ДНФ: .

Рассмотрим еще один метод построения сокращенной ДНФ – метод Нельсона. Этот метод основан на следующей теореме.

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

Пример 3. Найти сокращенную ДНФ для функции

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

Так как , , то имеем:

Далее, применяя правило поглощения, получаем сокращенную ДНФ:

Рассмотрим табличный метод построения сокращенной ДНФ. Этот метод основан на составлении прямоугольной таблицы (минимизирующей карты).

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

Z X y	0	1
00
01
11
10

X4 X3 X1 X2	0 0	0 1	1 1	1 0
0 0
0 1
1 1
1 0

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

Пример 4. Найти сокращенную ДНФ для функции, заданной следующей таблицей.

X4 X3 X1 X2	0 0	0 1	1 1	1 0
0 0	1	1	0	1
0 1	0	1	1	0
1 1	1	1	1	0
1 0	0	1	0	0

В данной таблице объединены клетки в максимальные интервалы

Этим интервалам соответствуют элементарные конъюнкции

, , , ,

Следовательно, сокращенная ДНФ для данной функции имеет вид:

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

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

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

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

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

Пусть К – элементарная конъюнкция, входящая в сокращенную ДНФ. Предположим, что К содержит отрицание переменных. Обозначим через произведение всех переменных, входящих в К без отрицания. Пусть – набор переменных, в которых всем переменным, входящим в , приписано значение 1, а всем остальным – значение 0. Ясно, что при этом наборе значение функции Равно 1. Элементарная конъюнкция обращается в 1 при всех наборах . Очевидно, что при этих наборах значение функции также равно 1. Следовательно, .

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

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

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

Элементарная конъюнкция поглощается дизъюнкцией остальных элементарных конъюнкций, т. е. .

Ввиду этого введем следующее определение.

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

Теорема 5. Всякая минимальная ДНФ является тупиковой.

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

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

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

1. Выделяются все максимальные интервалы, и строится сокращенная ДНФ.

2. Строятся все тупиковые ДНФ.

3. Среди всех тупиковых ДНФ выделяются все минимальные ДНФ.

Рассмотрим алгоритм построения всех тупиковых ДНФ. Суть данного алгоритма состоит в следующем:

1) для булевой функции строим сокращенную ДНФ;

2) для каждой вершины из выделяем в сокращенной ДНФ функции F все такие элементарные конъюнкции , что ;

3) составляем выражение вида

(*)

4) применяем к выражению вида (*) законы дистрибутивности и поглощения. В результате получаем .

Теперь каждая ДНФ является тупиковой ДНФ функции .

Рассмотрим работу данного алгоритма на следующем примере.

Пример 5. Рассмотрим булеву функцию, заданную следующей таблицей:

X	Y	Z
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	0

Найдем сокращенную ДНФ данной функции по методу Нельсона. Для этого составим КНФ данной функции .

Применяя законы дистрибутивности, получаем:

Обозначим , , , , , .

Составляем выражение (*)

Преобразуем данное выражение к виду

= =.

Таким образом, имеет шесть тупиковых ДНФ:

Две из них и являются минимальными.

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

	…		…


…
		+
…

Для каждой находим набор такой, что .

Клетку импликантной матрицы, образованную пересечением I-строки и J-столбца отметим крестиком.

Чтобы получить минимальную ДНФ заданной функции, достаточно найти минимальное число , которые совместно накрывают крестиками все столбцы импликантной матрицы.

Пример 6. Найти минимальные ДНФ для функции

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

Строим импликантную матрицу

(0,0,1)	(0,1,0)	(0,1,1)	(1,0,0)	(1,0,1)	(1,1,0)
			+	+
			+		+
	+	+
	+				+
+		+
+				+

Отсюда видно, что данная функция имеет два минимальные ДНФ:

; .

Вопросы для самоконтроля.

1. Дайте определение основных логических операций булевой алгебры.

2. Дайте определение булевой функции.

3. Что такое таблицы истинности булевой функции?

4. Каково число булевых функций от переменных?

5. Какие булевы функции называются элементарными?

6. Дайте определение формулы алгебры логики.

7. Какие формулы алгебры логики называются равносильными?

8. Сформулируйте законы алгебры логики.

9. Какая формула алгебры логики называется двойственной к данной формуле алгебры логики?

10. Сформулируйте принцип двойственности.

11. Сформулируйте теорему о разложении и следствие из нее.

12. Дайте определение СДНФ.

13. Приведите алгоритмы построения СДНФ.

14. Дайте определение СКНФ.

15. Приведите алгоритмы построения СКНФ.

16. Дайте определение ДНФ.

17. Как найти ДНФ?

18. Дайте определение КНФ.

19. Как найти КНФ?

20. Какая формула алгебры логики называется тождественно истинной?

21. Какая формула алгебры логики называется тождественно ложной?

22. Какая формула алгебры логики называется выполнимой?

23. Что называется проблемой разрешимости?

24. Сформулируйте методы решения проблемы разрешения.

25. Что называется алгеброй Жегалкина?

26. Сформулируйте законы алгебры Жегалкина.

27. Что называется полиномом Жегалкина?

28. Сформулируйте алгоритмы построения полиномов Жегалкина.

29. Какая система булевых функций называется полной?

30. Что называется замыканием множества булевых функций?

31. Какой класс булевых функций называется замкнутым?

32. Дайте определение пяти важнейших замкнутых классов.

33. Сформулируйте теорему о полноте.

34. Сформулируйте алгоритм Поста.

35. Какая система булевых функций называется несократимой?

36. Каково максимальное возможное число функций в несократимой полной системе булевых функций?

37. Что такое релейно-контактная схема?

38. Почему любую булеву функцию можно изобразить в виде релейно-контактной схемы?

39. В чем состоит проблема анализа релейно-контактных схем?

40. В чем состоит проблема синтеза релейно-контактных схем?

41. Что такое логические элементы?

42. Приведите геометрическое изображение логических элементов.

43. Что такое логическая схема?

44. Что Вы понимаете под двоичным сумматором?

45. Какая ДНФ называется минимальной?

46. Чему равно число всех ДНФ от переменных?

47. Сформулируйте тривиальный алгоритм построения МДНФ?

48. Что такое элементарная конъюнкция?

49. Что такое ранг элементарной конъюнкции?

50. Что называется интервалом элементарной конъюнкции?

51. Какой интервал называется максимальным?

52. Что называется областью истинности булевой функции?

53. Сформулируйте теорему об области истинности булевой функции.

54. Что называется покрытием области истинности булевой функции?

55. Какое число элементов содержится в интервале?

56. Какая ДНФ называется сокращенной?

57. В чем состоит геометрическая интерпретация задачи минимизации булевой функции?

58. Сформулируйте геометрический метод построения сокращенной ДНФ.

59. Сформулируйте метод Нельсона построения сокращенной ДНФ.

60. Сформулируйте метод Блейка построения сокращенной ДНФ.

61. Сформулируйте метод карт Карно построения сокращенной ДНФ.

62. Какая связь между МДНФ и сокращенной ДНФ?

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

64. Какая ДНФ называется тупиковой?

65. Какая связь между МДНФ и тупиковой ДНФ?

66. Сформулируйте алгоритм построения всех тупиковых ДНФ.

67. Как строится импликантная матрица?

68. Сформулируйте алгоритм нахождения МДНФ методом импликантных матриц.

< Предыдущая		Следующая >

Источник

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

Уточним задачу.

Определение 6.5. Булеву функцию g называют импликантой* булевой функции f, если для любых наборов значений переменных из g = 1 следует f = 1.

*иногда употребляют и термин «импликант» (мужского рода).

Замечание 6.7. Напомним, что функции f и g можно рассматривать
как функции от одного и того же числа переменных
(см. 6.3). Обозначая это число через n, можно так уточнить
понятие импликанты: функция g ∈ P_2,n есть импликанта функции f
∈ P_2,n, если для каждого набора α˜ ∈ Bⁿ из g(α˜)= 1 следует
f(α˜)= 1. Термин «импликанта» естественным образом ассоциируется
и с логической связкой, называемой импликацией, и с
одноименной булевой функцией. Действительно, если g импликанта
f, то из (g → f) = 1 и g = 1 следует, что и f = 1, т.е.
истинно высказывание

(∀α˜ ∈ Bⁿ)((g(α˜) = 1) ⇒ (f(α˜) = 1)). #

Если функция f представлена СДНФ, то любая ее элементарная
конъюнкция (конституента единицы функции f) будет
ее импликантой. Полезно заметить также, что если g₁ и g₂ —
импликанты f, то дизъюнкция g₁ ∨ g₂ также является импликантой f.
Действительно, если g₁ ∨ g₂ = 1, то g₁ = 1 или g₂ = 1.
Но тогда, поскольку каждая из этих функций есть импликанта
f, и g₁ ∨ g₂ есть импликанта f.

Из определения 6.5 и понятия равных булевых функцuй (см.
определение 6.2) следует, что булевы функции f и g равны,
если и только если каждая из них служит импликантой другой:
f =1 ⇔ g= 1.

Определение 6.6. ДНФ называют минимальной, если
она содержит наименьшее число литералов среди всех ДНФ,
эквивалентных ей.

Обратим внимание на то, что под числом литералов в ДНФ
понимают число всех подформул этой ДНФ, которые являются
литералами. Так, СДНФ (6.9) содержит 12 литералов (по три
литерала в каждой из четырех элементарных конъюнкций).

Пример 6.10. ДНФ х₁х₂ ∨ х₁х₂ не является минимальной,
так как ее можно преобразовать к эквивалентной ДНФ, не
содержащей ни рдного из литералов х˜₁:

х₁х₂ ∨ х˜₁₁х₂ = (х₁ ∨ х˜₁)х₂ = х₂.

Вместо четырех литералов в исходной ДНФ получаем ДНФ,
состоящую из одного литерала.

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

ДНФ называют кратчайшей, если она имеет наименьшую
длину среди всех эквивалентных ей ДНФ.

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

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

Опишем последовательно этапы, составляющие алгоритм
Квайна — Мак-Клоски.

1. Склейка. Пусть К₁ и К₂ — две элементарные конъюнкции,
входящие в исходную СДНФ Ф, которая представляет
функцию f, причем для некоторого переменного х и некоторой
элементарной конъюнкции К выполняются равенства К₁ = хК
и К₂ = xК.

Тогда имеем, согласно тождествам булевой алгебры,

К₁ ∨ К₂ = xK ∨ xK = (x ∨ x)K = K.

Мы получаем элементарную конъюнкцию К, которая содержит
на один литерал меньше, чем К₁ и К₂, и является, как и обе
конъюнкции К₁ и К₂, импликантой f. Образно говоря, мы
«склеили» две импликанты в одну, в которой число литералов
на единицу меньше.

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

Установим геометрический смысл простой склейки* (с точки
зрения структуры, или «геометрии», булева куба, см. 6.1).

Из доказательства теоремы о представлении булевой функции
в виде ДНФ (см. теорему 6.2) мы знаем, что существует
взаимно однозначное соответствие между множеством элементарных
конъюнкций СДНФ, представляющей функцию f,
и множеством С^1f ее конституент единицы. Это соответствие, напомним, таково, что каждому набору α˜ = (α₁, …, α_n) ∈ С^1f ,
отвечает элементарная конъюнкция К_{α_˜} =
x^α₁1 ⋅…⋅ x^α_nn , принимающая
значение 1 только на наборе α˜. Тогда простая склейка
может быть применена только к таким двум элементарным
конъюнкциям К_α˜ и К_β˜, соответствующим наборам α˜, β˜ ∈ С^1f, что для некоторого i = (1 ≤ i ≤ n)

α˜ = (α₁, …, α_i-1, α_i, α_i+1, …, α_n),

β˜ = (α₁, …, α_i-1, α_i, α_i+1, …, α_n).

Это значит, что наборы α˜, β˜ таковы, что один из них доминирует
над другим (они различаются значением только одной
компоненты), т.е. они образуют ребро булева куба Bⁿ.

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

С алгебраической же точки зрения мы из двух элементарных
конъюнкций К_α˜ и К_β˜ получаем новую элементарную
конъюнкцию x^α₁1 … x^α_i-1i-1 x^α_i+1i+1 … x^α_nn , лишенную литерала x^α_ii .

*подробно о геометрической сути минимизации см.: Яблонский С.В.

Итак, применяя простую склейку к исходной СДНФ Ф, получаем новую ДНФ Ф₁; к ней также применяем простую склейку — получаем ДНФ Ф₂; продолжаем выполнять эту операцию
до тех пор, пока не окажется, что для некоторого k в ДНФ
Ф_k уже нельзя склеить никакие две элементарные конъюнкции.
Такое k всегда найдется, так как СДНФ Ф состоит из конечного
числа элементарных конъюнкций, а они, в свою очередь,
состоят из конечного числа литералов. Полученную в результате
ДНФ Ф_k называют сокращенной ДНФ функции f, а
ее элементарные конъюнкции — простыми импликантами
булевой функции f.

Замечание 6.8. Понятие простой импликанты определено
через процедуру многократного повторения простой склейки.
Иногда простую импликанту булевой функции f определяют
независимо от понятия о склейке как такую элементарную
конъюнкцию в составе некоторой ДНФ, представляющей функцию
f, что удаление из нее любого литерала лишает ее свойства
«быть импликантой». Например, конъюнкция х₁х₂x₃ не является простой импликантой мажоритарной функции, так как из
ее СДНФ (6.9) можно удалить литерал x₃ и получить конъюнкцию
х₁х₂, которая будет снова импликантой функции, но уже,
как будет показано далее, простой.

Можно доказать, что эти два определения простой импликанты
равносильны. #

Геометрия описанного выше многократного повторения простой склейки, как можно показать, состоит в дальнейшем «склеивании» каждой пары соседних ребер (граней размерности 1),
на которых значение функции равно 1, в грани размерности 2,
соседних граней размерности 2 в грани размерности 3 и т.д.
Разбираемый ниже пример поясняет эту идею.

Пример 6.11. Зададим функцию f от трех переменных
следующей СДНФ:

f = x₁x₂x₃ ∨ x₁x₂х₃ ∨ х₁x₂x₃ ∨ х₁x₂х₃. (6.11)

Подвергнем простой склейке первую и третью, а также вторую
и четвертую элементарные конъюнкции в (6.11):

f = x₂x₃ ∨ x₂x₃ (6.12)

С геометрической точки зрения склейка первой и третьей конъюнкций
в формуле (6.11) означает, что функция f принимает
единичное значение на ребре [000, 100] (рис. 6.6), а склейка
второй и четвертой конъюнкций точно
так же определяет ребро [001, 101).
Эти ребра являются соседними, и, кроме
того, оказывается, что функция f
принимает единичное значение и на
другой паре соседних ребер: [000, 001]
и [100, 101]. Здесь сказывается существенное
отличие «геометрии» булева
куба от классической: в булевом кубе
ребро — это пара вершин, между
которыми нет никаких «точек». Тогда любая пара соседних
ребер образует грань размерности 2, любая пара соседних граней
размерности 2 образует грань размерности 3 и т.д. Таким
образом, если функция принимает единичное значение на двух
соседних ребрах булева куба, то она равна 1 в любой точке
образуемой ими грани размерности 2, если она равна 1 на двух
параллельных соседних гранях размерности 2, то она равна 1
на соответствующей грани размерности 3 и т.д.

Применяя простую склейку к (6.12) (по переменному х₃),
получаем f(х₁,х₂,х₃) = x₂. Побочным результатом склейки
явилось и удаление фиктивных переменных функции х₁ и х₃.

Пример 6.12. Рассмотрим СДНФ мажоритарной функции (6.9).

Имеем следующие склейки:

x₁х₂х₃ ∨ х₁х₂х₃ = х₂х₃,

х₁x₂х₃ ∨ х₁х₂х₃ = х₁х₃,

х₁х₂x₃ ∨ х₁х₂х₃ = х₁х₂.

В данном случае сразу получаем сокращенную ДНФ:

Ф₁ = x₁x₂ ∨ x₁x₃ ∨ x₂x₃. #

Для булевых функций от трех и четырех переменных процедура
склейки наглядно и просто выполняется на так называемых картах Карно. Форма карт Карно, представляющих собой
прямоугольные таблицы, для функции от трех переменных
показана на рис. 6.7, а для функции от четырех переменныхна
рис. 6.8. На рис. 6.7 строки отмечены наборами значений
переменного х₁, а столбцы — х₂, х₃, а на рис. 6.8 строки —
наборами значений переменных х₁, х₂, а столбцы — х₃, x₄.

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

С геометрической точки зрения карта Карно есть способ
изображения булева куба (размерностей 3 и 4)*. Любая пара
соседних клеток (с учетом «закрученности» карты) определяет
некоторое ребро булева куба, а любой прямоугольник, состоящий
из 2^k клеток (или, как говорят, прямоугольник с площадью
2^k) для некоторого k, определяет грань размерности k.

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

С геометрической точки зрения такой прямоугольник площади
2 соответствует ребру булева куба, в каждой вершине которого функция принимает значение 1. Запись прямоугольника в виде слова можно понимать как обозначение соответствующего ребра. Так, на карте, показанной на рис. 6.9, прямоугольник
11× обозначает ребро [110, 111], прямоугольники же 1×1 и
×11 — ребра [101, 111] и [011, 111] соответственно.

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

По таким обозначениям легко получить и ту импликанту,
которая является результатом простой склейки: для этого
достаточно записать литерал x_i (соответственно x_i), eсли в i-й позиции стоит 1 (соответственно 0), и пропустить литерал x_i,
если в i-й позиции стоит «крестик». Так, по слову 1×O получим
импликанту x₁x₃.

Наличие на карте Карно двух прямоугольников площади 2,
находящихся в соседних столбцах или строках, показывает, что
функция принимает значение 1 на некоторой паре соседних
ребер, т.е. на некоторой грани размерности 2. Тогда они могут
быть объединены в один большой прямоугольник площади 4 (рис. 6.10).

Этот прямоугольник можно записать в виде слова ×0×,
показывая тем самым, что соответствующая грань (размерности 2) образована любой из двух пар соседних ребер: (×00, ×01) (два вертикальных прямоугольника площади 2) или (00×, 10×)
(два горизонтальных прямоугольника площади 2).

Точно так же можно объединять в один прямоугольник
площади 8 два соседних прямоугольника площади 4 (рис. 6.11).

Если такие большие прямоугольники находить сразу, то
«поглощаемые» ими меньшие прямоугольники уже не рассматриваются.
Тем самым, находя на карте Карно прямоугольники
максимальной площади и не содержащиеся друг в друге, мы
находим грани максимальных размерностей и максимальные по
включению, такие, на которых заданная функция принимает
единичное значение. Поскольку грань размерности k имеет
2^k вершин, то выделяемые описанным способом прямоугольники
могут состоять только из 2^k клеток (для некоторого k,
не превышающего числа переменных). Так, на карте, приведенной
на рис. 6.12, получим два прямоугольника площади 4:
×0×0 и 0×0×, соответствующие граням размерности 2, и один
прямоугольник 01×1, отвечающий ребру, которое не содержится
ни в одной из указанных выше граней. Подчеркнем еще
раз, что соседство клеток, прямоугольников и само выделение
прямоугольников на карте Карно производится с учетом
ее «закрученности». В этой связи интересен «прямоугольник»
на карте, приведенной на рис. 6.12, обозначенный ×0×0. Он
образован двумя парами противоположных угловых клеток.

Таким образом, если на карте Карно сразу выделять все
максимальные (в указанном выше смысле) прямоугольники площади
2^k (для некоторого k ≥ 0 и не превышающего числа
переменных), то тем самым мы «геометрически» реализуем
описанный ранее алгебраический итерационный процесс склейки
и в результате получаем все простые импликанты исходной
функции (составляющие сокращенную ДНФ). Эти импликанты
восстанавливаются по записям прямоугольников точно так
же, как описано выше для простой склейки. Так, для карты,
приведенной на рис. 6.12, получим сокращенную ДНФ в виде
x₂x₄ ∨ x₁x₃ ∨ x₁x₂x₄.

2. Определение ядра. Говорят, что элементарная конъюнкция
К покрывает элементарную конъюнкцию L (и пишут
К ≻ L), если любой литерал, входящий в К, входит в L. Так,
x₁x₂ ≻ x₁x₂x₃, x₁x₃ ≻ x₁x₂x₃, но x₁x₃ ⊁ x₁x₂x₃, поскольку вторая
конъюнкция содержит литерал x₃, отсутствующий в первой
конъюнкции. Легко понять, что если К ≻ L, то К ∨ L = К (согласно
тождествам поглощения).

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

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

Множество всех ядровых импликант (склеек) сокращенной
ДНФ называют ядром.

Пример 6.13. а. У мажоритарной функции все импликанты
являются ядровыми. Напротив, у функции, изображенной
на карте Карно на рис. 6.13, ядро пусто, т.е. ядровых импликант
нет вовсе.

б. На карте Карно на рис. 6.14 в ядро попадают склейки
0××1, 0×1×, 1×00. #

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

В остальных случаях переходят к отысканию так называемых
тупиковых ДНФ.

3. Перечисление тупиковых ДНФ. Простую импликанту
называют избыточной (относительно некоторой ДНФ,
содержащей только простые импликанты и эквивалентной исходной
СДНФ), если ее можно удалить из этой ДНФ без потери
эквивалентности ее исходной СДНФ. Так, сокращенная ДНФ
(см. рис. 6.14) содержит избыточные импликанты: импликанта,
соответствующая прямоугольнику 10 × 0, или импликанта, соответствующая
прямоугольнику ×010, может быть удалена (но не
обе сразу!). Это значит, что каждая из этих импликант является
избыточной относительно сокращенной ДНФ, но удаление
одной из них приводит к новой ДНФ, относительно которой
вторая из упомянутых импликант уже не будет избыточной. В
том случае, когда каждую элементарную конъюнкцию исходной
СДНФ покрывает некоторая ядровая импликанта, импликанты,
не вошедшие в ядро, можно удалить одновременно.

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

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

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

Для СДНФ, карта Карно которой приведена на рис. 6.14,
имеются две тупиковые ДНФ:

x₁x₄ ∨ x₁x₃ ∨ x₁x₃ ⋅ x₄ ∨ x₂x₃x₄,
x₁x₄ ∨ x₁x₃ ∨ x₁x₃ ⋅ x₄ ∨ x₁x₂ ⋅ x₄.

Первые три конъюнкции соответствуют ядру.

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

Присвоим каждой простой импликанте сокращенной ДНФ
некоторое имя: т.е. обозначим их, например, как К¹, К², …,
К^m. Для любой единицы карты Карно, не покрываемой ядром,
перечислим все простые импликанты, которые ее покрывают,
записав их в виде элементарной дизъюнкции, в которой переменными
считаются введенные выше имена простых импликант.
Переменное, именующее данную простую импликанту,
при нимает, по определению, значение 1, если данная простая
импликанта выбирается для покрытия рассматриваемой единицы
карты Карно.

Записав все элементарные дизъюнкции, составим из них
КНФ. Рассмотрим карту Карно на рис. 6.13. Обозначив

К¹ = х¹x² (10×), К² = x²х³ (01×), К³ = x¹х³ (0×1),
К⁴ = x¹x² (01×), , К⁵ = х²x³ (×10), К⁶ = х¹x³ (1×0),

получим

(К₁ ∨ К₆) ∧ (К₁ ∨ К₂) ∧ (К₂ ∨ К₃) ∧
Л (К₃ ∨ К₄) ∧ (К₄ ∨ K₅) ∧ (K₅ ∨ К₆). (6.13)

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

Для нашего примера поступим так: вычислим конъюнкцию
первой и второй скобки в выражении (6.13), а также третьей и
четвертой, пятой и шестой скобок, после чего получим

(K₁ ∨ K₁K₂ ∨ K₆K₁ ∨ K₆K₂) ∨ (K₂K₃ ∨ K₂K₄ ∨ K₃ ∨ K₃K₄) ∨ (K₄K₅ ∨ K₄K₆ ∨ K₅ ∨ K₅K₆). (6.14)

Используя тождества поглощения, в первой скобке в формуле
(6.14) мы можем удалить все члены, содержащие К₁, во
второй скобке — все члены, содержащие К₃, в третьей скобке
— все члены, содержащие К₅. Проделав это, раскрыв все
три скобки и применив еще раз поглощение, окончательно получим

K₁K₃K₅ ∨ K₁K₃K₄K₆ ∨ K₁K₂K₄K₅ ∨ K₂K₃K₅K₆ ∨ K₂K₄K₆. (6.15)

Элементарные конъюнкции в (6.15) определяют тупиковые
ДНФ. Более того, так как в данном случае отсутствуют ядровые
импликанты, найденные конъюнкции исчерпывают тупиковые
ДНФ. Первая тупиковая ДНФ состоит из конъюнкций
К₁, К₃ и K₅, т.е. имеет вид

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

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

4. Отыскание среди тупиковых ДНФ кратчайших
и минимальных. Среди найденных тупиковых ДНФ находят кратчайшие и минимальные. Можно легко показать, что минимальная ДНФ всегда является кратчайшей, но обратное
неверно. Так, х₁х₂ ∨ х₁ = х₁ ∨ х₁ и первая ДНФ кратчайшая, но не минимальная. Действительно, легко сообразить, что
вторая из записанных ДНФ минимальна. Следовательно, представляемую
ею функцию нельзя представить ДНФ, содержащей
менее двух элементарных конъюнкций. Но в первой ДНФ три
литерала, а во второй — два. Из пяти тупиковых ДНФ, соответствующих
функции Патрика (6.15), кратчайшими являются
две. Каждая из них минимальна, так как обе они имеют одинаковое
число литералов.

Пример 6.14. Рассмотрим карту Карно на рис. 6.15.

В результате проведения склейки получим следующую сокращенную
ДНФ*:

x₁x₃ ∨ x₁x₂ ∨ x₂x₄ ∨ x₂x₃ ∨ x₃x₄ ∨ x₁x₂x₄ ∨ x₁x₂x₃ ∨ x₁x₃x₄

Ядро составляют склейки (простые импликанты) x₁x₃ и x₁x₂.

Шесть клеток, содержащих единицу, на карте Карно остаются
непокрытыми ядровыми склейками. Для неядровых склеек
(обозначенных К¹, …, К⁶) составляем функцию Патрика в
виде

(K₃ ∨ K₄)(K₄ ∨ K₅)(K₅ ∨ K₆)(K₁ ∨ K₂)(K₂ ∨ K₃)(K₁ ∨ K₆)

Преобразуя ее аналогично функции (6.13), получаем

K₁K₃K₅ ∨ K₂K₄K₆ ∨ K₂K₃K₅K₆ ∨ K₁K₂K₄K₅ ∨ K₁K₃K₄K₆.

Имеем, следовательно, пять тупиковых ДНФ. Запишем их, для
наглядности, так:

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

В итоге получаем минимальную ДНФ в виде

x₁x₃ ∨ x₁x₂ ∨ x₂x₄ ∨ x₃x₄ ∨ x₁x₂x₃.

* Обратим еще раз внимание на то, что каждый выделяемый прямоугольник
на карте Карно имеет площадь, равную некоторой степени двойки.
Поэтому, например, три соседние единичные клетки не могут быть объединены
в один прямоугольник, а их «накроют» два прямоугольника площадью 2, пересекающиеся по одной клетке.

В данном случае минимальная ДНФ оказалась единственной,
хотя, как это мы видели в ранее разобранных примерах, в
общем случае могут существовать несколько минимальных
ДНФ. #

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

Первое из тождеств (6.16) называют тождеством (или
правилом) обобщенного склеивания, второе — тождеством
(или правилом) nоглощения.

Технология» использования метода Блейка такова: применяют
тождество обобщенного склеивания до тех пор, пока не
перестанут появляться новые элементарные конъюнкции (вида
К₁К₂). После этого применяют тождество поглощения*.

* См.: Гавршов Г.П., Сапожекко А.А.

Для примера 6.13.б (см. рис. 6.14) получим таблицу Квайна,
изображенную на рис. 6.16.

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

По таблице Квайна можно составить и функцию Патрика
для перечисления тупиковых ДНФ. Для этого нужно отметить
все столбцы таблицы, в которых на пересечении со строками,
соответствующими ядровым импликантам, не стоит знак «+».
Для разбираемого примера таковым является только последний
столбец. Чтобы покрыть соответствующую элементарную
конъюнкцию СДНФ, можно выбрать одну из двух простых импликант:
х₁x₁x₁ или x₂x₃x₄.

В заключение рассмотрим очень кратко применение карт
Карно к построению минимальных ДНФ частичных булевых
функций, т.е. частичных отображений из множества
{0, 1}ⁿ в множество {0, 1}.

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

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

Пример 6.15. Пусть частичная функция f(х₁,х₂,х₃) задана картой Карно, приведенной на рис. 6.17. Прямоугольник максимальной
площади (равной 4), состоящий из единицы и прочерков,
записывается как 0××. Следовательно, минимальная ДНФ для заданной функции будет x₁. #

По поводу рассмотренного примера возникает такой вопрос: почему не принят во внимание
другой прямоугольник (площади 2), содержащий клетку с единицей
и клетку с прочерком: х00? Связано это вот с чем.
Перед тем как выделять упомянутые вьппе прямоугольники,
мы на самом деле доопределяем исходную частичную функцию
(получая обычную булеву функцию) так, чтобы в максимальном
числе клеток, в которых стоят прочерки (но не нули!),
появились единицы. Точнее говоря, среди прямоугольников
(с прочерками), содержащих данную единицу, выбирают для
замены прочерков единицами такой, который имеет максимальную
площадь. Прочерки же в остальных прямоугольниках
заменяют нулями.

В примере 6.15 мы доопределяем исходную функцию так,
что получается функция f₁, задаваемая картой Карно, приведенной на рис. 6.18. Эта функция имеет минимальную ДНФ
x₁. Следовательно, и частичная исходная функция может быть
представлена такой ДНФ, поскольку на всех наборах, на которых
она определена, она принимает такое же значение, как и
функция f₁.

Конечно, мы могли бы доопределить функцию f по-другому, так, чтобы получилась функция f₂, заданная картой Карно,
приведенной на рис. 6.19. Ясно, что f₂ = х₂х₃, поэтому и частичная функция f может быть определена такой ДНФ. Но эта
ДНФ не минимальна для данной частичной (именно частичной!)
функции, поскольку первый способ доопределения дал
ДНФ, содержащую лишь один литерал.

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

Пример 6.16. Для карты на рис. 6.20 следует взять обе
склейки на четыре позиции: 00×× и ××00, получив для заданной
этой картой частичной функции минимальную ДНФ в виде
x₁x₂ ∨ x₃x₄.

Заметим, что без использования склеек с прочерками мы
вообще не могли бы минимизировать данную функцию. Нужно также отметить, что не всегда
использование «частичности»
функции позволяет получить минимальную
ДНФ для нее. Так, на представленной на рис. 6.20
карте в случае, если мы переместим
нижнюю единицу на строку выше, обычная склейка на две
позиции дает лучший результат:
x₁x₃x₄, а записанная выше ДНФ
уже не будет минимальной (и даже кратчайшей).

Источник