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