NP-полнота задачи о выполнимости булевой формулы в форме КНФ — различия между версиями
(→Определение) |
(→Определение) |
||
| Строка 4: | Строка 4: | ||
* Говорят, что формула записана в ''конъюнктивной нормальной форме'' (КНФ), если представляет собой логическое '''И''' дизъюнктов. | * Говорят, что формула записана в ''конъюнктивной нормальной форме'' (КНФ), если представляет собой логическое '''И''' дизъюнктов. | ||
==== Определение ==== | ==== Определение ==== | ||
| − | <tex>CNFSAT = \{\phi | в КНФ, \phi \in SAT\} </tex> — задача о выполнимости булевой формулы в форме КНФ. | + | <tex>CNFSAT = \{\phi \ |\ в КНФ, \phi \in SAT\} </tex> — задача о выполнимости булевой формулы в форме КНФ. |
== Теорема == | == Теорема == | ||
<tex> CNFSAT \in NPC. </tex> | <tex> CNFSAT \in NPC. </tex> | ||
== Доказательство == | == Доказательство == | ||
Версия 14:31, 17 марта 2010
Содержание
Определения
- Литералом является переменная или отрицание переменной. Например, или .
- Дизъюнктом называется логическое ИЛИ одного или нескольких литералов. Например,
- Говорят, что формула записана в конъюнктивной нормальной форме (КНФ), если представляет собой логическое И дизъюнктов.
Определение
— задача о выполнимости булевой формулы в форме КНФ.
Теорема
