Как из днф сделать кнф
Перейти к содержимому

Как из днф сделать кнф

  • автор:

«Учебник по дискретной математике ДНФ, СДНФ, КНФ, СКНФ»

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Это преобразование проводится достаточно просто: – Раскрыть скобки и упростить. Пример 1:

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

Здесь возможны два варианта. Первый вариант основан на многократном применении дистрибутивного закона дизъюнкции относительно конъюнкции п. 1.6. 8,б.Пример 2:Сначала распределяем , затеми, наконец, удаляем 1. Второй вариант сложнее. Порядок действий здесь таков. 1. Взять двойное отрицание от всего выражения; 2. Используя одно отрицание и законы де Моргана, перевести исходное выражение под вторым отрицанием в КНФ (второе отрицание сохранить); 3. Перевести полученную КНФ под общим отрицанием в ДНФ – раскрыть скобки и упростить. Получим ДНФ с общим отрицанием; 4. Используя второе отрицание и законы де Моргана перевести результат предыдущего действия в КНФ. Пример 3:

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

Если требуется сравнить две логические функции f1 и f2, то следует преобразовать их или представить в виде а) Таблиц истинности – ТИ1 и ТИ2; б) СДНФ – СДНФ1 и СДНФ2; в) СКНФ – СКНФ1 и СКНФ2; г) Полиномов Жегалкина. Сравнение логических функций с помощью таблиц истинности – это стандартный прием, а почему сравнение логических функций удобно проводить в совершенных формах или в форме полинома Жегалкина? Ответ прост: логическая функция может иметь много формул, ее представляющих, но совершенные формы и полином жегалкина у нее единственны. Замечание:От СДНФ легко можно перейти к СКНФ, (а от СКНФ к СДНФ) – если СДНФ имеетkконъюнкций, то СКНФ будет иметь 2 nkдизъюнкций, гдеn– число переменных (если СКНФ имеетkдизъюнкций, то СДНФ будет иметь 2 nkконъюнкций). Пример: Доказать, что.

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

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

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

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

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

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

  1. По СДНФ или по СКНФ легко построить таблицу истинности (табл. 11.4).
Таблица 11.4
x y z f
0 0 0 0 0
1 0 0 1 1
2 0 1 0 0
3 0 1 1 1
4 1 0 0 0
5 1 0 1 1
6 1 1 0 1
7 1 1 1 1

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

В п. 11.2.1 (правила 13 (1) и (2)) показаны два варианта разложения логической функции по переменным. При разложении логической функции по всем переменным по варианту (1) получается СДНФ, а по варианту (2) – СКНФ. Реализовать эти разложения можно либо последовательно, либо параллельно. В качестве примера рассмотрим разложение функции а) Последовательное разложение логической функции по всем переменным Разложение по 13 (1) Разложение по переменнойx1 Сначала определяем значение функции приx1= 1 и получаемЗатем при x1= 0 получаем Подставив полученные значения функции fв выражение дляf1, получаем В результате разложения по x1получили функцию Разложение по переменнойx2 Действуя аналогично, но с функцией , получаем Таким образом, Разложение по переменнойx3Получили СДНФ функции. разложение по13 (2) Имеем функцию . Разложение по переменнойx1Сначала в формулу вместоx1подставляем 0 и получаемПриx1= 1 получаем Разложение по переменнойx2 Имеем Обратите внимание на скобку , которая преобразуется впо дистрибутивному закону 8,б (см. п. 1.6). Разложение по переменнойx3 Имеем Здесь также применяется дистрибутивный закон 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 Вопросы для контроля

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

— нуля и единицы, — повторения, — дополнительности, — коммутативные, — ассоциативные и — дистрибутивные.

  1. Приведите законы:

— поглощения, — склеивания и — де Моргана.

  1. Покажите на примерах разложение логических функций по переменным.
  2. Как доказываются тождества в булевой алгебре?

ДНФ, КНФ, Минимальная форма. Как решать задачи такого рода?

f55c0e1000604d29ae47bd9fb76fadd4.png

Доброй ночи тостер, наверно надо извиниться за вопрос такого рода, но к сожалению пропустил лекцию и из всех заданий никак не пойму И не могу найти информацию в интернете по именно этому заданию.
— Надо «определить DNF, KNF и минимальную форму от p(x, y, z)»

Это не домашнее задание на какие-либо зачеты. Просто очень важно понять, как это решается. В интернете нахожу только с базовыми операторами V, ^, ! и таблицами, где DNF = все единицы. KNF = все нули. Но как я понял задание, тут надо доказывать без всяких таблиц.
— Буду рад не столько за решение, сколько за обьяснение со всякими нюансами (понятные статьи в интернете именно в таком стиле, как это на картинке) .
п.с. у нас все на немецком, так что на русском это очень усложняет поиск 🙂

  • Вопрос задан более трёх лет назад
  • 2160 просмотров

