Дизъюнктивные и конъюнктивные нормальные формы. Проблема минимизации

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

Очевидно, что СКНФ функции из примера 3.8 можно упростить, например, так:

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

Убирая ряд ограничений из определений СДНФ (СКНФ), приходим к понятию дизъюнктивной (конъюнктивной) нормальной формы ДНФ (КНФ).

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

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

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

П р и м е р 3.10. Представить в дизъюнктивной нормальной форме формулу F = (ж —> у) V ху.

Заменяя импликацию х —и/ равносильной формулой, имеем F = = (хУу) V ху - это ДНФ формулы F, так как представляет собой трехчленную дизъюнкцию элементарных конъюнкций. Проводя дальнейшие упрощения с помощью законов ассоциативности и дистрибутивности, получаем:

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

Двойственным образом можно определить конъюнктивную нормальную форму.

Определение 3.11. Элементарной дизъюнкцией п переменных называется дизъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более одного раза. Конъюнктивной нормальной формой (КНФ) формулы F называется равносильная ей формула, которая представляет собой конъюнкцию (возможно одночленную) элементарных дизъюнкiщй.

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

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

  • 1. Если формула F(xi,...,xn) не является булевой, т. е. содержит символы «—?» и «=», то используя равносильности 1, 2 пункта 3.4, переходим к равносильной ей булевой формуле.
  • 2. С помощью законов де Моргана (равносильности 9, пункт 3.3) все отрицания «спускаем» до переменных, убирая двойные отрицания (равносильность 8, пункт 3.3).
  • 3. На основании законов дистрибутивности (равносильности 3, пункт 3.3) раскрываем скобки.
  • 4. С помощью законов идемпотентности, противоречия и исключенного третьего (равносильности 4, 6, 7, пункт 3.3) удаляем лишние конъюнкции и повторы переменных в конъюнкциях.
  • 5. Используя равносильности 5, пункт 3.3, удаляем константы 0 и 1.

Если на третьем шаге используем закон дистрибутивности конъюнкции относительно дизъюнкции, т. е. Л(В/С) = АВУ АС, то в результате указанных преобразований получаем ДНФ формулы F. В случае применения закона дистрибутивности дизъюнкции относительно конъюнкции: АУВС = (АУ В)(АУС) получаем КНФ формулы F.

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

Для перехода от КНФ к СКНФ поступают аналогично, но используют двойственный закон расщепления:

П р и мер 3.11. Формулу F = (ху^z)(xVyz) привести к ДНФ и С ДНФ.

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

  • 1. F = (;ху —>• z)(x/yz) = А—>В = АУВ = (хуУ z)(хVyz). Получили равносильную булеву формулу.
  • 2. F= (хуУ z)(xyyz) = | АВ = А У В = ((хУу)У z)(xyyz). Получили формулу, в которой отрицания относятся только к переменным.
  • 3. Применяем закон дистрибутивности F = ((х У у) У z) (.х У yz) = = (ж V у У z) (х У yz) = хх У xyz У ух У yyz У zx У zyz.
  • 4. F = хх У xyzУ ухУ yyzУ zxy zyz = ОУх/yzy ух V О V zx yyz. Использовали равносильности А А = 0 и АА = А.
  • 5. Так как О У А = А, то F = 0yxyzy у хУОУ zxy у z = xyzy у хУ zxy у z.

Получили ДНФ формулы F.

Данная формула допускает следующее упрощение:

Чтобы получить С ДНФ, можно взять любую из полученных ДНФ и «расщепить» все неполные конъюнкции. Применим равенство (3.5) к ДНФ, полученной выше

Последняя формула представляет собой СДНФ исходной формулы F.

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

В данном случае сразу получили КНФ, которая, впрочем, допускает упрощение. Для получения СКНФ «расщепляем» второй сомножитель с помощью переменной z, а третий - с помощью переменной у, используя двойственный закон расщепления (3.6):

Пусть F и G две равносильные формулы, т. е. F — G. Как показано выше, существуют эквивалентные преобразования, которые приводят F и G к СДНФ. По теореме 3.4 СДНФ этих формул совпадают. Если сначала преобразовать F к СДНФ, а затем обратить преобразования, с помощью которых G приводится к СДНФ, то в результате эквивалентными преобразованиями из F получим G.

Таким образом, справедлива следующая теорема.

Теорема 3.7. Для любых двух равносильных формул F и G существует эквивалентное преобразование F в G с помощью основных равносильностей булевой алгебры логики (равносильности 1-10, пункт 3.3).

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

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

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

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

Составим минимизационную карту. Она представляет собой таблицу, в которой каждая строка соответствует некоторой элементарной конъюнкции от п переменных - хД... х^п, где {0,1}, k= 1,2,..., п. Именно такая конъюнкция является элементом последнего столбца строки. А число строк в таблице равно числу всевозможных конъюнкций такого вида.

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

MPTTTTTTvTP’ Г*1 Г*2 7»^^ гу®п гуРП~ 1 гу®71 О О СПрД/Г

iVlCll 1 IIJDH3. Jbcy ^ *^3 з • • • 5 «ау Y ,д з .Xj су Jb о ^ ^ «А/*) Jb ^ ^ ^ ^ р, 1 Ц *) ^ 1V1

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

Если некоторая конъюнкция переменных хД ... хД, из j-ой строки таблицы не входит в С ДНФ минимизируемой функции /(xi,..., хп), то это означает, что /(<л,..., ап) = 0. Следовательно, любая конъюнкция из этой строки таблицы не входит ни в одну из ДНФ исходной функции.

Опишем алгоритм построения минимальной ДНФ.

  • 1. Отметим в минимизационной карте все строки, которые соответствуют конъюнкциям, не входящим в С ДНФ данной функции /(х 1,...,хте). Вычеркнем все конъюнкции в этих строках.
  • 2. Во всех остальных строках вычеркнем все те конъюнкции, которые были вычеркнуты в пункте 1.
  • 3. В каждой строке, которая осталась после вычеркивания строк в пункте 1, выберем конъюнкции с наименьшим числом сомножителей, а остальные вычеркнем.
  • 4. Составим все возможные ДНФ, выбирая в каждой строке только по одному оставшемуся элементу.
  • 5. Среди всех ДНФ, построенных в пункте 4, выберем минимальную ДНФ.

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

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

П р и м е р 3.12. Минимизировать в классе ДНФ функцию

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

Таблица 12

В табл. 12 вычеркнуты строки, которые соответствуют конъюнкциям, не входящим в СДНФ. Значком * отмечены те конъюнкции, которые подлежат вычеркиванию по пункту 2, а значком ** - конъюнкции, которые вычеркиваются по пункту 3. После выполнения трех пунктов алгоритма таблица примет вид:

Таблица 13

Перейдем к выполнению пункта 4. Составим из оставшихся конъюнкций все возможные ДНФ и упростим их.

Очевидно, что минимальной ДНФ является первая, следователь- но f(xiyX2,%3) = xiXz/XiX2- Убедимся в справедливости данного равенства, для этого, используя правило расщепления, преобразуем полученную ДНФ к С ДНФ:

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

Карта Карно для п переменных представляет собой таблицу из 2п ячеек, каждая из которых соответствует одной из 2п возможных комбинаций значений п логических переменных ад, ..., хп. Столбцы таблицы соответствуют значениям переменных ..., Хк, строки - значениям переменных Хк+, хп, а соседние ячейки отличаются значением только одной переменной.

На рис. 7 и 8 приведены карты Карно для функций трех и четырех переменных, соответственно. Все ячейки, отмеченные ад, соответствуют наборам значений с ад = 1, а не отмеченные од, соответствуют наборам значений с Xi = 0. Например, на рис. 7 ячейка а соответствует набору 010 значений переменных х, а;2, Х3. На рис. 8 изображены две карты Карно для функции четырех переменных. Первая карта соответствует разбиению переменных [1], вторая - [2].

Рис. 7

Рис. 8

Ячейки, отличающиеся значением только одной переменной, называют смежными. Поскольку каждая ячейка может иметь не более четырех ячеек, соседних по строке или столбцу, для представления смежных ячеек необходимо использовать и более удаленные ячейки. Например, на рис. 8 ячейки b и с отличаются значением только переменной Хз, т. е. я в л я ются с межны ми.

Булева функция может быть представлена на карте Карно выделением 1 -ячеек, т. е. ячеек, в которых функция принимает значение 1. На рис. 9 изображена карта функции четырех переменных, для которой / (0,0,1,1) = = /(0,1,0,0) = /(0,1,1,0) =

Рис. 9

= /((), 1,1,1) = /(1,1,0,0) =

= /(1,1,1,0) = 1.

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

Ячейки b и с на рис. 8 лежат в 1-кубе, который соответствует произведению х 1X0X4. Ячейки {ф е,/, д} образуют 2-куб, соответствующий конъюнкции X1 Х.

Рис. 10

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

П р и м е р 3.13. Составить минимальную ДНФ для функции, представленной на рис. 9.

Минимальной ДНФ является формула

Соответствующие элементарным конъюнкциям кубы выделены на рисунке.

П р и м е р 3.14. Минимизировать в классе ДНФ функцию из примера 3.12.

Отметим на карте Карно (рис. 10) для трех переменных 1-ячейки функции.

Покроем 1-ячейки минимальным количеством Аэкубов. Нам потребуется два 1-куба, Один соответствует конъюнкции ту ад, так как для ячеек этого куба значения переменных х = 1, Жз = 0, второй - ХХ<) так как для ячеек этого куба - rri = 0, Хч = 1 • Значит, минимальная ДНФ данной функции f(x,X2-Xz)=XiXzVXiX2.

  • [1] жцо^}, {^3,0^4
  • [2] цд }, {жз, Хз,Х4
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >