2.5. Ядро днф
Определение. Ядром ДНФ D называется совокупность H всех таких конъюнкций:
для каждой из которых выполняется условие
Иными словами, конъюнкция входит в ядро H ДНФ D, если она не поглощается совокупностью других конъюнкций ДНФ D.
В рассмотренном выше примере конъюнкции , , входят в ядро, остальные – нет.
Будем иметь в виду, если ДНФ является безызбыточной (тупиковой), то каждая ее конъюнкция входит в ядро.
ДНФ, сопоставляемая безызбыточному покрытию функции f( ,…, ), называется безызбыточной или тупиковой.
Теорема 2.7. Конъюнкция k из ДНФ D входит в пересечение тупиковых ДНФ, если и только если она входит в ядро этой ДНФ.
Доказательство. Достаточность. Пусть k входит в ядро. Покажем, что она содержится в пересечении тупиковых ДНФ. Допустим противное, то есть k не содержится в пересечении тупиковых ДНФ. Это значит, что она была исключена при построении одной из тупиковых ДНФ. Однако тогда , то есть не принадлежит ядру ДНФ. Пришли к противоречию.
Необходимость. Пусть k входит в пересечение тупиковых ДНФ. Покажем, что она принадлежит ядру ДНФ. Допустим противное: k не принадлежит ядру. Тогда для нее выполняется условие , то есть k может быть удалена при построении некоторой тупиковой ДНФ. Значит, k не принадлежит пересечению тупиковых ДНФ. Пришли к противоречию. Ч.Т.Д.
Будем иметь в виду, что для некоторых функций совершенная ДНФ совпадает с сокращенной и, следовательно, совершенная ДНФ является минимальной и кратчайшей одновременно. Речь идет о совершенной ДНФ, конъюнкции которой попарно ортогональны по двум и более переменным. Такие ДНФ встречаются на практике, представляя, например, кодовые слова равновесных кодов, кодов Бергера и т.д.
Сокращенная ДНФ монотонной функции совпадает со своим ядром и, значит, является минимальной и кратчайшей ДНФ одновременно. Это утверждается в нижеследующей теореме.
Функция называется монотонной, если для любых двух наборов и таких, что , имеет место неравенство f () f ().
Теорема 2.8. Сокращенная ДНФ монотонной функции не содержит отрицаний переменных и является ее единственной минимальной (кратчайшей) ДНФ.
Доказательство. Докажем сначала первую часть утверждения. Рассмотрим простую импликанту k функции f( ,…, ) ранга r и представим ее в виде . Простая импликанта, так же как и функция, обращается в единицу на всяком наборе α значений переменных ,…, , удовлетворяющем условию: = … = = 1, = … = = 0. В силу монотонности функция f( ,…, ) обращается в единицу на всяком наборе , удовлетворяющем условию = … = = 1. Последнее означает, что конъюнкция является импликантой функции f( ,…, ). Тогда конъюнкция k не является простой импликантой этой функции. Пришли к противоречию, следовательно, допущение о наличии отрицаний переменных в простых импликантах сокращенной ДНФ монотонной функции f( ,…, ) не верно.
Итак, на основании только что доказанного произвольная простая импликанта k ранга r монотонной функции f( ,…, ) представляется в виде . Покажем, что она не может быть исключена из сокращенной ДНФ функции. Рассмотрим набор α значений переменных ,…, такой, что в нем = … = = 1, = … = = 0. Покажем, что на этом наборе только конъюнкция k обращается в единицу. Допустим, что найдется другая простая импликанта , которая обращается в единицу на этом наборе. По доказанному ранее не содержит отрицаний переменных. Следовательно, поглощает k, то есть k не является простой импликантой. Пришли к противоречию. Делаем заключение: k является единственной простой импликантой, обращающейся в единицу на наборе α, значит, k нельзя исключить из сокращенной ДНФ. В силу произвольного выбора k ни одну из простых импликант нельзя исключить из сокращенной ДНФ функции f( ,…, ). Значит, сокращенная ДНФ является минимальной (кратчайшей) ДНФ монотонной функции. Ч.Т.Д.
Лекция 05. Продолжение темы «ДНФ»
Носитель элементарной конъюнкции ранга R будем называть интервалом ранга R.
Интервал ранга R содержит 2N-R векторов.
N – количество рассматриваемых векторов.
Интервал – носитель элементарной конъюнкции.
Носитель дизъюнкции двух функций равен объединению носителей этих функций.
Носитель ДНФ является объединением интервалов.
Допустимым интервалом для данной функции называется интервал, который целиком содержится в носителе этой функции.
Nf = I1 V I2 V … V Ik
Интервал для данной функции является максимальным, если он не содержится целиком ни в каком другом допустимом интервале.
Элементарная конъюнкция, носителем которой является допустимый интервал, называется импликантой.
ЭК, N – максимальный интервал – простая импликанта.
Представление носителя в виде объединения максимальных интервалов будем называть Покрытием носителя максимальными интервалами.
Дизъюнкция всех возможных простых импликант называется Сокращенной ДНФ функции.
Покрытие носителя интервалами будем называть Неприводимым, если ни один нельзя отбросить из правой части равенства, не нарушив это равенство.
ДНФ, которая соответствует неприводимому покрытию, называется Тупиковой ДНФ.
Минимальная ДНФ Содержится среди тупиковых ДНФ.
Максимальный интервал называется ядровым, если он содержит хотя бы одну вершину из носителя функции, которая не принадлежит больше никакому другому максимальному интервалу.
Элементарная конъюнкция, соответствующая ядровому интервалу – ядровая импликанта.
Объединение всех ядровых интервалов – ядро функции.
Дизъюнкция всех ядровых импликант — ядровая ДНФ.
Ядро функции обязательно входит в любое неприводимое покрытие.
Алгоритм получения минимальной ДНФ.
1. Выделяем носитель функции.
2. Выделяем все возможные интервалы.
3. Выписываем все простые импликанты.
4. Выделяем ядровый интервал.
5. Используя ядро функции и комбинацию неядровых интервалов, получаем все неприводимые покрытия, для каждого из которых выписываем тупиковую ДНФ.
Построение минимальных ДНФ
СДНФ, которая строится по таблице булевой функции, зачастую оказывается весьма сложной, т.е. она содержит достаточно много элементарных конъюнкций и литералов. Необходимо уметь находить в определенном смысле минимальную ДНФ, представляющую исходную функцию. Уточним задачу.
Определение 6.5. Булеву функцию называют импликантой булевой функции , если для любых наборов значений переменных из следует .
Замечание 6.7. Напомним, что функции и можно рассматривать как функции от одного и того же числа переменных. Обозначая это число через , можно так уточнить понятие импликанты: функция есть импликанта функции если для каждого набора a следует . Термин "импликанта" естественным образом ассоциируется и с логической связкой, называемой импликацией, и с одноименной булевой функцией. Действительно, если д импликанта , то из и следует, что , т.е. истинно высказывание
Если функция представлена СДНФ, то любая ее элементарная конъюнкция (констпигпуентпа единицы функции ) будет ее импликантой. Полезно заметить также, что если и — импликанты , то дизъюнкция также является импликантой . Действительно, если , то или . Но тогда, поскольку каждая из этих функций есть импликанта , и есть импликанта .
Из определения 6.5 и понятия равных булевых функций (см. определение 6.2) следует, что булевы функции и равны, если и только если каждая из них служит импликантой другой: .
Определение 6.6. ДНФ называют минимальной, если она содержит наименьшее число литералов среди всех ДНФ, эквивалентных ей.
Обратим внимание на то, что под числом литералов в ДНФ понимают число всех подформул этой ДНФ, которые являются литералами. Так, СДНФ (6.9) содержит 12 литералов (по три литерала в каждой из четырех элементарных конъюнкции).
Пример 6.10. ДНФ не является минимальной, так как ее можно преобразовать к эквивалентной ДНФ, не содержащей ни одного из литералов
Заметим, что кратчайшая ДНФ не обязана быть в то же время минимальной среди всех ДНФ, эквивалентных исходной функции. Но поиск минимальных ДНФ, как мы сейчас увидим, проводится среди кратчайших ДНФ.
Наша задача состоит в том, чтобы описать метод построения минимальной ДНФ, эквивалентной заданной булевой функции. Мы рассмотрим простейший метод такого рода, основанные на алгоритме Квайна — Мак-Клоски. Этот алгоритм исходит обязательно из СДНФ, которая строится по таблице функции так, как это было описано ранее.
Алгоритм Квайна–Мак-Клоски
Опишем последовательно этапы, составляющие алгоритм Квайна–Мак-Клоски .
1. Склейка. Пусть и — две элементарные конъюнкции, входящие в исходную СДНФ Ф, которая представляет функцию , причем для некоторого переменного и . Тогда имеем, согласно тождествам булевой алгебры,
Мы получаем элементарную конъюнкцию и , и является, как и обе конъюнкции и , импликантой . Образно говоря, мы "склеили" две импликанты в одну, в которой число литералов на единицу меньше.
Операцию получения и , описанную выше, можно провести и для любых двух элементарных конъюнкций подобного вида, составляющих любую ДНФ, эквивалентную исходной функции. Такую операцию называют простой склейкой импликант и по переменному , и множеством ее конституент единицы. Это соответствие, напомним, таково, что каждому набору отвечает элементарная конъюнкция , принимающая значение 1 только на наборе . Тогда простая склейка может быть применена только к таким двум элементарным конъюнкциям и , соответствующим наборам , что для некоторого
Это значит, что наборы таковы, что один из них доминирует над другим (они различаются значением только одной компоненты), т.е. они образуют ребро булева куба , подлежат те и только те элементарные конъюнкции, которые соответствуют элементам какого-либо ребра булева куба, на котором функция принимает единичное значение. Образно говоря, две соседние вершины куба, на которых функция равна 1, псклеиваются" в ребро, их "соединяющее".
С алгебраической же точки зрения мы из двух элементарных конъюнкций и получаем новую элементарную конъюнкцию , лишенную литерала .
Итак, применяя простую склейку к исходной СДНФ ; к ней также применяем простую склейку — получаем ДНФ ; продолжаем выполнять эту операцию до тех пор, пока не окажется, что для некоторого уже нельзя склеить никакие две элементарные конъюнкции. Такое называют сокращенной ДНФ функции , а ее элементарные конъюнкции — простыми импликантами булевой функции .
Замечание 6.8. Понятие простой импликанты определено через процедуру многократного повторения простой склейки. Иногда простую импликанту булевой функции определяют независимо от понятия о склейке как такую элементарную конъюнкцию в составе некоторой ДНФ, представляющей функцию , что удаление из нее любого литерала лишает ее свойства "быть импликантой". Например, конъюнкция не является простой импликантой мажоритарной функции, так как из ее СДНФ (6.9) можно удалить литерал и получить конъюнкцию , которая будет снова импликантой функции, но уже, как будет показано далее, простой.
Можно доказать, что эти два определения простой импликанты равносильны.
С геометрической точки зрения склейка первой и третьей конъюнкций в формуле (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). Любая пара соседних клеток (с учетом "закрученности" карты) определяет некоторое ребро булева куба, а любой прямоугольник, состоящий из клеток (или, как говорят, прямоугольник с площадью ) для некоторого задана таблицей, представленной в форме карты Карно. Описанный выше итерационный процесс склейки, в результате которого получается сокращенная ДНФ, представляющая функцию , проводится на карте Карно так: любые две соседние клетки, содержащие единицы, обводятся, и "поглотивший" их прямоугольник (он и есть обозначение результата склейки на карте) представляется словом, содержащим "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, получим сокращенную ДНФ в виде
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.18. Эта функция имеет минимальную ДНФ . Следовательно, и частичная исходная функция может быть представлена такой ДНФ, поскольку на всех наборах, на которых она определена, она принимает такое же значение, как и функция .
Конечно, мы могли бы доопределить функцию по-другому, так, чтобы получилась функция , заданная картой Карно, приведенной на рис. 6.19. Ясно, что поэтому и частичная функция может быть определена такой ДНФ. Но эта ДНФ не минимальна для данной частичной (именно частичной!) функции, поскольку первый способ доопределения дал ДНФ, содержащую лишь один литерал.
Таким образом, в отличие от минимизации булевых функций при минимизации частичных булевых функций не следует выделять все максимальные прямоугольники с прочерками, содержащие данную единичную клетку карты Карно, достаточно выбрать произвольно любой из таких прямоугольников. Но, конечно, не нужно забывать о том, что каждая единица на карте должна быть покрыта некоторой склейкой.
Пример 6.16. Для карты на рис. 6.20 следует взять обе склейки на четыре позиции: .
Заметим, что без использования склеек с прочерками мы вообще не могли бы минимизировать данную функцию. Нужно также отметить, что не всегда использование "частичности" функции позволяет получить минимальную ДНФ для нее. Так, на представленной на рис. 6.20 карте в случае, если мы переместим нижнюю единицу на строку выше, обычная склейка на две позиции дает лучший результат: , а записанная выше ДНФ уже не будет минимальной (и даже кратчайшей).
Научный форум dxdy
Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".
Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.
Не ищите на этом форуме халяву , правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.
Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.
Минимизиция булевых функций
Я не спорю, могла и напутать, а хотя-бы образцов решений типовых задач ни у кого нет?
Здесь более наглядно задачи
Помогите, пожалуйста, разобраться в тот как надо находить минимальные ДНФ и ядровые ДНФ.
Допустим, у меня функция заданная вектором . С помощью булева куба я нашел сокращенную ДНФ этой функции: 
. Вот никак в голову не могу взять, как находить минимальные и ядровые ДНФ данной функции. Помогите разобраться. Или ссылки привести на источники, где это доходчиво объясняется.
Я так понял условие упражнения: функция принимает значения 1 на наборах c номерами 0, 2, 4, 5, 7.
Тогда у меня получается другой результат при минимизации на кубе — «более минимальный».
По поводу минимальных ДНФ посмотрите ссылки, приведенные Выше участником Brukvalub .
// 8.05.09 близкие темы соединены. / GAA
Ну, сокращённая ДНФ не обязана быть минимальной…
Я все эти материалы перерыл — так и не понял как найти ядровую и все минимальные ДНФ по булеву кубу. Ну не могу понять!
Добавлено спустя 38 минут 14 секунд:
Мне надо по булеву кубу найти минимальные и ядровые ДНФ.
Последний раз редактировалось GAA 10.05.2009, 11:37, всего редактировалось 1 раз.
1. По поводу минимальных ДНФ по кубу. Нарисуйте куб и нанесите на него точки — пометьте вершины. В Вашем случае нет граней со всеми помеченными вершинами, но точки можно «покрыть» ребрами. Два определенных ребра войдут в ответ обязательно. А вот точку 
можно покрыть ребрами двумя способами. Т.обр. в ответе будет две минимальных ДНФ. Приведите, пожалуйста, эти ДНФ.
Добавлено спустя 8 минут 31 секунду:
2. По поводу ядровой см. приведенную Brukvalub ом ссылку .
и 
есть 
).
4. Записать результат в виде дизъюнкции трех конъюнктов (т.е. трех элементарных конъюнкций).
При редактировании добавлена расшифровка: «т.е. трех элементарных конъюнкций.»
Употреблять множественное число в обоих случаях не очень корректно.
Ядровая ДНФ — она единственная. Собственно, фишка в том и состоит, что мы можем ещё чуть-чуть «сократить» сокращённую ДНФ, не начиная строить и перебирать тупиковые.
Что касается минимальных, то обычно тоже довольствуются тем, что отыскивают какую-нибудь одну. Дело в том, что могут иметься минимальные ДНФ, не являвшиеся тупиковыми, и «выцеплять» их сложно.
Вообще, элементарные геометрические соображения не могут много дать для построения минимальной ДНФ. В общем случае мы получим лишь сколько-то тупиковых ДНФ, которые нужно будет просто выписать и сравнить на предмет «длины».
Объясню на примере, что такое ядровая ДНФ. Пусть сокращённая ДНФ некоторой формулы имеет такой вид, как указал rar : . Каждому из дизъюнктов соответствует некоторая «грань» куба. В нашем случае все «грани» одномерные, т. е. рёбра.
Отыщем теперь в сокращённой ДНФ «важные» грани, то есть те, единственно благодаря которым оказались покрыты некоторые точки. К примеру, «важной» будет грань 
: если бы не она, кто из граней сокращённой ДНФ покрыл бы вершину 
? Другая «важная» грань сокращённой ДНФ — это 
. Установите самостоятельно вершину, которая оказалась покрыта лишь благодаря ей.
Других «важных» граней отыскать не удаётся. Собственно, объединение этих «важных» граней и называется ядром. В некоторых источниках и сами эти грани называются ядровыми .
При минимизации сокращённой ДНФ ядровые грани выкинуты из неё быть не могут. Это, конечно, плохо. Но раз уж так, можно попытаться выкинуть из сокращённой ДНФ те грани, которые покрываются объединением ядровых. ДНФ, получаемая из сокращённой выкидыванием всех («неважных») граней, покрываемых ядром, и называется ядровой.
В нашем случае сокращённая ДНФ не имеет «неважных» граней, покрываемых ядром. Значит, ядровая ДНФ совпадает с сокращённой.
Похоже, в предыдущем сообщении я напутал и рассказал о том, что у Яблонского называется ДНФ Куайна .
А ядровая ДНФ — это просто объединение через дизъюнкцию ядровых граней. Следует иметь в виду, что ядровая ДНФ может быть неэквивалентна исходной формуле .
За это автору термина «ядровая ДНФ» (сам Яблонский его не употребляет) следовало бы объявить строгий выговор. Все прочие «ДНФ» (совершенные, сокращённые, ΣΤ, тупиковые, минимальные) эквивалентны своим исходным формулам, а вот ядровая, видите ли, нет. Как будто просто понятием ядра нельзя было обойтись.
Итак, ядровая ДНФ — некоторое вспомогательное понятие. Его можно использовать чтобы чуть-чуть сократить перебор, поскольку элементарные конъюнкции, в неё входящие, нельзя выбрасывать.
Яблонский же использует понятие ядра (что по сути то же самое) ещё и для того, чтобы попытаться продвинуться немного вперёд на пути однозначной минимизации ДНФ, и только потом начать перебор.