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

ДНФ, СДНФ, КНФ, СКНФ

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

Конъюнкцией 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_n).

Заметим, что в перечисленных далее свойствах в роли 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, то добавляем в нее выражение (это не меняет самой дизъюнкции), после чего раскрываем скобки с использованием распределительного закона):

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

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

Совершенная нормальная форма — дизъюнктивная и конъюнктивная, правило построения

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

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

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

Осторожно! Если преподаватель обнаружит плагиат в работе, не избежать крупных проблем (вплоть до отчисления). Если нет возможности написать самому, закажите тут.

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

ДНФ выглядит следующим образом:

СДНФ обладает некоторыми определенными свойствами:

включает различные элементарные конъюнкции;
все логические слагаемые формулы содержат все переменные, которые входят в функцию F;
ни в одном логическом слагаемом не содержится переменная и её отрицание.

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

При построении таблицы истинности важно помнить, что логические переменные со значением «0» необходимо брать с отрицанием.

Что такое СКНФ

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

Формула должна соответствовать нескольким условиям, чтобы называться СКНФ:

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

Правила построения по таблице истинности

Дизъюнктивная форма

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

Конъюнктивная форма

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

Алгоритм приведения к СДНФ и СКНФ

Рассмотрим логическую функцию в виде таблицы истинности.

Алгоритм построения СДНФ по таблице истинности выглядит следующим образом:

Отметить наборы переменных, значение функции F на которых равно 1.
Записать для всех отмеченных наборов конъюнкцию всех переменных так: если значение некоторой переменной в этом наборе равняется 1, в конъюнкцию включается сама переменная. В случае противного результата, в конъюнкцию включается ее отрицание.
Связать полученные конъюнкции операциями дизъюнкции.

Построим совершенную ДНФ:

И как результат получим следующую СДНФ:

Алгоритм построения СКНФ по таблице истинности выглядит следующим образом:

Отметить в таблице истинности наборы переменных, значение функции F на которых равно 0.
Записать для всех отмеченных наборов дизъюнкцию всех переменных — в том случае, когда значение некоторой переменной в этом наборе равняется 0, в дизъюнкцию включается сама переменная, если происходит наоборот, то в дизъюнкцию включается ее отрицание.
Связать полученные дизъюнкции операциями конъюнкции.

Построим совершенную КНФ:

И как результат получим следующую СКНФ:

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

Доказательство эквивалентности

Эквивалентность — понятие, означающее, что две и более формул представляют одну и ту же функцию. Для обозначения эквивалентности могут использоваться следующие знаки: $ \equiv , = , \Leftrightarrow .$

Доказать эквивалентность формул можно двумя способами.

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

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

Поглощение

Склеивание

Обобщенное склеивание

$xz\;\vee\;y\overline z\;\vee\;xy\;=\;xz\;\vee y\overline z$

$xz\;\vee\;y\overline z\;\vee\;xy\;=\;xz\;\vee y\overline z\;\vee\;xyz\;\vee\;xy\overline z\;=\;xz\;\vee\;y\overline z$

Расщепление

$x\;\vee\;\overline xy\;=\;xy\;\vee\;x\overline y\;\vee\;\overline xy\;=\;xy\;\vee\;x\overline y\;\vee\;xy\;\vee\;\overline xy\;=\;x\;\cdot\;l\;\;\vee\;y\;\cdot\;l\;=\;x\;\vee\;y$

Примеры с решением

Задача №1

Приведите к СКНФ $((((A\rightarrow B)\rightarrow\overline A)\rightarrow\overline B)\rightarrow\overline C)$ .

Через применение закона де Моргана и правила $ x\;\rightarrow\;y\;=\;\overline x\;\vee\;y$ упростим выражения:

$F\;=\;((((A\;\rightarrow\;B)\;\rightarrow\;\overline A)\;\rightarrow\overline B)\;\rightarrow\;\overline C)\;=\;(((\overline A\;\vee\;B)\;\rightarrow\;\overline A)\;\rightarrow\;\overline B)\;\rightarrow\overline C\;)\;=$

$=\;((((\overline A\;\vee\;B)\;\rightarrow\overline A)\;\rightarrow\overline B)\;\rightarrow\;\overline C)\;=\;((\overline<((\overline A\;\vee\;B)>\;\vee\;\overline A)\;\rightarrow\overline B)\;\rightarrow\overline C)\;=$

$=(((\overline A\;\vee\;B)\;\vee\;\overline A)\;\rightarrow\;\overline B)\;\rightarrow\;\overline C)\;=((\overline<(\overline<(\overline A\vee B)>\;\vee\;\overline A\;)>\;\vee\;\overline B)\;\rightarrow\;\overline C)\;=$

$=\;((\overline<(\overline A\;\vee\;B)>\;\vee\;\overline A)\;\wedge\;B)\;\vee\;\overline C\;=\;(((A\;\wedge\;\overline B)\;\vee\;\overline A)\;\wedge B)\;\vee\;\overline C\;=$

$=((A\overline B\;\vee\;\overline A)\;\vee\;\overline A)\;\wedge\;B)\;\vee\;\overline C\;=(((A\;\wedge\;\overline B)\;\vee\;\overline A)\;\wedge\;B)\;\vee\;\overline C\;=$

$=\;((A\overline B\;\vee\;\overline A)\;\wedge\;B)\;\vee\;\overline C\;=\;(A\overline BB\;\vee\;\overline AB)\;\vee\;\overline C\;=\;(0\;\vee\;\overline AB)\;\vee\;\overline C\;=\;\overline AB\;\vee\;\overline C$

Далее приведем выражение к КНФ:

$F\;=\;\overline AB\;\vee\;\overline C\;\;=\;(\overline A\;\vee\;\overline C)\;\wedge\;(B\;\vee\;\overline C)$

Далее приведем выражение к СКНФ:

$F\;=\;(\overline A\;\vee\;\overline C)\;\wedge\;(B\;\vee\;\overline C)\;=\;(\overline A\;\vee\:\overline C\;\vee\;B\overline B)\;\wedge\;(A\overline A\;\vee\;B\;v\;\overline C)\;=$

$=\;(\overline A\;\vee\;\overline C\;\vee\;B)\;\wedge\;(A\;\vee\;B\;\vee\;\overline C)\;\wedge\;(\overline A\;\vee\;\overline C\;\vee\;\overline B)\;\wedge\;(\overline A\;\vee\;B\;\;\overline C)$

Задача №2

Используя эквивалентные преобразования, постройте ДНФ функции $f(\widetilde x^n)$

$f(\widetilde x^3) = (\overlinex_2\;\oplus\;x_3)\;\cdot\;(x_1x_3\;\rightarrow\;x_2)$

$f(\widetilde x^3) = (\overlinex_2\;\oplus\;x_3)\;\cdot\;(x_1x_3\;\rightarrow\;x_2) = ((\overlinex_2\;\cdot\;\overline\;)\;\vee\;(\overline<\overlinex_2>\;\cdot\;x_3))\;\cdot\;(\overline\;\vee\;x_2)\;=$

$=(\overlinex_2\overline\;\cdot(x_1\vee x_3\vee x_2)\;\vee\;x_1x_3\;\cdot\;(\overline\;\vee\;\overline\;\vee\;x_2)\;\vee\;\overlinex_3\;\cdot\;(\overline\;\vee\;\overline\;\vee\;x_2))\;=$

Построение СКНФ и СДНФ по таблице истинности

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

Нормальная форма существует в двух видах:

конъюнктивная нормальная форма (КНФ) — конъюнкция нескольких дизъюнкций, например, $\left(A\vee \overline\vee C\right)\wedge \left(A\vee C\right)$;

дизъюнктивная нормальная форма (ДНФ) — дизъюнкция нескольких конъюнкций, например, $\left(A\wedge \overline\wedge C\right)\vee \left(B\wedge C\right)$.

Совершенная конъюнктивная нормальная форма (СКНФ) — это КНФ, удовлетворяющая трем условиям:

не содержит одинаковых элементарных дизъюнкций;

ни одна из дизъюнкций не содержит одинаковых переменных;

каждая элементарная дизъюнкция содержит каждую переменную из входящих в данную КНФ.

Любая булева формула, которая не является тождественно истинной, может быть представлена в СКНФ.

Правила построения СКНФ по таблице истинности

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

Совершенная дизъюнктивная нормальная форма (СДНФ) — это ДНФ, удовлетворяющая трем условиям:

не содержит одинаковых элементарных конъюнкций;

ни одна из конъюнкций не содержит одинаковых переменных;

каждая элементарная конъюнкция содержит каждую переменную из входящих в данную ДНФ, к тому же в одинаковом порядке.

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

Правила построения СДНФ по таблице истинности

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

Примеры нахождения СКНФ и СДНФ

Записать логическую функцию по ее таблице истинности:

Решение:

Воспользуемся правилом построения СДНФ:

\[F\left(x_1,\ x_2,\ x_3\right)=\left(\overline\wedge \overline\wedge \overline\right)\vee \left(\overline\wedge \overline\wedge x_3\right)\vee \left(x_1\wedge \overline\wedge \overline\right)\vee \left(x_1\wedge \overline\wedge x_3\right)\vee \left(x_1\wedge x_2\wedge x_3\right)\]

Воспользуемся правилом построения СКНФ:

\[F\left(x_1,\ x_2,\ x_3\right)=\left(x_1\vee \overline\vee x_3\right)\wedge \left(x_1\vee \overline\vee \overline\right)\wedge \left(\overline\vee \overline\vee x_3\right)\]

Функция задана таблицей истинности:

Представить эту функцию в виде СДНФ и СКНФ.

Решение:

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

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

Полученные во вспомогательном столбце конъюнкции соединим знаком дизъюнкции и получим искомую логическую функцию в виде СДНФ:

Запишем логическую функцию в СКНФ.

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

Полученные во вспомогательном столбце дизъюнкции соединим знаком конъюнкции и получим искомую логическую функцию в виде СКНФ:

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, то ее отрицание.

Похожие публикации:

Privacy badger что это

Аудио сигнал в массив чем записать

Как посмотреть прикрепленные к html файлы

Как посмотреть скрытые процессы