Как найти все минимальные днф

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

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

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

Замечание 6.7. Напомним, что функции и можно рассматривать как функции от одного и того же числа переменных. Обозначая это число через , можно так уточнить понятие импликанты: функция есть импликанта функции если для каждого набора a из следует . Термин “импликанта” естественным образом ассоциируется и с логической связкой, называемой импликацией, и с одноименной булевой функцией. Действительно, если д импликанта , то из и следует, что , т.е. истинно высказывание

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

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

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

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

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

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

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

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

---

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

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

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

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

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

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

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

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

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

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

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

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

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

---

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

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

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

---

Карты Карно

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

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

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

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

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

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

По таким обозначениям легко получить и ту импликанту, которая является результатом простой склейки: для этого достаточно записать литерал (соответственно ), если в i-й позиции стоит 1 (соответственно 0), и пропустить литерал ж», если в i-й позиции стоит “крестик”. Так, по слову 1×0 получим импликанту .

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

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

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

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

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

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

, но .

Поскольку вторая конъюнкция содержит литерал , отсутствующий в первой конъюнкции. Легко понять, что если , то (согласно тождествам поглощения).

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

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

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

---

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

б. На карте Карно на рис. 6.14 в ядро попадают склейки .

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

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

---

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

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

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

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

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

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

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

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

получим

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

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

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

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

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

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

---

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

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

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

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

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

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

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

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

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

---

Метод Блейка

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

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

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

---

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

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

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

---

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

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

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

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

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

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

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

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

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

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

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

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

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

Минимальной ДНФ (МДНФ) функции F(X1, … ,Xn) называется ДНФ, реализующая функцию F и содержащая минимальное число символов переменных по сравнению со всеми другими видами ДНФ, реализующими функцию F.

Если для всякого набора = (A1, …, An) значений переменных условие G( )=1 влечёт , то функция G называется частью функции F (или функция F накрывает функцию G). Если при этом для некоторого набора = (C1, …, Cn) функция G( )=1, то говорят, что функция G накрывает единицу функции F на наборе (или что G накрывает конституенту единицы функции F). Заметим, что конституента единицы функции F есть часть функции F, накрывающая единственную единицу функции F.

Элементарная конъюнкция K называется импликантом функции F, если для всякого набора =(A1, …, An) из 0 и 1 условие K( )=1 влечет F( )=1.

Импликант K функции F называется простым, если выражение, получающееся из него выбрасыванием любых множителей, уже не импликант функции F.

Ясно, что всякий импликант функции F есть часть функции F.

Теорема. Всякая функция реализуется дизъюнкцией всех своих простых имликант (ПИ).

Доказательство. Пусть F(X1, …, Xn) есть функция, а A = K1 v… v Km – дизъюнкция всех ее простых импликант. Пусть = (A1, …, An) – произвольный набор длины N из 0 и 1.

Если A( ) = 1, то найдется дизъюнктивное слагаемое Ki ( ) = 1, что влечет F( ) = 1, ибо Ki есть импликант функции F.

Если F( ) = 1, то в СДНФ для функции F найдется элементарная конъюнкция K, равная на этом наборе единице. Один из простых имликантов Kj функции F получается выбрасыванием некоторых множителей из K и потому Kj( ) = 1, а тогда A( ) = 1.

Следовательно, F = A. Теорема доказана.

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

Пусть A и B – произвольные формулы. Из свойств булевых операций вытекают следующие обратимые правила преобразования ДНФ:

1) – полное склеивание (развертывание);

2) – неполное склеивание;

3) – обобщенное склеивание;

4) – поглощение;

5) – идемпотентность ( удаление дублирующих членов).

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

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

Алгоритм Квайна построения сокращенной ДНФ.

1. Получить СДНФ функции F.

2. Провести все операции неполного склеивания.

3. Провести все операции поглощения.

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

Таблица 3.1

X Y Z T	0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
F	1 1 1 1 0 1 0 0 1 0 1 0 1 1 1 1

1. Строим СДНФ функции F:

. Пронумеруем дизъюнктивные члены в полученной СДНФ в порядке от 1 до 11.

2. Проводим все операции неполного склеивания.

Первый этап склеивания в таблице 3.2.

После первого этапа склеиваний (и возможных поглощений) получаем, что

Пронумеруем дизъюнктивные члены в полученной ДНФ в порядке их следования от 1 до 15.

Второй этап склеиваний в таблице 3.3.

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

Таблица 3.2

Слагаемые	Склеивание по	Результат
1,2	T
1,3	Z
1,6	X
2,4	Z
2,5	Y
3,4	T
3,7	X
5,9	X
6,7	Z
6,8	Y
7,10	Y
8,9	T
8,10	Z
9,11	Z	Xyt
10,11	T	Xyz

Таблица 3.3

Слагаемые	Склеивание по	Результат
1, 6	Z
2, 4	T
2, 8	X
3, 7	Z
8, 13	Y	X
10, 11	Z	X
12, 15	Z	Xy
13, 14	T	Xy

Метод Блейка

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

Пример 2. Построить сокращенную ДНФ по ДНФ D функции F(X,Y,Z), где

После первого этапа получаем:

После второго этапа получаем сокращенную ДНФ:

Алгоритм построения сокращенной ДНФ с помощью КНФ

(метод Нельсона)

Пусть F(X1, … , Xn) есть некоторая функция алгебры логики. Построим для F некоторую КНФ. Осуществим далее следующие преобразования.

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

2. В полученном выражении удалим нулевые дизъюнктивные слагаемые.

3. В полученном выражении проведем все поглощения, а затем удалим дублирующие члены.

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

Для каждой элементарной дизъюнкции D в КНФ и каждой элементарной конъюнкции K в сокращенной ДНФ (сокр. ДНФ) существует некоторый множитель вида X из K, содержащийся в D, т. е.

” DÎ ДНФ ” K Î сокр. ДНФ $ Xa Î K (XaÎ D).

Допустим противное: в КНФ существует элементарная конъюнкция D, в сокращенной ДНФ существует элементарная конъюнкция K, для которой всякий множитель вида Xa из K не входит в D. Не уменьшая общности возьмем для простоты

Положим X1 = A1, …, Xk=Ak, Xk+1 = Ck+1 ¹ Ak+1, …, Xr = Cr ¹ Ar. Тогда K(A1, …, Ak) = 1, и потому F (A1, …, Ak, Ck+1, …, Cr ) = 1. С другой стороны, D(Ck+1,…, Cr) = 0, и потому F (A1, …, Ak, Ck+1, …, Cr ) = 0. Противоречие.

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

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

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

F = (1111010010101111) из примера 1 :

Сокращенная ДНФ для функции

Что, естественно, совпадает с результатом примера 1.

Пример 4. Построить сокращенную ДНФ по заданной КНФ

После раскрытия скобок имеем:

После второго этапа получаем сокращенную ДНФ:

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

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

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

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

Построение всех тупиковых ДНФ.

Пусть F(X1, …, Xn) есть функция алгебры логики.

1. Построим СДНФ функции F, и пусть P1, P2, …,Pn есть ее коституенты единицы).

2. Построим сокращенную ДНФ функции, F и пусть K1, K2, …, Km – ее простые импликанты.

3. Построим матрицу покрытий простых импликант функции F ее конституентами единицы (табл. 3.4), полагая, что

+, если каждый множитель в Ki является множителем в Pj; (Pj есть Aij= часть для Ki ); Æ в противном случае.

Таблица 3.4

N	P1 P2 … Pj …Pn
K1 K2 Ki Km	A11 a12 … a1J …a1N A21 a22 … a2J … a2N Ai1 ai2 … aij … ain Am1 am2… amj … amn

4. Для каждого столбца J ( 1 £ J £ N ) найдем множество Ej всех тех номеров I строк, для которых Aij = 1. Пусть Составим выражение Назовем его решеточным выражением. Это выражение можно рассматривать как формулу, построенную в свободной дистрибутивной решетке с образующими 1, 2, …,M и с операциями & и Ú .

5. В выражении A раскроем скобки, приведя выражение A к равносильному выражению где перечислены все конъюнкции элементы которой взяты из скобок 1,2,…,N соответственно в выражении A.

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

Утверждение. Каждая элементарная конъюнкция I1&I2&…&Ir в С дает ТДНФ для F . Все ТДНФ для функции F исчерпываются элементарными конъюнкциями в выражении С.

Пример 5. Сокращенная ДНФ для функции F = (1111010010101111) имеет вид

Для функции F построим все минимальные ДНФ.

1. Строим матрицу покрытий (таблица 3.5).

Таблица 3.5

Конституенты единицы функции F
N	ПИ	X `X `X `X `X X X X X X X Y `Y `Y `Y y `Y `Y y y y y Z `Z z z `Z `Z z `Z `Z z z T t `T t t `T `T `T t t t
1 2 3 4 5 6	x y `X`Y `Y`T x`T `X`Z t y`Z t	+ + + + + + + + + + + + + + + + + + + +

2. Строим решеточное выражение (по столбцам таблицы).

