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>
* Говорят, что формула записана в ''конъюнктивной нормальной форме'' (CNF), если представляет собой логическое '''И''' дизъюнктов.
+
* Говорят, что формула записана в ''конъюнктивной нормальной форме'' (КНФ), если представляет собой логическое '''И''' дизъюнктов.
 +
=== Определение ===
 +
<tex>CNFSAT = \{\phi \| в КНФ, \phi \in SAT\} </tex> &mdash; задача о выполнимости булевой формулы в форме КНФ.
 +
== Теорема ==
 +
<tex> CNFSAT \in NPC. </tex>
 +
== Доказательство ==

Версия 14:29, 17 марта 2010

Определения

  • Литералом является переменная или отрицание переменной. Например, [math]x[/math] или [math]\neg y[/math].
  • Дизъюнктом называется логическое ИЛИ одного или нескольких литералов. Например, [math]x \vee \neg y \vee z[/math]
  • Говорят, что формула записана в конъюнктивной нормальной форме (КНФ), если представляет собой логическое И дизъюнктов.

Определение

[math]CNFSAT = \{\phi \| в КНФ, \phi \in SAT\} [/math] — задача о выполнимости булевой формулы в форме КНФ.

Теорема

[math] CNFSAT \in NPC. [/math]

Доказательство