Конъюнктивная совершенная нормальная форма: Совершенная конъюнктивная нормальная форма — Википедия – Конъюнктивная нормальная форма — Википедия

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

Материал из Википедии — свободной энциклопедии

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

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

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

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

В ячейках строки́ f(x1,x2,x3,x4){\displaystyle f(x_{1},x_{2},x_{3},x_{4})} отмечаются лишь те комбинации, которые приводят логическое выражение в состояние нуля.

Четвёртая строка содержит 0 в указанном поле. Отмечаются значения всех четырёх переменных, это:

• x1=0{\displaystyle x_{1}=0}
• x2=0{\displaystyle x_{2}=0}
• x3=1{\displaystyle x_{3}=1}
• x4=1{\displaystyle x_{4}=1}

В дизъюнкцию записывается переменная без инверсии, если она в наборе равна 0, и с инверсией, если она равна 1. Первый член СКНФ рассматриваемой функции выглядит так: x1∨x2∨x3¯∨x4¯{\displaystyle x_{1}\vee x_{2}\vee {\overline {x_{3}}}\vee {\overline {x_{4}}}}

Остальные члены СКНФ составляются по аналогии:^[2]

(x1∨x2∨x3¯∨x4¯)∧(x1∨x2¯∨x3∨x4)∧(x1∨x2¯∨x3∨x4¯)∧(x1∨x2¯∨x3¯∨x4¯)∧{\displaystyle ({x_{1}}\lor {x_{2}}\lor {\overline {x_{3}}}\lor {\overline {x_{4}}})\land ({x_{1}}\lor {\overline {x_{2}}}\lor {x_{3}}\lor {x_{4}})\land ({x_{1}}\lor {\overline {x_{2}}}\lor {x_{3}}\lor {\overline {x_{4}}})\land ({x_{1}}\lor {\overline {x_{2}}}\lor {\overline {x_{3}}}\lor {\overline {x_{4}}})\land }

(x1¯∨x2∨x3∨x4)∧(x1¯∨x2∨x3∨x4¯)∧(x1¯∨x2∨x3¯∨x4)∧(x1¯∨x2∨x3¯∨x4¯)∧{\displaystyle ({\overline {x_{1}}}\lor {x_{2}}\lor {x_{3}}\lor {x_{4}})\land ({\overline {x_{1}}}\lor {x_{2}}\lor {x_{3}}\lor {\overline {x_{4}}})\land ({\overline {x_{1}}}\lor {x_{2}}\lor {\overline {x_{3}}}\lor {x_{4}})\land ({\overline {x_{1}}}\lor {x_{2}}\lor {\overline {x_{3}}}\lor {\overline {x_{4}}})\land }

(x1¯∨x2¯∨x3∨x4)∧(x1¯∨x2¯∨x3∨x4¯){\displaystyle ({\overline {x_{1}}}\lor {\overline {x_{2}}}\lor {x_{3}}\lor {x_{4}})\land ({\overline {x_{1}}}\lor {\overline {x_{2}}}\lor {x_{3}}\lor {\overline {x_{4}}})}

Конъюнктивная нормальная форма — Википедия

Материал из Википедии — свободной энциклопедии

Конъюнкти́вная норма́льная фо́рма (КНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид конъюнкции дизъюнкций литералов. Конъюнктивная нормальная форма удобна для автоматического доказательства теорем. Любая булева формула может быть приведена к КНФ.^[1] Для этого можно использовать: закон двойного отрицания, закон де Моргана, дистрибутивность.

Формулы

в КНФ:

¬A∧(B∨C),{\displaystyle \neg A\wedge (B\vee C),}

(A∨B)∧(¬B∨C∨¬D)∧(D∨¬E),{\displaystyle (A\vee B)\wedge (\neg B\vee C\vee \neg D)\wedge (D\vee \neg E),}

A∧B.{\displaystyle A\wedge B.}

Формулы не в КНФ:

¬(B∨C),{\displaystyle \neg (B\vee C),}

(A∧B)∨C,{\displaystyle (A\wedge B)\vee C,}

A∧(B∨(D∧E)).{\displaystyle A\wedge (B\vee (D\wedge E)).}

Но эти 3 формулы не в КНФ эквивалентны следующим формулам в КНФ:

¬B∧¬C,{\displaystyle \neg B\wedge \neg C,}

(A∨C)∧(B∨C),{\displaystyle (A\vee C)\wedge (B\vee C),}

A∧(B∨D)∧(B∨E).{\displaystyle A\wedge (B\vee D)\wedge (B\vee E).}

Алгоритм построения КНФ[править | править код]

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

A→B=¬A∨B,{\displaystyle A\rightarrow B=\neg A\vee B,}

A↔B=(¬A∨B)∧(A∨¬B).{\displaystyle A\leftrightarrow B=(\neg A\vee B)\wedge (A\vee \neg B).}

2) Заменить знак отрицания, относящийся ко всему выражению, знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул:

¬(A∨B)=¬A∧¬B,{\displaystyle \neg (A\vee B)=\neg A\wedge \neg B,}

¬(A∧B)=¬A∨¬B.{\displaystyle \neg (A\wedge B)=\neg A\vee \neg B.}

3) Избавиться от знаков двойного отрицания.

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

Пример построения КНФ[править | править код]

Приведем к КНФ формулу

F=(X→Y)∧((¬Y→Z)→¬X).{\displaystyle F=(X\rightarrow Y)\wedge ((\neg Y\rightarrow Z)\rightarrow \neg X).}

Преобразуем формулу F{\displaystyle F} к формуле, не содержащей →{\displaystyle \rightarrow }:

F=(¬X∨Y)∧(¬(¬Y→Z)∨¬X)=(¬X∨Y)∧(¬(¬¬Y∨Z)∨¬X).{\displaystyle F=(\neg X\vee Y)\wedge (\neg (\neg Y\rightarrow Z)\vee \neg X)=(\neg X\vee Y)\wedge (\neg (\neg \neg Y\vee Z)\vee \neg X).}

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

F=(¬X∨Y)∧((¬Y∧¬Z)∨¬X).{\displaystyle F=(\neg X\vee Y)\wedge ((\neg Y\wedge \neg Z)\vee \neg X).}

По закону дистрибутивности получим КНФ:

F=(¬X∨Y)∧(¬X∨¬Y)∧(¬X∨¬Z).{\displaystyle F=(\neg X\vee Y)\wedge (\neg X\vee \neg Y)\wedge (\neg X\vee \neg Z).}

k-конъюнктивной нормальной формой называют конъюнктивную нормальную форму, в которой каждая дизъюнкция содержит ровно k литералов.

Например, следующая формула записана в 2-КНФ:

(A∨B)∧(¬B∨C)∧(B∨¬C).{\displaystyle (A\lor B)\land (\neg B\lor C)\land (B\lor \neg C).}

Если в простой дизъюнкции не хватает какой-то переменной (например, z), то добавляем в неё выражение :Z∧¬Z=0{\displaystyle Z\wedge \neg Z=0} (это не меняет самой дизъюнкции), после чего раскрываем скобки с использованием распределительного закона:

(X∨Y)∧(X∨¬Y∨¬Z)=(X∨Y∨(Z∧¬Z))∧(X∨¬Y∨¬Z)=(X∨Y∨Z)∧(X∨Y∨¬Z)∧(X∨¬Y∨¬Z).{\displaystyle (X\vee Y)\wedge (X\vee \neg Y\vee \neg Z)=(X\vee Y\vee (Z\wedge \neg Z))\wedge (X\vee \neg Y\vee \neg Z)=(X\vee Y\vee Z)\wedge (X\vee Y\vee \neg Z)\wedge (X\vee \neg Y\vee \neg Z).}

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

Формальная грамматика, описывающая КНФ[править | править код]

Следующая формальная грамматика описывает все формулы, приведенные к КНФ:

<КНФ> → <дизъюнкт>

<КНФ> → <КНФ> ∧ <дизъюнкт>

<дизъюнкт> → <литерал>;

<дизъюнкт> → (<дизъюнкт> ∨ <литерал>)

<литерал> → <терм>

<литерал> → ¬<терм>

где <терм> обозначает произвольную булеву переменную.

В теории вычислительной сложности важную роль играет задача выполнимости булевых формул в конъюнктивной нормальной форме. Согласно теореме Кука, эта задача NP-полна, и она сводится к задаче о выполнимости формул в 3-КНФ, которая сводится и к которой в свою очередь сводятся другие NP-полные задачи.

Задача о выполнимости 2-КНФ формул может быть решена за линейное время.

1. ↑ Поздняков С.Н., Рыбин С.В. Дискретная математика. — С. 303.

• Ю.И. Галушкина, А.Н. Марьямов: Конспект лекций по дискретной математике — 2-е изд., испр. — М.: Айрис-пресс, 2008. — 176 с. — (Высшее образование)

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

Материал из Википедии — свободной энциклопедии

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

• в ней нет одинаковых элементарных конъюнкций
• в каждой конъюнкции нет одинаковых пропозициональных переменных^{[уточнить]}
• каждая элементарная конъюнкция содержит каждую пропозициональную букву из входящих в данную ДНФ пропозициональных букв, причём в одинаковом порядке.

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

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

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

x1{\displaystyle x_{1}}	x2{\displaystyle x_{2}}	x3{\displaystyle x_{3}}	f(x1,x2,x3){\displaystyle f(x_{1},x_{2},x_{3})}
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	0

В ячейках результата f(x1,x2,x3){\displaystyle f(x_{1},x_{2},x_{3})} отмечаются лишь те комбинации, которые приводят логическое выражение в состояние единицы. Далее рассматриваются значения переменных, при которых функция равна 1. Если значение переменной равно 0, то она записывается с инверсией. Если значение переменной равно 1, то без инверсии.

Первая строка содержит 1 в указанном поле. Отмечаются значения всех трёх переменных, это:

• x1=0{\displaystyle x_{1}=0}
• x2=0{\displaystyle x_{2}=0}
• x3=0{\displaystyle x_{3}=0}

Нулевые значения — тут все переменные представлены нулями — записываются в конечном выражении инверсией этой переменной. Первый член СДНФ рассматриваемой функции выглядит так: x1¯⋅x2¯⋅x3¯{\displaystyle {\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot {\overline {x_{3}}}}

Переменные второго члена:

• x1=0{\displaystyle x_{1}=0}
• x2=0{\displaystyle x_{2}=0}
• x3=1{\displaystyle x_{3}=1}

x3{\displaystyle x_{3}} в этом случае будет представлен без инверсии: x1¯⋅x2¯⋅x3{\displaystyle {\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot x_{3}}

Таким образом анализируются все ячейки f(x1,x2,x3){\displaystyle f(x_{1},x_{2},x_{3})}. Совершенная ДНФ этой функции будет дизъюнкцией всех полученных членов (элементарных конъюнкций).

Совершенная ДНФ этой функции:

f(x1,x2,x3)=(x1¯∧x2¯∧x3¯)∨(x1¯∧x2¯∧x3)∨(x1¯∧x2∧x3¯)∨(x1∧x2∧x3¯){\displaystyle f(x_{1},x_{2},x_{3})=({\overline {x_{1}}}\land {\overline {x_{2}}}\land {\overline {x_{3}}})\vee ({\overline {x_{1}}}\land {\overline {x_{2}}}\land x_{3})\vee ({\overline {x_{1}}}\land x_{2}\land {\overline {x_{3}}})\vee (x_{1}\land x_{2}\land {\overline {x_{3}}})}

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

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

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

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

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

СКНФ

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

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

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

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

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

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

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

СДНФ

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

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

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

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

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

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

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

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

Пример 1

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

Рисунок 1.

Решение:

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

Рисунок 2.

Получим СДНФ:

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

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

Рисунок 3.

Получим СКНФ:

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

Пример 2

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

Рисунок 4.

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

Решение:

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

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

   

   Рисунок 5.

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

   \[F\left(x_1,x_2,x_3,x_4\right)=\left(\overline{x}\wedge \overline{y}\wedge z\wedge f\right)\vee \left(\overline{x_1}\wedge x_2\wedge \overline{x_3}\wedge \overline{x_4}\right)\vee \left(\overline{x_1}\wedge x_2\wedge x_3\wedge x_4\right)\vee \left(x_1\wedge \overline{x_2}\wedge \overline{x_3}\wedge \overline{x_4}\right).\]

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

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

   

   Рисунок 6.

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

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

Дизъюнктивные и конъюнктивные совершенные нормальные формы

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

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

Среди нормальных форм выделяются совершенные нормальные формы (такие формы, в которых функции записываются единственным образом).

Совершенная дизъюнктивная нормальная форма (СДНФ)

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

Примеры: y,   ¬ y,   х₁ ∧ ¬ х₂ ∧ х₃ ∧ х₄

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

ДНФ записывается в следующей форме: F₁ ∨ F₂ ∨ … ∨ F_n, где F_i — элементарная конъюнкция

Примеры: ¬ х₁ ∧ х₂ ∨ х₁ ∧ ¬ х₂ ∨ х₁ ∧ ¬ х₂ ∧ х₃,   ¬ y₁ ∨ y₁ ∧ y₂ ∨ ¬ y₂

Определение. Логическая формула от k переменных называется совершенной дизъюнктивной нормальной формой (СДНФ), если:
1) формула является ДНФ, в которой каждая элементарная конъюнкция есть конъюнкция k переменных х₁, х₂, …, х_k, причем на i-м месте этой конъюнкции стоит либо переменная х_i, либо ее отрицание;
2) все элементарные конъюнкции в такой ДНФ попарно различны.

Пример: (¬ х₁ ∧ х₂ ∧ х₃) ∨ (х₁ ∧ ¬ х₂ ∧ х₃) ∨ (х₁ ∧ х₂ ∧ ¬ х₃)

Совершенная конъюнктивная нормальная форма (СКНФ)

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

Примеры: ¬ х₃,    х₁ ∨ х₂,    х₁ ∨ х₂ ∨ ¬ х₃

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

КНФ записывается в следующей форме: F₁ ∧ F₂ ∧ … ∧ F_n, где F_i — элементарная дизъюнкция

Примеры: (х₁ ∨ ¬ х₂) ∧ х₃,    (х₁ ∨ х₂) ∧ ( ¬ х₁ ∨ х₂ ∨ х₃) ∧ ( х₁ ∨ ¬ х₂ ∨ ¬ х₃)

Определение. Логическая формула от k переменных называется совершенной конъюнктивной нормальной формой (КДНФ), если:
1) формула является КНФ, в которой каждая элементарная дизъюнкция есть дизъюнкция k переменных х₁, х₂, …, х_k, причем на i-м месте этой дизъюнкции стоит либо переменная х_i, либо ее отрицание;
2) все элементарные дизъюнкции в такой КНФ попарно различны.

Пример: (х₁ ∨ х₂ ∨ х₃) ∧ ( ¬ х₁ ∨ ¬ х₂ ∨ х₃)

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

Алгоритм построения СДНФ по таблице истинности

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

Алгоритм построения СКНФ по таблице истинности

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

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

Пример: Дана таблица истинности логической функции от трех переменных. Построить логическую формулу, реализующую эту функцию.

x	y	z	F (x, y, z)
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

Т.к. на большинстве строк таблицы истинности значение функции равно 1, то построим СКНФ. В результате получим следующую логическую формулу:
F = (¬ x ∨ y ∨ z) ∧ (¬ x ∨ y ∨ ¬ z)

Проверим полученную формулу. Для этого построим таблицу истинности функции.

x	y	z	¬ x	¬ x ∨ y ∨ z	¬ z	¬ x ∨ y ∨ ¬ z	F (x, y, z)
0	0	0	1	1	1	1	1
0	0	1	1	1	0	1	1
0	1	0	1	1	1	1	1
0	1	1	1	1	0	1	1
1	0	0	0	0	1	1	0
1	0	1	0	1	0	0	0
1	1	0	0	1	1	1	1
1	1	1	0	1	0	1	1

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

Дизъюнктивная нормальная форма — Википедия

Материал из Википедии — свободной энциклопедии

Дизъюнкти́вная норма́льная фо́рма (ДНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид дизъюнкции конъюнкций литералов. Любая булева формула может быть приведена к ДНФ.^[1] Для этого можно использовать закон двойного отрицания, закон де Моргана, закон дистрибутивности. Дизъюнктивная нормальная форма удобна для автоматического доказательства теорем.

Формулы в ДНФ:

A∨B{\displaystyle A\lor B}

(A∧B)∨¬A{\displaystyle (A\land B)\lor \neg A}

(A∧B∧¬C)∨(¬D∧E∧F)∨(C∧D)∨B{\displaystyle (A\land B\land \neg C)\lor (\neg D\land E\land F)\lor (C\land D)\lor B}

Формулы не в ДНФ:

¬(A∨B){\displaystyle \neg (A\lor B)}

A∨(B∧(C∨D)){\displaystyle A\lor (B\land (C\lor D))}

Но последние две формулы эквивалентны следующим формулам в ДНФ:

¬A∧¬B{\displaystyle \neg A\land \neg B}

A∨(B∧C)∨(B∧D).{\displaystyle A\lor (B\land C)\lor (B\land D).}

Алгоритм построения ДНФ[править | править код]

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

A→B=¬A∨B{\displaystyle A\rightarrow B=\neg A\vee B}

A↔B=(A∧B)∨(¬A∧¬B){\displaystyle A\leftrightarrow B=(A\wedge B)\vee (\neg A\wedge \neg B)}

2) Заменить знак отрицания, относящийся ко всему выражению, знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул:

¬(A∨B)=¬A∧¬B{\displaystyle \neg (A\vee B)=\neg A\wedge \neg B}

¬(A∧B)=¬A∨¬B{\displaystyle \neg (A\wedge B)=\neg A\vee \neg B}

3) Избавиться от знаков двойного отрицания.

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

Пример построения ДНФ[править | править код]

Приведем к ДНФ формулу F=¬((X→Y)∨¬(Y→Z)){\displaystyle F=\neg ((X\rightarrow Y)\vee \neg (Y\rightarrow Z))}

Выразим логическую операцию → через ∨∧¬{\displaystyle \vee \wedge \neg }

F=¬((¬X∨Y)∨¬(¬Y∨Z)){\displaystyle F=\neg ((\neg X\vee Y)\vee \neg (\neg Y\vee Z))}

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

F=(¬¬X∧¬Y)∧(¬Y∨Z)=(X∧¬Y)∧(¬Y∨Z){\displaystyle F=(\neg \neg X\wedge \neg Y)\wedge (\neg Y\vee Z)=(X\wedge \neg Y)\wedge (\neg Y\vee Z)}

Используя закон дистрибутивности, получаем:

F=(X∧¬Y∧¬Y)∨(X∧¬Y∧Z){\displaystyle F=(X\wedge \neg Y\wedge \neg Y)\vee (X\wedge \neg Y\wedge Z)}

Используя идемпотентность конъюкции, получаем ДНФ:

F=(X∧¬Y)∨(X∧¬Y∧Z){\displaystyle F=(X\wedge \neg Y)\vee (X\wedge \neg Y\wedge Z)}

k-дизъюнктивной нормальной формой называют дизъюнктивную нормальную форму, в которой каждая конъюнкция содержит ровно k литералов.

Например, следующая формула записана в 2-ДНФ:

(A∧B)∨(¬B∧C)∨(B∧¬C){\displaystyle (A\land B)\lor (\neg B\land C)\lor (B\land \neg C)}

Если в какой-то простой конъюнкции недостаёт переменной, например, Z, вставляем в неё выражение

Z∨¬Z=1{\displaystyle Z\vee \neg Z=1},

после чего раскрываем скобки (при этом повторяющиеся дизъюнктные слагаемые не пишем, так как Z∨Z=Z{\displaystyle Z\vee Z=Z} по закону идемпотентности). Например:

X∨¬Y¬Z=X(Y∨¬Y)(Z∨¬Z)∨(X∨¬X)¬Y¬Z={\displaystyle X\vee \neg Y\neg Z=X(Y\vee \neg Y)(Z\vee \neg Z)\vee (X\vee \neg X)\neg Y\neg Z=}

XYZ∨X¬YZ∨XY¬Z∨X¬Y¬Z∨X¬Y¬Z∨¬X¬Y¬Z={\displaystyle XYZ\vee X\neg YZ\vee XY\neg Z\vee X\neg Y\neg Z\vee X\neg Y\neg Z\vee \neg X\neg Y\neg Z=}

=XYZ∨X¬YZ∨XY¬Z∨X¬Y¬Z∨¬X¬Y¬Z{\displaystyle =XYZ\vee X\neg YZ\vee XY\neg Z\vee X\neg Y\neg Z\vee \neg X\neg Y\neg Z}

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

Формальная грамматика, описывающая ДНФ[править | править код]

Следующая формальная грамматика описывает все формулы, приведенные к ДНФ:

<ДНФ> → <конъюнкт>

<ДНФ> → <ДНФ> ∨ <конъюнкт>

<конъюнкт> → <литерал>

<конъюнкт> → (<конъюнкт> ∧ <литерал>)

<литерал> → <терм>

<литерал> → ¬<терм>

где <терм> обозначает произвольную булеву переменную.

1. ↑ Поздняков С.Н., Рыбин С.В. Дискретная математика. — С. 303.

• Ю.И. Галушкина, А.Н. Марьямов: Конспект лекций по дискретной математике — 2-е изд., испр. — М.: Айрис-пресс, 2008. — 176 с. — (Высшее образование).

Совершенная конъюнктивная нормальная форма — Карта знаний

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

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

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

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

Источник: Википедия

Связанные понятия

Бу́лева фу́нкция (или логи́ческая функция, или функция а́лгебры ло́гики) от n аргументов — в дискретной математике — отображение Bn → B, где B = {0,1} — булево множество. Элементы булева множества {1, 0} обычно интерпретируют как логические значения «истинно» и «ложно», хотя в общем случае они рассматриваются как формальные символы, не несущие определённого смысла. Неотрицательное целое число n называют арностью или местностью функции, в случае n = 0 булева функция превращается в булеву константу… Математическая формула (от лат. formula — уменьшительное от forma — образ, вид) — в математике, а также физике и прикладных науках, символическая запись высказывания (которое выражает логическое суждение), либо формы высказывания. Формула, наряду с термами, является разновидностью выражения формализованного языка. Квазианалити́ческие фу́нкции в математическом анализе — класс функций, которые, нестрого говоря, можно полностью реконструировать по их значениям на небольшом участке (например, на границе области). Такое свойство значительно облегчает решение дифференциальных уравнений и исследование других задач анализа. Поскольку это свойство выполняется для аналитических функций (см. Комплексный анализ), то класс квазианалитических функций содержит класс обычных аналитических функций и может рассматриваться как…

Подробнее: Квазианалитическая функция

Ля́мбда-исчисле́ние (λ-исчисление) — формальная система, разработанная американским математиком Алонзо Чёрчем, для формализации и анализа понятия вычислимости. В математике и информатике подстановка — это операция синтаксической замены подтермов данного терма другими термами, согласно определённым правилам. Обычно речь идёт о подстановке терма вместо переменной.

Подробнее: Подстановка

Конъю́нкция (от лат. conjunctio — «союз, связь») — логическая операция, по смыслу максимально приближенная к союзу «и». Синонимы: логи́ческое «И», логи́ческое умноже́ние, иногда просто «И». Трои́чная ло́гика (трёхзначная логика или тернарная логика) — один из видов многозначной логики, предложенный Яном Лукасевичем в 1920 году. Трёхзначная логика — исторически первая многозначная логика. Она является простейшим расширением двузначной логики. Формальное дифференцирование — операция над элементами кольца многочленов или кольцом формальных степенных рядов, повторяющая форму производных из математического анализа. Алгебраическое преимущество формального дифференцирования состоит в том, что оно не опирается на понятие предела, которое в общем случае невозможно определить для кольца. Многие свойства производной верны для формального дифференцирования, но некоторые, особенно касающиеся утверждений, содержащих числа, не верны. В основном формальное… Логика первого порядка, называемая иногда логикой или исчислением предикатов — формальное исчисление, допускающее высказывания относительно переменных, фиксированных функций и предикатов. Расширяет логику высказываний. В свою очередь является частным случаем логики высших порядков. Обобщённая фу́нкция или распределе́ние — математическое понятие, обобщающее классическое понятие функции. Двенадцатикратный путь или двенадцать сценариев — это систематическая классификация 12 связанных перечислительных задач, касающихся двух конечных множеств, которые включают классические задачи подсчёта перестановок, сочетаний, мультимножеств и разбиений либо множества, либо числа. Идею классификации приписывают Джиану-Карло Роту, а название двенадцатикратный путь предложил Джоэл Спенсер. Название намекает, что используя те же подходы в 12 случаях, но с небольшими изменениями в условиях, мы получаем… Множество больших тригонометрических сумм — понятие теории чисел — множество индексов, в которых преобразование Фурье характеристической функции заданного подмножества группы принимает достаточно большие значения. Дробная производная (или производная дробного порядка) является обобщением математического понятия производной. Существует несколько разных способов обобщить это понятие, но все они совпадают с понятием обычной производной в случае натурального порядка. Когда рассматриваются не только дробные, но и отрицательные порядки производной, к такой производной обычно применяется термин дифферинтеграл. Математи́ческий ана́лиз (классический математический анализ) — совокупность разделов математики, соответствующих историческому разделу под наименованием «анализ бесконечно малых», объединяет дифференциальное и интегральное исчисления. Конъюнкти́вная норма́льная фо́рма (КНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид конъюнкции дизъюнкций литералов. Конъюнктивная нормальная форма удобна для автоматического доказательства теорем. Любая булева формула может быть приведена к КНФ. Для этого можно использовать: закон двойного отрицания, закон де Моргана, дистрибутивность. Дизъюнкти́вная норма́льная фо́рма (ДНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид дизъюнкции конъюнкций литералов. Любая булева формула может быть приведена к ДНФ. Для этого можно использовать закон двойного отрицания, закон де Моргана, закон дистрибутивности. Дизъюнктивная нормальная форма удобна для автоматического доказательства теорем. Граф зависи́мостей — ориентированный граф, отображающий соотношение множества элементов некоторой совокупности в соответствии с выбранным транзитивным отношением над ней. Логика Хоара (англ. Hoare logic, также Floyd—Hoare logic, или Hoare rules) — формальная система с набором логических правил, предназначенных для доказательства корректности компьютерных программ. Была предложена в 1969 году английским учёным в области информатики и математической логики Хоаром, позже развита самим Хоаром и другими исследователями. Первоначальная идея была предложена в работе Флойда, который опубликовал похожую систему в применении к блок-схемам (англ. flowchart). Теневое исчисление (от англ. Umbral calculus, далее от лат. umbra — «тень») — математический метод получения некоторых алгебраических тождеств. До 1970-х термин относился к схожести некоторых внешне несвязанных алгебраических тождеств, а также к техникам, использованных для доказательства этих тождеств. Эти техники предложил Джон Блиссард и они иногда называются символическим методом Блиссарда. Их часто приписывают Эдуарду Люка (или Джеймсу Джозефу Сильвестру), которые их интенсивно использовали… При конструктивном подходе к определению вещественного числа вещественные числа строят, исходя из рациональных, которые считают заданными. Во всех трёх нижеизложенных способах за основу берутся рациональные числа и конструируются новые объекты, называемые иррациональными числами. В результате пополнения ими множества рациональных чисел, мы получаем множество вещественных чисел.

Подробнее: Конструктивные способы определения вещественного числа

Вариацио́нное исчисле́ние — раздел анализа, в котором изучаются вариации функционалов. Наиболее типичная задача — найти функцию, на которой заданный функционал достигает экстремального значения. Хорновский дизъюнкт — дизъюнктивный одночлен с не более чем одним положительным литералом. Изучены Альфредом Хорном (англ. Alfred Horn) в 1951 году в связи с их важной ролью в теории моделей и универсальной алгебре. Впоследствии стали основой для языка логического программирования Пролог, в котором программа являются непосредственно набором хорновских дизъюнктов, а также нашли важные приложения в конструктивной логике и теории сложности вычислений. Мультимножество в математике — обобщение понятия множества, допускающее включение одного и того же элемента по нескольку раз. Число элементов в мультимножестве, с учётом повторяющихся элементов, называется его размером или мощностью. В математике и теоретической физике функциональная производная является обобщением производной по направлению. Разница заключается в том, что для последней дифференцирование производится в направлении какого-нибудь вектора, а для первой речь идёт о функции. Оба эти понятия можно рассматривать как обобщение обычного дифференциального исчисления.

Подробнее: Функциональная производная

Гладкая функция, или непрерывно дифференцируемая функция, — функция, имеющая непрерывную производную на всём множестве определения. Очень часто под гладкими функциями подразумевают функции, имеющие непрерывные производные всех порядков. Циклический избыточный код (англ. Cyclic redundancy check, CRC) — алгоритм нахождения контрольной суммы, предназначенный для проверки целостности данных. CRC является практическим приложением помехоустойчивого кодирования, основанным на определённых математических свойствах циклического кода. Не путать с «симплекс-методом» — методом оптимизации произвольной функции. См. Метод Нелдера — МидаСимплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве.

Подробнее: Симплекс-метод

По́ле в общей алгебре — множество, для элементов которого определены операции сложения, взятия противоположного значения, умножения и деления (кроме деления на нуль), причём свойства этих операций близки к свойствам обычных числовых операций. Простейшим полем является поле рациональных чисел (дробей). Хотя названия операций поля взяты из арифметики, следует иметь в виду, что элементы поля не обязательно являются числами, и определения операций могут быть далеки от арифметических. В теории информации теорема Шеннона об источнике шифрования (или теорема бесшумного шифрования) устанавливает предел максимального сжатия данных и числовое значение энтропии Шеннона. Ме́тоды Ру́нге — Ку́тты (в литературе встречаются названия: ме́тоды Ру́нге — Ку́тта или же ме́тоды Ру́нге — Кутта́) — большой класс численных методов решения задачи Коши для обыкновенных дифференциальных уравнений и их систем. Первые методы данного класса были предложены около 1900 года немецкими математиками К. Рунге и М. В. Куттой. Метод наименьших квадратов (МНК) — математический метод, применяемый для решения различных задач, основанный на минимизации суммы квадратов отклонений некоторых функций от искомых переменных. Он может использоваться для «решения» переопределенных систем уравнений (когда количество уравнений превышает количество неизвестных), для поиска решения в случае обычных (не переопределенных) нелинейных систем уравнений, для аппроксимации точечных значений некоторой функции. МНК является одним из базовых методов… Логистическая регрессия или логит-регрессия (англ. logit model) — это статистическая модель, используемая для прогнозирования вероятности возникновения некоторого события путём подгонки данных к логистической кривой. Переме́нная — атрибут физической или абстрактной системы, который может изменять своё, как правило численное, значение. Понятие переменной широко используется в таких областях как математика, естественные науки, техника и программирование. Примерами переменных могут служить: температура воздуха, параметр функции и многое другое. Вычислительные (численные) методы — методы решения математических задач в численном видеПредставление как исходных данных в задаче, так и её решения — в виде числа или набора чисел. Дифференциальное исчисление — раздел математического анализа, в котором изучаются понятия производной и дифференциала и способы их применения к исследованию функций. Формирование дифференциального исчисления связано с именами Исаака Ньютона и Готфрида Лейбница. Именно они чётко сформировали основные положения и указали на взаимообратный характер дифференцирования и интегрирования. Создание дифференциального исчисления (вместе с интегральным) открыло новую эпоху в развитии математики. С этим связаны… Полуинварианты, или семиинварианты, или кумулянты — коэффициенты в разложении логарифма характеристической функции случайной величины в ряд Маклорена. Компьютер для операций с математическими функциями (в отличие от обычного компьютера) оперирует с функциями на аппаратном уровне (то есть без программирования этих операций). Задача выполнимости формул в теориях (англ. satisfiability modulo theories, SMT) — это задача разрешимости для логических формул с учётом лежащих в их основе теорий. Примерами таких теорий для SMT-формул являются: теории целых и вещественных чисел, теории списков, массивов, битовых векторов и т. п. Смешанные частные производные одной и той же функции, отличающиеся лишь порядком (очерёдностью) дифференцирования, равны между собой при условии их непрерывности. Такое свойство называется равенством смешанных производных.

Подробнее: Равенство смешанных производных

Коды Боуза — Чоудхури — Хоквингема (БЧХ-коды) — в теории кодирования это широкий класс циклических кодов, применяемых для защиты информации от ошибок (см. Обнаружение и исправление ошибок). Отличается возможностью построения кода с заранее определёнными корректирующими свойствами, а именно, минимальным кодовым расстоянием. Частным случаем БЧХ-кодов является код Рида — Соломона. Дифференциа́л (от лат. differentia «разность, различие») — линейная часть приращения функции. Произво́дная функции — понятие дифференциального исчисления, характеризующее скорость изменения функции в данной точке. Определяется как предел отношения приращения функции к приращению её аргумента при стремлении приращения аргумента к нулю, если такой предел существует. Функцию, имеющую конечную производную (в некоторой точке), называют дифференцируемой (в данной точке). Гауссовский процесс назван так в честь Карла Фридриха Гаусса, поскольку в его основе лежит понятие гауссовского распределения (нормального распределения). Гауссовский процесс может рассматриваться как бесконечномерное обобщение многомерных нормальных распределений. Эти процессы применяются в статистическом моделировании; в частности используются свойства нормальности. Например, если случайный процесс моделируется как гауссовский, то распределения различных производных величин, такие как среднее значение… Модель бинарного выбора — применяемая в эконометрике модель зависимости бинарной переменной (принимающей всего два значения — 0 и 1) от совокупности факторов. Построение обычной линейной регрессии для таких переменных теоретически некорректно, так как условное математическое ожидание таких переменных равно вероятности того, что зависимая переменная примет значение 1, а линейная регрессия допускает и отрицательные значения и значения выше 1. Поэтому обычно используются некоторые интегральные функции… В прикладной статистике метод наименьших полных квадратов (МНПК, TLS — англ. Total Least Squares) — это вид регрессии с ошибками в переменных, техника моделирования данных с помощью метода наименьших квадратов, в которой принимаются во внимание ошибки как в зависимых, так и в независимых переменных. Метод является обобщением регрессии Деминга и ортогональной регрессии и может быть применён как к линейным, так и нелинейным моделям. В математике централизатор подмножества S группы G — это множество элементов G, которые коммутируют с каждым элементом S, а нормализатор S — это множество элементов G, которые коммутируют с S «в целом». Централизатор и нормализатор S являются подгруппами G и могут пролить свет на структуру G.