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