ДНФ и КНФ

Стандартный базис. Элементарные формулы — литералы. Элементарная конъюнкция (дизъюнкция). Дизъюнктивная (конъюнктивная) нормальная форма и совершенная форма. Теорема: любая булева функция, отличная от 0 (от 1) представима в виде СДНФ (СКНФ). Полнота стандартного базиса. Примеры полных базисов: базис Жегалкина, штрих Шеффера, стрелка Пирса.

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

Здесь мы будем называть литералом переменную x или ее отрицание x и обозначать xˆ. Булево пересечение нескольких литералов, определяемых различными переменными, т.е. выражение вида X = xˆ12 . . . xˆл, называется элементарной конъюнкцией. Требование, чтобы все переменные были различны обусловливается следующим. Если в конъюнкцию входит несколько одинаковых литералов, то в силу коммутативности, ассоциативности и идемпотентности конъюнкции можно, переходя к эквивалентной формуле, оставить лишь один литерал (например, x 1 x 1 = x 1). Если в конъюнкцию входит переменная и ее отрицание, то формула эквивалентна константе 0, поскольку x x = 0 и для любой формулы Y имеем Y x x = 0.

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

Если состав переменных в каждой элементарной конъюнкции данной ДНФ один и тот же, то ДНФ называется совершенной. Приведенный пример — это ДНФ, не являющаяся совершен- ной. Напротив, формула

есть совершенная форма.

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

Теорема 1.4. Любая булева функция, отличная от константы 0 представима в виде СДНФ.

Дискретная математика

◀Условимся под x σ понимать формулу x, если σ = 1, и формулу x , если σ = 0. Пусть функция f(y1, . . . , yn) принимает значение 1 на векторе (t1, . . . , tn) (такой вектор называют конституэнтой единицы). Тогда элементарная конъюнкция также принимает значение 1 на этом наборе, но обращается в нуль на всех остальных n-мерных булевых векторах. Рассмотрим формулу

Формула Φ. ДНФ и КНФ

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

Нетрудно заметить, что формула Φ обращается в 1 при тех, и только при тех значениях переменных, при которых обращается в 1 рассматриваемая функция. Значит, формула Ψ представляет функцию f. ▶

Следствие 1.1. Стандартный базис является полным.

◀ Действительно, если функция не является константой 0, то она представима либо в виде СДНФ, которая является формулой над стандартным базисом. Константу 0 можно представить, например, формулой f(x1, x2, . . . , xn) = x1 x 1. ▶

Пример 1.2. Рассмотрим функцию трех переменных m(x1, x2, x3) (табл. 1.4), называемую мажоритарной функцией. Эта функция принимает значение 1, если больше половины ее аргументов имеют значение 1. Поэтому ее часто называют функцией голосования. Построим для нее СДНФ.

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

Аналогично строится СКНФ. Выбираем конституэнты нуля и для каждой составляем элементарную дизъюнкцию. Получим:

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

Пример 1.3. Множество из операций сложения по модулю 2, умножения и константы 1 называют базисом Жегалкина. Сложение по модулю 2 и умножение — базовые операции кольца Z2, выражения, составленные с их помощью — это многочлены над кольцом Z2. Кон- станта 1 в данном случае необходима для записи свободного члена. Поскольку xx = x, то все сомножители в многочлене имеют степень 1. Поэтому при записи многочлена можно обойтись без понятия степени. Примеры формул над базисом Жегалкина:

xy⊕x⊕y, x⊕1, xyz⊕xz⊕x⊕y⊕1.

Любую такую формулу называют полиномом Жегалкина. Фактически полином Жегалкина — это многочлен над кольцом Z2.

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

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

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

Пример 1.4. Рассмотрим множество из единственной функции — штриха Шеффера*. Это множество полно, что следует из следующих легко проверяемых тождеств:

x =x|x, xy= x|y =(x|y)|(x|y), x+y= x | y =(x|x)|(y|y).

Пример 1.5. Базис, состоящий из единственной функции — стрелки Пирса, также является полным. Проверка этого аналогична случаю штриха Шеффера. Впрочем, это заключение можно сделать и на основании принципа двойственности для симметричных полуколец.

*Штрих Шеффера — бинарная, но не ассоциативная операция. Поэтому при использовании инфиксной формы следует быть внимательным: результат зависит от порядка выполнения операций. В этом случае рекомендуется явно указывать порядок операций при помощи скобок, например писать (x | y) | z, а не x | y | z, хотя обе формы равнозначны.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *