Как из днф получить кнф

11.2.4 Преобразование кнф в днф и днф в кнф

Пример 1:

Преобразование днф в кнф

Здесь возможны два варианта.

Первый вариант основан на многократном применении дистрибутивного закона дизъюнкции относительно конъюнкции п. 1.6. 8,б.

Сначала распределяем , затеми, наконец, удаляем 1.

Второй вариант сложнее. Порядок действий здесь таков.

1. Взять двойное отрицание от всего выражения;

2. Используя одно отрицание и законы де Моргана, перевести исходное выражение под вторым отрицанием в КНФ (второе отрицание сохранить);

3. Перевести полученную КНФ под общим отрицанием в ДНФ – раскрыть скобки и упростить. Получим ДНФ с общим отрицанием;

4. Используя второе отрицание и законы де Моргана перевести результат предыдущего действия в КНФ.

11.2.5 Доказательства равенства логических функций

Если требуется сравнить две логические функции f₁ и f₂, то следует преобразовать их или представить в виде

а) Таблиц истинности – ТИ₁ и ТИ₂;

г) Полиномов Жегалкина.

Сравнение логических функций с помощью таблиц истинности – это стандартный прием, а почему сравнение логических функций удобно проводить в совершенных формах или в форме полинома Жегалкина? Ответ прост: логическая функция может иметь много формул, ее представляющих, но совершенные формы и полином жегалкина у нее единственны.

Замечание:От СДНФ легко можно перейти к СКНФ, (а от СКНФ к СДНФ) – если СДНФ имеетkконъюнкций, то СКНФ будет иметь 2 n –kдизъюнкций, гдеn– число переменных (если СКНФ имеетkдизъюнкций, то СДНФ будет иметь 2 n –kконъюнкций).

Пример: Доказать, что.

Раскрываем скобки в левой части и упрощаем

В результате получили выражение идентичное правой части.

Переход к СДНФ удобно производить от ДНФ.

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

Если установить порядок входных переменных xyz,z– младшая переменная, то единичными наборами (для которых определена СДНФ) являются 7, 6, 5, 3, 1 (определяем по значениям переменных), а нулевыми наборами (для которых надо написать произведение сумм) будут 0, 2, 4, поэтому для СКНФ получаем

Не забывайте: если в СКНФ переменная без отрицания, то в соответствующем входном наборе она имеет значение 0, если с отрицанием, то 1.

Переход к СКНФ удобнее производить от КНФ. Здесь вместо недостающей переменной в дизъюнкции ставим 0 а затем 0 заменяем произведением прямого и инверсного значений этой переменной.

Как видим, результаты преобразований совпали, следовательно, тождество доказано.

По СДНФ или по СКНФ легко построить таблицу истинности (табл. 11.4).

11.2.6 Разложение логических функций по переменным

В п. 11.2.1 (правила 13 (1) и (2)) показаны два варианта разложения логической функции по переменным. При разложении логической функции по всем переменным по варианту (1) получается СДНФ, а по варианту (2) – СКНФ. Реализовать эти разложения можно либо последовательно, либо параллельно. В качестве примера рассмотрим разложение функции

а) Последовательное разложение логической функции по всем переменным

Разложение по 13 (1)

Разложение по переменной x₁

Сначала определяем значение функции приx₁= 1 и получаемЗатем при x₁= 0 получаем

Подставив полученные значения функции fв выражение дляf₁, получаем

В результате разложения по x₁получили функцию

Разложение по переменной x₂

Действуя аналогично, но с функцией , получаем

Таким образом,

Разложение по переменной x₃

Получили СДНФ функции.

разложение по13 (2)

Имеем функцию .

Разложение по переменной x₁

Сначала в формулу вместоx₁подставляем 0 и получаемПриx₁= 1 получаем

Разложение по переменной x₂

Имеем

Обратите внимание на скобку , которая преобразуется впо дистрибутивному закону 8,б (см. п. 1.6).

Разложение по переменной x₃

Имеем

Здесь также применяется дистрибутивный закон 8,б п. 1.6.

Произведя перестановку переменных (как при разложении по п. 1.6.13 (1)), получаем

Получили СКНФ логической функции.

б) Параллельное разложение логической функции по всем переменным

разложение по13 (1)

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

После их подстановки и упрощения получим

При разложении функции по всем переменным по п. 1.6.13 (1) получили СДНФ, в соответствии с которой функция имеет значение 1 на наборах: 7, 5, 4.

Разложение по 13 (2)

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

При разложении функции по всем трем переменным по п. 1.6.13 (2) получили СКНФ, в соответствии с которой функция имеет значение 0 на наборах 0, 1, 2, 3, 6.

Как видим, результаты последовательного и параллельного разложений функции по всем переменным совпадают.

11.2.7 Вопросы для контроля

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

2_ ДНФ ,КНФ ДНФ, СКНФ алгоритмы преобразования

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

Раскрыто понятие совершенная ДНФ и КНФ. Приведены примеры преобразований

Просмотр содержимого документа
«2_ ДНФ ,КНФ ДНФ, СКНФ алгоритмы преобразования»

Логические функции, СДНФ СКНФ

1.4 Формы представления функций алгебры логики

Функции алгебры логики могут быть заданы различными способами:

— таблицей истинности — в аналитической форме- в числовой форме..

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

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

элементарная конъюнкция — конъюнктивный терм или минтерм — конъюнкция произв числа попарно независимых перем. Напр, Х ₁Х ₂ Х₃ — минтерм 3-его ранг

– это не минтерм, так как перем и зависимы.

Для аналитической записи функций используют две формы:

1) Дизъюнктивную Нормальную Форму — ДНФ

2) Конъюнктивную Нормальную Форму – КНФ

ДНФ это дизъюнкция минтермов разл ранга

КНФ это конъюнкция макстермов различного ранга

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

— это СДНФ

— это СКНФ

Т е СДНФ есть дизъюнкция конституент 1, а СКНФ — есть конъюнкция конституент 0

Составление совершенных форм по табл истинности

Совершенные формы составляют по табл истинности функции. СДНФ : для каждого набора переменных на которых функция=1, записывают минтерм ранга n , в которых с отрицанием берутся переменные = 0 на данном наборе. Все минтермы объединены дизъюнктивно.

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

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

Числовая форма для СКНФ:

Алгоритм преобразованияя в ДНФ

1) Сначала избавляемся от операций импликации, эквивалентности и неравнозначности, выразив их через логические связки ¬, & и ∨ по законам:

2) Доводят знаки отрицания до независимых переменных, используя законы де Моргана:

3) Применяя з-н дистрибутивности

преобразуют формулу к дизъюнкции элементарных конъюнкций

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

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

Если кажд слаг содер все арг или их отриц, то получ соверш дизъюнкт норм форму (СДФН), напр

Для перехода от табл истинн к СДНФ учит только те сост, для кот функц= 1. Для каждого такого сост запис элем произв всех ар. Если арг имеет зн "0", то запис его отриц. Для привед примера СДНФ имеет вид (17.4)

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

ДНФ, но не СДНФ от 3 перем

-представл импликации в виде ДНФ.

-СДНФ для импликации

-СДНФ для оп эквивалентности

-СДНФ для оп неравнозначности

Прим.1 Привести к ДНФ формулу

2. Привести ту же формулу к СДНФ. Начав преобразования с ДНФ

Нахождение СДНФ по табл истинности функции

Нахождение СКНФ по табл истинности функции

1)Отметить те строки таблицы истинности, в последнем столбце которых стоят 1.

2)Выписать для каждой отмеченной строки конъюнкцию всех переменных так: если значение некоторой переменной в данной строке — 1, то в конъюнкцию включать саму эту переменную, если равно 1, то ее отрицание.

3)Все полученные конъюнкции связать в дизъюнкцию.

1)Отметить те строки таблицы истинности, в последнем столбце которых стоят 0.

2)Выписать для каждой отмеченной строки дизъюнкцию всех переменных так: если значение некоторой переменной в данной строке= 1, то в дизъюнкцию включать саму эту переменную, если равно 0, то ее отрицание.

Как из кнф получить днф – 11.2.4 Преобразование кнф в днф и днф в кнф

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

Конъюнкцией n переменных f (x₁, x₂, …, x_n) = x₁ x₂…x_n называется функция, которая принимает значение 1, если и только если все переменные равны 1 (и, значит, равна 0, если хотя бы одна из этих переменных равна 0).

Дизъюнкцией n переменных f (x₁, x₂, …, x_n) = x_1Ú x_2Ú … Ú x_n называется такая функция, которая равна 0 если и только если все переменные равны 0 (и, значит, равна 1 тогда и только тогда, когда хотя бы одна переменная равна 1).

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

Будем обозначать через (x₁,x₂,… ,x_n) новую функцию, которая на наборе переменныхx₁,x₂, …,x_n принимает значение, противоположноеf(x₁,x₂, …,x

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

1. Универсальные границы:

x1 = 1; x0 =х;х1 =х;х0 = 0.

2. Ассоциативность конъюнкции и дизъюнкции:

x(yz) = (xy)z;x (y z) = (x y)z.

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

3. Поглощение (“целое поглощает часть”):

х ху=х(1у) =х.

4. Два распределительных закона:

х (y z) =x y  x z;х (y z) = (x y)(x z),

оба свойства могут быть доказаны простым рассуждением (например, если х = 0, тогда по свойству 1 справа выражение равно 0 и слева тоже 0, еслих = 1, то справа стоитy z и слева будет то же самое).

5. Правила де Моргана:

оба эти правила обобщаются на любое число переменных:

6.Правило Блейка:

Пусть К₁ иК₂ – какие-то логические функции, тогда

что легко доказывается справаналево:

Следствием правила Блейка являются два правила обобщенного поглощения:

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

Замечание.Конъюнкция, дизъюнкция, отрицание были определены для объектов, принимающих лишь два значения0и1. Однако бывают случаи, когда можно ввести такие операции для некоторых других объектов (эти операции также называют иногда конъюнкцией, дизъюнкцией и отрицанием), для которых также выполнены свойства 1–6. В этом случае говорят, что на этих объектах введена

Например, пусть– некоторое множество точек (или элементарных событий в теории вероятности),– множество подмножеств из. ЕслиA,Bпринадлежат, то можно ввестисумму множеств (дизъюнкцию)A+B=AB(равную объединению точек изАиВ), произведение множеств (конъюнкцию)АВ=А В(равное набору точек, входящих и вА, и вBодновременно) и дополнение(отрицаниеА), т. е.– множество точек из, не входящих вА. Тогда для этих операций (и это легко проверить) будут выполнены свойства 1–6. Таким образом, множество всех подмножеств изявляетсябулевой алгеброй.

3. ДНФ, СДНФ, КНФ, СКНФ

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

Например, является простой конъюнкцией,

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

Например, выражение является ДНФ.

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

Например, выражение является ДНФ, но не СДНФ. Выражениеявляется СДНФ.

Аналогичные определения (с заменой конъюнкции на дизъюнкцию и наоборот) верны для КНФ и СКНФ. Приведем точные формулировки.

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

Конъюнктивнойнормальнойформой(КНФ)называетсяконъюнкцияпростыхдизъюнкций(например выражение– КНФ).

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

Например, выражение является СКНФ.

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

а) переход от ДНФ к КНФ

Алгоритм этого перехода следующий: ставим над ДНФ два отрицания и с помощью правил де Моргана (не трогая верхнее отрицание) приводим отрицание ДНФ снова к ДНФ. При этом приходится раскрывать скобки с использованием правила поглощения (или правила Блейка). Отрицание (верхнее) полученной ДНФ (снова по правилу де Моргана) сразу дает нам КНФ:

Заметим, что КНФ можно получить и из первоначального выражения, если вынести уза скобки;

б) переход от КНФ к ДНФ

Этот переход осуществляется простым раскрытием скобок (при этом опять-таки используется правило поглощения)

Таким образом, получили ДНФ.

Обратный переход (от СДНФ к ДНФ) связан с проблемой минимизации ДНФ. Подробнее об этом будет рассказано в разд. 5, здесь же мы покажем, как упростить ДНФ (или СДНФ) по правилу Блейка. Такая ДНФ называется

в) сокращение ДНФ (или СДНФ) по правилуБлейка

Применение этого правила состоит из двух частей:

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

— если добавляемое слагаемое уже содержалось в ДНФ, то его можно отбросить совсем, например,

Разумеется, сокращенная ДНФ не определяется единственным образом, но все они содержат одинаковое число букв (например, имеется ДНФ , после применения к ней правила Блейка можно прийти к ДНФ, равносильной данной):

в) переход от ДНФ к СДНФ

Если в какой-то простой конъюнкции недостает переменной, например, z, вставляем в нее выражение,после чего раскрываем скобки (при этом повторяющиеся дизъюнктные слагаемые не пишем). Например:

г) переход от КНФ к СКНФ

Этот переход осуществляется способом, аналогичным предыдущему: если в простой дизъюнкции не хватает какой-то переменной (например, z, то добавляем в нее выражение(это не меняет самой дизъюнкции), после чего раскрываем скобки с использованием распределительного закона):

Таким образом, из КНФ получена СКНФ.

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

9.Днф и кнф

1)ДНФ назыв. дизъюнкция элементар. коньюкций

2)КНФ назыв. коньюкция элементар. дизъюнкций

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

Форма вида (краткая запись), где- дизъюнкцииназывается конъюнктивной нормальной формой (КНФ).

Такими являются, например, выражения:

, . Для любой формулы алгебры логики существует равносильная ей конъюнктивная нормальная форма.

10.Алгебра Жегалкина. Полином Жегалкина

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

Непосредственно проверкой (с помощью таблиц истинности) устанавливаются следующие законы:

– закон коммутативности; – закон ассоциативности;

В алгебре Жегалкина роль совершенных нормальных форм булевой алгебры играют полиномы Жегалкина.

Полиномом Жегалкина называется полином вида

причем в каждом наборе все координаты различны, а суммирование ведется по некоторому множеству таких не совпадающих наборов, а – константа 0 или 1.

Например, выражение является полиномом Жегалкина, а выраженияи– нет, так как в первом выражении имеется конъюнкция, содержащая две переменные y, а второе выражение содержит два одинаковых слагаемыхи.

Каждая булева функция может быть единственным образом выражена при помощи полинома Жегалкина.

11.Теоремы о разложении.

1 Всякая булева функция f(x1,x2,…,xn) может быть представлена в следующей форме:

где 1 ≤ k ≤ n, в дизъюнкции берется по всем наборам значений переменных.

Разложение по переменной Xn:

Если булева функция не есть константа 0, то справедливо разложение

Разложение по всем переменным:

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

Теорема 2 Всякая булева функция может быть представлена в следующей форме:

где 1≤k≤n, а конъюнкция берется по всем 2k наборам значений переменных.

Теорема3.Для любой формулы алгебры логики существует равносильная ей дизъюнктивная нормальная форма.

Теорема 4 Для любой формулы алгебры логики существует равносильная ей конъюнктивная нормальная форма.

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

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

12.Сднф и скнф. Алгоритмы их нахождения.

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

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

Таким образом, существует взаимно однозначное соответствие между таблицей истинности функции и ее СДНФ. А это значит, что СДНФ для булевой функции единственна.

Единая булева функция, не имеющая СДНФ, есть константа 0.

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

однозначное соответствие между таблицей истинности функции и ее СКНФ. А это значит, что СКНФ для булевой функции единственна.

Единственная булева функция, не имеющая СКНФ, есть константа 1

Контрольное задание №2. Получить сднф, скнф, используя таблицу истинности. Построить днф, кнф, упростив выражение.

((х  у)  (х  z))y

Методические указания

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

Характеристическое множество логической переменной функции – это множество М₁ двоичных наборов, на котором функция принимает значение 1. Логическая функция может быть задана с помощью своего характеристического множества М₁ или с помощью множества М₀ наборов, на котором она равна 0.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• 1. Если формула F(xi. x_n) не является булевой, т. е. содержит символы «—?» и «=», то используя равносильности 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. х_п), то это означает, что /( п ячеек, каждая из которых соответствует одной из 2 п возможных комбинаций значений п логических переменных ад, . х_п. Столбцы таблицы соответствуют значениям переменных . Хк, строки — значениям переменных Хк+, х_п, а соседние ячейки отличаются значением только одной переменной.

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

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

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

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

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

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

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

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