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