E = (2Ú3)(2Ú5)(2Ú3)2(5Ú6)(3Ú4)(3Ú4)(1Ú4)(1Ú6)(1Ú4)(1) = (2Ú3)(2Ú5)(5Ú6)(3Ú4)(1Ú4)(1Ú6)12 = (5Ú6)(3Ú4)(1)(2) = 1235Ú1245Ú1236Ú1246.

3. Строим все тупиковые ДНФ функции F:

простые импликанты 1,2,3,5;

простые импликанты 1,2,4,5;

простые импликанты 1,2,3,6;

простые импликанты 1,2,4,6.

4. Все найденные ТДНФ являются минимальными ДНФ.

Алгоритм минимизации функций в классе ДНФ

1. Строим СДНФ функции F.

2. Строим сокращенную ДНФ функции F.

3. С помощью матрицы покрытий и решеточного выражения строим все ТДНФ функции F.

4. Среди построенных ТДНФ выбираем все минимальные дизъюнктивные нормальные формы функции F.

Алгоритм минимизации функций в классе КНФ

Чтобы построить все минимальные КНФ (МКНФ) функции F, следует построить все МДНФ функции `F и взять от каждой из них отрицание, для чего заменить знаки & на Ú , а Ú на & ( сохранив первоначальное распределение скобок) и над каждой буквой поставить знак отрицания. Полученные КНФ для функции F будут минимальными. В самом деле, если бы для F существовала КНФ с меньшим числом букв, то ее отрицание дало бы для `F ДНФ с меньшим числом букв, чем в любой из минимальных ДНФ для `F. Противоречие с их минимальностью.

Алгоритм минимизации функций в классе нормальных форм

Пусть F – функция алгебры логики.

1. Строим все МДНФ функции F.

2. Строим все МКНФ функции F.

3. Из построенных минимальных форм выбираем простейшие ( по числу букв).

Пример 6. В классе нормальных форм минимизировать функцию F=(01011110).

1. Строим СДНФ для функции F :

2. Строим сокращенную ДНФ функции F:

3. Строим матрицу покрытий (таблица 3.6).

Таблица 3.6

N	ПИ	`X`Y z `X y z x`Y`Z x`Y z x y`Z
1 2 3 4	`X z `Y z X`Y x`Z	+ + + + + + + +

Решеточное выражение E = ( 1 Ú 2 ) 1 (3 Ú 4 ) 4 = 134 Ú 124.

4. Строим все тупиковые ДНФ функции F :

5. Обе построенные ТДНФ являются минимальными.

6. Повторяем эти этапы для функции `F.

СДНФ :

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

Строим матрицу покрытий (таблица 3.7).

Таблица 3.7

N	ПИ	X`y`z `x y`z x y z
1 2	`x`z X y z	+ + +

Решеточный многочлен E = 112 = 12. Единственная тупиковая ДНФ (она же минимальная) для функции Минимальная КНФ функции Из построенных МДНФ и МКНФ выбираем простейшую

Пример 7. В классе нормальных форм минимизировать функцию F=(11011011).

1. СДНФ:

2. Сокращенная ДНФ : =

3. Строим матрицу покрытий (таблица 3.8).

Таблица 3.8

N	ПИ	`X`Y`Z `X`Y z `X Y z x`Y`Z X y`Z x y z
1 2 3 4 5 6	X y X`Z Y`Z `X z Y z `X`Y	+ + + + + + + + + + + +

E = ( 3 Ú 6 ) ( 4 Ú 6 ) ( 4 Ú 5 ) ( 2 Ú 3 ) ( 1 Ú 2 ) ( 1 Ú 5 ) = 1246 Ú 1356 Ú 134 Ú 256 Ú 2345.

4. Тупиковые ДНФ функции F :

5. Минимальные ДНФ функции F :

6. Повторяем указанные выше этапы для функции `F .

СДНФ :

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

Построенная сокращенная ДНФ функции `F является для нее тупиковой и минимальной.

Минимальная КНФ функции

Построенные МДНФ и МКНФ имеют одно и то же число букв; все они составляют минимальные формы для F :

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

Минимальная ДНФ булевой функции

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

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

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

Другие примеры решений о булевых функциях:

Задачи и решения о минимизации ДНФ булевых функций

Задача 1. Применяя равносильные преобразования привести булеву функцию $f=(bar x to bar y)to (yz to bar xz)$ к минимальной ДНФ.

Задача 2. Для заданной логической функции:
$$F= overline {(bar A vee Bcdot bar C)} cdot overline{( overline {(B downarrow C)}cdot D} $$
– найти дизъюнктивную нормальную форму;
– составить таблицу истинности и построить диаграмму Карно;
– получить минимальную дизъюнктивную нормальную форму;
– от минимальной дизъюнктивной нормальной формы перейти к конъюнктивной нормальной форме.

Задача 3. Для функции $f(x_1,x_2,x_3,x_4)$, заданной списком номеров наборов из $Nf$ методом Квайна найти сокращенную и минимальные ДНФ.
Список номеров: 0,1,2,3,6,7,8,9,11,15.

Задача 4. С помощью карт Карно найдите сокращенную, все тупиковые и минимальные ДНФ или КНФ булевой функции f(x1,x2,x3,x4), заданной вектором своих значений.
(1100 0101 0011 0011)

Задача 5. Найти минимальные КНФ булевых функций, зависящих от аргументов $A, B, C, D$. В квадратных скобках указаны неопределенные состояния

$$f = ( 1, 2, 5, 6, 14), [4, 9, 11, 12, 15].$$

Задача 6. Найти минимальные ДНФ и КНФ булевых функций, зависящих от аргументов $A, B, C, D$

$$f = (1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 15).$$

Задача 7. Для булевой функции $f(x, y, z)$ найти методом преобразования минимальную ДНФ. По таблице истинности построить СКНФ. По минимальной ДНФ построить релейно-контактную схему.

$$f(x,y,z)=(bar x vee bar y)wedge (bar y vee bar z) to (bar x vee bar z)$$

Задача 8. Переключательная функция от трех аргументов задана номером в десятичной системе счисления. Получить номер ПФ в двоичном, восьмеричном и шестнадцатеричном кодах, таблицу истинности, определить СДНФ, СКНФ, символическую форму функции с восьмеричной нумерацией наборов. Минимизировать функцию по кубу соседних чисел и карте Карно. Определить свойства функции. Реализовать функцию переключательной схемой на функциональных элементах в базисах а) И, ИЛИ, НЕ, б) И-НЕ, в) ИЛИ-НЕ.

Задача 9. Для булевой функции f, заданной в таблице 1:
а) найти сокращённую ДНФ;
б) найти ядро функции;
в) получить все тупиковые ДНФ и указать, какие из них являются минимальными;
г) на картах Карно указать ядро и покрытия, соответствующие минимальным ДНФ.

Задача 10. Двумя способами: с помощью карты Карно и методом Квайна найти сокращенную, ядровую и все минимальные дизъюнктивные нормальные формы булевой функции $f$, заданной вектором значений 0101101001001110. Построить минимальную функциональную (над системой ${vee, wedge, neg}$ ) и минимальную контактную схемы для функции $f$.

Решение задач о минимальной ДНФ на заказ

Выполняем для студентов очников и заочников решение заданий, контрольных и практических работ о минимизации булевых функций. Также оказываем помощь в сдаче тестов. Подробное оформление, таблицы, графики, пояснение, использование специальных программ при необходимости. Стоимость примера от 150 рублей, оформление производится в Word, срок от 2 дней.

Сокращенная и минимальная ДНФ

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

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

Элементарную
конъюнкцию К будем называть импликантой
функции f
, если для ∀ã
, K(ã)=1
влечет за собой выполнение условия
f(ã)=1.

Импликант К
–простой,
если выражение получающееся из его
выбрасывания любых их множителей не
является импликантой f.

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

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

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

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

Тупиковой ДНФ
функции f(ⁿ)
называется такая ДНФ её простых импликант
из которой нельзя выбросить ни одного
импликанта не изменив функцию f.

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

Алгоритм построения
тупиковой ДНФ:

Пусть f(ⁿ)
– функция алгебры логики (булевая).

1)находим табличные
значения функции f(ⁿ)=(101…01)

2)по табличным
значениям строим СДНФ

3)строим СДНФ
функции f
в виде: f=K₁˅
K₂˅….˅K_m
, где K_i
– простые импликанты.

4)строим матрицу
покрытий простых импликант функции f

5)для каждого
столбца j
(1jK)
находим множество E_j
номеров
строк для которых a_j=1.

Cоставляем
множество E_jтаких
элементов, E_j=
(e_j1
,e_j2
,…, e_ji),
где
e_ji–
импликанты соответствующие значению
1.

Полученное выражение
A=˅(j=1,k)E_j–
называется решёточным
покрытием
ДНФ функции f.

Удаляя все
дублирующиеся символы получаем тупиковую
ДНФ.

33. Сокращённые днф. Построение сокращённых днф булевых функций методом Блейка.Пример.

Элементарную
конъюнкцию К будем называть импликантой
функции f
, если для ∀
ã, K(ã)=1
влечет за собой выполнение условия
f(ã)=1.

Импликант К
–простой,
если выражение получающееся из его
выбрасывания любых их множителей не
является импликантой f.

Теорема:
Всякая функция реализуется дизъюнкцией
своих простых импликант. Сокращённая
–дизъюнкция всех простых импликант
функции f.

Любая функция f
реализуется своей СДНФ.

Для преобразования
ДНФ в СДНФ:

1. (полное склеивание)

2. (неполное склеивание)

3. (обобщенное
   склеивание)

4. A˅A*B=A
   (поглощение)

5. A˅A=A
   ; A&A=A
   (удаление дублирующих членов)

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

На первом этапе
производится операция обобщенного
склеивания, до тех пор пока это возможно.
На втором этапе операция поглощения.

Пример: D=x*y˅⌐x*z˅⌐y*z;

D₁=x*y˅⌐x*z˅⌐y*z˅y*z˅x*z˅z=x*y˅z˅z˅z=x*y˅z

34. Построение сокращённых днф булевых функций методом Квайна.Пример.

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

Пример:f(
⁴)=(0101101001101001)
;

ДНФ=⌐x₁⌐
x₂⌐
x₃
x₄
˅⌐x₁⌐x₂
x₃
x₄
˅⌐x₁
x₂⌐x₃
⌐
x₄
˅⌐x₁
x₂
x₃
x₄
˅x₁⌐x₂⌐
x₃
x₄
˅x₁⌐x₂
x₃
⌐
x₄
˅x₁
x₂⌐x₃
⌐
x₄
˅x₁
x₂
x₃
x₄

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

	x4	x3 x4	x2 x4	x2 x3	x1 x4	x1 x3	x1 x2	x1 x2 x3 x4
x4		x4	x4		x4
x3 x4	x4
x2 x4	x4
x2 x3
x1 x4	x4
x1 x3
x1 x2
x1 x2 x3 x4

	⌐x1⌐ x2⌐ x3 x4	⌐x1⌐x2 x3 x4	⌐ x1 x2⌐x3 x4	⌐x1 x2 x3 ⌐x4	x1⌐x2⌐ x3 x4	x1⌐x2 x3 ⌐ x4	x1 x2⌐x3 ⌐ x4	x1 x2 x3 x4
⌐x1⌐x2 x4	Ӿ	Ӿ
⌐x1⌐x3 x4	Ӿ		Ӿ
⌐x2⌐ x3 x4	Ӿ				Ӿ

⌐x₁⌐x₂x₄
˅⌐x₁x₂⌐x₃
x₄
˅x₁⌐x₂⌐x₃
x₄

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Схемотехника. Минимизация логических функций

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

Зачем это нужно?

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

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

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

Минимизация логических функций при помощи карт Карно

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

Карты Карно были изобретены в 1952 Эдвардом В. Вейчем и усовершенствованы в 1953 Морисом Карно, физиком из «Bell Labs», и были призваны помочь упростить цифровые электронные схемы.

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

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

Возможность поглощения следует из очевидных равенств

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

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

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

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

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

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

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

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

Карта Карно может быть составлена для любого количества переменных, однако удобно работать при количестве переменных не более пяти. По сути Карта Карно — это таблица истинности составленная в 2-х мерном виде. Благодаря использованию кода Грея в ней верхняя строка является соседней с нижней, а правый столбец соседний с левым, т.о. вся Карта Карно сворачивается в фигуру тор (бублик). На пересечении строки и столбца проставляется соответствующее значение из таблицы истинности. После того как Карта заполнена, можно приступать к минимизации.

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

1. Объединяем смежные клетки содержащие единицы в область, так чтобы одна область содержала 2ⁿ (n целое число = 0…) клеток(помним про то что крайние строки и столбцы являются соседними между собой), в области не должно находиться клеток содержащих нули;
2. Область должна располагаться симметрично оси(ей) (оси располагаются через каждые четыре клетки);
3. Не смежные области расположенные симметрично оси(ей) могут объединяться в одну;
4. Область должна быть как можно больше, а кол-во областей как можно меньше;
5. Области могут пересекаться;
6. Возможно несколько вариантов накрытия.

Далее берём первую область и смотрим какие переменные не меняются в пределах этой области, выписываем конъюнкцию этих переменных, если неменяющаяся переменная нулевая, проставляем над ней инверсию. Берём следующую область, выполняем то же самое что и для первой, и т. д. для всех областей. Конъюнкции областей объединяем дизъюнкцией.
Например(для Карт на 2-ве переменные):

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

В формате КНФ: