Викия

Математика

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

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Поделиться

Обнаружено использование расширения AdBlock.


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

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

Шаблон:Чистить Конъюнкти́вная норма́льная фо́рма (КНФ) в булевой логикенормальная форма, в которой булева формула имеет вид конъюнкции нескольких дизъюнктов.

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

A \and B
A\!
(A \or B) \and \neg A
(A \or B \or \neg C) \and (\neg D \or E \or F) \and (C \or D) \and B

Конъюнктивная нормальная форма удобна для автоматического доказывания теорем.

Приведение булевой формулы к КНФ Править

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

(X_1 \and Y_1) \or (X_2 \and Y_2) \or \dots \or (X_n \and Y_n)

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

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

<КНФ> → <дизъюнкт>
<КНФ> → <КНФ> ∧ <дизъюнкт>
<дизъюнкт> → <литерал>
<дизъюнкт> → (<дизъюнкт> ∨ <литерал>)
<литерал> → <терм>
<литерал> → ¬<терм>

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

Задача выполнимости формулы в КНФ Править

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

См. также Править


Шаблон:Нет источниковhe:CNF

hu:Konjunktív normálformanl:Conjunctieve normaalvorm pl:Koniunkcyjna postać normalna

Викия-сеть

Случайная вики