NP-полнота задачи о выполнимости булевой формулы в форме КНФ
Определения
- Литералом является переменная или отрицание переменной. Например, или .
- Дизъюнктом называется логическое ИЛИ одного или нескольких литералов. Например,
- Говорят, что формула записана в конъюнктивной нормальной форме (КНФ), если представляет собой логическое И дизъюнктов.
Определение
в КНФ, — задача о выполнимости булевой формулы в форме КНФ.
Теорема
Доказательство
Для доказательства теоремы необходимо установить два факта: